サービス終了のお知らせサービス終了のお知らせ いつもYahoo! JAPANのサービスをご利用いただき誠にありがとうございます。 お客様がアクセスされたサービスは本日までにサービスを終了いたしました。 今後ともYahoo! JAPANのサービスをご愛顧くださいますよう、よろしくお願いいたします。
Perceptron を勉強する前にオンライン機械学習ライブラリを試してみる (nakatani @ cybozu labs)
今度は CLUTO を試してみた話を書こうと思っていたのですけど、あまりふくらみそうにないので、保留。 オンライン学習(逐次学習)に興味があるので、まずは Perceptron 周辺を勉強し始めてます。 が、その前に動くものをさわっておこうということで、岡野原さんのオンライン機械学習ライブラリをちょっぴり試してみました。 oll プロジェクトページ(日本語) ビルド Linux なら ./configure & make でＯＫ。 Windows の場合 oll.hpp の先頭のどこかに #include <algorithm> を追加すれば VC++ でもコンパイルできました。 サンプルデータ サンプルデータには、プロジェクトページにも実験としてあがっている news20.binary をまずは使ってみることにしましょう。 「シャッフルし、15000例の訓練データと4996例のテストデー
Huffman Coding in Haskell | LAMBDAPHONE
This is the second of probably three posts (the first was on run-length encoding in Haskell) inspired by Thomas Guest’s interesting article on the Deflate algorithm. This is also my first post in literate haskell. Please post any improvements to the code if you have them! For a refreshingly readable introduction to Huffman Coding and the Deflate algorithm, have a look at this short explanation by
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
mots quotidiens.
信学会のノンパラメトリックベイズ講座をようやく書き終えました。 具体的な学習例(上のイメージ)や細かい図を描く必要があり, 結局連休後半からずっと かかった気がします。 最後のページではInfinite HMM (NIPS 2001) [pdf] の紹介をしています。 ちょうど岡野原君がohmmをリリースした所で, やたらとタイミングがいいのですが..。 HMMはよく考えるとかなり凄いモデルですが, 上のohmmも含め, 普通のHMMは 隠れ状態の数は事前にセットしておく必要があります。 これに対し, IHMMは隠れ状態の総数すらも観測データを見るだけで決めてくれる という驚異的なモデルで, 僕はD3の時(2003年くらい)に知って, かなり感動しました。 ただ, IHMMは理論を理解するのもそうですが, 実装がかなりややこしいので *1 僕は実際に実装はしていなかったのですが, 最近素晴
出現頻度と連接頻度に基づく専門用語抽出 - yasuhisa's blog
この前の続き。先週の週末にやるつもりだったけど、暇がなかった。 MeCabで区切った単語を再びつなげる - yasuhisa's blog 前回の流れとしては 専門用語を一つの単語として取ってくるのは難しい MeCabを使うと細かくなりすぎる 専門用語には名詞のsequenceが多そう じゃあ、名詞つなげてみればいいんじゃね? ということで名詞を繋げてみるだけというところをやりました(それだけ。。。)。id:niamさんがコメントしてくださったように"出現頻度と連接頻度に基づく専門用語抽出",自然言語処理, 2003を使うと専門用語らしさ(?)のようなスコア付けができるようなので、それをやってみることにしました。とりあえずp6のLR(CN)のところまでを実装。あとはスコア付けの関数を2つくらい用意して、評価指標の関数を用意すれば、という感じです。 # -*- coding: utf-8 -
R de Isomap - 元データ分析の会社で働いていた人の四方山話
RでIsomapを書いてみた。 ただそれだけ。 まだあんまりRのことは分かってないんだけど、for文を使うと明らかに実効速度的に不利であることは判明した。 applyとかでうまく回避するんだろうけど、C言語育ちの私にとっては「行列の全ての要素に何らかの処理を行う」ってなるとすぐにfor文が頭に浮かんでしまう。 というわけで、僕の書いたIsomapには二重ループがやたらと登場してきて実行速度的に速度的に非常にだめだめです。 どうしたものか。 まともに固有値・固有ベクトルを求めてソートをかけるのがめんどくさかったので、主成分分析の関数を代用してみたんだけどこれでいいのだろうか？ まあ、前にPythonで書いたやつと結果が大きく違わないからいいんだろうけど... あと、eigen(A)とprincomp(A)とprcomp(A)で固有値が違う気がするのは俺だけ？ # データ取得 swiss <-
ohmm（オンラインEMによるHMM学習）をリリースしました - DO++
Ohmm-0.01をリリースしました [Ohmm 日本語] [Ohmm English] これは、以前のブログで書いた、オンラインEM法をそのまま素直に隠れマルコフモデル(HMM)に対し適用したライブラリです。 使う場合は、単語（アクセス履歴とかなんでもよい）に分けられているテキストを入力として与えれば、HMMによる学習を行い、結果を出力します。他で利用できるように、パラメータを出力したり、単語のクラスタリング結果を出力します。 HMM自体は、言語情報やアクセス履歴、生物情報（ＤＮＡ）といったシーケンス情報において、前後の情報を用いて各要素をクラスタリングしたい場合に用います。 本ライブラリの特徴はオンラインEMの特徴通り、従来のEMよりも速く収束します。一応標準的な最適化手法（スケーリング、スパースな期待値情報の管理）もいれているので、そこそこ高速に動きます 速度的には100万語、隠れ状
Canonical Huffman Codes での符号長の効率的な計算 - naoyaのはてなダイアリー
週末に参加した Managing Gigabytes の読書会で第2章のハフマン符号を担当しました。この中で Canonical Huffman Codes の解説がありますが、そこにハフマン符号の符号長を効率的に求める手法の説明が含まれています。 輪講では時間切れのためこのアルゴリズムの解説が駆け足になってしまいましたので、改めて解説資料を作ってみました。2009 年の今に Managing Gigabytes を読んでいるという方はあまり多くないかもしれませんが、参考になれば幸いです。 https://www.dropbox.com/s/539fhyc7rf6b9ik/090518computing_huffman_code_length.ppt?dl=0 (PPT, 258K) 先日 Canonical Huffman Codes の習作を Python で実装しましたが、このコード
ipm.dvi
Spectra of graphs Andries E. Brouwer Willem H. Haemers 2 Contents 1 Graph spectrum 9 1.1 Matrices associated to a graph . . . . . . . . . . . . . . . . . . . 9 1.2 The spectrum of a graph . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 Characteristic polynomial . . . . . . . . . . . . . . . . . . 11 1.3 The spectrum of an undirected graph . . . . . . . . . . . . . . . . 11 1.3.1 Regular gr
kd-tree Visualization(2) - agwの日記
先日のエントリにて、kd木を紹介しました。前回はアルゴリズム Cに倣って、要素の追加のみでkd木を構築してみました。 繰り返しになりますが、一般的に要素の追加のみでkd木を構築するとバランスの悪い木となることが知られています。先日のエントリで作成したkd木を可視化したものは以下のようなものでした。 同じく、木構造として可視化したものは以下のようなものでした。 さて、では何故均衡の取れない木が構築されてしまうのでしょう? 座標群の初めの点、1番の点を挿入した直後の状態を可視してみましょう。 この可視と先ほどの木構造としての可視を比較すると不均衡な木が構築される理由がより明らかとなります。木構造の可視にて1番の左側にぶら下がっている2番以下の座標群は、この可視では1番によって空間分割された領域の下側、つまり、y座標値がより小さい側に分布しています。 同様に、木構造にて1番の右側にぶら下がってい
Kernel Averaged Perceptron の話 - mtbrの日記
要約すると、 カーネルパーセプトロンを使うくらいならサポートベクターマシンを使ったほうがいい という話。 以下、パーセプトロンとかカーネルとか基本的なところばかり書きます。 ＜パーセプトロン＞ 正負ラベルを予測する二値分類を行うパーセプトロンの場合、以下のアルゴリズムで訓練する。 ・以下を、重みが収束するまで繰り返す 1. サンプル（正解ラベル付き）をランダムにとってくる 2. 現在の重みとサンプルの内積をとって、その符号（つまり予測されたラベル）が正しければ 1. へ 3. 重み = 重み - あるべき符号 * サンプル 推論（符号が未知のサンプルに対するラベルの予測）のときも、2. と同様に重みとの内積の結果の符号をとって返す。 パーセプトロンはオンラインで使える。 つまり、サンプルが次々と追加される場合でも、順序がランダム（変な偏りがない）と仮定できるなら、上記のアルゴリズムをそのま
Canonical Huffman Codes - naoyaのはてなダイアリー
1999年出版と少し古い書籍ですが Managing Gigabytes を読んでいます。理解のために 2.3 で出て来る Canonical Huffman Codes の習作を作りました。 ハフマン符号は情報圧縮で利用される古典的なアルゴリズムで、圧縮対象データに出現するシンボルの出現確率が分かっているときに、その各シンボルに最適な符号長の接頭語符号を求めるものです。 通常のハフマン符号はポインタで結ばれたハフマン木を構築して、ツリーを辿りながら各シンボルに対する接頭語符号を計算します。このハフマン木には曖昧な箇所が残されています。ハフマン木は木の辺を右に辿るか左に辿るかで符号のビットが決まりますが、右が 0 で左が 1 などというのはどちらでも良いという点です。(曖昧だから駄目、という話ではありません。) 従って、ハフマン木から生成される符号は一意には決まりません。 ここで各シンボル
algorithm - 最近点検索をkd-treeで : 404 Blog Not Found
2009年04月30日01:00 カテゴリMathLightweight Languages algorithm - 最近点検索をkd-treeで というわけで、kd-treeによる検索も実装してみました。 はてなブックマーク - ototoiのブックマーク データ数が少ない場合、この全検索が高速。ただデータが多くなってくるとkd-treeがいいと思う。点ならば配列をソートするだけで実現できる。 以下のデモでは、単にkd-treeによる検索だけではなく、kd-tree構築の速度と、総当たりの場合の速度の比較もできるようにしてあります。10,000点ぐらいだと、その差を顕著に感じることが出来るでしょう。100,000点ぐらいあると、感動的なほど差が出ます。それだけあってもkd-treeの方はほぼ1ms以内に検索が終わるのですから(ただしこの場合、デモの実行に合計10秒以上かかるので注意!)。
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
http://mono.kmc.gr.jp/~oxy/d/?date=20090602
plda - Google Code
機械学習についての日々の研究: 2009/02/02 Putting one of your legs on the shoulders of giants
人工知能学会 (The Japanese Society for Artificial Intelligence) | 人工知能学会のホームページです。入会手続き、会議やセミナーの開催予定、学会誌情報などを掲載しています。