京大 情報学研究科 知能情報学コース 2021年度 院試 解答例・解説

回転と拡大に分ける

設問1の本質は、$A$ が「2倍の拡大」と「角 $\pi/3$ の回転」の合成になっている点である。 行列を直接何度も掛けるより、$A=2R_{\pi/3}$ と見抜く方が符号のミスが少ない。

非負固有値の示し方

$A^{\mathsf T}A$ 型の行列では $\langle p,A^{\mathsf T}Ap\rangle=\|Ap\|^2$ を使うのが定石である。これは特異値分解につながる議論で、設問2の $p_i$ と $q_i$ の関係は右特異ベクトルと左特異ベクトルの対応そのものである。

値域は端点の扱いに注意

シグモイドも $\tanh$ も、$x$ は実数全体を動くが、$y$ は開区間にしか入らない。 したがって導関数の下限 $0$ は近づくだけで達しない。一方、最大値は $x=0$ で達する。

ヤギの問題はインボリュート

円筒に巻き付いた糸の先端が描く曲線は円のインボリュートである。 座標を丸暗記するより、「接点 $T(\theta)$」と「残りの直線部分 $\theta$」に分解すると自然に導ける。

Quickselect の分岐

$p$ が $L$ に含まれる点が重要である。$p$ の順位は $|L|$ なので、$|L|=k$ のときだけ即座に返せる。 $|L|>k$ のときは左側、$|L|<k$ のときは右側で順位を $k-|L|$ に補正して探す。

期待コストの見方

長く挿入を続けたとき、あるキーが選ばれた時点の探索リスト長は、そのキーが入るバケットの確率質量に比例する。 したがって、期待コストの主要項は $\sum_h q_h^2$ で決まる。完全な $0.25$ ずつには分けられないため、上の割当のように $0.30,0.25,0.25,0.20$ まで均すのが最良である。

貪欲法が失敗する理由

単位重さ当たりの価値だけを見る貪欲法は、容量をどれだけ消費するかを局所的にしか見ない。 小さい高密度アイテムを先に選ぶことで、大きな価値を持つアイテムが入らなくなる場合がある。設問3の反例はこの弱点を最小構成で示している。

動的計画法の状態

$OPT(i,j)$ は「最初の $i$ 個だけを見る」「容量は $j$」という状態である。 第 $i$ アイテムを使わない場合と使う場合を比較するだけで全探索を整理できるため、ナップサック問題の標準的な解法になる。

記述問題の採点軸

用語説明では、単なる直訳ではなく「何を処理するか」「どのような実験事実や症状と関係するか」を入れると答案として強い。 侵襲性の問題では、安全性だけでなく、計測できる信号の粒度との対応を書くと比較が明確になる。

変化の見落としの核心

空白画面は、変化によって生じる局所的な運動信号を消す役割を持つ。 そのため、参加者は画像全体を記憶して比較する必要があり、注意資源の制約が反応時間に表れる。

検出力の符号

片側検定では、真の平均が大きいほど統計量は右にずれる。 そのため検出力は $\Pr[Z>u]$ の形になり、効果量が大きいほど $u$ は小さくなる。

二項分布とポアソン近似

$n$ が大きく $p$ が小さいとき、二項分布 $\mathrm{Bin}(n,p)$ は $\mathrm{Poisson}(np)$ で近似できる。 ここでは $np=2.5$ なので、0個の確率は $e^{-2.5}$ となる。

対数尤度の形

クラスAの密度では $x$ 方向と $y$ 方向で $a$ の入り方が逆である。 したがって $a$ の最尤推定量は、$x^2$ の和と $y^2$ の和の比の平方根になる。

判別境界

事後確率の大小比較は、事前確率の比と尤度比の比較に直せる。 ここでは共分散が同じガウス型なので、判別境界は直線になる。

等号成立条件

$\lceil x\rceil=x$ となるのは $x$ が整数のときである。 したがって $H(S)=\overline N$ は、全ての $-\log_2p_i$ が整数、すなわち全確率が dyadic であることを意味する。

ハフマン符号との接続

dyadic な確率では、確率 $2^{-l_i}$ と符号長 $l_i$ がぴったり対応する。 このときクラフト等式も等号で成立するため、対応する二分木はハフマン木として構成できる。

$z^{-1}$ は1サンプル遅延

FIR回路では $z^{-1}$ の次数がそのまま遅延段数になる。 IIR回路では分母がフィードバックを表し、極が単位円内にあるかどうかが安定性を決める。

有限長矩形列のDTFT

$u[n]-u[n-6]$ は長さ6の矩形列である。 等比級数の形に直すと、振幅包絡が $\sin(3\omega)/\sin(\omega/2)$ で表されることが分かる。

Church 真理値

$\mathsf{true}$ は2つの引数のうち第1引数を返し、$\mathsf{false}$ は第2引数を返す。 したがって条件分岐は、真理値そのものを関数として使うことで表現できる。

再帰の考え方

$\mathsf{fix}$ は固定点演算子であり、関数 $F$ に対して $F(\mathsf{fix}\ F)$ を作る。 $\mathsf{any}$ では、再帰関数 $g$ を「末尾リストに対する any」として使えば、通常の再帰定義と同じ形になる。