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が現
ナップサック問題として複数文書要約を解くを試す - 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
正規表現エンジンメモ - Negative/Positive Thinking
はじめに 正規表現とそのエンジンについてちょっとメモ。 正規表現とは 文字列の集合を文字列で表現する方法の一つ 正規言語を表現するための手段 「正規言語」とは、「有限オートマトンで受理可能」な言語 正規表現と有限オートマトンは記述能力において等価 任意の正規表現は、有限オートマトンに相互に変換可能 有限オートマトン 以下の5つの組(Q,Σ,δ,q0,F)のことをいう 有限状態機械ともいう 有限個の状態Q 有限個の文字集合Σ 状態と文字集合の組から状態へ遷移する関数δ 状態Qの一つとして、開始状態q0 状態Qの一つとして、受理状態の集合F 入力に対して、開始状態から状態を遷移させ、状態に応じて出力(受理or拒否)を返す 状態遷移図とは、有限オートマトンを(抽象的に)記述した図 非決定性(Nondeterministic)と決定性(Deterministic) 「決定性有限オートマトン(DFA
ウェーブレット木を試す - Negative/Positive Thinking
はじめに 巨大な文字列でも高速にクエリ処理できる噂の木を、挙動を確認するため作ってみた。 コード アルファベット(a〜z)の文字列を扱う場合 完備辞書の操作が愚直、ビット列がvector 本を参考にしたけど、2か所間違ってる？ #include <iostream> #include <vector> #include <queue> #include <cmath> //top_kのためのタプル struct ST { int t; size_t st, en; ST(int t, size_t st, size_t en):t(t),st(st),en(en){} }; bool operator<(const ST& a, const ST& b){ return (a.en-a.st) < (b.en-b.st); } //アルファベット([a-z]+)用のウェーブレット木 cla
へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集 - Negative/Positive Thinking
この記事はCompetitive Programming Advent Calendar Div2012の2日目の記事です。 12月20日追記： Darseinさんが20日目の記事で、ビット演算についての詳しい説明を紹介してくださっています！必読ですね！！！！：） はじめに Y＾´ ∨／／ ／,∠ ,. ' ／l／／／ ／, ' , '／ ! ｜ ｌ }´ 〈 〉 変 〈/ , ' ／／￣｀>< ／／／ ／／／ _,.=‐|'"´l ｌ〈 変 / 〈 態. ∨, '／l| ,.'-‐､｀/／｀7/ ／''"´__ ｜ ﾊ l丿 態 { 人） ! ! （／! |ヽ〈_ ・.ﾉ〃 〃 ／ '／⌒ヾ.! ,' !く ! ! （_ ト､__／ ヽ､_,.イ ／ｌ ｌ ｜:::::::｀｀`/:::::／...´..
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
