プログラミング
はじめに 1次元のガンマ分布または逆ガンマ分布に従う乱数を生成したい。 いろんな人が書いているのでちょっと自分も実装してみる。 コード 参照論文 http://www.economicsbulletin.com/2008/volume3/EB-07C10012A.pdf #include <iostream> #include <cmath> //xorshift // 注</cmath></iostream>…
はじめに 歪んだサイコロを使ってベイズ統計学の初歩を勉強してみる。 歪んだサイコロ 6面サイコロがある。しかし、よく見ると各面の大きさが違う。 以下、疑似的に出目を生成してみる。 歪んだサイコロの出目 コード #include <iostream> #include <vector> #include <climits> static </climits></vector></iostream>…
はじめに ちょっと遊びで多腕バンディット問題で遊んでみた。UCB1-tunedも書いてみたけどUCB1より最終的な儲けが低くてあれ？ってなった。どっか間違ってるか。。。 追記(2012/2/12)：コメントをいただいて、修正しました。一応、報酬額がUCB1よりtunedの方…
はじめに ギブスサンプリングで2次元正規分布からサンプリングを試してみる。 サンプリングの流れ 2次元正規分布なので(x,y)がサンプリングされる。 初期値(x0,y0)を決める y0を固定した場合の条件付き正規分布からx1をサンプリングする→(x1,y0) 次に、x1を…
はじめに ある分布に従った乱数を生成したいことがよくあったりする(一様分布に従う一様乱数や正規分布に従う正規乱数など)。 ベイズ統計学なんかだと、自然共役事前分布が使えないような複雑な分布の場合にMCMCで分布のサンプリングをして計算したりするの…
はじめに Suffix Arrayあたりをちょっと調べてみたのでとりあえずメモ。 調べてみたら結構研究されていて全部まとめるのが面倒あとできちんと理解しておきたい。 Suffix Array(接尾辞配列)とは 文字列に対して、その文字列の接尾辞集合を辞書順ソートしたも…
はじめに 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…
はじめに 先日作ったDouble ArrayにPredictive Searchを追加してみた。 Predictive Searchとは Common Prefix Searchは、入力文の長さまでで共通の接頭辞を持つ部分文字列を列挙した 入力文が「今日は晴れ」なら「今」「今日」「今日は」...が登録されている…
はじめに 雑誌に簡単なラティス構築とビタビアルゴリズムについて書かれていたので、参考にしてc++で書いてみた。 実際のコスト値などはいれてない。。。 説明 入力文に対し、部分文字列に対し辞書引きをして、ノードとする エッジは文字列上で隣接している…
はじめに 先日作成したDoubleArrayに共通接頭辞検索機能を追加してみた。 共通接頭辞検索とは ある文字列の接頭辞(「今日のご飯」という文字列なら「今」「今日」「今日の」...)について、それが辞書に含まれるかどうかを検索すること Trie(DoubleArray)やAC…
はじめに 形態素解析器などで利用されている「ダブル配列(double array)」の勉強するため、実装をしてみた。 動作を確認するために書いただけなので重い。。。 ダブル配列とは 文字列の検索をO(1)で行えるTrie(トライ木)の効率的なデータ構造 2つの配列BASE…
はじめに 探索空間から大域的最適解を求めることができる汎用的なアルゴリズムの「焼き鈍し法」についてちょっと調べてみたのでメモ。latticelmでも用いられているみたい。 SAアルゴリズム 温度Tによって、動作が変わる メインは「メトロポリスの手続き」で…
はじめに 超大規模なテキストデータでのN-gram統計を取る場合、そもそもデータがメモリにのらなくてSuffixArrayを使ったカウントも無理だったりする。近似値でよい場合、効率的な方法があると知ったのでちょっとメモ＆試してみた。 与えられるデータ 大量の…
はじめに 大規模なテキストデータでのN-gram統計を取る場合、特にNが大きい場合(N>=3)は、組み合わせの数が多くなり出てくるN-gramをすべてメモリに保持しながら個数をカウントするのが難しい。効率的な方法があるのを知ったのでちょっと試してみた。 大規模…
はじめに Trieとその周辺を調べたのでまとめた。 Trie(トライ木)とは 文字列探索のための順序付木構造 Prefix Treeとも呼ばれる 由来は「reTRIEval」らしい 共通のPrefixをまとめたデータ構造で、文字列が辞書(Trie)に登録されているかを高速に検索すること…
はじめに ハッシュのkeyにID、valueにソート済み整数列を持つようなデータに対して、valueの整数列を圧縮したい。 perlで簡単なUnary符号化を書いてみた。転置インデックス圧縮などに。 コードについて Unary符号とは、1を区切りとして連続する0の個数で数字…
スプレイ木とは SleatorとTarjanによって紹介 自己調整を行う平衡二分探索木 アクセスした頂点がルートにくるように「スプレイ操作」を繰り返し行う 頂点へのアクセスに偏りがある場合に有効(ある頂点によくアクセスするなど) 逆に一様にアクセスする場合は…
はじめに 形態素解析器が何たるかも知らずにいたのでメモ。 形態素とは？ 意味を持つ最小の言語単位 形態素＜単語＜文＜テキスト(ドキュメント) 例えば「今日は晴れ」という文は「今日」＋「は」＋「晴れ」のような形態素(単語)に分解できる 形態素解析とは…
はじめに Passive-AggressiveアルゴリズムとLIBSVMでどの程度の性能差がでるのか試してみた。 使用したデータ LIBSVMのページにあるUCIデータセットのa9aを用いた http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ 学習データ : a9a.txt テストデー…
はじめに PAアルゴリズムは回帰問題にも適用することができる、と書いてあったのでとりあえず試してみた。 パラメータの設定などがわかっていないので、要調査。 使用したデータ LIBSVMのページにあるUCIデータセットのeunite2001を用いた http://www.csie.n…
はじめに 以前、g++で日本語処理をするという記事を書いたけど、できるだけ環境に依存せずにUTF8で書かれた文章を処理したい。 調べてみると、UTF8は文字の最初のbyteを見れば何バイトの文字なのかがわかるので、簡単なラッパーを作った。 UTF8の仕様 http:/…
XORshiftとは XORshiftは、random number generator(乱数生成器, RNG)の一つ。周期が十分長く、演算も簡単なので生成速度も速いのが特徴。 コード wikipediaや論文に載っているのは、周期が2^128-1のもの。 C/C++では、「^」はビットXOR、「>>」はビットシフ…
はじめに SGDによるパーセプトロンの学習がどんな感じに収束していくかを見たかったので確認用にflashで作ってみた。 いじっている限りではちゃんと収束してくれた。 プロット結果 ぱーせぷとろんのがくしゅう - wonderfl build flash online
TF-IDFについて いくつかの文書が与えられたとき、文書中の単語の重みを決める手法の一つ。 TF(Term Frequency, 文書中の単語出現頻度) 「よくでてくる単語はその文書の主題を表しやすい」 ある文書dに単語tがでてきた個数をtf(t,d)と定める tfの定義として…
はじめに 配列が与えられたとき、それをバラバラに並び替えたい。 C++のSTLのrandom_shuffle関数を実現したい。 Fisher-Yates shuffle http://en.wikipedia.org/wiki/Fisher-Yates_shuffle一番使われていると思われるシャッフルアルゴリズム。 n個の配列のう…
