ノイズ耐性のある二分探索 - www.kotha.netの裏
観測にノイズが乗っても対処できる二分探索が意外と簡単に書けることが分かったのでメモ。 問題 (n-1)個の整数からなる列がある。そのうち左からi個は(-1)であり、それ以外は1である。 n=6, i=3の例 -1 -1 -1 1 1クエリを繰り返すことでiを求めたい。各クエリは整数kであり、答として左からk番目の整数の値が得られる。ただし、この答にはノイズが加算される。ノイズは標準偏差σ(既知とする)の正規分布に従う。 解法 iがどの値を取るかの確率分布を持っておいて、クエリの答が得られるたびにベイズの定理に従って更新する。最初はn通りの一様分布。クエリは、得られる情報量の期待値を最大化するように選ぶ。これには、(-1)と1の境界よりも右にあるか左にあるかが半々に近い位置を選べば良い。 iの確率分布が十分に偏ったら終了。 実験 以下では、iが特定の値を取る確率が95%を越えた時点で探索を終
A/Bテストよりすごい？バンディットアルゴリズムとは一体何者か - Qiita
オバマ大統領の再選に大きく寄与したことで大きな注目を集めているA/Bテスト。A/Bテストを導入した、することを検討している、という開発現場も多いのではないだろうか。 そんな中、Web上で次のような議論を見つけた。 20 lines of code that will beat A/B testing every time Why multi-armed bandit algorithm is not “better” than A/B testing 一言でまとめると「A/Bテストよりバンディットアルゴリズムの方がすごいよ」「いやいやA/Bテストの方がすごいし」ということだ。 で、バンディットアルゴリズムとは一体何者なのか？ そこでBandit Algorithms for Website Optimization (O'REILLY)を読んでみた。その結果分かったことを踏まえてざっくりと
BLOG::broomie.net: 機械学習の勉強を始めるには
thriftとかhadoopなど，何やらいろいろと手を出してしまい，ここのところブログの更新が滞ってしまっていますが，今日は前から書きたかったトピックについて自分へのメモの意味も含めて記しておきたいと思います． はじめに 最近，といっても結構前からなのですが，海外のブログなどで「機械学習の勉強を始めるガイドライン」についてのエントリーがいくつか見られ，かつ，議論も少し盛り上がっています．僕は機械学習が好きなだけで，専門というにはほど遠いのですが，僕も一利用者としてはこのトピックに関してはとても興味があります． 機械学習というと，色々な数学的な知識が必要であったり，統計学や人工知能の知識も必要になったりしまったりと，専門的に学ぶ機会が無かった人にとっては興味が湧いてもなかなか始めるには尻込みしてしまうことかと思います．今日紹介するエントリーは，そんな方々にヒントになるような内容になっていると
K-means法によるクラスタリングのスマートな初期値選択を行うK-means++ - kaisehのブログ
K-means法は、入力データからK個のランダムな個体を初期クラスタの中心として選択し、以降、クラスタの重心を移動させるステップを繰り返すことでクラスタリングを行う非階層的手法です。K-means法はシンプルで高速ですが、初期値依存が大きいのが弱点で、不適切な初期値選択をすると間違った解に収束してしまいます。 以下は、Introduction to Information Retrievalの16章に出てくる例です。 {d1, d2, ..., d6}をK=2でクラスタリングする場合、{{d1, d2, d4, d5}, {d3, d6}}が大域最適解ですが、初期クラスタの中心をd2, d5で与えると、{{d1, d2, d3}, {d4, d5, d6}}という誤った解に収束してしまいます。 この問題を改善するK-means++という手法を見つけたので、試してみました。 K-means+
適切なクラスタ数を推定するX-means法 - kaisehのブログ
K-means法によるクラスタリングでは、あらかじめクラスタ数Kを固定する必要があります。HatenarMapsでもK-means法を使っているのですが、クラスタ数は（特に根拠もなく）200個に決め打ちになっていました。 これに対して、X-means法というK-means法の拡張が提案されていることを知りました。X-means法を使うと、データに応じて最適なクラスタ数を推定できます。 K-means and X-means implementations http://www-2.cs.cmu.edu/~dpelleg/download/xmeans.pdf X-means法の考え方は、K=2で再帰的にK-means法を実行していくというもので、クラスタの分割前と分割後でBIC（ベイズ情報量規準）を比較し、値が改善しなくなるまで分割を続けます。 調べたところ、Javaのデータマイニングツー
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://cl-www.msi.co.jp/reports/svm.pdf
Kernel density estimation - Wikipedia