この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／…

はじめに 深イイ学習とかで使われているらしいRestricted Boltzmann Machineでちょっと遊んでみる。 Restricted Boltzmann Machineとは 制約Boltzmann Machine 各層内のノード間の結合がないようなBoltzmann Machine この制約によって、学習時の隠れ層の各ノ…

はじめに 最近再び注目を浴びているニューラルネットで遊んでみた。 簡単な3層の完全結合の階層型ニューラルネット(多層パーセプトロン)。 XOR 2入力1出力で、xorの出力は線形分離可能ではない (0,0)->0, (1,1)->0, (0,1)->1, (1,0)->1 単純パーセプトロンで…

はじめに Rabin-Karp法による複数文字列検索に続いて、同様に複数の文字列検索を行えるAC法を試しに書いてみた。 AhoCorasick法 えいほこらしっくほう 文字列探索するときに、パターンマッチオートマトン(PMA)を使い、状態を遷移させながらO(n)でパターンマ…

はじめに 「構文解析」まわりについてちょっと調べたのでメモ。 ただ、資料が少なくて内容が怪しい部分が多い。 構文解析とは 入力された文に対して、文を構成しているそれらの構文構造を同定すること 文法規則が定められたプログラミング言語、正規表現、HT…

はじめに 正規表現とそのエンジンについてちょっとメモ。 正規表現とは 文字列の集合を文字列で表現する方法の一つ 正規言語を表現するための手段 「正規言語」とは、「有限オートマトンで受理可能」な言語 正規表現と有限オートマトンは記述能力において等…

はじめに 形態素解析するとき、最初に用意された辞書だけでは固有名詞などが少なく、うまくいかないことがある。 しかし、名詞は無数に存在し、どんどん新しい言葉がでてくるので、、形態素解析器の辞書に入れておくのが難しい。そこで、ネットにあるデータ…

はじめに オライリーの「入門自然言語処理」に、焼きなまし法を使った教師なし単語分割について書かれていたので、これを試す。 アプローチ 「出現単語数」＋「のべ出現単語数」＋「入力文の文字数(固定)」＝目的関数を最小化 単語の区切り位置を温度によっ…

はじめに 最近どういうのが流行ってるとかよく知らないので、論文とか読んでいきたい。。。 読書会やtwitter、ブログで紹介されていたりするので、そういうのを参考にしたいです。 以下、参考ページを参考に有名なトップ国際学会についてメモ。 自然言語処理…

はじめに 立派な庭師になるために、木についてちょっと調べてみたので、まとめておく。 木(構造)とは 閉路を含まない無向グラフを「森」という 連結な森を「木」という 与えられた頂点が全てつながっていて、閉路を含んでいない 閉路を含まない有向グラフは…

はじめに 焼きなまし法について、どんな挙動で、どこを気をつけないといけないのかよくわかってないので、遊んでみる。焼きなまし法メモ : http://d.hatena.ne.jp/jetbead/20111014/1318598381 評価関数 簡単のために、4次関数を使って、初期位置は小さい山…

はじめに 単語の分類法としてよく利用されている「品詞」についてちょっとメモ。 【以下、「基礎日本語文法-改訂版-」(益岡・田窪共著)がベースの文、語、品詞について】 1.文 1-1.文とは 言語表現の基本的な単位 文章や会話は、複数の文の組み合わせにより…

はじめに 連立一次方程式(Ax=b)を直接法(ガウスジョルダン法)、反復法(最急降下法、共役勾配法)でちょっと解いてみた。 コード #include <algorithm> #include <cmath> #include <iostream> #include <vector> static const double EPS = 1e-8; typedef std::vector<double> vec; //ベクトル typedef std:</double></vector></iostream></cmath></algorithm>…

はじめに 前から気になっていたRabin-Karp法による複数文字列検索を試しに書いてみた。ここでいう問題は、「ある長い文字列の中に、複数の探したい部分文字列が含まれるかどうか、含まれる場合そのindexは？」を考える。 Rabin-Karp法 文字列探索するときに…

はじめに 決定木についてちょっと調べてみたので、メモ。 決定木(decision tree)とは 木構造(多分木)を使って、分類・回帰問題を解く root(根)を含む各内部ノードは、「変数」を表す leaf(葉)は、変数に対する「予測値、分類値」を表す 入力xを、ルートから…

この度、基礎から応用まで広くカバーした「言語モデル」という本を書かせていただきました。(嘘でした！) 6月にオライリーさんから出版させていただく予定です。(オライリーさんに迷惑！) 言語モデルーー言語モデルの基礎と応用 (オライリーさん、あの動物の…

はじめに 世の中には言語モデルを構築するToolkitはたくさんあるということで、簡単に探してみた。 言語モデルツールキット SRILM - The SRI Language Modeling Toolkit http://www.speech.sri.com/projects/srilm/ Palmkit - a statistical language modeli…

はじめに 最近「言語モデル」がマイブームなので、最近有名になりつつあるというMCMC法を使ったベイズな言語モデルとして、「階層的Pitman-Yor言語モデル(HPYLM)」を試しにちょっと作ってみた。とりあえず、文字bigramのHPYLMを試してみる。 毎度のことなが…

はじめに ノンパラメトリックに関する論文やチュートリアルを見ていると「混合正規分布の混合数も推定できちゃうんですよぱねぇ」みたいなこと書いてあったり、その図が載ってたりする。 試してみたいなぁと思ったので、書いて実験してみる。理解が乏しいの…

はじめに MCMCによるベイズ推定として、正規分布に従うデータが与えられたとき、その正規分布のパラメータ(平均と分散)が従う分布および推定値を求める。尤度関数が正規分布の場合、共役事前分布はそれぞれ、平均は正規分布、分散は逆ガンマ分布になるので、…

はじめに 気分転換に、よく使うgnuplotのplotファイル出力クラスを作ってみる。 状況に応じて修正して使おう。。。 コード #include <iostream> #include <fstream> #include <vector> #include <string> #include <utility> class SimpleGnuplotOutput { std::string png_filename; int png_width, png_h</utility></string></vector></fstream></iostream>…

はじめに 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>…

ちらっと見ておきたいやつメモ。 まとめ Introduction to the Dirichlet Distribution and Related Processes http://www.ee.washington.edu/research/guptalab/publications/UWEETR-2010-0006.pdf ディリクレ過程事前分布 Ferguson, T.S., A bayesian analy…

はじめに ちょっと遊びで多腕バンディット問題で遊んでみた。UCB1-tunedも書いてみたけどUCB1より最終的な儲けが低くてあれ？ってなった。どっか間違ってるか。。。 追記(2012/2/12)：コメントをいただいて、修正しました。一応、報酬額がUCB1よりtunedの方…

はじめに ギブスサンプリングで2次元正規分布からサンプリングを試してみる。 サンプリングの流れ 2次元正規分布なので(x,y)がサンプリングされる。 初期値(x0,y0)を決める y0を固定した場合の条件付き正規分布からx1をサンプリングする→(x1,y0) 次に、x1を…

はじめに ある分布に従った乱数を生成したいことがよくあったりする(一様分布に従う一様乱数や正規分布に従う正規乱数など)。 ベイズ統計学なんかだと、自然共役事前分布が使えないような複雑な分布の場合にMCMCで分布のサンプリングをして計算したりするの…

はじめに Suffix Arrayあたりをちょっと調べてみたのでとりあえずメモ。 調べてみたら結構研究されていて全部まとめるのが面倒あとできちんと理解しておきたい。 Suffix Array(接尾辞配列)とは 文字列に対して、その文字列の接尾辞集合を辞書順ソートしたも…

やろうと思ったことはやる 調べたりやったりしたことはメモを残す ベイズ周りをちゃんと勉強する 今年もよろしくお願いします：）