Machine learning is the new algorithms
my biased thoughts on the fields of natural language processing (NLP), computational linguistics (CL) and related topics (machine learning, math, funding, etc.) When I was an undergrad, probably my favorite CS class I took was algorithms. I liked it (a) because my background was math so it was the closest match to what I knew and (b) because even though it was "theory," a lot of the stuff we learn
ナップサック問題として複数文書要約を解くを試す - 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
文法圧縮入門：超高速テキスト処理のためのデータ圧縮（NLP2014チュートリアル）
言語処理学会第２０回年次大会（2014/3）のチュートリアル講義資料です。 - 要旨 - 文法圧縮とは，入力テキストをよりコンパクトな文脈自由文法（CFG）に変換する圧縮法の総称である． 文法圧縮の強みは圧縮テキストを展開すること無く，検索等のテキスト処理を効率よく行える点にある． 驚くべきことにその処理速度は，元テキスト上での同じ処理を理論的に，時には実際にも凌駕する． また近年，ウェブアーカイブやログ，ゲノム配列等の大規模実データを高効率に圧縮できることで注目を集めている． しかしながら，文法圧縮についての初学者向けの解説資料はまだまだ少ない． そこで本チュートリアルでは，文法圧縮の歴史的背景から最新動向までを幅広く紹介する． 具体的には文法変換アルゴリズム，圧縮テキスト上での文字列パターン検索，文法圧縮に基づく省メモリデータ構造等の解説を行う．
Latent semantic analysis - Wikipedia
Latent semantic analysis (LSA) is a technique in natural language processing, in particular distributional semantics, of analyzing relationships between a set of documents and the terms they contain by producing a set of concepts related to the documents and terms. LSA assumes that words that are close in meaning will occur in similar pieces of text (the distributional hypothesis). A matrix contai
perlで高速な類似検索エンジンを構築できるようにしてみた - download_takeshi’s diary
すみません。タイトルはやや釣り気味です。 類似検索エンジンというか、そのアイデア程度の話なんですが、以前から考えていた類似検索エンジン風のネタがあったので、ちょっとperlで書いてみたので、そいつを晒してみます。 Luigi https://github.com/miki/Luigi 類似検索なのでLuigi。ルイージとか読みたい人はそう読んじゃっても良いです。（冷） 考え方と仕組み 類似文書の検索、となりますと一般的には超高次元での空間インデックスとかが必要になります。 昔からR-TreeやSR-Treeなど、いろいろと提案されていますが、より高次元になると「次元の呪い」によりパフォーマンスが出なくなる、なんて言われていますね。 そこで最近ではLSHに代表されるような、より高度な「近似」型のインデキシング手法が人気を集めているようです。 で、今回考えたLuigiも実は近似型のインデッ
Não Aqui! » SimString (類似文字列検索ライブラリ) 1.0 released
SimStringという類似文字列検索ライブラリをBSDライセンスでリリースしました．類似文字列検索とは，文字列集合（データベース）の中から，クエリ文字列と似ているものを見つけ出す処理です．コンピュータは，正確に一致する文字列を探すのは得意ですが，表記揺れに出くわすと，途端に対応できなくなります．例えば，「スパゲティ」に対して，レストラン情報などを返すサービスにおいて，「スパゲッティ」や「スパゲティー」などの表記揺れが検索クエリに与えられると，通常のデータベースでは情報を提示することが出来ません．類似文字列検索を用いると，表記揺れが検索クエリに与えられても，「スパゲティ」という既知語を代替クエリとして提案したり，「スパゲティ」の情報をダイレクトに引き出すことができるようになります． 似てる語を探す技術って，文字列処理の基本中の基本で，自然言語処理では当たり前のように使われていてもおかしくな
Dynamic Programming による類似文字列マッチの実装例
Dynamic Programming による類似文字列マッチの実装例 2007-01-22-4 [Programming][Algorithm] 「Modern Information Retrieval」(8.6.1 p.216) での Dynamic Programming (DP) の解説のところのアルゴリズムを 素直に Perl で実装したみた。 さらにマッチ箇所取り出しロジックも実装してみた。 # DP はいわゆる「類似文字列検索（あいまい検索）」に使うと 便利なalgorithm。 実は、大学院でも前の会社でも、PerlやらC++やらで実装して使ってた。 単純ながら使い勝手もよく、まさに現場向きかと。 grep 式に頭から見ていくので計算量的にはイマイチなのだが、 転置インデックス検索などで範囲を絞ってから適用すれば実用上問題ない。 ■定義みたいなの Q1. 二つの文字列 "
情報系修士にもわかるLOUDS - アスペ日記
一回でわかりやすく書くのは難しいので、簡潔データ構造 LOUDS の解説（全12回、練習問題付き）というシリーズにまとめました。 (2014/01/26) 古い内容を削除しました。
情報系修士にもわかるダブル配列 - アスペ日記
最近話題の「日本語入力を支える技術」を途中まで読んだ。 3章がものすごく気合いが入っている。 trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。 ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。 ありがたい。 感銘を受けたので、この本を教材に友達と2人勉強会をした。 この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。 しかし、いざやってみるといろいろと難しい。 次のようなところでひっかかるようだ。 例のサイズが小さく、イメージを喚起するのが難しい。 最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。 単語終端について言及がないので、どのノードが単語を表しているかがわから
大規模テキストにおける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をカウントするときは、単語の
Luceneの曖昧検索を100倍高速化したアルゴリズム - nokunoの日記
@nobu_k さんのつぶやきでこのエントリを知りました。Changing Bits: Lucene’s FuzzyQuery is 100 times faster in 4.0Luceneで曖昧検索を効率化した話です。 最初の実装では、転置インデックスを全探索して編集距離がN以下の単語を拾っていたレーベンシュタインオートマトンという、編集距離がN以下の単語のみをアクセプトするオートマトンを利用することにした 単語ごとに構築したレーベンシュタインオートマトンをマージするという操作が必要になるが、なかなかうまくいかなかった 難解な論文を見つけたが、実装は難しかった良いライブラリを見つけたので、PythonからJavaに移植した 最後に1つだけ残ったバグは、移植の失敗ではなく元ライブラリのバグだった。報告すると1日で直ってきた。この前のエントリでは、有限状態トランスデューサを使った辞書の圧縮
TinySegmenter: Javascriptだけで実装されたコンパクトな分かち書きソフトウェア
TinySegmenterはJavascriptだけ書かれた極めてコンパクトな日本語分かち書きソフトウェアです。 わずか25kバイトのソースコードで、日本語の新聞記事であれば文字単位で95%程度の精度で分かち書きが行えます。 Yahoo!の形態素解析のように サーバーサイドで解析するのではなく、全てクライアントサイドで解析を行うため、セキュリティの 観点から見ても安全です。分かち書きの単位はMeCab + ipadicと互換性があります。 デモ 日本語の文章を入力し、解析ボタンをクリックしてください。 ダウンロード TinySegmenterはフリーソフトウェアです. 修正BSDライセンスに従って本ソフトウェアを使用,再配布することができます. Download TinySegmenter version 0.2 使い方 <script type="text/javascript" src
最大マージン kNN と SVM の関係: kNN も最近はがんばっています - 武蔵野日記
先日書いた機械学習における距離学習の続き。 kNN (k-nearest neighbour: k 近傍法)は Wikipedia のエントリにも書いてある通り、教師あり学習の一つで、あるインスタンスのラベルを周辺 k 個のラベルから推定する手法。memory-based learning と呼ばれることもある。単純に多数決を取る場合もあれば(同点を解決する必要があるが)、近いインスタンスの重みを大きくする場合もあるのだが、いずれにせよかなり実装は単純なので、他の機械学習との比較(ベースライン)として使われることも多い。 簡単なアルゴリズムではあるが、1-NN の場合このアルゴリズムの誤り率はベイズ誤り率(達成可能な最小誤り率)の2倍以下となることが示されたり、理論的にもそれなりにクリアになってきているのではないかと思う。また、多クラス分類がちょっと一手間な SVM (pairwise に
livedoor Developers Blog:String::Trigram でテキストの類似度を測る - livedoor Blog（ブログ）
こんにちは。検索グループ解析チームの nabokov7 です。 今回は、livedoor キーワードでの事例より、テキストの類似度を測るのに便利な手法を紹介します。 livedoor キーワードは、livedoor ブログでその日その日で話題になった語をランキング表示するサービスです。 当初、はてなキーワードやWikipediaを足して2で割ったようなサービスを作れといった開き直った指示のもとで開発が開始されたともいう、分社化前の芸風の名残で、キーワードの検索結果にはユーザが自由に解説を書き込める Wikipedia 的スペースもついています。 で、この解説部分に、さまざまなサイトから文章をまる写ししちゃう人がとても多いのですね。 特に多いウィキペディア日本語版からの剽窃を防止するために、livedoor キーワードでは以下のような対策を講じることにしました。 ウィキペディア日本語版の解説
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Perlで入門テキストマイニング » SlideShare (share powerpoint...
