Inside-Outsideアルゴリズムを試す - Negative/Positive Thinking
はじめに 確率文脈自由文法での生成規則の適用確率の推定アルゴリズムで紹介されている「Inside-Outsideアルゴリズム」について、Webで検索してみても、最尤導出の構文木や内側確率の計算例などはあっても、外側確率や生成確率の推定などまで計算例を書いてくれているのはなさそうだったので、手計算確認用にプログラムを書いた。 Inside-Outsideアルゴリズムとは 内側・外側アルゴリズム 確率文脈自由文法の生成規則(チョムスキー標準形)の確率値をコーパスを求める際に、内側確率βと外側確率αを導入することで効率よく求められる 隠れマルコフモデルにおける前向き・後ろ向きアルゴリズムに似た感じ 内側確率 : 非終端記号Aから終端記号列w_i^jが生成される確率 外側確率 : 導出中に出現するAについて、Aが支配しているw_i^j以外の両側の終端記号列w_1^{i-1}とw_{j+1}^Nが現
Minimal Acyclic Subsequential Transducerで遊ぶ - Negative/Positive Thinking
はじめに https://pycon.jp/2015/ja/proposals/vote/11/ Pycon2015で発表された「Pythonで作って学ぶ形態素解析」で紹介されていた辞書データ構造の「Minimal Acyclic Subsequential Transducer」について、勉強のために書いてみた。 Minimal Acyclic Subsequential Transducerとは Finite State Transducerの一種 Transducerにおいて、initial stateが一つで、同じ入力ラベルを共有する同じ状態からのの遷移が2つ以上なく、各最終状態での最終出力文字列が高々p個のとき、p-subsequentialで、pが整数ならfinitely subsequentialというらしい minimal(状態数が最少)、Acyclic(サイクルが無い)
AdaDeltaを試す - Negative/Positive Thinking
はじめに 勉強会で、学習率を改善(自動調整)する事で学習時間を短縮し、ファンタジスタドールを見る時間を多く確保できる事が示されていた。 AdaGrad等をさらに改良したらしいAdaDeltaがあるようなので、ロジスティック回帰に適用してみた。 AdaDeltaとは M. D. Zeiler, ADADELTA: AN ADAPTIVE LEARNING RATE METHOD http://www.matthewzeiler.com/pubs/googleTR2012/googleTR2012.pdf 学習率を自動調整する方法の一つ 他の関連手法の問題点等を改良 過去すべての勾配を考慮→直近の勾配だけを考慮したいので、指数関数的に減衰するように考慮 グローバルな学習率を指定→second order methodsの特性を持つように、パラメータの変化について直近のパラメータの変化から計算し
DSIRNLP#6で発表させていただきました＆懺悔とNaiveBayes教入信 - Negative/Positive Thinking
DSIRNLP#6 10/11にデンソーアイティーラボラトリさんで行われたDSIRNLP#6勉強会で発表させていただきました 聴いていただいた方、ありがとうございました。 勉強会のページ http://partake.in/events/38e416b0-5e64-4bd4-8388-4e19acd0ef97 発表資料 一部、発表時の資料を修正しています 主だって参考にした論文は以下になります Zheng&Webb, Semi-naive Bayesian Classification, 2008 http://www.csse.monash.edu.au/~webb/Files/ZhengWebb08a.pdf No Bayes No Life -Naive Bayesは今でも進化しているようです。- from phyllo 補足(2014/10/12追記修正しました) 質問への回答で、
単語の数学的表現メモ - Negative/Positive Thinking
はじめに 単語をベクトルや確率分布などの数学的表現で扱いたい場合があったりする。 しかし、「どのようなベクトル・確率分布にすべきか？」などはタスクに依存したりして、自明じゃない。 たくさんあって、派生や新しいものもどんどんでていると思うので、どんなものがあるか調べたかぎりメモ。 One hot表現 各次元が「その単語か否か」を表すベクトルで表現 次元の大きさ＝ボキャブラリ数 例: スカイツリー = (「船」か否か, 「スカイツリー」か否か, ... ) = (0,1,0,...) 素性のどれか1つしか1にならなくてスパースネスの問題がでる 未知語はゼロベクトルになってしまう 文字nグラムによる表現 単語の表層から得られる情報を利用 単語に出現している文字nグラムを利用 カタカナ語とか有効そう 例: スカイツリー = (「スカ」の出現回数, 「カイ」の出現回数, 「イツ」の出現回数, 「アア
ナップサック問題として複数文書要約を解くを試す - Negative/Positive Thinking
はじめに 複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。 手法 西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」 https://www.jstage.jst.go.jp/article/jnlp/20/4/20_585/_pdf 上記の論文中で紹介されている「動的計画ナップサックアルゴリズム」を参考に。 (論文で提案されている手法ではないことに注意) コード #include <iostream> #include <vector> #include <map> #include <sstream> class KPSummary { // T[i][k] := 文iまでで最大要約長がkのときの最適解値 // U[i][k] := 経路復元用(文iを利用したかどうか) std::vector< std::vector<int
Counting Bloom Filterを試す - Negative/Positive Thinking
はじめに 悩み多き年頃なので、進捗ダメです。 KVS見てるときに出てきた、次元圧縮っぽさがあるBloom Filterを試してみる。 Bloom Filterとは 「ある要素が集合に含まれるか否か？」を扱えるデータ構造 要素をそのまま保存せず、ハッシュ値にしたものを配列に保存する アルゴリズム サイズがMの配列A[]を用意し、すべて値を0にしておく 要素の追加 K個の独立なランダムハッシュ関数(0〜M-1を返す)を使い、要素をK個のハッシュ値にする 配列Aでハッシュ値のindexのところを1にする(値がなんであっても) 要素の検索 追加時と同様にハッシュ値にし、すべて1になっていれば、要素が含まれると判断する 他の組み合わせでも1となってしまう組み合わせがあるために、「間違って要素がある、と判断してしまう可能性」がある＝偽陽性 MやKを調整する事で、記憶容量と偽陽性のトレードオフを実現でき
Matrix Factorizationで遊ぶ - Negative/Positive Thinking
はじめに 次元削減せずにはいられない。 0の扱いがいまいちピンとこなかったので、ちょっと調べて試してみた。 Matrix Factorizationとは Netflix Prizeという推薦システム・協調フィルタリングのコンテストで良い結果を残した手法 行列Mを、2つの行列P,Qの掛け算で近似するもの 行列Mが与えられたとき、行列Pと行列Qをそれぞれ見つける ユーザー数m、アイテム数nとして、Mはm*n行列。Pはm*k行列。Qはn*k行列。 行列Mには欠損データが含まれている 行列PとQを求めるために次式を最小化する min Σ_{(u,i)∈κ} (M[u][i] - Q_vec[i]*P_vec[u])^2 + λ(|Q_vec[i]|^2 + |P_vec[u]|^2) κは、既知のM[u][i]が存在する(u,i)のペアの集合 SGDで解を探す場合は以下の反復式になる e_ui :
やる夫が(インライン)アセンブラを使って競技プログラミングに挑戦するようです - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2013の9日目の記事です。 今年も、競技プログラミングでほとんど役に立たないネタをお送りします。 1：名無しのターゲットさん：2013/12/9(月) 00:25:07 id:jetbead ! | !l |! ! | ! | ! l | ! l |! | !ll |! l |!| !l | ! ! | !l |! ! | ! !ll |! l !| l !ll |! l !| | ! l il i (ヽ＝＝＝＝＝＝＝＝ | |! ! | ! | ! l | l | !| ! l | ! l ノ￣ﾉ￣ﾉ￣ﾉ￣ﾉ￣ﾉ ある日の競技プログラミング終了直前のやる夫家 |! l |! ノ
文書分類メモ - Negative/Positive Thinking
はじめに 文書分類マスターを目指して修行の旅に出るために必要そうな知識を、ざっとメモしておく。(かなり雑だけど・・・) 文書分類とは テキスト分類、Text Classification あらかじめ決められたカテゴリ集合に基づき、与えられた文書に適切なカテゴリを付与する事 排他的分類 : 1つのテキストにカテゴリを1つだけ付与される場合 マルチラベル分類 : 1つのテキストに複数のカテゴリ付与を許す場合 基本的には、目的の分類をどのような分類手法に落とし込むか？を考えることになる 主なアプローチとして、以下のような流れで処理する(教師あり分類) 学習データから素性(なんらかの特徴)を抽出し、それらの規則を見つけだす 規則に基づく分類モデルを作成 未知の文書に対して素性を抽出したものにモデルを適用し、分類結果を返す 利用例 内容に関する分類 ニュースジャンル分類 SPAMフィルタ 属性に関す
疎行列の格納方式メモ - Negative/Positive Thinking
はじめに 巨大だけどほとんどの要素がゼロであるような疎行列は、そのまま保持するより、要素がゼロじゃないところだけをうまく保持する事でメモリや計算量を減らせたりする。 扱う行列のタイプによって、効率のよい形式がいくつかあるようなので代表的なものをメモしておく。 Coodinate(COO) Format 非ゼロ要素の(row indices, column indices, value)を要素数分持たせる形式 非ゼロ要素が散らばっている場合に有利 0 4 0 0 2 0 0 0 1 を row 0 1 2 column 1 1 2 value 4 2 1 のように保持する。 compressed sparse row(CSR) Format / compressed sparse column(CSC) Format Coodinate Formatにおいて、左から右、上から下へ順番に要素を
トピックモデルメモ - Negative/Positive Thinking
はじめに トピックモデルについてメモ。 トピックモデルとは 文書は、何らかの話題について書かれていたりする 「ある文書内に一緒にでてくる単語は、意味的な関連性が強い」など考えられる トピックモデルは、文書から「何らかの話題(＝トピック)」を発見するための統計的なモデルのこと トピックモデルのいろいろ Unigram Mixtures ナイーブベイズでクラス数kと各パラメータをEMで繰り返し推定していく http://www.kamalnigam.com/papers/emcat-mlj99.pdf Probabilistic Latent Semantic Indexing(PLSI) 検索技術であった潜在意味解析(LSI,1990年)を確率的に解析、開発された生成モデル(1999年) 各単語ごとに別なトピックから生成されたと仮定する http://cs.brown.edu/~th/pap
SCWを試す - Negative/Positive Thinking
はじめに 分類器の決定版(？)的なSoft Confidence Weighted Learningを試してみた。 Soft Confidence Weighted Learningとは 2012年に提案された、各重みを正規分布と考え更新時にその分布が変わるようにしたConfidence Weighted(CW)関係のノイズに強くなった版 オンライン学習 http://icml.cc/2012/papers/86.pdf 詳しい解説記事 http://d.hatena.ne.jp/kisa12012/20120625/1340616659 使用したデータ LIBSVMのページにあるUCIデータセットのa9aを用いた http://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/ 学習データ : a9a テストデータ : a9a.t コード 毎
Locality Sensitive Hashによる類似ベクトル検索を試す - Negative/Positive Thinking
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関数のこと 高次元データの次元圧縮を行える (P1,P2,r,cr)-sensitiveなHash族とは、 2つの特徴ベクトルp,qについて(P1>P2) ||p-q||P1 ||p-q||>crならPr[h(p)=h(q)] を満たすハッシュ関数h:R^d->U コサイン類似度に対するLSH 2つのk次元ベクトルu,vについて コサイン類似度: u*v / sqrt(|u|*|v|) d個のk次元のランダムベクトルr_iを考え、ハッシュ関数h_i(u)を h_i(u) = 1 (r*u >=0) h_i(u)
文字列カーネルで遊ぶ - Negative/Positive Thinking
はじめに ちょっと、高次元特徴空間での2つの文字列の像の内積である文字列カーネルで遊んでみる。 文字列カーネルを類似度として使いたい。遊びなので、数式はちゃんと追ってない、、、 文字列カーネル 文字列に対するカーネル カーネルKは、入力空間Xから特徴空間Fへの写像φについて、x,y∈Xに対してK(x,y)=<φ(x),φ(y)>を満たす関数のこと 2つの文字列の距離的なものを考えるのに、共通する部分列や部分文字列を考えたもの いろんな考え方ができるので、いろんなものが存在する 部分列と部分文字列の違い 部分列(Subsequence) 記号列に対して、「並び」だけを保持した部分的な記号列 「abcde」に対して、「abd」や「be」や「bcde」など 長さがkの部分列は「k-merの部分列」という 部分文字列(Substring) 記号列に対して、「隣接性」と「並び」を保持した部分的な記号
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
RBMで遊ぶ - Negative/Positive Thinking
はじめに 深イイ学習とかで使われているらしいRestricted Boltzmann Machineでちょっと遊んでみる。 Restricted Boltzmann Machineとは 制約Boltzmann Machine 各層内のノード間の結合がないようなBoltzmann Machine この制約によって、学習時の隠れ層の各ノードが独立に計算できる RBMの学習は、「Contrastive Divergence Learning」で行うことができる http://www.cs.toronto.edu/~hinton/absps/cdmiguel.pdf http://dl.dropbox.com/u/2048288/RestrictedBoltzmannMachine.pdf コード できたモデルからどうやって生成するのかよくわからなかったので、適当にサンプリングしてみる。 #inc
大規模テキストにおけるN-gram統計 - Negative/Positive Thinking
はじめに 大規模なテキストデータでのN-gram統計を取る場合、特にNが大きい場合(N>=3)は、組み合わせの数が多くなり出てくるN-gramをすべてメモリに保持しながら個数をカウントするのが難しい。効率的な方法があるのを知ったのでちょっと試してみた。 大規模テキストにおけるN-gram統計の取り方 岩波講座ソフトウェア科学15「自然言語処理」 論文: http://ci.nii.ac.jp/naid/110002934647 手順 ngramを取りたい文章を1つの文として扱う この文をメモリに読み込み、各文字の先頭アドレスを保持する配列を作成 その先頭アドレスの場所の文字から文最後までの部分文字列を1つの単語とみる この単語を辞書順に並び替える(アドレス配列だけ) ソートした単語の順番で、次の単語と「先頭から共通している文字数」を保持する配列を作成 Ngramをカウントするときは、単語の
コーパス・言語データ - Negative/Positive Thinking
はじめに 言語処理するのに基となるデータ(言語データ、コーパス)についてまとめてみる。 データ・テキストマイニングなどに。必要に応じてダウンロードして試してみたい。 コーパス(corpus)とは 自然言語処理の研究に用いるために、自然言語の文章(用例)を構造化し大規模に集積したもの(電子データ) 辞書は、言語データだけど用例ではないのでコーパスではない よいコーパスとは、より対象をよくとらえているもの 特定の著者の小説を集めたもの(その著者の言語情報をよくとらえている) 新聞記事(新聞に使われている言語情報をよくとらえている) 例えば「日本語」のコーパスというのは、「日本語」を的確にとらえてなくてはいけない 新聞記事だけでは「日本語」の一部しかとらえられていない(ブログなどはとらえられていない) コーパスの種類 生コーパス：収集したままでなんの情報も付加されていないコーパス タグ付きコーパ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
