1

AIの教科書のパラグラフを理解しようとしていますが、これについてサポートが必要です。

基本的に、私の質問は、関数を定義するのに2 ^ nビットかかるのに、n個の属性に2 ^（2 ^ n）個の関数があるのはなぜですか？

これがテキストのパラグラフです（出典：AI：A Modern Approach、Stuart Russell、Peter Norvig）：

デシジョンツリーは、ある種の機能には適していますが、他の機能には適していません。あらゆる種類の機能に効率的な表現はありますか？残念だけど違う。これは非常に一般的な方法で示すことができます。n個の属性のすべてのブール関数のセットを検討してください。このセットにはいくつの異なる関数がありますか？関数は真理値表によって定義されているため、これは書き留めることができるさまざまな真理値表の数にすぎません。各入力ケースはn個の属性で記述されるため、真理値表には2^n行あります。表の「回答」列は2^nビットの数値と見なすことができます関数を定義します。関数にどの表現を使用しても、一部の関数（実際にはほとんどすべて）は、表現するために少なくともその数のビットを必要とします。

関数を定義するのに2^nビットかかる場合、n個の属性に2 ^（2 ^ n）個の異なる関数があります。

2番目の質問は次のとおりです。なぜ2^nビット数が必要なのですか（上記の太字を参照）。nビット数のみが必要だと思いました。たとえば、3つの属性がある場合、2 ^ 3=8関数を定義できます。 8つの関数（000、001、010、011など）すべてを定義するために必要なのは3ビットだけです。

私はこれについてしばらく考えていましたが、何が私を逃れるのかわかりません、これを調べてくれてありがとう！

4

4 に答える 4

2

彼が言っているのはこれです: n 属性のすべての可能な値を次のように書き出すことができます:

0 1 2 .. n

0 0 0 0 0 0 0 1

明らかに行数は 2^n です

次に、追加の列を追加して関数を定義します。ビットが 1 の場合、その値はその関数で「真」になり、それ以外の場合は偽になります。行数は 2^n であり、バイナリ文字列の 0 と 1 のすべての組み合わせで関数を定義しているため、明らかに 2^(2^n) のような文字列があり、2^(2^n ) n 個の属性に対する関数。

簡単な例を見てみましょう: n = 3. 属性の値は次のとおりです。

000 001 010 011 100 101 110 111

これで、1 行目と 2 行目で「真」、1 行おきで「偽」となる 1 つの関数 f を定義できます。これは、row1="true" row2="true" row3="false" などと表すことができます。さて、このような異なる文字列をいくつ取得できるでしょうか? 書き出すことができます

000000000 000000001 000000010 .. 111111111

これらの文字列はそれぞれ別の関数にマップされ、2^8 = 2^(2^n) 個あるため、2^(2^n) 個の関数になります。

于 2011-04-15T02:41:34.997 に答える
1

私はそれを理解したと思います、そして私はあなたの答えに間違いがあるかもしれないと思います...

3つの属性の例についての私の理解に従って説明させてください..

n = 3

行 1 000

行 2 001

行 3 010

...

行 8 111

関数 0 : すべての行で false したがって 0 0 0 0 0 0 0 0 (8 行あるので 8 '0')

関数 1: 行 1 の場合は true、残りの場合は false: 00000001

関数 2: 行 2 の場合は true、残りの場合は false: 00000010

...

したがって、2^8 関数があり、これは 2^(2^3) つまり 2^(2^n) です。

正しい？

于 2011-04-15T03:04:42.380 に答える
0

余談ですが、関数を表すために少なくともその数のビットが必要であると彼が言う理由は、各関数には、入力の特定の行がその関数に対して「真」か「偽」かを指定するのに十分な情報が含まれている必要があるためです。

情報理論の観点からは、これが 2^(2^n) ビット未満、またはもっと簡単に言えば、m ビット (m は関数の数) で実行できることを理解するのは困難です。なぜなら、これらすべての関数を実際に書き出したとします。どちらを使用していますか？m ビットの ID を指定する必要があります。

于 2011-04-15T02:58:13.493 に答える