mkotha https://blog.hatena.ne.jp/mkotha/ www.kotha.netの裏 https://mkotha.hatenadiary.org/ algorithm 観測にノイズが乗っても対処できる二分探索が意外と簡単に書けることが分かったのでメモ。 問題 (n-1)個の整数からなる列がある。そのうち左からi個は(-1)であり、それ以外は1である。 n=6, i=3の例 -1 -1 -1 1 1クエリを繰り返すことでiを求めたい。各クエリは整数kであり、答として左からk番目の整数の値が得られる。ただし、この答にはノイズが加算される。ノイズは標準偏差σ(既知とする)の正規分布に従う。 解法 iがどの値を取るかの確率分布を持っておいて、クエリの答が得られるたびにベイズの定理に従って更新する。最初はn通りの一様分布。クエリは、得られる情報量の期待値を最大化するよ… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmkotha.hatenadiary.org%2Fentry%2F20140712%2F1405174033" title=" ノイズ耐性のある二分探索 - www.kotha.netの裏" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-07-12 23:07:13 rich https://mkotha.hatenadiary.org/entry/20140712/1405174033 1.0 100%