チューリングマシンはディープラーニングで最も注目されているリカレントニューラルネットワークRNNですか？ 1996 年の論文がそれを証明しました。

フィンランド人工知能協会とヴァーサ大学が主催するフィンランド人工知能カンファレンスは、1996 年 8 月 19 日から 23 日までフィンランドのヴァーサで開催されました。

カンファレンスで発表された論文は、チューリング マシンがリカレント ニューラル ネットワークであることを証明しました。

はい、これは 26 年前のことです。

1996 年に発表されたこの論文を見てみましょう。

1 はじめに

1.1 ニューラル ネットワークの分類

ニューラル ネットワークは、入力パターンが特定のカテゴリに属する​​かどうかを判断する分類タスクに使用できます。

単層フィードフォワード ネットワークは、線形分離可能なパターンの分類にのみ使用できること、つまり、層が連続するほど、クラスの分布が複雑になることは長い間知られていました。

ネットワーク構造にフィードバックが導入されると、パーセプトロンの出力値が再利用され、連続する層の数は原理的に無限になります。

コンピューティング能力は質的に向上しましたか?答えは「はい」です。

たとえば、入力整数が素数かどうかを判断する分類器を構築できます。

この目的に使用されるネットワークのサイズは有限であり、入力整数のサイズが制限されていない場合でも、正しく分類できる素数の数は次のとおりであることがわかります。無限。

この記事では、「同じ計算要素で構成される循環ネットワーク構造」を使用して、(アルゴリズム的に) 計算可能な関数を完成させることができます。

1.2 計算可能性について

計算可能性理論の基本公理によれば、チューリング マシンを使用して計算可能な関数を実装できます。チューリング マシンを実装するにはさまざまな方法があります。

プログラミング言語を定義します。この言語には 4 つの基本的な演算があります。

ここで、V は正の整数値を持つ変数、 j# を表します。 ## は任意の行番号を表します。

関数がチューリング計算可能である場合、この単純な言語を使用してエンコードできることがわかります (詳細については [1] を参照) 。

2 チューリング ネットワーク

2.1 再帰的ニューラル ネットワークの構造

この記事で研究するニューラル ネットワークはパーセプトロンで構成されており、そのすべてが同じパーセプトロン番号 q の構造は

と定義できますが、このうち現在のパーセプトロン出力はモーメント ( を使用) は、n 入力 を使用して計算されます。

非線形関数 f は

として定義できるようになりました。負の値を単に「カットオフ」するだけで、パーセプトロン ネットワーク内のループは、パーセプトロンを複雑な方法で組み合わせることができることを意味します。

#図 1 リカレント ニューラル ネットワークの全体的なフレームワーク。構造は外部入力なしで自律的であり、ネットワークの動作は初期状態によって完全に決定されます。

図 1 では、再帰構造が一般的な枠組みで示されています。 と n はパーセプトロンの数であり、パーセプトロン p からパーセプトロンへの接続です。 q は #スカラー重み表現で与えられます。

つまり、初期状態が与えられると、ネットワーク状態は変化しなくなるまで反復され、結果は安定した状態またはネットワークの「固定点」で読み取ることができます。 。

2.2 ニューラル ネットワークの構築

以下では、プログラムがどのようにパーセプトロン ネットワークに実装されるかを説明します。ネットワークは次のノード (またはパーセプトロン) で構成されます:

プログラム内のすべての変数 V

に対して、変数ノード

• 。 各プログラム行 i には、命令ノード
• があります。 行 i の条件付き分岐命令ごとに、2 つの追加分岐ノード
• および があります。 #言語

#プログラムの実装には、パーセプトロン ネットワークへの次の変更が含まれます:

プログラムの場合 V

の各変数について、次のリンクを使用してネットワークを拡張します:

プログラム コードの場合 i

行に操作 (

• ) がない場合は、次のリンクを使用してネットワークを拡張します (ノード が存在すると仮定します:

行 i

にインクリメンタル操作 (

• ) がある場合は、次のようにネットワークを拡張します。 ＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
  • 行 i にデクリメント操作 () がある場合は、次のようにネットワークを拡張します。

  

  • ##i 行目に条件分岐 () がある場合は、次のようにネットワークを拡張します。

  

  2.3 等価性の証明

  これから証明する必要があるのは、「ネットワークの内部状態またはネットワーク ノードの内容」が次のように識別できるということです。ネットワーク状態の継続性はプログラム フローに対応します。

  ネットワークの「法的状態」を次のように定義します:

  • すべての遷移ノード および (2.2 で定義) の出力はゼロ ();
  • 最大 1命令ノード にはユニット出力 () があり、他のすべての命令ノードにはゼロ出力があり、
  • 変数ノードの出力値は負ではない整数です。

  すべての命令ノードの出力がゼロの場合、状態 が最終状態 になります。正当なネットワーク状態は、プログラムの「スナップショット」として直接解釈できます。 の場合、プログラム カウンターは i 行にあり、対応する変数値は次のようになります。変数ノードに格納されます。

  ネットワーク ステータスの変化は、ゼロ以外のノードによってアクティブになります。

  まず、変数ノードに注目すると、変数ノードはインテグレータのように動作し、ノードの前の内容が同じノードにループバックされることがわかります。

  変数ノードから他のノードへの接続のみが負の重みを持ちます。非線形性 (2) のため、ゼロを含むノードは変化しません。

  次に、命令ノードについて詳しく説明します。唯一の非ゼロ命令ノード が時刻 k---これは行 i のプログラム カウンタに対応すると仮定します。プログラムコード内で。

  プログラムの i 行が の場合、ネットワークの動作が 1 歩前進する可能性があります。 (影響を受けたノードのみを表示)

  
  

  

  新しいネットワーク状態が再び正当であることが判明しました。 。プログラム コードと比較すると、これはプログラム カウンタが i 1 行に移動することに対応します。

  一方、プログラムの i 行目が # の場合、1 ステップ進む動作は

  ## となります。

  

  #このようにして、プログラム カウンタを次の行に移動するだけでなく、変数 V の値もデクリメントされます。行 i が

  の場合、変数 V の値が増加することを除いて、ネットワークの動作は同じになります。 。

  行 i の条件分岐操作 (IF GOTO j) は、より複雑なシーケンスをアクティブにします。操作 :

  

  ##最終的に、

  

  次のことが判明しました。これらのステップの後、ネットワーク状態は別のプログラムのスナップショットとして再び解釈できるようになります。
  変数値が変更され、対応するプログラム行が実行されたかのようにトークンが新しい場所に移動されました。
  トークンが消えると、ネットワークの状態は変化しなくなります。これは、プログラム カウンタがプログラム コードを「超過」した場合、つまりプログラムが終了した場合にのみ発生します。
  ネットワークの動作も対応するプログラムの動作と同様であり、証明は完了です。

  3 変更

  3.1 拡張機能
  プログラミングを容易にする追加の合理化された命令を簡単に定義できます。生成されたプログラムはより読みやすく、より高速に実行されます。たとえば、
  ## 行
  i
  • の無条件分岐 (GOTO j) は、 # として実装できます。
    ##定数 c を i
  行目の変数に追加します (
  • ) は # として実装できます。
    # 行の別の条件分岐 (IF V=0 GOTO
  j
  • ) は、# に対して達成できます。 さらに、さまざまなインクリメント/デクリメント命令を同時に評価できます。次の操作を実行するとします:
    。必要なノードは 1 つだけです。
  • ： 上記の方法は絶対に使用できません。チューリングマシンの唯一の実装を意味します。
    これは単純な実装であり、アプリケーションでは必ずしも最適であるとは限りません。

  3.2 行列の定式化

  上記の構築は行列の形で実装することもできます。

  基本的な考え方は、変数値と「プログラム カウンタ」をプロセス状態 s

  に保存し、状態遷移行列

  A を使用することです。間のノードリンクを表します。

  マトリックス構造の操作は、離散時間の動的プロセスとして定義できます

  

  ここで、非線形ベクトル値関数 は (2) のように要素ごとに定義されます。

  状態遷移行列Aの内容はネットワーク公式から簡単に解読できます。行列要素はノード間の重みです。

  この行列式は、[3] で提案されている「概念行列」フレームワークに似ています。

  4 例

  単純な関数 y=x を実装するとします。つまり、変数 x# の値を入力します。 ## 出力変数 y に渡す必要があります。 # 言語を使用すると、これは次のようにエンコードできます (そのため、「エントリ ポイント」は 1 行目ではなく 3 行目になります):

  

  生成されたパーセプトロン ネットワークを図 2 に示します。

  実線は正の接続 (重みは 1) を表し、点線は負の接続 (重みは -1) を表します。 ）。図 1 と比較すると、ネットワーク構造はノードに遅延要素を統合することによって再描画され、簡素化されています。

  

  #図 2 単純なプログラムのネットワーク実装

  マトリックス形式、上記のプログラムは次のようになります。

  
  

  行列 A の最初の 2 つの行/列は、を表すために接続された変数に対応します。ノード Y および #XX への 2 つのリンク。次の 3 行は 3 つのプログラム行 (1、2、および 3) を表し、最後の 2 行は分岐に必要な追加ノードを表します。命令 (3 ' および 3'')。 次に、初期状態 (反復前) と最終状態 (反復後、固定点が見つかったとき) があります。

  
  変数ノードの値が厳密に 0 と 1 の間に維持される場合、動的システム (3) の動作は線形になり、関数

  まったく効果がありません。 原則として、線形システム理論を解析に使用できます。

  例えば、図３には、状態遷移行列

  A

  の固有値が示されている。 上記の例で単位円の外側に固有値がある場合でも、非線形性により反復は常に安定します。

  反復は、

  ステップ () の後で常に収束することがわかります。

  図3 簡単なプログラムの「特性値」

  5 考察

  5.1 理論的側面

  結果は、チューリング マシンをパーセプトロン ネットワークとしてエンコードできることを示しています。

  定義上、すべての計算可能な関数はチューリング計算可能です。計算可能性理論の枠組み内では、これ以上強力な計算システムは存在しません。

  これが、結論付けることができる理由です -

  リカレント パーセプトロン ネットワーク (上に表示) はチューリング マシンです (まだ別の）形式。

  この等価性の利点は、計算可能性理論の結果が簡単に得られることです。たとえば、ネットワークと初期状態が与えられた場合、プロセスを判断することは不可能です。やがて止まるのだろうか。

  上記の理論的等価性は、計算効率については何も述べていません。

  ネットワーク内で発生するさまざまなメカニズムにより、従来のチューリング マシン実装 (実際には今日のコンピューター) と比較して、このフレームワークで一部の機能をより適切に実装できるようになります。

  # 少なくとも場合によっては、たとえば、スナップショット ベクトルで複数の 「プログラム カウンター」を許可することで、アルゴリズムのネットワーク実装を並列化できます。

  ネットワークの運用は厳密にローカルであり、グローバルではありません。

  たとえば、NP 完全問題をネットワーク環境でより効果的に攻撃できるかどうかなど、興味深い疑問が生じます。

  #言語と比較して、ネットワーク実装には次の「拡張機能」があります:# #変数 整数値だけでなく、連続値も使用できます。実際、実数を表現する (理論上の) 能力により、ネットワーク実装は、表現されるすべての数値が有理数である

  • 言語よりも強力になります。 さまざまな「プログラム カウンタ」が同時に存在する可能性があり、制御の転送が「あいまい」になる可能性があります。つまり、命令ノードによって提供されるプログラム カウンタ値は、非整数。
  • #小規模な拡張機能は、自由に定義できるプログラム エントリ ポイントです。これはプログラムを簡素化するのに役立ちます。たとえば、変数のコピーは上記の 3 つのプログラム行で行われますが、公称ソリューション ([1] を参照) では 7 行と追加のローカル変数が必要です。
  • 元のプログラム コードと比較すると、行列式は明らかにプログラム コードよりも「連続した」情報表現です。パラメーターは (頻繁に) 変更できますが、反復結果が突然変わることはありません。

  この「冗長性」は、一部のアプリケーションでは役立つ場合があります。

  たとえば、構造の最適化に遺伝的アルゴリズム (GA) を使用する場合、遺伝的アルゴリズムで使用されるランダム検索戦略をより効率的にすることができます。コストを検索することができます。関数の局所最小値は、いくつかの伝統的な手法を使用します ([4] を参照)。

  [5] で説明されているように、例を通じて有限状態マシンの構造を学習すると、ネットワーク構造を反復的に強化する方法が、このより複雑な状況でも使用されることがわかります。 。

  ニューラル ネットワーク理論だけが上記の結果から恩恵を受けるわけではありません。動的システムの公式 (3) を見るだけで、計算可能性理論の分野で見られるすべての現象も同様であることは明らかです。簡単に言えば、フォームが存在する - 非線形の動的プロセスを探しているということです。

  たとえば、停止問題の決定不可能性は、システム理論の分野への興味深い貢献です。チューリング マシンとして表されるあらゆる決定プロセスに対して、このプロセスに違反する形式 (3) の動的システムが存在します。 - たとえば、一般的な安定性解析アルゴリズムを構築することはできません。

  5.2 関連研究

  提示されたネットワーク構造と再帰的ホップフィールド ニューラル ネットワーク パラダイムの間にはいくつかの類似点があります (例: [2] を参照) ）。

  どちらの場合も、「入力」はネットワークの初期状態としてエンコードされ、「出力」は反復後のネットワークの最終状態から読み取られます。

  ホップフィールド ネットワークの固定点は、事前にプログラムされたパターン モデルであり、入力は「ノイズ」パターンです。このネットワークは、損傷したパターンを強化するために使用できます。

  # の非線形関数の見通し (2) により、上記の「チューリング ネットワーク」の可能な状態の数は無限になります。

  ユニット出力が常に -1 または 1 であるホップフィールド ネットワークと比較すると、理論的には、これらのネットワーク構造が大きく異なることがわかります。

  たとえば、ホップフィールド ネットワークの安定点のセットは限られていますが、チューリング ネットワークで表されるプログラムでは、多くの場合、無限の結果が考えられます。

  ホップフィールド ネットワークの計算能力については、[6] で説明されています。

  ペトリ ネットは、イベントベースの同時システム モデリングのための強力なツールです [7]。

  ペトリ ネットは、ビットと遷移、およびそれらを接続するアークで構成されます。各場所には任意の数のトークンを含めることができ、トークンの配布はペトリ ネットのマークと呼ばれます。

  変換のすべての入力位置がマーカーで占められている場合、変換がトリガーされ、各入力位置からマーカーが削除され、各出力位置にマーカーが追加されます。

  追加の抑制アークを備えた拡張ペトリ ネットにもチューリング マシンの機能があることが証明できます ([7] を参照)。

  上記のチューリング ネットとペトリ ネットの主な違いは、ペトリ ネットのフレームワークがより複雑で、単純な一般形式では表現できない特別にカスタマイズされた構造を持っていることです。 (3)。

  参考文献

  1 Davis, M.およびWeyuker, E.: 計算可能性、 Complexity, and Languages---Fundamentals of Theoretical Computer Science. Academic Press, New York, 1983.

  2 Haykin, S.: Neural Networks. A Comprehensive Foundation. Macmillan College Publishing,ニューヨーク、1994.

  3 Hyötyniemi, H.: 相関関係 --- 知能の構成要素? Älyn ulotuvuudet ja oppihistoria (知能の歴史と次元)、フィンランド人工知能協会、 1995、pp. 199--226.

  4 Hyötyniemi, H. およびコイヴォ, H.: 遺伝子、コード、および動的システム. 遺伝的アルゴリズムに関する第 2 回ノルディック ワークショップの議事録(NWGA'96)、フィンランド、ヴァーサ、1996 年 8 月 19 ～ 23 日。

  5 Manolios, P. および Fanelli, R.: 1 次リカレント ニューラル ネットワークと決定論的有限State Automata. Neural Computation 6、1994、pp. 1155--1173.

  6 Orponen, P.: The Computational Power of Discrete Hopfield Nets with Hidden Units. Neural Computation 8、1996 、pp. 403--415.

  7 Peterson, J.L.: ペトリ ネット理論とシステムのモデリング. プレンティス -- ホール、ニュージャージー州イングルウッド クリフス、1981.

  参考資料:

  https://www.php.cn/link/ 0465a1824942fac19824528343613213

以上がチューリングマシンはディープラーニングで最も注目されているリカレントニューラルネットワークRNNですか？ 1996 年の論文がそれを証明しました。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。