@johtaniの日記 3rd

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

以前から春山さんのブログ（リンク）や勉強会で耳にはしていたのですがソースは読んでいませんでした。 先日、Luceneにcontributeされた（リンク）ので軽くソースを読んでみました。 公式サイトはこちら まずはMeCabのページにある比較表（リンク）を基準に特徴を調べてみました。せっかくなので、lucene-gosenも隣に。   Kuromoji lucene-gosen 解析モデル なし（学習機能なし） なし（学習機能なし） コスト推定 なし（学習機能なし） なし（学習機能なし） 学習モデル なし（学習機能なし） なし（学習機能なし） 辞書引きアルゴリズム Double Array Trie Double Array Trie 解探索アルゴリズム Viterbi Viterbi 連接表の実装 2次元 Table 3次元 Table 品詞の階層 無制限多階層品詞？ipadic、unidic形式に対応 無制限多階層品詞 未知語処理 字種 (動作定義を変更可能)（おそらく。） 字種（変更不可能） 制約つき解析 たぶん、不可？ たぶん、不可？ N-best解 不可能 不可能 こうやって比較してみるとlucene-gosen（Sen）とあまりかわりはありませんが、lucene-gosenが少し古いのがわかりますね。。。

忘れてしまうので、備忘録を残しておきます。 一応、ソースには少しずつコメントをいれてはいるのですが。 私は残念ながら、自然言語処理は初心者に毛が生えた程度（現在、鋭意勉強中）で、対応方法に問題があるかもしれません。気づいた方はコメントをいただけると助かります。

lucene-gosen 1.1.1をリリースしました。 先日お知らせしたバグ修正を取り込んだjarを用意いしました。 ダウンロードはこちらから

Solr/Lucene 3.3がリリースされました。（速報） 以下、各サイトへのリンクです。 Solrリリースのお知らせ Luceneリリースのお知らせ リリースのタイミングがどんどん早くなってる。。。

「Hadoopを中心とした分散環境での開発方法論・モデリング・設計手法等についての座談会(第5回）」に参加しました。300名入るイベントルームでしたが、後ろの方まで人が埋まっていました。 ということで、主に自分用ですが、メモを取ったので。 ※二次会行きたかった。。。 1.「鉄道システムへの誘い」 @ayasehiro（本名無理w） Hadoopの話はありません。 ○鉄道系基幹システムの開発 実態： 耐用年数：１０年以上 開発期間：数年～５年程度 開発規模：～10Mステップ、10k人月～ ほとんどテスト、しかも異常系が主体。 夜間に実際に鉄道を走らせて試験したり。 開発サイクルが長い 人材育成が難しい、ノウハウがたまらない。 開発自体はほとんど時間がなく、設計・製造・試験など新規技術の採用が難しい。 開発４年前の調査・検証自体が２年程度。 Hadoopも調査中。 ○鉄道システム３大システム マルス（予約オンラインシステム）（1960～） コムトラック（運行管理システム）（1972～） ヤックス（ヤード自動化システム）（1968～1984） ○鉄道輸送システムとは 用語： 運行を計画する=>輸送計画 列車を運行する=>運行管理 需要想定＋営業施策＋その他（お召し列車など）＝列車ダイヤ作成 基本計画（長期）＋短期計画（数日～四半期程度）＝列車ダイヤ（重ねあわせてできあがり） ダイヤの計画（発車時刻など）と車両運用（車両自体の走る組み合わせ（仮の車両））の作成 ＋乗務員運用（乗務員の運用計画） 運行管理： なにも起きなければすることなし。（車両故障、天候、人身事故などによる整合性を取る作業） ＝事前に計画した輸送計画をすべて見直し 遅延の検知は？ 昔：人による伝令 今：システムによる検知（レールに電流流して検知） 運転整理（実際に遅れた）： 部分運休、折り返し駅の変更などにより対応 元の計画になるべく近づく形で修正していく。 新幹線、山手線、京浜東北線などは速度信号という信号が表示される。 線路上に信号はないらしい。 ○鉄道システムを取り巻く情勢 少子高齢化・人口減少のため凋落産業となっている。 社会インフラの責務＝動くのが当たり前 2007年問題（ベテランの引退）＝スジ屋さんは最近いないらしい。 高度な判断支援をするシステムが必要 連続稼動＝分散技術を適用できない？ 関係各所との情報共有 計画立案のための情報支援＝最適化技術を適用できない？ ○分散処理技術の適用 個人的な感想 可用性（連続稼動）のための仕組み バッチ処理 ○分散技術の適用 ・連続稼動 active-active構成がメイン 主系の出力だけを行う。問題が出れば副系の出力。 3系統の出力を比較器にて出力もある magiシステム 問題点： ハードが高い（H社） ソフトウェアの作り込みが複雑＝テストが前パターンできない 解決案： 汎用的なハードが使いたい。 作り込みも減らしたい ・バッチ処理： Asakusa使えないかなーw ○最適化技術の採用 コンピュータ技術の発展 2007年問題 職人に言わせれば最適化はいらない、俺の言うことを聞けｗ ・車両運用のモデリング 車両数大=>組み合わせ大 制約条件が多い 車両運用の場合、走行累積キロの条件もある ->有向グラフにモデル化される。（ただし、グラフ化するまでが大変） ・乗務員運用のモデリング 車両と違い、乗務員は1回で2人とか運べる（運転士＋移動する人とか） ・車両割当のモデリング やはり、グラフ化が可能 ・乗務員交番のモデリング。。。など 結構一般的なモデルに落とし込める。ただし、落し込みが大変。 机上研究だったものが、コンピュータの発展により実証研究になりつつある。 ○まとめ 鉄道システムはまだまだ未到の領域が残っている。 開発サイクルが長いため、保守的な開発になる（35年前の設計思想からあまり変わってなかったりする） しかし業務要件やシステム利用者の意識は変化している 興味を持たれた方は、ぜひ、我社に！（社名は2次会でｗ） ○Q&A Q：鉄道システムのカルチャーってイケイケ？保守的？（@okachimachiorgさん） A：最新技術も知らないとだめじゃないかという人が出てきている。 コア部分（安全第一なところ）＋周辺領域（ある程度融通が効きそうな部分）と考えることができるんじゃないかって人も出てきている。 JR九○＝先進的 JR四○、北○道＝お金ない JR○海＝超保守（企業的に超保守） JR東、西＝うーむ？ 東京メト○（運行計画）、阪○＝先進的 京○急行＝基本人間で進路制御w 基本的には新しいものには興味をもつ人たちでは。 Q：Su○caとかで分散処理は利用出来るんでは？ A：匿名なので外側から見ていると分散処理はいろいろ使えるんでは？ ログデータからいろいろできるんじゃないの？活かすべきでないの？ 使いどころはいっぱいある。 Q：鉄道システムでどうしようもなくなったことはあるか？ A：保守体制が一番気になる。 OSSとかならまだ調べられる。ミドルウェアなどの保守契約が必要。 保守体制が確立されてればある程度の保守費用は飲み込む。 どうしようもないことはないが、今すごく困ってることは Excelで帳票を出したいとかいわれること。（ちょっと前に作ったシステムでExcel2003。バージョンあげると速度が遅くなったりするｗ） ilog社のものを使ってたが、IBMに買収されて保守費用があがってこまってるｗ 保守が10年と長いため、サポートなどの折衝が必要。 Q：最適化の適用範囲は？ A：走行順序（どこで追い抜くか）の算出に活用。ほぼ完成でユーザ教育中。 1列車の波及がかなり影響が出る。ダイヤだけ見ると列車だけだが、乗務員も関係しており、大変。 ある時点から終電までを最適化の対象としたりして割り切っている。 また、不足分について算出が出来れば、そこで打ち切ったりもする。 2.「九州電力におけるHadoopの取り組みについて」 株式会社キューデンインフォコム e－ビジネス部　@hisashi_yano 概要：2年間関係したOSSをメインにしたシステムの話。 ○九州電力の概要 現在風当たりが強い業界。 東電の1/10くらい 部門ごとに大手ベンダーが関わってる。 ○Hadoop採用の経緯 部門ごとに個別最適なシステムを導入していてベンダーロックインされてる。 ・ホストのリプレース ・両現用センター構成への対応 ・スマートグリッドへの対応 問題点 ・コスト削減 ・技術革新への中の人の対応（内部でも問題を理解できるように） ・商用パッケージのカスタマイズの限界 ・脱ベンダーロックイン（実は楽なんだけど。。。） ○過去2年間の研究内容 ・H21年度の結果 テーマ：クラウドの要素技術の研究 KVM、Eucalyptus、wakame、hadoop　性能比較：VMWareとKVM->ベンチマーク比較 結論：性能的にあまり問題なし。 MapReduceの耐障害性など ダミーデータにより台数増加による影響を検証 結論：台数大->性能向上 ストリーミングは性能劣化する スループットはリニアに向上 信頼性は？ 実行中にノードを抜いたりして検証。 結論：問題なし。 クラウド環境におけるシステム管理手法 複数ハードで1アプリという構成になる。 監視対象が膨大になる。 障害発生時の切り離しや監視対象も膨大。 データセンター自体を監視する仕組みが必要では？というところで終了。 ・H22年度の結果 分散に特化した研究 前年度の課題 サーバの仮想化・管理に関する課題 分散処理に関する課題 分散処理環境の運用監視に関する課題 目的： Hadoopを本番への適用（実際にはダミーデータ＋本番の仕組み） 柔軟なサーバ統合基盤（サーバを起動->バッチを起動->回す仕組み）＝MonkeyMagic libvirtを使ってる 50台の仮想サーバの起動が10数分で完了。 運用監視基盤（monkey magic） 仮想、実サーバ混在の監視 監視状況（サーバの状況）から判断して制御する仕組みを構築 DSLにてルール（判断＋制御）を指定 ・ジョブの監視 ・ジョブの実行管理 ・構成管理の省力化 volanteと連携が可能＝AmazonWebServiceとも連携可能 ・サーバリソース＋アプリケーションの一括監視が可能 分散バッチ処理の概要 RDBからKV形式にして抽出し、MRで回してRDBに戻すという研究 対象： 配電部門（電柱の設備情報の目視検査）のデータの月間バッチ処理 現状： 19時間程度かかってる。 テスト環境： 実サーバ2台（仮想10台） MySQL、Javaで実装 処理内容 電柱104万本 巨大バッチを分割して実装 結果 MySQL1台では15日以上かかる処理（現行システムで19時間） 処理が32分で終了！他でも効果でるよね。 バッチ短縮の理由は？ 1.データアクセスが分散された 2.処理の並列化（多重化出来る部分がうまくできた） 分散処理を書くのに2名死亡。。。 適用基準の策定、開発ガイドライン、フレームワーク整備などが必要。 ・H23年度は？ Asakusaの適用など。 ・さらに今後は？ スマートグリッドへの適用 ->メーターの交換が必要だが、10年くらいかかる ->スパンが長い（10年）ので商用製品だときつい？ データ量も半端ない。 テネシー州とClouderaでOpenPDCってのやってるらしい。 電力と気温の関係は密接な関係あり。 エアコンが割合を占めてるから。 過去実績と予想気温データから分析するのにHadoop使える！ ・2年間やってきて思うこと 将来目指すべき理想像を掲げるのが重要 新技術導入は段階を踏むことが必要 コミュニケーション大切！ ○Q&A Q：仮想化環境のオーバヘッドは？（I/O） A：台数を増やしたときにどうなるか？というのを検証したかった。 アプリ配布も考えていたので、物理サーバに縛られたくなかった。 Q：仮想化に関して気をつけたM/RのPGで気をつけたことありますか？ A：まったくないです。 Q：日本でスマートグリッドははやるの？ A：電力会社的にはやりたくない。費用対効果があまりない。 Q：今後のスケジュールは？ A：文書管理システムの組織名変更などの処理時間が540時間とかでてくるらしい。 これをHadoopで対応してみようかと思ってる。 Q：Asakusaをどう評価していくのか？ A：開発効率性があがるか？は検証する予定。1/3くらい楽になるんじゃないかなぁ？byのぐちさん バッチの種類などにもよると思うが、標準化も指標にする予定。 結果はまたこの場で報告する予定。 Q：Asakusa＋MonkeyMagicの連携はどんなこと考えてる？ A：MonkeyMagicを運用基盤として行く予定。合意が取れればだけど。 ※MonkeyMagicもOSSにするよー

以前、こちらで話題に上がっていた「未知語」に関するcompositePOSのエラーの件を調査しました。（Twitterでも流れてました。） 次のような条件の場合にエラーが発生するようです。 compositePOSの設定に構成品詞として「未知語」が指定されたエントリが存在する。 未知語が連続して出現する文字列をanalyzeする。（例：ニンテンドーDSi） ということで、trunkに修正版をコミットしました。 Issueはこちら。

lucene-gosenのtrunkbranches/impl-mecab-dicにNAIST-JDic for MeCabの辞書を利用出来るPreprocessorをコミットしました。 ビルド方法は次のとおりです。