@johtaniの日記 3rd

ということで、Ruby2日目の感想（2日目だけで2日間かかったのは内緒。。。） 今回もセルフスタディの私の回答が最後の方に記載されてます。見たくない人は気をつけてください。 ツッコミ大募集です。コメント欄にどしどしコメントください。そこは違うだろ？こっちのほうがいいのでは？という感じで。

実に3年ぶりくらいにゆっくりできる日々が訪れたので、積読状態の本を消化しようと「7つの言語　7つの世界」を読み始めました。 せっかくブログも始めたので、備忘録も兼ねて感想などを書いていこうかと。

現在の出先でMBAを使えないので、なかなか進んでいないMBAのセットアップです。。。 とりあえず、Eclipse、homebrewをインストールしたので、lucene-gosenの開発やビルドには支障がない程度になってきました。（肝心のSolrがまだ動く状況になかった。。。）

すぐにテストケース追加しますといいつつ、はや一週間。 ようやく仕事が落ち着いたので、テストケースを追記しました。まだパッチの段階です。 一応、異なる辞書の読み込みのテストケースなどを追加し、テストケース追加時点で いくつか気になったところもあったので、ついでに修正を加えました。 一応、辞書の分離＋複数辞書対応については現時点ではこんなところかと。

先日、辞書のjarファイルからの分離についてパッチと記事を書きました。 IssueにあげていたパッチをRobertさんが見ていたらしく、次のようなコメントをもらいました。 Maybe if we change SenFactory.getInstance to use a ConcurrentHashMap then you can easily use multiple dictionaries at the same time? 「SenFactory.getInstanceメソッドでConcurrentHashMap使ったら複数辞書対応できるんじゃない？」（訳） たしかに。。。なんで思いつかなかったのだろう。。。

ひさびさに、lucene-gosenの話題です。 lucene-gosenはjarファイルに辞書も同梱されており、jarファイルをクラスパスに取り込むだけで、 簡単に形態素解析器が利用できるといお手軽さがあり、便利です。

すみません、また、MBA関連の記事になってしまいました。 ということで、備忘録その２です。 前回からいくつかインストールや環境の設定をしたので、リストアップ。

Mac Book Airのセットアップ関連の備忘録 （今回は備忘録なので、文体も変かも） インストールしたもの（順不同）だいたい、このサイトを参考にした。 Evernote Dropbox XCode Twitter YoruFukurou GNU Emacs For Mac OS X Java Office for mac 現状はこんなところ。

個人用のPCを８年ぶりに新調しました。 前回購入した家のデスクトップPCがもう８年ものになりつつあるということで、 さすがに今年はPCを買おうと思い、年初からいろいろと調べていました。 当初は次もデスクトップPCを購入する予定でした。ただ、次のような状況ということもあり デスクトップは見送ることにし、代わりにノートPCにすることに。

かなり遅くなりましたが、第1回 データ構造と情報検索と言語処理勉強会 #DSIRNLPに参加しました。 帰ってから２日半ほど寝込んでしまい、更新が遅れました。。。 初の土曜日開催の勉強会でしたが、家族を説得してなんとか参加しました。 おかげで色々と面白そうなキーワードが拾えてよかったです。（拾っただけで理解するのはかなり時間がかかりそうですが。。。） ということで、前回同様、個人的にメモを取ったので。誤記などあるかもしれませんが、その時はコメントいただければと。 0.DSIRNLPについて ※ボランティアで受付してたので聞けず。 1.TRIEにトライ！～今日からはじめるTRIE入門～ @echizen_tm さん 資料：http://www.scribd.com/doc/58688141/Try-for-Trie 1.TRIEの説明 実装についてはあとでスライドをみればいいか。（※ボランティアで受付してたので前半聞けず） ・パトリシア木 ・Double Array ・LOUDS ・XBW 2.作ってみた その1　ベーシック Q.ノードのラベルどーする？ ・固定長（ラベル＝1文字） 定数時間でアクセス可能 ・可変長（ラベル＝任意文字列） Patricia木に拡張可能 A.拡張性を考えて可変長に！ 3.LOUDSとは？ 概要 Jacobsonが提案　Level-Order Unary Degree Sequenceの略（いつからLOUDSになったのか不明） 構築済みTRIEからLOUDSを構築 作業領域がO(NlogN)からO(N)に ・ノードに幅優先で順番（Level-Order）をつける ・子ノードの数を付ける。Unary符号で実装 作ってみた ・UnaryよりVerticalCodeのほうがよさそう http://d.hatena.ne.jp/echizen_tm/20100531/1275323074 ・dag_vectorを使ってもいいかもよ？ 4.QA Q.可変長を配列にすればいいんじゃね？ A.単純にやると効率悪そう？ ※LOUDSをlucene-gosenに適用するとなんか嬉しいことあるかな？ 現状はDouble-Arrayだけど。 2. ランキング学習ことはじめ（Solr系に利用できそうな予感。。。ごごご。。。むずかしい。。。） @sleepy_yoshi さん NTTのSuharaさん「話がうまい」 数原　良彦 自己紹介 情報検索、ランキング学習をやってる。 三浦半島在住 ねらい ランキング学習の認知度を高める、ざっくり伝える。　ごめんなさい　「実装」についてをわすれてた。 ・ランキング学習とは？ Learning to rank preference learningとは違う 教師あり機械学習で検索ランキングに適用 ・歴史 従来は単一ランキング クエリ・文書関連度（TF-IDF、BM25） 文書の重要度（PageRank、HITS、SALSAなど） 近代的なランキングの実装方法 上記データを利用して関数を適用する。 ・何を正解とするのか？ 適合性評価の作成方法 評価点数を多段階で点数化 ランキング評価方法 ランキングを正解データと比較 NDCG（Normalized Discounted Cumulative Gain）　※分類問題におけるモデルの生成 Training Data＋学習アルゴリズム＝＞モデル ランキング学習の訓練データ 素性や評価はクエリごとに変わってくるTraining data（ここが違う） ここまでのまとめ 正解データは適合度至上主義！ ランキング学習手法 ３つのアプローチ 教師あり機械学習（識別学習）≒ どのような目的関数/損失関数を どのように最適化するのか アプローチ 1.Pointwise手法 単一のデータに対して損失関数を設定 2.Pairwise手法 同一クエリのペアに対して損失関数を設定 3.Listwise手法 同一クエリのリストに対して損失関数を設定 Pointwise：あまりつかえない。 例：二値分類（適合＋１不適合－１）で学習 補足：Perceptron 例：PRank しきい値と重み両方修正する。 Pairwise：Pointwiseよりいいらしい 文書ペアで損失を設定 MQ2007、MQ2008データセットの結果 Pairwise手法とListwise手法を比較しても そんなに悪くないらしい IR-SVMってので偏りなどを排除できて、精度向上になるよ NLP2011でPARankっての発表したよ（手前味噌） QA Q.じゃんけんみたいに循環しない？（nokuno） A.半順序のデータだと起きるが、検索の場合は全順序なので大丈夫だよ Listwise：Pairwiseよりいいらしい ListNetってのあり。 AdaRank 検索評価指標を直接最適化するブースティング手法 性能はいまいち？実装は簡単 その他の話題 Click-through logs Query-dependent ranking Feature selection Transfer learning/Domain adaptation Diversity/Novelty 公開Dataset LETOR3.0/4.0 Dataset MSLR-WEB Datasetなど 実装 RankingSVM Stoch…. Learning to Rank教科書 英語の資料が今年複数出たみたい まとめ 近代的な検索エンジンは多数のランキング素性を利用 評価データを用いてランキング素性の最適な重み付けを求める方法 。。。 機械学習手法は論文≒実装 なので、ソースコード見るほうが重要（論文にないノウハウがあるよ） 3.snappy調べてみた @machy　町永圭吾（赤いポータルサイト） TopCoderなどで活躍中？ ・snappyは圧縮/伸張ライブラリ zlibよりサイズが大きいけど一桁はやいですぞ。 ・インストールなど google－gflagsってのがないと動作しないよ。 ・比較してみた（zlib） 一桁は言い過ぎだけど、はやかった。 ・比較してみた（lzo） Hadoopで利用されているlzo はやかった。 ・仕組みは？ zlib　辞書式符号化＋ハフマン符号化＝出力 snappy　辞書式符号化＋リテラル＝出力 ・辞書式符号化は？ 前に出てきたデータで同じ文字列の部分について端折る ・ハフマン符号化 よく出てくる記号を短い符号で置き換えることで圧縮する。 ・snappyの符号化 基本バイト単位での処理にすることで、高速化してるみたい。 ・snappyの辞書参照元の探し方 ハッシュテーブル利用してマッチする位置を検索 4byte窓でハッシュ値を計算してハッシュテーブルを更新 ・圧縮しにくいデータ（同じ単語が出てこないパターン）について 圧縮をあきらめ始める（32回同じのが見つからないと窓の移動幅が1つずつ大きくなる） 16KB（フラグメント内）での比較回数が1008回に抑えられる。 ・特徴 ハッシュがしょうと移したらあるはずのマッチが見つからないこともある。 メモリ消費量を抑えるためのハッシュのサイズ？ 最悪ケースのサイズを予め確保してから処理するため、メモリの再確保が起きないのではやいぞ。 4.類似文字列検索してますか？ @overlast さん　Yな会社 1.曖昧な情報を処理する能力 曖昧な情報を解決しようとする能力が高い。 例：お笑い芸人の芸がサンプルｗ 画像検索は曖昧クエリに答える例。。。 スターバックス、スタバ、SUTABA スータバでも画像が出てきた。->女子高生とかが「スータバ」で画像をアップしてたりするから。 文字列を使った検索は現代のインフラになってるよね。 例：iタウンページ タイトルとかに「スターバックスコーヒー」って書いてないとだめ。？ 「スタバ」800件くらい　->　正規化で「ー」消してるんじゃないの？ 「スータバックスコーヒー」0件　ちがうな。シノニム辞書登録してるな。 曖昧なクエリ（キーワード）から検索できないかなぁ？ 曖昧情報の処理は文字列処理にこそ必要 なんでヒットしたかがわかるのが正解　なんでヒットしたかわからないけど、ちゃんと出てきたから正解！ 2.ゼロ件ヒット問題（ゼロマッチ） ピクシブ百科事典 「ピングドラム」だと17件 「ピンクドラム」だと0件　しかも真っ白！！ 使いにくいよね。けど、一般的な検索システムの問題だよね。 Googleだと出てくる「ピンクドラム」の結果の最初にはピングドラムが出てくる。 ->リンクがはられているから出てきた？みんなの間違いで助けられてる 食べログ 「俺のハンバーグ」 「俺はハンバーグ」で検索したら。。。「俺はハンバーグで連れは。。。」がヒット->しらねーよｗ まとめ ゼロ件ヒットは機会損失！！ 3.曖昧な文字列で正しい文字列を探す方法 正しい文字列って？ 1.表記誤りがない 2.心の底で求めている ※異表記同義、同表記異義、異言語表記（日本語の情報を英語で検索）などもある 正しさはユーザによって変わる。 正しい文字列をさがす手法 クエリ表記の正誤という軸 誤の場合表記をヒントに似た文字列を検索してみる。 探したい対象が正確か曖昧か 表記意外がヒントで同じ対象に到達できる？ どんな情報を手がかりにする？ 編集距離（レーベンシュタイン） 検索ログ 4.Apporoの紹介 チョコ？いや、ロケット？いや、Approximate … http://code.google.com/p/apporo/ 中小規模だと使えそう SimString 今後 よみかな、ローマ字表記に基づく類似文字列検索＋高速化の予定 技術概要 Suffix Array N-gram Searchベースの近似文字列照合 Bit Parallel Matchingによる編集距離計算 5.検索と言語と文化（仮） @mizuno_takaaki さん 放送禁止のためメモなし。 7.自然言語処理におけるargmax操作 @hitoshi_ni さん ※順番変更 ・近似解法 その１　全探索 いや、無理でしょ、計算が。 その２　貪欲法 最適解が出るかは不明。 その３　ビームサーチ 上位kこの仮説を保持しながら幅優先探索 ・動的計画法 すでに最大値がわかっていて、ゴールから眺めてみる。 逆からたどるとルートがわかるんじゃないか。 マルコフ性につけ込むことで、わかるんじゃないか。 計算量：品詞数の2乗 （品詞数の2乗）＊形態素数 DPの実装 Viterbiかなぁ？ ・整数計画法（線形->整数） 自然言語処理としては整数計画法でだいたいOK。 アルゴリズム ・手元の解空間中から許容解を得る ・分枝してそこから最大値を求める 最大値＞許容解ならそちらを探索。 プログラム実装する？ すごく大変じゃないけど簡単でもないね。 問題の弱点がわかってるなら実装してもいいよね。 整数計画法の場合lp_solveなどのフリーのソフトで解くのがいいよ。エクセルでも解けるよ ILP（整数計画法？） 問題の切り分けに使える。 まとめ ILPで解けたら、いろいろ自分で考えると面白いよ。 その他のバズワード 参考資料 組み合わせ最適化＝1万円超 アリ本 6.ソーシャルグラフ分析(導入編) @kimuras さん　mixiの木村さん ・グラフ探索部分はまた今度。 ・テキストマイニングや検索エンジンまわりやってる。 ・ノードが数1千万、エッジが数億のオーダー ・分散技術の発展によるアルゴリズムの多様化 これまで RDBからDumpしたデータをKVSに入れて頑張ってた。 Dump部分でデータ構造を毎回構築 問題点 変更による再実装、メンテナンスコスト、 これから graphDBに取組中。マイニングに最適な感じ graphDBの実装 OrientDB、Neo4jとか Neo4jって ACIDトランザクション可能 EmbeddedGraphDatabaseだとAGPLｖ３だから気をつけてね。 luceneで全文検索インデックスつくってるみたい。 Gremlinってのがquery言語を汎化してるらし。 とあるSNSのデータを使ってみたよ。 メモリ64G、CPUは1コアしか使えなかったよ。 ノード：15million、枝：600million