読者です 読者をやめる 読者になる 読者になる

あざらしとペンギンの問題

主に漫画、数値計算、幾何計算、TCS、一鰭旅、水族館、鰭脚類のことを書きます。

全問外すことは全問当てることと同じくらい凄い?

これまで話してきたエントロピーの応用として、こんな問題を考えてみることにします。

たかし君は選択問題だけからなるテストで0点を取ってしまいました。しかし、彼はそれを受けて、自慢げにこんなことを言い出しました。「全問外すってことは、全問答えを知らないとできないことだから、逆に俺は凄いんだよ。」果たして、たかし君は本当に凄いのでしょうか?

まだ問題を詰めてはいませんが、もしすべての問題が2択であるならば、たかし君の主張は正しいでしょう。なぜなら、彼の選択を真逆にすれば、全問正解することになるからです。よって、全問の正解を知らなければ、このような芸当はまずできません。当てずっぽうに答えを書いても、半分近くは正解してしまいます。

では、すべての問題が3択、4択、5択…である場合はどうなるでしょうか?というのが今回の問題です。

それでは、どのような尺度で凄さを測るかと言うと、問題を答えるために使う情報量です。ここでいう情報量とは、データを表現するためのビット数のことです。これがエントロピーと等しいというのは、前回の圧縮符号のところで述べた話と同じです。

情報量とランダム性

エントロピーと情報量

問題のモデルとして、選択問題の正解の番号は、各問ごとに独立にランダムに与えられるものとします。例えば、出題者が正解を配置するときに、サイコロを振って正解の番号を決めるといったところです。このとき、正解の番号の列は無記憶情報源と見なすことができます。

上の情報源のエントロピーは、解答者から見ると、1問を正解するために使う情報量(ビット数)と見なすことができます。まず、正解の番号の列を圧縮符号化すれば、1問あたりでは、正解の番号をエントロピーに近いビット数にまで圧縮することができます。問題の数が多くなれば、各問あたりの正解の番号の符号長は、いくらでもエントロピーに近づけることができます。そこで、エントロピーをもって、1問を正解するための情報量と見なすのです。

出題者しては、当たりをつけにくい方が望ましいので、正解の番号は一様分布に従って与えるとします。このとき、q 択問題の1問あたりのエントロピー\log q となることは明らかでしょう。これを解答者から見ると、1問を正解するのに使う情報量ということになります。

ランダム性の消去

上の「1問を正解するのに使う情報量」という見方を言い換えると、「1問のランダム性を消去するのに使う情報量」と言うことができます。まず、問題が出題された時点では、正解の番号は一様分布に従って決まるので、解答者は当たりをつけることができません。このとき、解答者にとって問題の答えは最大限ランダムであると考えられます。そこで、解答者は(脳内にある)答えの情報を参照して、問題の答えを選ぶとします。このとき、もし解答者がその問題に確実に正解できるならば、問題の答えのランダム性が、情報(ビット列)によって消去されたと考えられます。その情報のビット数こそが、1問の全情報量なのです。例えば、ある4択問題の答えが \{a,b,c,d\} のいずれかであったとします。最初の時点では、解答者にとってそれらはランダムです。よって、何の情報も持っていない場合の正解率は25%であると考えられます。ここで、解答者が

a \to 00
b \to 01
c \to 10
d \to 11

という符号を採用して、答えの情報を保存していたとしましょう。保存している情報の最初の1ビットが0だと判ると、

0 \to a \;\mbox{or}\;b

と、答えの候補を半分に絞り込むことができます。このときの正解率は50%になります。さらに、次のビットが1だと判ると、

01 \to b

と、答えを完全に確定することができます。このとき解答者は、2ビットの情報を使って、答えのランダム性を消去したのです。

ところで、最初の1ビットが判った時点で、答えのランダム性が部分的に消えていることも明らかでしょう。これによって、正解率が50%に高まっているのです。すなわち、4択問題で正解率50%を達成するには、1問あたり1ビットの情報を持っておけば十分なのです。

一方で、4択問題を必ず外すにも、1ビットの情報が与えられれば十分であることが、次のようにして分かります。上の符号で最初の1ビットが与えられたとき、そこから先にはないものを答えとして出せばよいのです。例えば、1ビット目が0であると判ったら c を、1であると判ったら a を答えとして出せば、必ず正解を外すことができます。2ビット目の情報を見る必要はありません。よって、すべての問題で間違えるには、1問あたり1ビットの情報を持っておけば十分なのです。

さて、これで50%と0%の正解率をそれぞれを同じ情報量で達成できることが判ったので、4択問題で全問外すことの凄さは50%で正解することと同程度、と言えるような気がしないでもありません。しかし、それは適切とは言えません。というのも、両者を達成するのに平均的により少ないビット数で十分である可能性があるためです。つまり、これだけでは比較できないのです。

ランダム性を部分的に消去するための情報量

先の話を一般化して、ランダム性を完全にではなく部分的に消去するために使う情報量について議論します。既に話した範囲では、4択問題の正解率を50%に上げるには、1ビットの情報量で十分であることが示されています。

これを分布同士の情報量の差として捉えてみましょう。まず、答えの候補が \{a,b,c,d\} であり4択問題を完全に正解するためには、2ビットの情報が必要十分です。これは、一様分布 Uエントロピーに相当します。一方で、答えが例えば b であるとき、50%の正解率を達成するためには、分布を次の p_1 で置き換えれば十分です。

p_1(a) = 0.5p_1(b) = 0.5p_1(c) = 0p_1(d) = 0

さらに、100%の正解率を達成するためには、分布を次の p_2 で置き換えます。

p_2(a) = 0p_2(b) = 1p_2(c) = 0p_2(d) = 0

こうして見ると、50%の正解率を達成する情報量は \mathrm{H}(U) - \mathrm{H}(p_1) = 1、100%の率を達成する情報量は \mathrm{H}(U) - \mathrm{H}(p_2) = 2 と書けることが分かります。

これを一般化すると、元の分布 U に対して、正解の候補を分布 p にまで絞るためには、\mathrm{H}(U) - \mathrm{H}(p) の情報量を消費すると考えることができます。ところで、これはKL情報量 \mathrm{D}(p || U) に一致します。すなわち、分布を絞るために使う情報量は、KL情報量で与えられるのです。以上を一般的に述べると、次のようになります。

原理: 正解の分布を分布 p に絞り込むには \mathrm{D}(p || U) ビットの情報量を消費する。

それでは、4択問題で1問あたり50%と0%の正解率を達成するには、どれだけの情報を使うかを見てみましょう。ここで使うのは \mathrm{D}(p || U) = \mathrm{H}(U) - \mathrm{H}(p) です。\mathrm{H}(U) = 2 なので、評価すべきは \mathrm{H}(p) の方です。

まず、50%の正解率を達成するために使う情報量の最小値について見てみましょう。なぜ最小値かと言うと、50%の正解率を達成するための情報だけを含み、それ以外の余計な情報を含まないようにするためです。それを求めるためには、\mathrm{H}(p) を最大化すればよいことが分かります。*1ただし、p は正解に対して50%以上の確率が乗っている分布です。仮に正解を a とすると、p(a) \geq 0.5 を達成するような分布です。この中で、\mathrm{H}(p) を最大化するには、可能な限り分布を分散させて

p(a) = 0.5p(b) = p(c) = p(d) = 0.5 / 3

とすればよいと考えられます。この分布のエントロピー

\mathrm{H}(p) = 0.5 * 1 + (0.5 / 3) * 3 * (\log 3 + 1) \approx 1.79

です。よって、50%の正解率を達成するための情報量は、\mathrm{D}(p || U) \approx 0.21 ビットとなります。

同様に、0%の正解率を達成するために使う情報量について見ると、\mathrm{H}(p) を最大化するためには

p(a) = 0p(b) = p(c) = p(d) = 1/3

とすればよいことから、

\mathrm{H}(p) = \log 3 \approx 1.58

です。よって、0%の正解率を達成するための情報量は、\mathrm{D}(p || U) \approx 0.42 ビットとなります。

以上の計算から、50%の正解率を達成する方が少ない情報量で済む、つまり、簡単であることが分かります。

正解率と情報量

先の話を一般化して、正解に関する情報が全くない状況から、指定された正解率を達成するのに使う情報量の式を与えます。

q 択問題に関して、答えを確率的に選ぶときの分布を考えます。何の情報も与えられていない場合は一様分布です。何らかの情報が与えられて、答えの分布を p に絞り込んだとしましょう。正解の番号を x_c とするとき、正解率をちょうど 1 - \delta にするためには、

p(x_c) = 1 - \delta

とします。ところで、できるだけ情報量を少なくしてこれを達成するには、\mathrm{D}(p || U) を最小化すればいいので、上のもとで \mathrm{H}(p) を最大化する分布を与えます。それは、

p(x) = \frac{\delta}{q - 1} \;(x \neq x_c)

というものです。すなわち、不正解の番号については特定しないという分布です。*2このもとで \mathrm{H}(p) を計算すると、

\mathrm{H}(p) = -(1 - \delta) \log (1 - \delta) - \delta \log \delta + \delta \log (q - 1)

となります。これを \delta の関数と見なして微分して計算すると、\delta = 1 - 1/q で最大値 \log q をとることが分かります。一方、\delta = 0 で最小値0をとります。

以上から、q 択問題に関して、誤り率 1 - \delta のもとでの \mathrm{D}(p || U) の値は

\log q +(1 - \delta) \log (1 - \delta) + \delta \log \delta - \delta \log (q - 1)

となります。この値は、\delta = 1 - 1/q で最小値0を、\delta = 0 で最大値 \log q をとります。

エントロピー関数

以上で情報量 \mathrm{D}(p || U) の式が求まりました。ところで、q を固定して情報量を比較することを考えると、全体を \log q で割って最大値を1にしても問題は起こりません。これは、対数の底を q に変えることに相当します。そこで、次の関数を定義します。

\mathrm{h}_q(\delta) := -(1 - \delta) \log_q (1 - \delta) - \delta \log_q \delta + \delta \log_q (q - 1)

これは、先の \mathrm{H}(p) の対数の底を q に変えた関数です。この関数を、「qエントロピー関数」と言います。

エントロピー関数を用いると、比較すべき量は 1 - \mathrm{h}_q(\delta) となります。よって、\mathrm{h}_q(\delta) を計算すれば十分です。

q=4 のときの y=\mathrm{h}_q(x) のプロットを例示します。

f:id:azapen6:20130118050505p:plain

数値計算

それでは、q 択問題で全問を間違えるのに必要な情報量は、どれだけの正解率分に匹敵するかを実際に計算してみましょう。

まず、全問を間違えるとき、正解率は 1 - \delta = 0 なので、注目すべき量は

\mathrm{h}_q(1) = \log_q (q - 1)

です。これを q = 2, 3, 4, 5, 6 と変えて計算してみると、

2: 0
3: 0.631
4: 0.792
5: 0.861
6: 0.898

となります。

同じ情報量で稼げる正解率を求めるには、\mathrm{h}_q(\delta) = \log_q (q - 1)\delta < 1 で解きます。数値計算によると、それぞれに関する \delta の値は

2: 0
3: 0.227
4: 0.391
5: 0.500
6: 0.576

となることが分かりました。

これより、全問を間違えるのと同じ情報量で取れる正解率は 1 - \delta

2: 100%
3: 77.3%
4: 60.9%
5: 50.0%
6: 42.4%

と計算されました。

以上のことから、3択以上の問題で全問外すということは、80%の正解率を達成するよりは情報量の意味で凄くないということが分かります。これより、たかし君の主張は否定されました。

まとめ

今回は、選択問題に関して「全問外すことは全問当てることと同じくらい凄い」という主張について、情報理論の観点から検証してみました。方法としては、全問外すのと同じだけの情報量でどれだけ正解できるかを計算することによってそれを行いました。2択問題に関しては、この方法論でもその主張が正しいことが分かりました。しかし、3択問題以上では、正解率80%には及ばないことが判明しました。これは、たかし君の主張を否定する根拠となるでしょう。

今回は、全くの私論でエントロピーの使い方を示してみました。ひとまず、エントロピーに関する話はこれで打ち止めとします。次回は今度こそ最初に示したネタで話をしたいと思います。では。

*1:最大エントロピー原理

*2:もちろん、ちゃんと証明することができます。