サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
TGS2024
echizen-tm.hatenadiary.org
CW(Confidence Weighted)を実装したので調子に乗ってSCW(Soft Confidence Weighted)も書いてみた。 SCWには1と2があって、それぞれL1,L2正則化っぽい感じのことをしている。今回はSCW1を実装した。 またCWは学習時に使う共分散行列が対角成分しかなかったのだが、SCWは対角成分以外にも値が入ってくるので取りうる特徴量が多い場合はなんらかの工夫が必要かも。 https://github.com/echizentm/ConfidenceWeighted test.plの最後でRGBそれぞれの重みをダンプした。scwのほうが重みが控えめになっているっぽい。 $$ perl test.pl 0.7 cw 1 3 < colors.csv update: 1,255 0 0 update: -1,0 255 0 update: -1,0 0 255
時代はSCW(Soft Confidence Weighted)らしいのだがCWさえまともに実装したことがなかった。これでは良くないということでCWを実装したので公開しておく。 https://github.com/echizentm/ConfidenceWeighted 参考: http://www.cs.jhu.edu/~mdredze/publications/icml_variance.pdf http://d.hatena.ne.jp/kisa12012/20120625/1340616659 http://d.hatena.ne.jp/jetbead/20130510/1368120547 以下はconfidenceパラメータη=0.7(0.7以上の確率で分類成功するように学習する)、分散の初期値を1、特徴量を3つ(RGB)として暖色系(1)or寒色系(-1)を判定する例。 $
学習器を実装しようとすると唐突に逆誤差関数(erf(誤差関数)の逆関数)が必要になったりする。 こんなときに慌てず騒がずコピペできるようにPerlで実装したものをメモしておく。 誤差関数および逆誤差関数は解析的に解が求まらないけれどテイラー展開で近似することができる(参考: http://ja.wikipedia.org/wiki/%E8%AA%A4%E5%B7%AE%E9%96%A2%E6%95%B0)。 #!/usr/bin/perl use strict; use warnings; use Math::Trig qw/pi/; my $num = shift @ARGV; my $pre = 0; for my $n (1..10) { my $order = $n * 10; my $erf_inv = erf_inv($num, $order); my $diff = abs(
転職して1年が経ちました。 前職での6年間は私の人生で最も辛い時期でした。転職してようやく本来の自分を取り戻せました。自分にあった場所で働くというのはとても大切だと思うので、転職するにあたって私がやったことをメモしておきます。 1.転職の意思を固める 辞めたいと思った時が辞めどきです。他人の意見は気にする必要はないです。よく「n年はうちで頑張れ」と言われたりしますが、実際は転職を決意してから転職完了までに身につけたことで充分なので「n年頑張る」という待ちのフェイズは不要です。決意から完了まで結果的にn年かかるということはあるかもしれないですが、特に意味もなくn年耐えても良いことはないです。 2.興味のある技術を持つ 人が技術を身につけるのは会社の仕事をするためだけではないです。必要な技術は会社によって異なりますし、会社内でも部署や情勢によって変わってきます。それに追随するためだけに技術を学
情報理論でエントロピーといえば確率変数が持つ情報量の期待値のこと。例えば P(x1) = 1/2, P(x2) = 1/4, P(x3) = 1/4という分布があったらエントロピーは 1/2 * lg2 + 1/4 * lg4 + 1/4 * lg4 = 1/2 * 1 + 1/4 * 2 + 1/4 * 2 = 3/2 = 1.5なので平均1.5ビットでこの分布から生成されたデータを表現できる。 では確率変数の列を表現するには平均何ビット必要だろうか。言い換えると確率変数の列にデータを追加するには平均何ビット必要だろうか。これはエントロピーレートという概念で説明できる。 実はエントロピーレートをよくわかっていなかったのだけど、最近になって理解したのでメモしておく。 エントロピーレートとは確率変数列に確率変数を1つ追加したときに増える情報量の期待値のこと。 まず前提として確率過程として、定
Googleの新しい圧縮アルゴリズムZopfliについて調べたのでメモしておく。 Compress data more densely with Zopfli - Google Developers Blog deflateアルゴリズム zopfliはdeflateアルゴリズムに基づいた圧縮ライブラリ。deflateアルゴリズムはデータをLZSSというLZ77を改良した圧縮法で圧縮し、その後ハフマン符号で符号化したもの。 deflateアルゴリズムの実装としてはzlibやgzipがある。zlibとgzipの違いはヘッダとフッタの持っている情報。 使ってみる googlecode(http://code.google.com/p/zopfli/)から取ってくる。 $$ git clone https://code.google.com/p/zopfli/ $$ cd zopfli $$ ma
ウェーブレット木/行列など「高速文字列解析の世界」で扱っているデータ構造やアルゴリズムは完備辞書(Fully Indexable Dictionary)を基本的な道具として用いるものが多い。 とはいえ実用的な完備辞書を一から作るのは大変なので、高速文字列本を読んで「ちょっとウェーブレット行列を作ってみようかな」と思ったとしても完備辞書は適当なモックで済まさないといけなかったりして面白くない。 というわけでPerlモジュールを書いた。 https://github.com/echizentm/FullyIndexableDictionary 例えば以下のような感じ。これでLOUDSもウェーブレット行列もさくさく作れますね! use FullyIndexableDictionary; my $fid = FullyIndexableDictionary->new(); $fid->set(1,
「入門機械学習」を献本していただきました。ありがとうございました。 というわけで早速読み終わったので感想を書いておく。 機械学習の入門書ではない 本書はタイトルから連想されるような機械学習に入門するような内容は書かれていない。一切数式は登場せずアルゴリズムはすべてブラックボックス化されている。では本書はダメな本なのかというとそんなことは全くない。少なくとも「入門 機械学習」というタイトルに興味をもって本書を手にとった人にとっては大変有益な本だと思う。 大きなデータを扱って何かしたい人が最初に読むべき本 繰り返すが本書は機械学習の仕組みについては書いていない。仕組みはブラックボックスとして割り切ることで従来の機械学習の入門書が触れていない部分を非常に大きく扱っている。それは何かというと「汚いデータからどうやって機械学習の入力データを作るか」「機械学習の手法をどのように選択するか」「機械学習に
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
DSIRNLP#03 で「ウェーブレット行列 最速攻略」の発表をしました。 詳しくは資料を見ていただけると良いです。 台風にぶつかってしまいどうなることかと思いましたが、@overlastさんの配慮で無事発表できました。ありがとうございました。 それから準備あまり手伝えなくて申し訳ないです。努力が足りませんでした。すみません>弊グループ各位。 以下、資料になります。 Wavelet Matrix DSIRNLPはデータ構造系の発表が大変充実していてとても面白いです。今後も盛り上がっていくといいですね。
9/30(日)に開催予定のDSIRNLP#03で発表予定の「ウェーブレット行列 最速攻略」の予告編資料を作成したので公開しておきます。 ウェーブレット行列とはそもそもどんなものなのかを解説した資料です。この資料によってウェーブレット行列に関心をもつ人が増えるとうれしいです。 Wavelet Matrix Overview 第3回 データ構造と情報検索と言語処理勉強会 #DSIRNLP
9/30(日)に開催予定のDSIRNLP#03でウェーブレット木について発表しません。 なんで発表しないかというとウェーブレット行列というウェーブレット木の上位互換であるまじぱないデータ構造について話すからです。 ウェーブレット木がわからないとウェーブレット行列もわからないんじゃないの?と思われるかもしれませんが、その逆でウェーブレット木では必要以上に難しく考えていたことを「それ、もっと単純に出来るよ」っていうふうに見方を変えたのがウェーブレット行列です。 ウェーブレット木を知らない人はむしろウェーブレット行列から入ったほうが近道です。 なのでDSIRNLP#03ではウェーブレット木については発表しません。発表予定だった資料は以下のURLで公開していますので興味ある方は参考にどうぞ。 よくわかるウェーブレット木
ごく一部で話題沸騰中のまじぱないデータ構造、ウェーブレット行列を用いた検索アルゴリズムであるFM-Index。このFM-Indexは以前私が実装したShellinfordというライブラリから利用可能になっている。さらにここで用いたウェーブレット行列にはオリジナルにはない高速化を加えている。 ウェーブレット行列を用いたFM-Indexを大幅に高速化した - EchizenBlog-Zwei とはいえC++からしか使えなくて少々不便だったのでPerlモジュールを用意してみた。 ライブラリのインストール方法は以下を参照。 http://code.google.com/p/shellinford/ サンプルを示す。 use strict; use warnings; use Shellinford; my @docs = ("apple", "orange", "remon", "applicat
FM-Indexで用いる簡潔データ列としてウェーブレット行列とウェーブレット木のどちらがいけてるのかを調べてみた。 データは以下の実験で用いた住所データを使った。 http://d.hatena.ne.jp/echizen_tm/20120215/1329315913 データサイズは ウェーブレット行列: 5, 693, 256 byte ウェーブレット木: 5, 709, 560 byteとなった。ビット列のセパレータ数が少ないぶんウェーブレット行列のほうがやや小さい。 速度についてはsample/search_fm_indexを用いてインデックスした住所データ(118,073件)をシャッフルしたものをクエリとして全件検索にかかる時間を測った。 $$ time sample/search_fm_index var/zenkoku.key.fm.wm m y < var/zenkoku.s
話題のウェーブレット行列(Wavelet Matrix)を自作のFM-Indexライブラリ、shellinfordに組み込んでみた。 ウェーブレット行列はウェーブレット木と互換性があるので、ウェーブレット木の代表的な適用例であるFM-Indexでも当然利用可能。 というわけでとりいそぎソースを公開しておく。構築部分がやっつけで書いたので構築時にやたらメモリ食う。良い方法を見つけたら修正する予定。効率化しました(Aug.15, 2012)。 構築後の検索は効率が良い(はず)。ウェーブレット木版との比較は気が向いたらやるかも。 https://code.google.com/p/shellinford/
久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。 これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文
ふと思ったのでメモしておく。 ダンジョンでは最初に脱出の呪文が使えるかどうかを確認する 退路の確保は重要。最深部で脱出の呪文が使えないダンジョンであると気づくと目も当てられないので最初に確認しておきたい。 レベル上げスポットを確保する 経験値やお金の少ない敵を倒し続けてもメリットは少ない。また回復が困難な場所でのレベル上げも効率が悪い。同じダンジョンでのレベル上げにこだわらずに回復所が近くにあってたくさん経験値が手に入る場所を見つけて集中的にレベルを上げたい。 パーティメンバーの離脱に注意する 例えば回復呪文の使い手が一人しかいないと、その仲間がイベントで離脱した時に大変なことになる。同じ技能をもった仲間は複数ほしい。 できる限り多くの属性の攻撃手段を揃えておく ダンジョンには様々な敵が出現するので多くの属性の攻撃呪文が欲しい。自分で習得できないなら習得済みの仲間と協力する、呪文と同等の効
ちょっと前に「4人のロシア人の方法(Method of Four Russians)」というのを論文で見かけて面白かったので紹介しておく。 簡単に言ってしまうと、ある処理を高速化したい時にデータ全体を小さなブロックに分割してブロック単位での結果を事前に計算したテーブルで持っておくよ、というアルゴリズム。 名前は知らなくてもアルゴリズム自体は知ってる人は多いかもしれない。 Method of Four Russians - Wikipedia, the free encyclopedia アルゴリズム自体は汎用的なものだが編集距離の高速化を例として説明するのが一般的なようなのでそれに倣う。 文章で書くとごちゃごちゃするのでスライドで。もっふる。 http://www.scribd.com/doc/94190119/MoFR ※追記:↑のスライド、正直自分でもわかりやすいとは思えないので余裕が
というわけで転職しました。 渋谷といってもモゲマスの会社ではなくDSIRNLPのときにお世話になっていた会社です。 待遇や環境、仕事内容などあらゆる面が大幅に改善されモチベーションがうなぎのぼりです。 さらに前職同様、一緒に仕事をする方にも恵まれていて圧倒的な感じがします。 思わず最善を尽くしたいと思える環境でした。がんばります。
個人的な報告で恐縮ですが本日を以って今の職場(以下、現職)の最終出社を迎えました。 「ここはルイーダの酒場。旅人たちが仲間をもとめて集まる出会いと別れの酒場よ」 私にとって現職はルイーダの酒場のような場所でした。多くの優れた人々との出会いは私にとって大きな刺激となりました。私が必死で乗り越えた壁を、いとも容易く乗り越えて遥か彼方をスキップしているような凄まじい技術力を持ったエンジニアに囲まれて非常に大きな刺激を受けました。具体的には「ちょっと暇だった」と言って片手間で実用的なダブル配列を実装してしまうような神ばかりでした。 私は学生時代に自分の力の限界を感じてしまい、無意識の内に目標を小さく持ってしまう癖がついていました。しかし就職してからは周りがものすごい力を持った方ばかりでしたので、何もできなければ直ちに死ぬだけでした。最早頭が悪いとか言っている場合ではありませんでした。高い技術力を身
最近サザエさんとキュアピースのじゃんけん対決が話題になっている。 じゃんけんポンで日曜日 またこれに関連して「サザエさん ジャンケン学」というサイトが注目を集めている様子。 サザエさん ジャンケン学 このサイトによるこれまでの予測的中率は44.7%とのこと。 さて自然言語処理という技術の分野ではNgramモデルというものがある。これは簡単に言うと「まことに」という言葉の後には「残念ですが」という言葉がつながりやすいとか、「ちょっと」の後には「いいですか」がつながりやすいというように「どういう言葉の後にどういう言葉がつながるか」ということを表現するモデルのこと。 これをじゃんけんに応用することで「この人はグー、グーときたら次はチョキを出す」というような傾向を予測することができる。 このNgramモデルを使うことでサザエさんに50%くらいの確率で勝てることがわかったので以下にまとめる。 Ngr
いけてるエンジニアが「これは良書だ!」と絶賛しているので買ってみたら、よくわからないことが書いてあるだけで理解できなかった。という経験をした人は多いのではないかと思う。 こういうことはなぜ起きるかというと、別にいけてるエンジニアが初心者に意地悪をしているわけでもないし、いけてるエンジニアとは頭の出来が違いすぎたということもなく、単純に「良書」には複数のパターンがあるからなのでは、と私は思っている。 全くの私見だが大別して3パターンある気がする。以下、これについて述べたい。 1.「わからない」を解決する良書 初心者にとって最もうれしいのがこのパターンの書籍。一般的に良書と言われるのはこのパターンに属する書籍だと思われる。 (私もそうだったのだが)初心者はそもそも、その技術分野に対するカンが全く働かないので、本を最初から順番に読む傾向がある。また自分で具体例をノートに書いたり、コーディングした
一般にソートアルゴリズムの計算量はソート対象となるデータ数NについてO(N^2)とかO(NlogN)等で評価する。数値データのソートであれば特に問題はないのだが、文字列データの場合は一回の比較に対して文字列長Mに比例する計算量O(M)がかかってしまう。例えばクイックソートであればO(NlogN)ではなくO(MNlogN)となる。よってMが非常に大きい場合はソート性能の劣化を招く。 文字列ソートに付いてはBently&Sedgewickのマルチキー・クイックソート(multikey-quicksort)という改良版クイックソートが存在する。このソート法は、ある工夫によって一回の比較を文字列長Mに依存しない形で実現している。 例えば文字列appleとapplicationの比較について考える。 # 先頭の文字を比較 [a]pple = [a]pplication # 2文字目を比較 a[p]p
IME本の効果でLOUDSの認知度が高まってきた気がする。が、一方で難しいという意見もチラホラある様子。 というわけでLOUDSをどこまでわかりやすく説明できるか?ということに挑戦したくなったので記事を書いてみるよ。 LOUDSというのは木を表すデータ構造。木というのは以下のようなものを想像すればよい。 この木を表すデータ構造を作りたい。単純に考えると各ノード毎に子ノードのIDを持たせておけばよい。つまり 0 => {1, 4, 5} 1 => {2, 3} 2 => {} 3 => {} 4 => {} 5 => {6} 6 => {7}というようなものを考える。ここで各IDと子ノード数を各1バイトで管理したとして 0 => {1, 4, 5} # 1 + 3 = 4バイト 1 => {2, 3} # 1 + 2 = 3バイト 2 => {} # 1 + 0 = 1バイト 3 => {}
「日本語入力を支える技術(IME本)」で紹介されたことで一躍市民権を得た感のあるLOUDS(Level Order Unary Degree Sequence)。LOUDSとは木の簡潔データ構造で、小さいデータサイズで木が実現できるので日本語入力の辞書引きに使うトライ木をLOUDSで実装すると効率が良い。 さて、そんなLOUDSにはパワーアップ版ともいうべきDFUDS(Depth First Unary Degree Sequence)というデータ構造がある。DFUDSはLOUDSが定数時間で扱える操作(parent(親ノードの位置を得る), i-th child(i番目の子ノードの位置を得る), degree(子ノード数を得る))に加えてsubtree size(現在のノードを根とする部分木のノード数を得る)という操作が定数時間で実現できる。よってDFUDSを使うと、トライでpredic
先日公開したウェーブレット木のライブラリshellinfordにFM-Indexの機能を追加した。 まだ基本的な機能しか実装していないけれど、とりいそぎ公開しておく。おいおい機能は追加していく予定。 shellinford - shellinford: succinct document retrieval library - Google Project Hosting An alphabet-friendly FM-index P. Ferragina, G. Manzini, V. Makinen, G. Navarro, 2004 ちなみにウェーブレット木はちょっと高速化したので一つ前の記事のパフォーマンス測定結果が改善されて rank_wavelet_tree: 14.71s select_wavelet_tree: 460.34sとなった。これについては機会があったら記事を書く
@tkngさんの力作「日本語入力を支える技術」が2/8に発売される。既に秋葉原のヨドバシ有隣堂や池袋のジュンク堂本店では早売りされている様子。ってことで早速購入してきた。 本書が扱うテーマはGoogleIMEのような「日本語入力」のシステム。これだけだとさして興味ないや、って人も多いかもしれない。ところがこの日本語入力というのは技術的には形態素解析に非常に近い。自然言語処理やテキストマイニングに関わる方にとっては形態素解析は最も基本的かつ重要な技術。その仕組みを知っておくのは非常に重要だと思う。 また日本語入力(形態素解析)は技術的には機械学習、グラフの最短経路問題、簡潔データ構造など多くの分野が関わっているので「日本語入力」を理解することでこれらの多くの基礎技術の具体例を体感できるというメリットがある。 そんな日本語入力をまとめて勉強できるのが本書「日本語入力を支える技術」である!ばーん
ついかっとなってウェーブレット木のライブラリを作ってみた。せっかくなので公開しておく。LOUDSはerika-trieを作ったので今度はウェーブレット木を作りたかった。 ライブラリ名はおおかたの予想を裏切りshellinford。かびーん。 なお、ウェーブレット木で用いている簡潔ビットベクトルは前回のDSIRNLPで発表したものの公開していなかった「少ない労力でそこそこいけてるビットベクトル」を使っている。 shellinford - shellinford: succinct document retrieval library - Google Project Hosting DSIRNLP#2で発表しました「作ろう!簡潔ビットベクトル」 - EchizenBlog-Zwei まずソースコードを取ってきてインスト。 $$ svn checkout https://shellinford
時代はテスト駆動開発(TDD)らしいので有名な単体テスト用フレームワークCppUnitを試してみた。 これまでテスト用コードは自前で書いていたのでフレームワークのありがたさを実感するなどした。ただCppUnitは「必ず書かないといけないコード」の量が何気に多くて初見でめげそうになる気もした。なので主に自分用にCppUnitコードのテンプレをメモしておく。 まずはCppUnitを入手する。例えば Download CppUnit - C++ port of JUnit from SourceForge.net から入手できる。入手したらインストする。 $$ tar xzfv cppunit-1.12.1.tar.gz $$ cd cppunit-1.12.1.tar.gz $$ ./configure $$ make $$ sudo make installでここから解説。CppUnitでテ
次のページ
このページを最初にブックマークしてみませんか?
『EchizenBlog-Zwei』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く