自然言語処理

Elias-Fano Encodingで遊ぶ

はじめに 読んでる論文に出てきてたElias-Fano Encodingをちょっと書いて遊んでみた。 Elias-Fano Encodingとは 単調増加整数列の表現方法のひとつ 他の方法としては、ちょっと情報が古いけど http://d.hatena.ne.jp/jetbead/20110918/1316373030 など 厳密…

XBWを試す

はじめに XBWをWaveletMatrixを使って、試しに実装してみた。 XBWとは 効率よくTrie木を表現する方法 Burrows-Wheeler Transform(BWT)の(木への)拡張 詳しい解説や作り方は以下のページや「高速文字列解析の世界」などを参照 https://research.preferred.jp/…

Kneser-Ney smoothingで遊ぶ

はじめに 100-nlp-papersで紹介されてた一番最初の論文に、クナイザーネイスムージングのスッキリな実装が載っていたので書いてみる。Joshua Goodman: A bit of progress in language modeling, MSR Technical Report, 2001. Kneser-Ney smoothingとは 言語…

Inside-Outsideアルゴリズムを試す

はじめに 確率文脈自由文法での生成規則の適用確率の推定アルゴリズムで紹介されている「Inside-Outsideアルゴリズム」について、Webで検索してみても、最尤導出の構文木や内側確率の計算例などはあっても、外側確率や生成確率の推定などまで計算例を書いて…

検索エンジンの日本語トークナイズメモ

はじめに 検索エンジンのトークナイズ処理の部分で行われている基本処理や工夫を少し調べてみたのでメモ。 トークナイズ処理 「検索クエリ」に対してマッチする「ドキュメント」を高速に検索するためにインデクス(索引)を作成する 本の最後の方にある「用語 …

ラティスのNbestを求める

はじめに 形態素解析とかの解析時に使うラティス(形態素候補をグラフにしたもの)のうち、1番ベストな解だけが欲しい場合が多いが、2番目以降の解も欲しい場合がある。 N番目までの解を効率よく求める方法があり、使いたいケースが出てきたのに書いてみる。 N…

pandas使ってwikipediaの表データを取得する

はじめに 特定ジャンルの用語などをまとめて取得するのに、wikipediaの「〜の一覧」が有用だったりする。 wikipedia:一覧の一覧多くは、リスト形式で書かれていたりするが、中には表(テーブル)形式でまとめられているものもある。 いろんな取得方法が考えら…

Minimal Acyclic Subsequential Transducerで遊ぶ

はじめに https://pycon.jp/2015/ja/proposals/vote/11/ Pycon2015で発表された「Pythonで作って学ぶ形態素解析」で紹介されていた辞書データ構造の「Minimal Acyclic Subsequential Transducer」について、勉強のために書いてみた。 Minimal Acyclic Subseq…

係り受け解析メモ

はじめに 今年の目標にしていた係り受け解析関係の資料について雑多にメモしておく。リンク集。 拾いきれていない、最新の論文まで追えていないので、あとで追加・整理し直す。 Wikipedia http://en.wikipedia.org/wiki/Dependency_grammar 文節単位がよいか…

ネット上の文書をきれいにするライブラリ「NetTextCleaner」を公開しました

エイプリルフールネタです:) 見ればわかりますが、30分ぐらいで作ったものなので、言ってることもコードもデータも結構適当です:p はじめに インターネット上で扱われる文書(Twitterや2ch、ニコニコ動画など)には、特殊な用語や言い回しをしているものがあり…

Feature Hashingを試す

はじめに Feature Hashingについて気になったことがあったので試してみた。 Feature Hashingとは Hashing trick ハッシュ関数を使って、素性群をM次元ベクトルにする 一種の次元圧縮 Bag of wordsなどの素性をそのままハッシュ値にすることで、素性とIDのペ…

NBSVMを試す

はじめに S. Wang & C. D. Manning, Baselines and Bigrams: Simple, Good Sentiment and Topic Classificatioin Naive Bayes素性を利用したSVM(NBSVM)なるものを試してみる。 SVM with NB features(NBSVM) Log-count ratio r = log( (p / ||p||_1) / (q / |…

Graph of Word、TW-IDFとTFのnormalizationメモ

はじめに Rousseau et al., Graph-of-word and TW-IDF: New Approach to Ad Hoc IR http://www.lix.polytechnique.fr/~rousseau/papers/rousseau-cikm2013.pdf 文書dのグラフ的表現とそこから計算されるTW-IDFというTermの重み付けについて、メモ。 Graph of…

編集距離で遊ぶ

はじめに 簡単な例としてよく出てくる「編集距離」を使って、英単語の修正を試してみる。(編集距離が小さいものを列挙するまで) dpができなすぎるので、「dpやるだけ」って言えるようになりたい。 編集距離とは ある文字列sからある文字列tへ、文字の削除、…

単語の数学的表現メモ

はじめに 単語をベクトルや確率分布などの数学的表現で扱いたい場合があったりする。 しかし、「どのようなベクトル・確率分布にすべきか?」などはタスクに依存したりして、自明じゃない。 たくさんあって、派生や新しいものもどんどんでていると思うので、…

ナップサック問題として複数文書要約を解くを試す

はじめに 複数文書要約をナップサック問題として解く、という話を聴いて、簡単に試せそうなのでやってみる。 手法 西川ら「冗長性制約付きナップサック問題に基づく複数文書要約モデル」 https://www.jstage.jst.go.jp/article/jnlp/20/4/20_585/_pdf上記の…

EntityLinkingメモ

はじめに WSDM2014(WWW2013,YSS2013,SIGIR2013)のチュートリアルで「EntityLinking」といタスクが紹介されていたので、ちょっと調べてメモしておく。 次元圧縮! Entity Linkingとは テキストに出てくるエンティティ(実体)を識別・決定するタスク 固有名詞抽…

大野の語彙法則を試す

はじめに 読んでた本に出てきた法則が気になったので、試してみた。 大野の語彙法則 任意の3作品A,B,Cについて、品詞ごとの構成比を計算しておく 名詞の構成比をX_0, x, X_1とし、任意の品詞の構成比をY_0, y, Y_1とする 次の関係式が近似的に成り立つ (y-Y_…

格メモ

はじめに 少しずつ曖昧な理解の部分をなくしていきたい。 「格」についてちょっとメモ。 格(case) おおざっぱに言うと、文法的または意味的役割のこと 格の種類を見れば、役割を判断できるような感じ 別の定義では、語と語(名詞と述語)の間に成り立つ意味関…

助詞メモ

はじめに 日に日に日本語がわからなくなっていっているので、助詞についてメモしておく。 細かい部分は各文法・体系や、使うときの都合によると思うので、ここでは大雑把に。 助詞とは 品詞の一つ 単語の文法的な性質による分類が「品詞」 助詞は、述語につ…

文書分類メモ

はじめに 文書分類マスターを目指して修行の旅に出るために必要そうな知識を、ざっとメモしておく。(かなり雑だけど・・・) 文書分類とは テキスト分類、Text Classification あらかじめ決められたカテゴリ集合に基づき、与えられた文書に適切なカテゴリを付…

語義曖昧性解消メモ

はじめに 意味を捉えた解析を行うためには、曖昧性のある語の意味を明確にする必要がある。 語義曖昧性解消周りをちょっと調べたので、メモ。 語義曖昧性解消(Word Sense Disambiguation)とは 複数の意味を持つ語(例えば、plantは「植物」「工場」など)が存…

Random Projectionを試す

はじめに 言語処理を行う場合、単語数を考えると高次元スパースなベクトルを扱うことが多い。 次元削減を行える手法の一つである、Random Projectionを試してみる。 Random Projectionとは 乱数を要素に持ち、各列ベクトルの大きさが1である行列Rを用意して…

DSIRNLP#4で発表させていただきました&他の発表者の方の資料メモ

9/1にVOYAGE GROUPさんで行われたDSIRNLP#4勉強会で発表させていただきました 聴いていただいた方、ありがとうございました 勉強会のページ http://partake.in/events/76854228-ba38-4f6e-87b9-f79e30add75c 発表資料 http://www.slideshare.net/phyllo/weig…

TWCNB分類器を試す

はじめに テキスト分類でよく使われるNaive Bayesにはいくつかの厳しい仮定や条件があり、それによって性能が落ちてしまっている。 経験則をいれたりして性能を向上させたTWCNB分類器を試してみる。 多項モデルによるNaiveBayes l_MNB(d) = argmax_c{ log P(…

読みメモ

はじめに 音声合成とかに興味が出てきたい気がするので、日本語文の「読み」について簡単にメモ。でてこいやるき。 「読み」とは 日本語文は、ひらがな、カタカナ、漢字、アルファベット、数字、記号、、など様々な文字で構成される 特に「漢字」は、「音読…

KWICを試す

はじめに 形態素解析辞書の登録単語の単位や品詞/活用などを考える時は、対象コーパスでその単語がどのような文脈で用いられているか調べたいことが多い。 単純にgrepコマンドやエディタの検索とかで調べればよいけど、検索速度や見やすさの問題があったりす…

トピックモデルメモ

はじめに トピックモデルについてメモ。 トピックモデルとは 文書は、何らかの話題について書かれていたりする 「ある文書内に一緒にでてくる単語は、意味的な関連性が強い」など考えられる トピックモデルは、文書から「何らかの話題(=トピック)」を発見す…

Z algorithmで文字列探索を試す

はじめに 名前がかっこいい。 codeforcesにある解説を試してみる。 Z algorithmとは 文字列Sと部分文字列S[i..]の最長共通接頭辞数をZ[i]とし、すべてのiについて、それをO(n)で求めるアルゴリズム 単純な方法だとO(n^2) 1996,97年あたりにGusfieldによって…

Locality Sensitive Hashによる類似ベクトル検索を試す

はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関…