東大 情報理工学系研究科 数理情報学専攻 数理情報学 2023年度 院試 解答例・解説

方針

核 $e^{-|x-y|}$ は「距離が近いほど似ている」ことを表す正の類似度である。 第1問全体は、この類似度平均の逆数を使って、集合どうしのずれを測る問題として読むと見通しがよい。

検算

$s=0$ のとき、移動する区間 $[s,s+1]$ は参照区間 $[0,1]$ と一致する。 このとき最小になるという結論は直観にも合う。一方、$s$ を大きく正または負に動かすと $h(z)$ が指数的に小さくなり、積分は急に大きくなる。

方針

平衡点では $v+Ax^*=0$ が成り立つので、非線形性の多くは $\operatorname{diag}(x)$ の形に押し込められる。局所安定性を見るだけなら、 原点 $z=0$ での二次形式の符号を見れば十分である。

採点上の注意

$\dot L$ の計算で $x_i'$ が分母と打ち消える点を書かないと、なぜ単純な二次形式に落ちるのかが見えにくい。 また、最後の $w_i=c_i/x_i^*$ は正値であることも確認しておく必要がある。

方針

等間隔台形公式の誤差は、単位根を極にもつ補助関数の留数として表せる。 正則性が単位円の外側まであるため、積分路を半径 $R>1$ に広げると $|z^N-1|$ が大きくなり、指数的な誤差評価が得られる。

典型ミス

留数の符号を間違えると $I_N(f)$ の符号が反転する。単位円上の表示 $dz=iz\,d\theta$ と、$z^N-1$ の導関数 $Nz^{N-1}$ を別々に確認すると安全である。

方針

$1/X^2$ は右裾が非常に重い分布で、平均は存在しない。 そのため通常の $n$ や $\sqrt n$ ではなく、$n^2$ で割る安定なスケーリングが現れる。

採点上の注意

密度変換では $x=+1/\sqrt y$ と $x=-1/\sqrt y$ の二つの枝がある。 この二つを足すことで係数 $1/\sqrt{2\pi}$ が得られる。 片方だけにすると係数が半分になり、以降のラプラス変換も合わなくなる。

方針

これは暗号実装などで使われる non-adjacent form の基本性質である。 奇数のときに $\pm1$ のどちらを選ぶかを $4$ で割った剰余で決めると、次の桁が必ず $0$ になり、非零桁が隣接しない。

検算

最初の数個は $$1=(1),\quad 2=(0,1),\quad 3=(-1,0,1),\quad 5=(1,0,1)$$ となる。隣接する非零桁を許せば $3=1+2$ と書けるが、疎な表現では $-1+4$ として重みを同じか小さく保ちながら隣接を消す。