Burrows-Wheeler変換の線形時間アルゴリズム - DO++
研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transform using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S
適切なクラスタ数を推定する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のデータマイニングツー
Perceptron を勉強する前にオンライン機械学習ライブラリを試してみる (nakatani @ cybozu labs)
今度は CLUTO を試してみた話を書こうと思っていたのですけど、あまりふくらみそうにないので、保留。 オンライン学習(逐次学習)に興味があるので、まずは Perceptron 周辺を勉強し始めてます。 が、その前に動くものをさわっておこうということで、岡野原さんのオンライン機械学習ライブラリをちょっぴり試してみました。 oll プロジェクトページ(日本語) ビルド Linux なら ./configure & make でＯＫ。 Windows の場合 oll.hpp の先頭のどこかに #include <algorithm> を追加すれば VC++ でもコンパイルできました。 サンプルデータ サンプルデータには、プロジェクトページにも実験としてあがっている news20.binary をまずは使ってみることにしましょう。 「シャッフルし、15000例の訓練データと4996例のテストデー
Cybozu Inside Out: コンピュータはオー・ヘンリーとエドガー・アラン・ポーの文章を見分けられるか？(機械学習/パーセプトロン)
コンピュータはオー・ヘンリーとエドガー・アラン・ポーの文章を見分けられるか？(機械学習/パーセプトロン) サイボウズ・ラボの中谷です。 以前は nakatani @ cybozu labs でブログを書いていましたが、この "Cybozu Development Inside Out" で書かせていただくことになりました。 よろしくお願いします。 そして初回の記事は、なんと前回の続きです（ごめんなさい）。 前回記事「Perceptron を手で計算して理解してみる」では、オンライン機械学習の手法の一つ、パーセプトロンを紙と鉛筆で計算してみましたので、今回はそれを実装してみましょうというお話です。 ソースは github においています。 http://github.com/shuyo/iir/tree/master Perceptron 実装は簡単。手で計算した後なら、空で実装できてしまい
Perceptron を手で計算して理解してみる (nakatani @ cybozu labs)
Perceptron の実装とか見ると、ものすごく簡単なので、本当にこれで学習できちゃうの？ と不安になってしまいました(苦笑)。 こういうときは、実際にパーセプトロンが計算しているとおりに、紙と鉛筆で計算してみて、期待する結果が出てくることを確認してみたくなります。 参照する教科書は「パターン認識と機械学習・上」(PRML) の「 4.1.7 パーセプトロンアルゴリズム」。 短い節です。必要最低限のことを一通り書いてある感じかな。 計算に用いるサンプルですが、手で計算できる規模でないといけないので、論理演算の AND を試してみることにします。 簡単に勉強 ちゃんとした説明は PRML などを見て欲しいですが、とても簡単にまとめます。 ２値の線形識別モデルは、N 次元空間内を (N-1) 次元の超平面(決定面)で分割することで、入力ベクトル x から得られる特徴ベクトル φ(x) が２つ
Tutorial Main Page - SSL Tutorial: ACL 2008
General Information June 15th, 2008. The Hyatt-Regency. Columbus, OH. 9:00 AM — 12:30 PM John Blitzer and Jerry Zhu SSL for NLP tutorial description. ACL 2008 ACL Tutorials Page Semi-supervised learning for NLP is a very broad topic, and we realize that we cannot possibly hope to cover all of it in a single tutorial. Because of this, we have provided several supplemental resources pages, each of w
Kernel Averaged Perceptron の話 - mtbrの日記
要約すると、 カーネルパーセプトロンを使うくらいならサポートベクターマシンを使ったほうがいい という話。 以下、パーセプトロンとかカーネルとか基本的なところばかり書きます。 ＜パーセプトロン＞ 正負ラベルを予測する二値分類を行うパーセプトロンの場合、以下のアルゴリズムで訓練する。 ・以下を、重みが収束するまで繰り返す 1. サンプル（正解ラベル付き）をランダムにとってくる 2. 現在の重みとサンプルの内積をとって、その符号（つまり予測されたラベル）が正しければ 1. へ 3. 重み = 重み - あるべき符号 * サンプル 推論（符号が未知のサンプルに対するラベルの予測）のときも、2. と同様に重みとの内積の結果の符号をとって返す。 パーセプトロンはオンラインで使える。 つまり、サンプルが次々と追加される場合でも、順序がランダム（変な偏りがない）と仮定できるなら、上記のアルゴリズムをそのま
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
機械学習についての日々の研究: 2009/02/02 Putting one of your legs on the shoulders of giants
http://sugiyama-www.cs.titech.ac.jp/~sugi/2008/NECsoft-MachineLearning-jp.html