はじめに 形態素解析辞書の登録単語の単位や品詞/活用などを考える時は、対象コーパスでその単語がどのような文脈で用いられているか調べたいことが多い。 単純にgrepコマンドやエディタの検索とかで調べればよいけど、検索速度や見やすさの問題があったりす…
はじめに トピックモデルについてメモ。 トピックモデルとは 文書は、何らかの話題について書かれていたりする 「ある文書内に一緒にでてくる単語は、意味的な関連性が強い」など考えられる トピックモデルは、文書から「何らかの話題(＝トピック)」を発見す…
はじめに 分類器の決定版(？)的なSoft Confidence Weighted Learningを試してみた。 Soft Confidence Weighted Learningとは 2012年に提案された、各重みを正規分布と考え更新時にその分布が変わるようにしたConfidence Weighted(CW)関係のノイズに強くなっ…
はじめに 名前がかっこいい。 codeforcesにある解説を試してみる。 Z algorithmとは 文字列Sと部分文字列S[i..]の最長共通接頭辞数をZ[i]とし、すべてのiについて、それをO(n)で求めるアルゴリズム 単純な方法だとO(n^2) 1996,97年あたりにGusfieldによって…
はじめに 類似性が高いベクトルのハッシュ値が近い値になるようなハッシュ関数を使って、 類似するものを高速に検索することができるので、それを試してみた。 Locality Sensitive Hash 類似するデータが高確率で近い値になる(Locality-Sensitive)ハッシュ関…
はじめに 「日本」は、「にほん」と「にっぽん」どちらの読み方もできる。 しかし、読み分けが必要な場合も存在する。(東京の日本(にほん)橋と大阪の日本(にっぽん)橋、会社名、など)同型異音語や多義性解消だと、よく周辺文字を素性にして分類問題を解く、 …
はじめに 時系列解析について、簡単にメモ。 時系列(time series)とは 時間の経過で変動する何かの数値の列 例：気象データ、株価、など 時系列解析は、このデータを統計解析すること 時系列の分類 連続時間・離散時間 時間間隔が連続的か、離散的(1時間おき…
はじめに せっかく文字列カーネルで遊んでみたので、可視化も試してみる。 Multidimensional Scalingとは n個のm次元ベクトルについて、それらの距離のみが与えられる それらの距離をできる限り保存して低次元空間(1,2,3次元など)にマッピングする方法 通常…
はじめに ちょっと、高次元特徴空間での2つの文字列の像の内積である文字列カーネルで遊んでみる。 文字列カーネルを類似度として使いたい。遊びなので、数式はちゃんと追ってない、、、 文字列カーネル 文字列に対するカーネル カーネルKは、入力空間Xから…
はじめに 前から気になっててほっといてた自動要約についてメモ。 文短縮とか試してみたい。 テキスト要約 与えられたテキストをより短いテキストに簡潔にまとめること 要約率 = (要約後の文字数or文数) / (与えらえたテキストの文字数or文数) 要約の過程 以…
はじめに くさいセリフを恋人につぶやいてドン引きされてしまう問題を自然言語処理の力で解決するため、くさいセリフかどうかを判定するプログラムを試してみる。 , -──- 、 ／:::::::::::::: ::＼ /::::::::::: ::∨ﾄ､ こいつはくせえッー！ :::::::::: :: ﾚ…
はじめに 「さぁ、お前の罪の異なり数を数えろ！」と言われたときに使えそうな「HyperLogLog」という異なり数をカウントする方法を教えてもらったので、遊んでみた。 いつもながら論文ちゃんと読んでないので、条件やコード間違ってるかも。。。 HyperLogLog…
はじめに 巨大な文字列でも高速にクエリ処理できる噂の木を、挙動を確認するため作ってみた。 コード アルファベット(a〜z)の文字列を扱う場合 完備辞書の操作が愚直、ビット列がvector 本を参考にしたけど、2か所間違ってる？ #include <iostream> #include <vector> #include <queue></queue></vector></iostream>…
去年の反省 やろうと思ったことはやる あんまりできていなかった気がする 後でやろうとすると溜まってく、、、 調べたりやったりしたことはメモを残す 比較的残せてたけど、半分くらい書けてない、、、 ベイズ周りをちゃんと勉強する さわりだけだけど、何を…
この記事は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月にオライリーさんから出版させていただく予定です。(オライリーさんに迷惑！) 言語モデルーー言語モデルの基礎と応用 (オライリーさん、あの動物の…
