Darts: Double ARray Trie System
Darts: Double-ARray Trie System はじめに Darts は, Double-Array [Aoe 1989]を構築するための シンプルな C++ Template Library です. Double-Array は Trie を表現するためのデータ構造です. ハッシュ木, デジタルトライ, パトリシア木, Suffix Array による擬似 Trieといった 他の Trie の実装に比べ高速に動作します. オリジナル の Double-Arrayは, 動的に key の追加削除を行えるような 枠組ですが, Darts は ソート済の辞書を一括してDouble-Array に変換することに機能を絞っています. ハッシュのような単純な辞書として使うことも可能ですが, 形態素解析器の辞書に必須の Common Prefix Search を非常に高速に行うことが
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
動的配列への追加コストは O(1) ってのは覚えていればそれだけの話ですが，どうしてかと言われると意外と難しいものです． というのも, このO(1)ってのは動的配列の実装方法に強く依存しているからです．実装を知っていないと答えられません． 一般論として，1つ要素を追加するとき，配列に空きがなかったら新しく配列を作り直して全要素をコピーする必要があります．コピーのコストは O(n) だから，追加コストも O(n) になるという議論が混乱の元になっています． こういうときは，要素追加を n 回繰り返したときの計算量を n で割った平均をとるという解析方法が使われるそうです．一般に, ある operation C の計算量を C を n 回行ったときの計算量 O(n) を n で割った値 O(n)/n で評価する手法をならし解析 (amortized analysis)と言うそうです． さて，s
きまぐれ日記: CRF と HMM
職場の人に質問されたのがきっかけで、CRF と HMM について 再考する機会をもった。 CRF は条件付き確率 P(Y|X) をモデル化するのに対し、HMM は 同時確率 P(Y,X) をモデル化する (Y: 形態素列, X: 入力文) ここで、いわゆる「言語モデル」とは 入力文がどれだけ観察されやすいか ということなので、言語モデル＝P(X)となる。 同時確率は、以下のように P(X) を導出できる。 Σ P(Y,X) = P(X) Y つまり、HMM は言語モデルとして使える。また、分布が鋭い場合は P(Y,X) を最大にならしめる Y' を使って P(Y', X) ~= P(X) と近似できる。 つまり、HMM ベースの 形態素解析器 (ChaSen) は、コストの総和を 言語モデルとして使うことができる。微妙に違う２つの入力 A, B を 形態素解析して、そのコストを相対的に比較
Probabilistic Latent Semantic Indexing (SIGIR '99)
Next: LSI Probabilistic Latent Semantic Indexing (SIGIR '99) Thomas Hofmann International Computer Science Institute, Berkley, CA & EECS Department, CS Divison, UC Berkeley hofmann@cs.berkley.edu 発表者 工藤 拓 taku-ku@is.aist-nara.ac.jp 自然言語処理学講座 M1 平成12年7月4日 LSI Aspect Model EM アルゴリズムによるパラメータ学習 PLSI と LSI の比較 U-PLSI,Q-PLSI 実験,結果 考察 この文書について... Taku Kudo 平成12年7月4日
きまぐれ日記: ファンに支えられるプロダクトとユーザにdisられるプロダクト
世の中には熱狂的なファンに支えられるサービスやプロダクトがあります。 Appleファン、Googleファン、日産ファンといえばピンときますが、 Microsoftファン、Yahooファン、トヨタファンと言うとあまり聞きません。 ファンに支えられることは素晴らしいことですが、ファンが多いからといって プロダクトの完成度やクオリティが高いとは限りません。私がファンになるのは アイドルぐらいで、ソフトウェアに関してこれとってファンはないのですが (いやむしろありとあらゆるプロダクトを触ってみては〇〇はウンコと言っていますが...) 某製品の改善点をそのファンに伝えると「愛が足りない」とか 「そんな所誰が気にするのか」とかわされます。 あるプロダクトのファンになるかどうかは、中の人がどれだけカリスマ性があるかとか、 彼らの長期的なビジョンや理念がどれだけ魅力的かと言ったハイレベルなところで 決まり
きまぐれ日記: 肥大化して破綻するオープンソースプロジェクト
一時期オープンソースがはやった時期がありましたが、今はどうなんでしょう? 当時はオープンソースでバラ色の人生みたく過大評価されていたような記憶があります。 過大評価は言い過ぎですが、いまこうやってブログをかけるのもオープンソースの おかげであることは間違いありません。 しかし、すべてのオープンソースプロジェクトが成功したかというと、簡単に YES といえないような気がします。こういう話を某エンジニアとしたら、彼も 同じような視点(というかその方の場合は実経験かもしれませんが)を持ってて、 なんか話が盛り上がってしまいました。 その問題点とは肥大化です。オープンソースは誰でもプロジェクトに参加できるのですが、 ディベロッパーの技術もピンキリなため、時にはどーでもいい拡張がコミットされてしまう ことがあります。その最たるものが周辺技術との統合。ホニャララメタデータをMySQLに保存, ○○バッ
きまぐれ日記: Ajax IME ブックマークレット
Ajax IME ブックマークレットを作ってみました．右クリックしてブックマークに登録してみてください． Ajax IME ブックマークにアクセスするだけで現在表示しているページにある textarea と inputbox が Ajax IME 経由で入力可能になるはずです．成功すれば2秒ほどで textarea の色が変わって Ajax IME 入力状態になります．Alt-O で元に戻ります． たいていはうまくいくようですが，まだまだ完璧ではなくて CSS がらみから入力のカーソル位置が激しくずれたり，javascript のイベントがフックできなくて変化なしといったことが頻発します．気長に修正していくつもりですが，みなさんのフィードバックもお待ちしております． Mixi の日記投稿や Movable Type の投稿も若干癖がありますが問題なかったです．海外からの日記更新がかなり楽に
きまぐれ日記: Autolink: 前方最長一致ではなく最長キーワード優先一致を実現する
Hatena のキーワード置換アルゴリズムがTRIE ベースの手法に変更になったようです。以前に AC法でやる方法の記事を書いたのですが、それと似たことをやってるのでしょうか。 AC法のやり方は単純で、前方から最長一致でキーワードを見つけていきます。これまでは長いキーワードから順番に見つけていく方法(最長キーワード優先一致)だったそうですが、前方から見つけていく方法だと短いキーワードが優先される場合があります。 http://d.hatena.ne.jp/ita/20060119/p1 http://d.hatena.ne.jp/hatenadiary/20060119/1137667217 本文：あいうえおかきくけこさしすせそ KW1 いう KW2 うえおかき KW3 かきく KW4 きくけこさし という文でKW1-KW4のキーワードがマッチする場合、新しくなった方法では「いう」と「かき
きまぐれ日記: colinux から VMware Player に乗り換え
一年以上 windows 上で colinux を使っていてこれといった不自由はなかったのですが、vmware player に乗り換えようと思い立ちました。colinux の環境のほとんどをある方に作ってもらって(カスタマイズされた linux kernel, xfs などなど)アップグレードの煩雑さや可搬性の問題があったからです。vmware player の利点は - ディスクイメージさえコピーすれば、Linux でも Windows でも同じようにゲストOS を動かせてポータブル - 普通のカーネルが使える - Linux 以外の OS も動かせる (Solaris 10 など) - 音が鳴る (あまり重要ではないけど) - USB デバイスが使える qemu を使って vmware 用のディスクイメージを作る方法がいろんなところで紹介されています。その通りにやるとあっけなくインス
きまぐれ日記: タグとマルチラベル問題と機械学習
ネット上のサービスを見ていると、メールなりWebページをある一意のカテゴリに分類するという整理法から、タグ（ラベル）をつけるという整理法に変わってきているようです。 代表的な例は Gmail。フォルダという概念はなくメールにラベルを付与していきます。私が良く使う方法は、「リマインダー」のラベル（メールの重要さという観点）と「内容」のラベルです。二つはそれぞれ独立した分類方法ですが、フォルダだと同居できません。他の例だと「はてなブックマーク」があります。ユーザが任意のタグを付与することができます。 機械学習の言葉を使えば、従来のフォルダは「シングルラベル」の分類問題、後者のタグは「マルチラベル」分類問題となります。文字どおり、前者はインスタンスに対し1つのラベルのみを付与する問題、後者は複数のラベルを付与する問題です。 さて、機械学習の分野でマルチラベル問題はどう進展してるのでしょうか？実際
きまぐれ日記: キーワード抽出: tf-idf の意味づけ
単語の重み付けの古典的な方法に tf-idf があります。文書中の各単語の tf-idf 値計算し、値でソートすると、その文書に特徴的な単語リストを得ることができます。 http://nais.to/~yto/clog/2005-10-12-1.html tf-idf は、単なるヒューリスティックスだと考えられていましたが、最近言語モデルに基づく情報検索手法がさかんに研究されるようになり、tf*idf の解釈が明らかになってきました。言語モデルに基づく手法は、ヒューリスティックスばりばりの手法と同性能にもかかわらず、文書のランキングに理論的で合理的な説明を与えることができます。 情報検索は、クエリ q に対し、もっとも適合する文書 d_opt を求めるタスクです。つまり、q が与えられたとき、文書 d が出現する確率 p(d|q) の最大化問題と解釈できます。 d_opt = argmax
きまぐれ日記: page popularity と page quality と randomness (PageRank 編)
昨日の話の続きです。よくよく考えてみると、PageRank も無作為性を取り入れたアルゴリズムでした。 PageRank は、Web Page の quality を求める方法の一つです。基本的な考え方は、ネットサーファーが ε の確率で無作為に選んだページにジャンプし、1-ε の確率で現在のページ内のリンクを辿ります。サーファがこの手続きを延々と続けていき、定常状態でのページの滞在時間が PageRank です。 このときの ε で無作為のページにジャンプする行為が、無作為性そのものです。 PageRank に似たアルゴリズムとして、Kleinberg の HITS があります。これは、たくさんのリンクを放出する HUB度 と、たくさんのリンクをもらう Authority度 という二つの quality を page に与え、HUB度 の高いページからリンクされると Authority
きまぐれ日記: Ajax で隠れた技術を表舞台に出す
Ajax を知ったのは、今年の2~3月ぐらいだったと思います。この技術に触れたとき、「これで一般には表に出しにくい技術をデモれるかも。。。」と感じたのを覚えています。ほどなくして Ajax KIWI, Ajax IME, Ajax Migemo を作ってそれなりの反響が得られました。 私自身、Webアプリケーション開発の経験はほとんどありません。最近の Web 開発インフラの進歩の速さにはいつも驚かされています。一方、私は急激な進歩とは程遠く、表舞台には出てこない機械学習とか言語処理のツールをふだん hack しています。私がいる分野は、パフォーマンス(実行速度)が結構重要です。 いまさらながら C++ を使って実装していますし、パフォーマンス向上のためのトリビアをそれなりに蓄積しています。ほかにも高速な辞書マッチや文字列検索処理などのコードも書き溜めていました。 今思えばこれがかえって良
きまぐれ日記: リアルめかぶ
めかぶが好物の私ですが、スーパーで売っているいろんなタイプのめかぶをトライしています。しかし納得できるものが少ない。NAIST近くのサカエに売っていた「カネキ吉田商店」の「若めかぶとろろ」がやっぱり一番です。引っ越してきてからは、なかかなこのめかぶに出会うことがなかったのですが、つい最近嫁さんが見つけたそうです。どうやら150円で売ってるみたい。奈良では100円だったのに。。 ひさびさに出会えたこともあり、改めてその味に感動しました。なんたって歯ごたえが違います。たいていのスーパーのめかぶは、単にヌルヌルしてるだけなのですが、カネキさんのは適度なコリコリ感があります。焼酎がすすみます。量も比較的多めです。 このめかぶを安定して入手したいのですが。ダイエー系のスーパーならあるのかな？ さて、形態素解析器 MeCab ですが、0.90の公開準備がようやく整いつつあります。解析精度のよきせぬバグ
きまぐれ日記: Ajax を使った手書き文字認識
Ajax で手書き文字認識を作ってみました。 http://chasen.org/~taku/software/ajax/hwr/ Javascript で描画処理を行い、非同期に座標情報をサーバに送ります。サーバでは文字認識を行い、尤もらしい結果を返します。 前回の Ajax IME と違い、今回はクライアントサイドではなくサーバーサイドの認識エンジンの開発をがんばってみました。画像処理は専門外で経験がありません。逆に言えば、チャレンジングな問題だったし、精度が向上していく様を見てるとわくわくしました。 認識には、機械学習アルゴリズムのひとつである SVM を用いています。学習データとして、オープンソースの手書き文字認識エンジンの Tomoe のデータを使っています。完全に機械学習ベースなので、適当に入力して正解を提示することを繰り返せば、精度が上がっていくと思います。 まだまだ、精度が
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
きまぐれ日記: C++ slice
http://chasen.org/~taku/blog/archives/2005/03/post_801.html
http://chasen.org/~taku/blog/archives/2005/10/popularity_qual.html
きまぐれ日記: はてなキーワードを高速に付与