はじめに NowいProfessionalなYoungにバカうけなLMを作ってみたいなぁと思ったので、Chinese Restaurant Process(CRP)についてちょっと調べてみた。 CRPとは 中華料理店過程(Chinese Restaurant Process) 以下のルールによって、集合{1,...,n}の分割Bnを決め…

12/10にmixiさんで行われたDSIRNLP勉強会で発表させていただきました 聴きにきていただいた方ありがとうございました スライド資料 http://www.slideshare.net/phyllo/ngram-10539181 自然言語処理はじめました - Ngramを数え上げまくる View more presentat…

はじめに 条件付き確率場(Conditional Random Fields)を実装してみた。 本の式導出がわからなくて、夜な夜なmac book airを涙で濡らしながら書いたので、あやしい。 説明 基本的に「言語処理のための機械学習入門」の本の通りに書いた(つもり、、、) すごく…

はじめに perlのプログラムをc++に移したいという話で、連想配列をどうするかでハッシュの話が出てきたので調べてみた。 ハッシュ関数とは あるデータ(key)に対応する数値(value)を得るための関数 例えば、文字列(key)に対応する数字(value)、など 優れたハ…

はじめに FOBOSという最近のオンライン学習の方法を知ったので試してみた。 FOBOSとは 2009年に提案された微分不可能な目的関数でもうまく正則化をしつつオンライン学習できる手法 http://jmlr.csail.mit.edu/papers/v10/duchi09a.html 劣勾配法という手法で…

はじめに 形態素解析器のデコーダ部分を超簡単に書いてみた。 いつも通り速度などは考えずに流れを学ぶために書いているので遅い。。。 あと「辞書の構築(コスト計算)」と「未知語処理」ができればそれっぽいものができそうな予感。 速度の改善などは、doubl…

はじめに 現在よく使われていると思われる確率的言語モデルについて簡単に調べてみたのでメモ。 Ngram言語モデルとは 例えば、「お酒が飲みたい」と「バリウムが飲みたい」という文章があった時に、前者の方がよく聞く文章で、後者はほとんど聞かない文章 上…

はじめに 先日作ったDouble ArrayにPredictive Searchを追加してみた。 Predictive Searchとは Common Prefix Searchは、入力文の長さまでで共通の接頭辞を持つ部分文字列を列挙した 入力文が「今日は晴れ」なら「今」「今日」「今日は」...が登録されている…

はじめに 雑誌に簡単なラティス構築とビタビアルゴリズムについて書かれていたので、参考にしてc++で書いてみた。 実際のコスト値などはいれてない。。。 説明 入力文に対し、部分文字列に対し辞書引きをして、ノードとする エッジは文字列上で隣接している…

はじめに 系列ラベリング問題についてちょっと調べてみたのでメモ。 系列ラベリング(系列分類)問題とは ある系列xの各要素に適切なラベル列yを付与する問題 例えば「This is a pen」という文書の各単語に「This(代名詞) is(動詞) a(冠詞) pen(名詞)」のよう…

はじめに 先日作成したDoubleArrayに共通接頭辞検索機能を追加してみた。 共通接頭辞検索とは ある文字列の接頭辞(「今日のご飯」という文字列なら「今」「今日」「今日の」...)について、それが辞書に含まれるかどうかを検索すること Trie(DoubleArray)やAC…

はじめに 形態素解析器などで利用されている「ダブル配列(double array)」の勉強するため、実装をしてみた。 動作を確認するために書いただけなので重い。。。 ダブル配列とは 文字列の検索をO(1)で行えるTrie(トライ木)の効率的なデータ構造 2つの配列BASE…

はじめに 探索空間から大域的最適解を求めることができる汎用的なアルゴリズムの「焼き鈍し法」についてちょっと調べてみたのでメモ。latticelmでも用いられているみたい。 SAアルゴリズム 温度Tによって、動作が変わる メインは「メトロポリスの手続き」で…

はじめに MeCabを使うと言っても、辞書には気をつけてなくて、実際MeCabページにおいてある辞書しか使ったことがなかった。しかし、この辞書は更新履歴(2007年！！)が古かったりして保守されているわけではない。MeCabで使えるほかの辞書はないかと思って調…

はじめに 超大規模なテキストデータでのN-gram統計を取る場合、そもそもデータがメモリにのらなくてSuffixArrayを使ったカウントも無理だったりする。近似値でよい場合、効率的な方法があると知ったのでちょっとメモ＆試してみた。 与えられるデータ 大量の…

はじめに 大規模なテキストデータでのN-gram統計を取る場合、特にNが大きい場合(N>=3)は、組み合わせの数が多くなり出てくるN-gramをすべてメモリに保持しながら個数をカウントするのが難しい。効率的な方法があるのを知ったのでちょっと試してみた。 大規模…

はじめに Trieとその周辺を調べたのでまとめた。 Trie(トライ木)とは 文字列探索のための順序付木構造 Prefix Treeとも呼ばれる 由来は「reTRIEval」らしい 共通のPrefixをまとめたデータ構造で、文字列が辞書(Trie)に登録されているかを高速に検索すること…

ポアソン分布とは http://ja.wikipedia.org/wiki/%E3%83%9D%E3%82%A2%E3%82%BD%E3%83%B3%E5%88%86%E5%B8%83 単位時間に平均で回発生する事象が、k回発生する確率 パラメータによって確率Pが決まる 最尤推定 あるポアソン分布から生成されたデータD={0,0,1,3,…

はじめに ハッシュのkeyにID、valueにソート済み整数列を持つようなデータに対して、valueの整数列を圧縮したい。 perlで簡単なUnary符号化を書いてみた。転置インデックス圧縮などに。 コードについて Unary符号とは、1を区切りとして連続する0の個数で数字…

スプレイ木とは SleatorとTarjanによって紹介 自己調整を行う平衡二分探索木 アクセスした頂点がルートにくるように「スプレイ操作」を繰り返し行う 頂点へのアクセスに偏りがある場合に有効(ある頂点によくアクセスするなど) 逆に一様にアクセスする場合は…

はじめに 形態素解析器が何たるかも知らずにいたのでメモ。 形態素とは？ 意味を持つ最小の言語単位 形態素＜単語＜文＜テキスト(ドキュメント) 例えば「今日は晴れ」という文は「今日」＋「は」＋「晴れ」のような形態素(単語)に分解できる 形態素解析とは…

条件付き確率場とは？ 対数線形モデルを系列ラベリング問題へ適用したもの 対数線形モデルメモ http://d.hatena.ne.jp/jetbead/20110923/1316794767 一般には、系列だけでなくグラフの頂点のラベルにも適用できる 系列の場合は、「linear-chain CRF」と呼ば…

はじめに Passive-AggressiveアルゴリズムとLIBSVMでどの程度の性能差がでるのか試してみた。 使用したデータ LIBSVMのページにあるUCIデータセットのa9aを用いた http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ 学習データ : a9a.txt テストデー…

はじめに Perceptronについて調べてたりするとよく間違えた出てくるPAアルゴリズムについて調べたのでメモ。 Passive-Aggressive(PA) Algorithm Passive-Aggressive 心理学とかだと「やれといわれる(受動的)けど実際はやらない(攻撃的)」みたいな意味らしい …

はじめに PAアルゴリズムは回帰問題にも適用することができる、と書いてあったのでとりあえず試してみた。 パラメータの設定などがわかっていないので、要調査。 使用したデータ LIBSVMのページにあるUCIデータセットのeunite2001を用いた http://www.csie.n…

対数線形モデルとは？ log-linear model 最大エントロピーモデルとも呼ばれる P(y|d)を直接モデル化する(y:ラベル、d:事例) P(d), P(d|y), P(d,y)などは求めることができない 素性関数 ラベルと事例の組(y, d)を素性として扱う そうでない場合としては、事例…

計量文献学とは？ 文献の特徴を数値化→統計的にその文献の分析・比較を行う方法または学問 「書き手によって文章に現れる言葉は違うのではないか？」に注目 文体(文章などのスタイル、和文・漢文、ですます・である調など)に注目＝計量文体学 著者が同じ人か…

はじめに 以前、g++で日本語処理をするという記事を書いたけど、できるだけ環境に依存せずにUTF8で書かれた文章を処理したい。 調べてみると、UTF8は文字の最初のbyteを見れば何バイトの文字なのかがわかるので、簡単なラッパーを作った。 UTF8の仕様 http:/…

はじめに 索引データの保存に関する記事を読んだのでメモ。 索引データの効率的な保存 ドキュメント数やできた索引数が多くなるにつれ、効率的に索引データを保存することが重要になってくる 工夫して索引データを保存することで、いろんなメリットがある メ…

はじめに 人工知能学会誌に「私のブックマーク」というのが連載されてるらしく、それに載ってたページをまとめてるものが公開されてることを最近(twitterで)知ったのでメモ。 メモ http://www.ai-gakkai.or.jp/jsai/journal/mybookmark/ 以下、特に自分に関…