門外漢から見た「第1回 データ構造と情報検索と言語処理勉強会（DSIRNLP）」

発表資料なんかは早速まとめてくれてる方が。

内容のまとめはこことか。

主催者の @overlast さんもあとでまとめてくれるそうなので。

以下はNLPって何のことか知らないで参加した人のメモと感想。

TRIEにトライ！〜今日からはじめるTRIE入門〜（@echizen_tmさん）

  • 前提としてるであろうことがわかってなかったので、少し調べてみた
    • データ構造の話っていうのは聞いててわかった。
    • 辞書データを持つときにつかうみたい。
    • ある文字列を、この構造の辞書データの中から検索するっていう場面を想定しとけばいいっぽい。
  • 発表を聞いたメモ（と感想とか疑問）
  • 前方一致検索に使える。
  • KVSよりリッチな操作、検索が高速、メモリをたくさん使う
    • （KVSってなんだろう。リッチな操作ってなんだろう）
  • ライブラリ
    • darts(@taku910さん)
    • tx-trie(@hillbigさん)
    • marisa-trie(@s5yataさん)など
  • TRIEをいい感じで作るためには、メモリを食わないアルゴリズムをいかに使うか。
  • 通常のTRIEでは、データがでかくなると破綻する。
  • データ構造はスライド参照。
    • （図とコードで示されるとわかりやすい）
    • （でもコードの動きはちゃんと理解できてない）
  • データの追加は、ノードをたどってマッチするノードが無かったら追加する。
  • 検索。同じくノードをたどる。見つからなかったら検索終了。
    • たどった現在地から先のノードを取ってくる事でサジェスト的なことができる。
  • 状況に最適なアルゴリズムを選ぶには、「プログラミングコンテスト チャレンジブック」を読むといい。

プログラミングコンテストチャレンジブック
プログラミングコンテストチャレンジブック
posted with amazlet at 11.07.24
秋葉 拓哉 岩田 陽一 北川 宜稔
毎日コミュニケーションズ
売り上げランキング: 23261
Amazon.co.jp で詳細を見る

  • 深いこと考えなければさくっと実装できる。
  • LOUDS：省メモリのTRIEのアルゴリズム
  • 構築済みのTRIEからLOUDSを構築する。
  • ノードは子ノードのIDではなく、子ノードの数だけ持ってればいい。
  • データの追加は出来ない。追加する場合は元のTRIEに追加して、再度LOUDSを構築する。-データの構造はスライドの図を参照。
    • 配列になる。
    • 葉の値の部分もIDを持つ。
  • 自分の最初の子ノードのIDがわかれば、それ以降の子ノードがわかる。
  • 自分の前のIDの子ノード数の合計　＋　１＝最初の子ノードのID
    • （ふしぎ！ふしぎ！）
    • この計算は簡潔データ構造を使えば実装できる。
  • 元の論文ではUnary符号を使っていたところ、今回はVerticalCodeを使ってみた。
    • 自分の前のIDの子ノード数の合計の計算につかってる？（よく理解できず）
    • Vertical Codeは累計値を計算するアルゴリズム
    • ある程度の累計値を計算しておいて、そのデータを持っておく
    • データを圧縮するために、データを縦に積んで持ってるのでVertical
01001011
10100011
 1 01 01
    • 縦が実データ、横がchar。char[3]で８個のデータが持てる
    • ひとつ長いのがあると足を引っ張ってるが、それも８個単位のグループまでしか影響が無い
    • dag_vectorをつかってもよいかも。
    • （構造はわかったけど、どう使ってるのかはよくわからなかった）
    • （そもそも簡易データ構造自体がわかってない）
  • テストにはネットで公開されてる住所リストをつかった
    • （実装からテストまでの一連の流れがあるのはありがたい）

実際手を動かして作ってみれば理解できるんだろうなっていうところが多々。そして実装するためのヒントというかそのまま実装があるんだから自分の環境でも動かせるはず。

ランキング学習ことはじめ（@sleepy_yoshiさん）

  • Learning to rank：ランキング学習、ランク学習
  • 教師あり機械学習の枠組み
  • web検索エンジン
    • 単一のランキング手法：pagerankなどの手法
    • それに対してspamやseoがキャッチアップするので、複数を組み合わせて。
    • クエリと文章の類似度、文章の重要度を使ったランキング関数を使って、検索スコアを出してる。
  • Googleの検索ランキング関数
  • ランキング関数は線形結合でやってる。結果を早く返すため。
  • 要因が多くなると、組み合わせの調整が難しい
  • →教師つき機械学習
  • 正解データ＝訓練データの作成（人手）
  • クエリと文章のペアに対して、評価点を付与（クエリに対して適してる・適してない）
  • 正解データを学習アルゴリズムに通して、モデルを生成する。
    • モデルは、未知のクエリに対して予測値を出す。
    • （この辺で勘違いした。）
    • （学習アルゴリズムがまったく新しいモデルを作るの？どうやって？とか思ってた）
    • （そうじゃなくて、既存のランキング関数を調整するんだった。）
    • （だから以降の発表がうまく理解できなかったのか。）
  • 懇親会中に教えてもらった、教師つき機械学習の基本的なこと
    • まず、何らかの問題を解く関数がある。（ランキング関数とか）
    • 教師データをつくる。
    • こっから機械学習。教師データの入力データで関数を動かして、出力が教師データの結果と一致するかを見る。
    • 誤っていたら関数を調整する。
  • ランキング学習の３つのアプローチ
    • どのような目的関数/損失関数を設定するかが違う。
    • Pointwise手法：単一のデータ（documentと評価の一組）一つ一つに対して損失関数を設定
      • Pointwise　精度が高くないので、実用的ではない
    • Pairwise手法：同一クエリのペアに対して損失関数を設定
    • Listwise手法：同一クエリのリクエストに対して損失関数を設定
  • 感想

google-snappy調べてみた（@machyさん）

  • （TopCoderってなんだろう）
  • snappy：速さを優先した圧縮
  • snappyとhadoopで使われてるlzoはほぼ同じくらいの性能だった。
  • snappyは辞書式符号化で圧縮
  • ハフマン符号化
    • データを2bitごとに区切って
      • いっぱい出てくるデータに小さい符号を
      • あんまり出てこないデータに長い符号を。
  • 辞書参照元の探し方
    • ハッシュテーブルを使って、同じ文字列がどこに現れたかを探す。
    • 既存のデータと一致したら、ハッシュ値が被る。長さを伸ばして、どこまで一致するかを見る。
  • 圧縮しにくいjpgなどは、圧縮を諦めたような動き。参照元を探すのを2バイトごと、3バイトごとと移動幅が増えてく。
  • それでも長いのには一部マッチする。
  • ハッシュテーブルが小さいので、メモリ消費量を抑えてるっぽい。

snappyがどうとかいうより、圧縮の仕組みを理解できた気がする。
そもそも圧縮を使う場面があんまり想像できないのがあたしのネック。
たとえばローカルからデータをアップロードするとき、ローカル側で圧縮するとして、snappyをブラウザで動かすことってできないのかな。

類似文字列検索してますか？（@overlastさん）

  • 文字で検索するときには厳密な検索。
  • 画像→画像検索は、欲求が満足されればOK→裏で何をやってもOK
  • 文字は結果の理由を明確に説明できるor便利ならOK
  • pixivさん。ピン「ク」ドラムは0件。
    • 自前で辞書をもって検索させているところはどこも抱えてる問題っぽい。
  • ゼロ件だったらその後にワンクリック・ゼロクリックで目的のページに飛べるのが便利なサイト。
  • 正しい文字列とは、表記誤りがないもの、「トトロの森美術館」みたいな文字列を入力したときに、心の底で求めてるものとか。
  • 「正しさ」はユーザーの状況で変わる。
  • 表記誤りは、事前に用意した辞書から正しい表記を探すことで解決できる。
  • 表記に誤りが無いけど探したい対象があいまいな場合、検索ログから関連する語を見つけてくる。
  • Apporo
    • 類似文字列検索ライブラリ
    • 0件検索を防ぐもの。
    • 辞書をメンテナンスするコストを減らす
    • 0件にならないクエリで辞書を作る。
    • 0件になるときにApporoを起動
    • →クエリに近い単語を辞書から探し配列で返す。
  • 使い方
    • データのある場所を教えてあげて、インデックスを作る
    • →もう使える
  • 技術は既存のもの。

perlにも対応してるので使ってみよう。
インデックスは定期的に作り直す必要があるっぽいのかな。
こういう検索をリアルタイムでやりたい。

ないしょばなし

自然言語処理におけるargmax操作（@hitoshi_niさん）

  • （スライド公開してくれないかな…）
  • （この段階でNLP=自然言語処理と知る。）
  • NLPとはなんぞや
  • 検索やマイニングは目的指向の言葉
  • NLPは対象指向の言葉
  • NLPタスクのうちargmax操作（デコード）が面白いよ
  • 中間表現←→自然言語をやるのが自然言語処理
    • 解析
      • 単語を分割→係り受け解析→述語項構造解析→談話構造解析
    • 生成
      • は恐ろしく難しい。
  • 自然言語タスクを解く。
    • 与えられた入力を、所望の出力に変換する関数を設計する。
    • y = arg max f(x;w)
      • fはいろんな解を生成してくる
      • arg maxは、そのなかの一番いいやつを選んでくる。
        • 例：今日　は　いい　天気　です
        • それぞれの単語に品詞がつく
        • 1.名詞　助詞　形容詞・・・・
        • 2.名詞　助詞　名詞・・・
        • こんなリスト。それに点数をつける。
  • モデルとパラメタを与えられたときに、それを計算するのがデコード
    • （モデルって言うのが上の関数 f(x;w)かしら？）
    • 一次のマルコフモデル
      • 縦の計算：各単語に対して、品詞ごとのスコア（今日：名詞のスコア５、みたいな）
      • 横の計算：単語同士の横の関係にスコア（名詞→助詞は３、名詞→助動詞は２みたいな）まず横と縦を足す。
      • （このスコアがパラメタ？）
  • たくさんのパターン→ルートによっていろんな得点がある形になる
    • （これが上記のリスト？）
    • このリストから一番いいやつを選ぶのがarg max。
  • 手法
    • ビームサーチ
      • ある時点で、上位何件かを候補に残してさらに先を検索する。
      • 早いけど最上の結果を保証しない。
    • 動的計画法
    • （以降いろんな手法を説明してくれて、）
    • （高専で習った工場の最適経路の解き方の話だなって、）
    • （手で解いたことを思い出したりしておりました。）
    • 探索木？
      • 不要な枝をばっさばっさと切り落としていく。
      • lp_solveなどのフリーのソフトに数式を代入して解くのが無難
      • 自分でモデルを作れば、ILPが解いてくれる。
  • ILP（整数計画法）の使いどころ
    • 問題点の切り分け？パラメタが悪いかモデルが問題か…
    • （普段は早いビームサーチで解いてて、問題解析する際に使うってことかしら）

自然言語処理の基本的な流れが理解できたのがうれしかった。
たぶんモデルもパラメタもコーパスも、いろんな人が考えたのがあるんだろうね。
こういうのもいっぺん使ってみたい。

ソーシャルグラフ分析(導入編)（@kimurasさん）

聞いてるときは自前でソーシャルグラフデータを取れるところだけの話かと思ってたけど、例えばTwitterのTLを取得して独自のソーシャルグラフを作ったりっていうこともできるよね。

懇親会とか、全体的な感想とか

日刊ホソコシ 31 | 日刊ホソコシに書いた。