東大 情報理工学系研究科 創造情報学専攻 創造情報学 専門科目 2024年度 院試 解答例・解説

方針

前半は最尤推定の標準計算である。対数を取ると積が和になり，正規分布では二乗和を最小にする 平均と，その平均まわりの平均二乗偏差が現れる。分散の推定量で分母を $N$ にする点は， 不偏推定量との混同が起きやすい。

EMの見方

混合正規分布で難しいのは，各観測値がどの成分から来たか分からないことである。EM法は， この不明な割当を責任度 $\gamma_{nk}$ という軟らかい重みで補い，重み付きの単一正規分布 推定へ分解する方法と見ればよい。Eステップは割当の推定，Mステップは重み付き平均と 重み付き分散の再計算である。

採点上の注意

Jensenの不等式を使う箇所では，$\lambda_{nk}$ を導入してから $\lambda_{nk}(\pi_k\varphi_k/\lambda_{nk})$ と書き直す一行が重要である。この一行がないと， なぜ下界が補助関数になっているのかが伝わらない。また，混合比の更新では $\sum_k\pi_k=1$ の制約を忘れず，ラグランジュ未定乗数または正規化の議論を添えるとよい。

方針

検索前処理の問題では，表を大きくすると一回の検索は速くなるが空間が増える。長さ $b$ の 全ビット列を直接見る表は速い一方で $2^b$ の欄を持つ。長さを半分に分けると空間は $2^{b/2}$ まで落ちるが，候補が $N/2^{b/2}$ 程度残るので照合が必要になる。

半径1検索の考え方

全体で1ビット以下しか違わないなら，前半か後半のどちらかは必ず完全一致する。この必要条件で 候補を拾い，最後に厳密な距離を計算する。これは「拾い漏らしをしない粗い条件で候補を作る」 という近傍検索の基本形である。

回路の注意

ハミング距離回路は，不一致ビットを数える加算回路である。最初に各ビットでXORを作り， その後は1の個数を足し上げる。4ビットでは最大値が4なので3ビット出力が必要であり， 最高位の桁上がりを落とすと距離4を表せない。

方針

用語説明では，最初に一文で定義し，続けて仕組み，最後に利点や注意点を書くと答案が安定する。 単語の日本語訳だけではなく，どの入力に対して何を出す技術なのかを明確にするとよい。

選択の理由

上の4項目は，いずれも短い行数で具体例や計算量上の特徴を書きやすい。動的計画法は状態遷移， BNFは生成規則，キャッシュは遅延削減と一貫性，$k$-近傍法は距離尺度と $k$ の選択という 採点されやすい観点を含められる。

典型ミス

動的計画法を単なる再帰，BNFをプログラムそのもの，キャッシュを常に正しい複製，$k$-近傍法を クラスタリングと書くと不正確である。用途だけでなく，内部で何を保存し，何を比較し，どの条件で 性能が変わるかを一つ添えると説明の説得力が増す。