指定された最大サイズのチューリングマシンのVC次元は何ですか?

質問の「最大サイズ」に注意してください。私はチューリングマシンのステートマシンのサイズを指しています。

私はチューリングマシンを選んで具体的に質問しましたが、プログラムの長さに制限があり(無限のVC次元を避けるため)、チューリング完全言語の既知のVC境界にも関心があります。

私が見た最も近いのは、リカレントニューラルネットのVC次元を与えるこの記事ですこれはチューリングが完了することができるが、重みの数および入力の長さに関する有限のVC次元を有する。

ベストアンサー

正確なVC境界は、アルファベットのサイズとトランジション関数の正確な仕様に依存します(常に左または右に移動する必要がありますか、置くなど)。固定アルファベットサイズの2の場合、DFA-VCdim分析を

Ishigami and Tani、 $ kを持つ有限オートマトンと可換性有限オートマトンのVC次元$ letterと$
n $ states
Discrete Applied Mathematics
74 (1997)、no。 3、229-240

$ n $ -state TMのVC-dimが$ Theta(n log n)$になることを示します。

あなたがNNの接続重みに関して言及したそれらの他のVC境界は、分離超平面のノルムに関してSVM境界の精神の中でより多くです。

更新:ここに証拠のスケッチがあります。固定されたアルファベットサイズ(例えば2)と$ n
$州の場合、(state、letter)から(state、letter、head move)までの$ n ^ {cn}
$遷移関数があります。定数。ログを取ると、$ O(n log n)$のVC上限推定値が得られます。石川谷分析の下限は、$ n
$状態のDFAを$ n $状態のTM($ n $追加ビット追加)で実現できるため、どの州が受け入れられているかを示すため、 $ n ^
{cn} $因数)を返します。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です