2020-02-14

モンテカルロ木探索を開墾する

勉強研究強化学習

会社で開墾会という論文などで見かけた手法を勉強して共有する会をしています。この記事は開墾会の資料で、モンテカルロ法とモンテカルロ木探索を具体例を交えながらまとめています。

問題設定

f:id:komei22:20200213234328p:plain

上の図は道にコインが落ちているマップである。2人のプレイヤーはスタート地点からコマを交互に移動させていき、多くコインを集めたほうが勝ちというゲームをする場合を考える。ただし、

一回通った地点は通れないものとする。
これから通る道にコインが何枚あるかは事前にわからないものとする。

この問題を題材にして、モンテカルロ法とモンテカルロ木探索を用いて先手のプレイヤーが取るべき手を学習していく。

ゲーム木

モンテカルロ法などの説明に入る前にこの問題のゲーム木を書いておきたいと思う。ゲーム木とは、ゲームの盤面をノード、盤面に対して打てる手をエッジとしたグラフのことである。今回の場合は、木の終端ノードがゴールまでの経路（解）、その他のノードがゴールまでの経路の一部を切り出した経路（部分解）となる。以下に、今回の問題のゲーム木を示す。

f:id:komei22:20200213234407p:plain

上のゲーム木において、赤の線が先手のプレイヤーが選択した道、青線が後手のプレイヤーが選択した道となる。終端ノードに付いている数字は、報酬であり、先手が勝ちの場合は1、引き分けの場合は0、負けの場合は−1としている。

モンテカルロ法

モンテカルロ法は、ランダムに何らかの報酬が得られるまで行動して、得られた報酬をそれまでに辿ってきた状態に分配していき、平均報酬Qを求める方法です。実行手順は以下のようになります。

終端ノードにたどり着くまでランダムに手を選ぶ
得られた報酬をこれまで通ってきた状態に伝搬する
1. このとき、選択された回数Nと平均報酬Qを記録しておく
1.2.を任意の回数繰り返す

モンテカルロ法を実行することにより、全ノードに対して平均報酬Qを求めることができ、平均報酬Qが大きい手を選ぶことで、最善手を導くことができる。

適用例

先程定義した問題に対して適用してみる。まず、ランダムに手を選択していって、以下の図のように終端ノードにたどり着いたとする。

f:id:komei22:20200214010837p:plain

たどり着いた終端ノードの報酬は1なので、この報酬を辿ってきたノードに伝搬させる。このとき、Nをカウントアップ、Qを計算する。

f:id:komei22:20200214011209p:plain

次に、以下の図のように終端ノードにたどり着いたとする。

f:id:komei22:20200214011332p:plain

たどり着いた終端ノードの報酬は0なので、この報酬を辿ってきたノードに伝搬させる。このとき、 $Q=\frac{1+0}{2}=0.5$ となる。

f:id:komei22:20200214033709p:plain

このような操作を繰り返すことで、全ノードの平均報酬を更新していく。

問題点

モンテカルロ法は、手の選択が完全にランダムなので、相手にとっての最良の手も平等に探索してしまい、探索に無駄が生じる。例えば、先程のゲーム木の根ノードの左側は、引き分けか負けしかないため、探索するだけ無駄になってしまう。また、これにより、Qが過大評価されることがある。例えば、先程のゲーム木の根ノードの左側は、引き分けか負けしかないため、評価は−1にして絶対に左側を選択しないようにしたい。

これを回避するためには、ノードの選択ををランダムではなく平均報酬で決めていく方法も考えられるが、勝てるパターンもあるのに最初に探索したパターンが負けのパターンだった場合に、勝ちパターンを探索しなくなってしまう。平均報酬が高いノードを積極的に探索して効率よく探索したい、でも平均報酬の見積もりが十分でないノードの見積もりもやりたい。この平均報酬の活用と見積もりのバランスを取りながら探索を行うのがモンテカルロ木探索である。

モンテカルロ木探索

モンテカルロ木探索は、上記したように、平均報酬の活用と見積もりのバランスを取りながら探索を行う方法である。モンテカルロ木探索では、一般的にゲーム木は膨大な大きさになるため（囲碁や将棋などの場合）、木を深さごとに展開しながら探索を行う。モンテカルロ木探索は以下の3つの操作を任意の回数繰り返すことで行われる。

Tree policy
Default policy
Backup

それぞれについて説明する。

Tree policy

このステップでは、木の展開済みの範囲におけるノードをUpper Confidencial Bound for Trees(UCT)に基づいて選択することを繰り返し、木の展開済みの範囲における終端ノードを求める。

$UCT = Q_i + C\sqrt{\frac{2\log N}{N_i}}$

ここで、 $Q_i$ はノードiの平均報酬、Nは全探索数、 $N_i$ はノードiの探索数、Cは重み（任意に決定）である。

この式は、基本的には第一項で平均報酬Qが高いノードを探索しようとするが（活用）、第二項によりノードそれぞれの探索数を考慮して、探索数が少ないノードであっても積極的に探索しようとする（探索）。重みCは活用と探索のバランスを取るために設定する。探索の優先度を高くしたい場合はCを大きくする。例えば、探索数が0のノードがあった場合は、第二項が無限となりUTCも大きくなるので、そのノードを探索しようとする。

Default policy

このステップでは、Tree policyによって選ばれた展開済みの範囲における終端ノードから、木全体の終端ノードにたどり着くまでランダムにノードを選び、終端ノードの報酬を求める。

Backup

このステップでは、Default policyによって得られた報酬を辿ってきたノードに伝搬し、平均報酬Qとノードの探索数Nを更新する。

適用例

先程定義した問題に対して適用してみる。まず、Tree policyで展開済みの範囲の木のノードをUCTに基づいて選ぶ。まだ一度も探索が行われておらずUCTは比較できないため、どちらかをランダムに選ぶ。今回は以下の図のように選ばれたとする。

f:id:komei22:20200214025413p:plain

次に、Default policyでランダムにノードを選択し、以下の図のように終端ノードにたどり着き、報酬が得られる。

f:id:komei22:20200214025534p:plain

得られた報酬は1。次に、得られた報酬をBackupで辿ってきたノードに伝搬する。また、このとき、ルートノードの右側のノードは一度探索されたので、そのノードの子のノードは展開済みとなる。

f:id:komei22:20200214030449p:plain

次に、Tree policyによりルートノードの左側が選ばれ、同様にDefault policyとBackupを行い、以下のような状態になったとする。

f:id:komei22:20200214030125p:plain

この状態から、次の探索でTree policyを適用する場合、UCTの式が効いてくる。 UCTの式に当てはめると、木の右側はUCT=1.776、左側はUCT＝0.776となる（C=1で計算）。そのため、Qが大きい右側が選ばれる。これは、これまでに得られたQを活用することで、勝ちパターンが多いであろう方向に積極的に探索が行われていることを意味する。また、右側のノードの先も同様にUCTで計算するが、まだ探索されておらず比較できないので、ランダムに選ぶ。以下のように選択されたとする。

f:id:komei22:20200214031946p:plain

Tree policyで選ばれたノードは、木全体において終端ノードであるため、Default policyはそのノードの報酬を返し、Backupで報酬が伝搬される。

f:id:komei22:20200214032305p:plain

このように、平均報酬Qが大きい、つまり良い解があるであろうノードを優先的に探索を行い、Qを更新していく。しかし、UCTの式の第二項により、ノードの探索回数も考慮されるため、Qが大きいノードばかりを探索せずにどこかのタイミングで、Qが小さい方も探索される。このパターンは、具体例を示すまでに何回か繰り返さないといけないので割愛する。（UCTにおけるCのを大きくすることでQが小さいノードの探索頻度が向上する）

特徴まとめ

途中過程の良し悪しはわからなくても、勝ち負けがはっきりしているゲームに有効
- モンテカルロ木探索では、途中の状態の良し悪しを判断せずに、最終的に行き着く結果の状態の良し悪しだけ分かればいいため
- また、組合せ最適化論において解の良し悪しは判断できるが、途中過程（部分解）での評価が難しい場合に有効と思う
木の探索をモンテカルロ法に比べて、無駄なく行える
- 木の規模が大きくなるとモンテカルロ法では現実的な探索ができずに学習が上手く進まない
モンテカルロ木探索は細く長い勝ちの手順が苦手
- 細く長い勝ちの手順とは、最前手が一手のみでその他は負けのような状況が複数回あるような状況。一歩間違えれば負けの連続。
- これは勝ちのパターンに探索でたどり着くのが難しくなる
- 例えば、細く長い勝ち手順の先の報酬だけ異様に高い2000点みたいになると困りそう

参考

2020-01-25

pythonのdefaultdict()について

python メモ勉強

defaultdict()をsklearnの実装で見かけて、調べたのでメモ。

サンプルコード

 from collections import defaultdict
 
 dict = defaultdict()
 dict.default_factory = dict.__len__
 
 dict["a"]
 dict["b"]
 dict["c"]
 
 print(dict["a"], dict["b"], dict["c"])
 
 # 出力 0 1 2

解説

default_factoryを設定することで、dictにkeyのみで（valueを渡さずに）追加しようとした場合の挙動を変更できる。上記のコードでは、dict.default_factory = dict.__len__としているので、keyを追加しようとしたときのdictのlenがvalueとして設定される。

公式の使い方の例では、key-valueのペアのシーケンスをlistに変更して、keyに対してlistが設定できるように変更する例が示されている。これはたまに使いそうなデータ構造なのでやり方を覚えておきたい。

参考

https://docs.python.org/ja/3/library/collections.html#collections.defaultdict

2019-10-25

英論文書いたときにもらった指摘事項まとめ

勉強

僕は英語があまり得意じゃないので、英論文を書いたときのレビューで様々なコメントをいただく。頂いたコメントをその場で理解して反映させることはできるのだが、次に書くときに忘れていて同じ過ちを繰り返すことが多いので、よく使う文法表現の変換などの気付きをメモしておこうと思う。また、英文校正サービスも利用した経験があるので、英文校正サービスがどのような英語表現の変換を行っているのかもメモしておこうと思う。

レビューコメントでの気付き

it（名詞を指す） -> The 名詞
- itが名詞を指しているとき、itがどの名詞を指しているかが曖昧になることがあるので、「the 名詞」とすることで指している名詞を明確にする
verify
- verifyはすでにあるものを検査したという意味になる
- 「実験で何かを検証した・評価した」というような場合は、evaluateやexplainなどを用いる
experiment
- 実験する、試すなどの意味だが、これはexperiment with a new idea「新しいアイディアを試した」のように使うのはいいが、「〜に関する実験をした」という意味では適していない
- この場合はevaluated ~ by an experiment「実験によって〜に関する評価を行った」という書き方にする
compare
- compare A with Bのように、何と何を比較したのかを述語に取らないといけない
- 「〜に基づいて比較する」という場合は、make a comparison based on ~とする
remove
- removeは「消えてなくなる・消し去る」という意味。「除外する」という表現には適していない
- 「除外する」はexclude
As a result
- resultが何の結果かが明確でないので、As a result of ~として明確にする
- 「実験結果として〜を確認した」という場合は、「実験結果は〜を示している」とすると、守護が実験結果になって英語にしやすい
  - Results of the experiment indicate ~
be likely to 動詞
- 形容詞などを取ってはいけない。
- 例：be likely to unnecessary -> be likely to be unnecessary
consider (that) ~
- considerの後は文が来る。名詞節は駄目。
fact
- 実験結果をfactと言い切ることは基本ない
- 論文でfactと言い切るのは危険。本当に事実なのか
Therefore, Consequently
- 「だから」「結果的に」を表す接続詞
- 強調したい文にのみ利用する
- 英語は前後の文で論理が通れば接続詞は不要

英文校正での気づき

The attacks can be prevented -> Attacks are preventable
- 形容詞でより簡単に表現
queries that are not in list -> unlisted queries
- 形容詞を用いてより簡単に表現
キーワードの順番を関連性が高い順に並べる
- Database security, SQL injection, Whitelist, Development process, Web application test という感じで適当に単語並べるのではなく、Database security, Development process, SQL injection, Web application test, Whitelistのようにセキュリティ関係のキーワードの後にその他というような順番で並べる
are not expected -> are unexpected
- 「be not 形容詞」な形は「be 形容詞の否定形」に変換できる
are caused by~ -> are attributable to~
- causedだと原因が限定的。attributable toも原因を表すが、原因の一部を表しているニュアンス
Theという冠詞を使いすぎない
- theは前文ですでに出てきたものを表す冠詞
- 前文に出てきたけど、その単語を明確に指す必要がないときは、名詞（複数形、単数形をしっかり考慮した）で書く
- theが多すぎるときは大体無駄に書いてる場合が多い
A is to 動詞 -> A is 名詞
- 例： A goal is to protect -> A goal is the protection
- Aは〜すること、と書きたいときは動詞の名詞形画を積極的に使う
impractical -> onerous
- impracticalは100％実行不可能に近い表現だが、onerousは100％ではないけど「大変な負荷がかかる」という意味
solve -> alleviate
- solveは解決するという意味だが、alleviateは軽減するという意味
- 全て解決するわけじゃないが、軽減するというときに使う
- 例：A method solves the shortcomings -> A method alleviates the shortcomings
「Because A , B」 -> 「A. Therefore B.」
- 「AなのでB」という文は、「A。だから、B」という文に書き換え
- 一文が短くなって読みやすいし、論理構造もわかりやすい
「the behavior of the web application」 -> 「the web application behavior」
- 「Webアプリケーションの振る舞い」のような「〜の〜」を英語にするとき、修飾が長くなりすぎないならば、ofを使わないほうが良い
- 「〜の〜」という形のときはofを使いがちで、指摘箇所が多かったので気をつけたい
「In this section, we describe〜」->「This section describes~」
- weという主語が冗長なパターン。This sectionを主語に取る
relationship -> relation
- relationshipよりrelationがフォーマルな表現
- 特定の物事に対して使う。
- 因果関係なども含めた「関係」
- relationは、政治と宗教の関係、重力と速度の関係などのときに利用される
not depend on -> independent of
- 否定形は指定した状態を表す形容詞に変換するパターン

まとめ

自分が気になった英語の変換を走り書きで書いただけなので、あまりまとまっていませんが、今後英語を書くときに抽象化せずに色んなパターンを覚えておくのも大事かと思ったので、今回はそのまま書いて置くことにした。そのため、重複している事項もある。少しずつ覚えていこうと思います。

英語を読む能力は、読む機会が多いことや辞書や翻訳ツールなどのサポートが受けられるので、上達しやすいと思うのですが、書く能力はまた別なので少しずつ積み上げていきたい。grammarlyのような文法をチェックしてくれるツールもあるので、利用してパターンを学習していきたい。

2019-09-03

neologdを利用するにあたってのテキストの前処理について

勉強

はじめに

最近、sklearnを使ってtf-idfをを計算するというのをしているのですが、この計算の前に日本語のテキストの分かち書きをしないといけません。しかし、この分かち書きがなかなか上手くいきません。例えば、「カラーブラック」というテキストがあったときに、「カラー、ブラック」に分かち書きしてほしいのですが、現在分かち書きで利用しているMeCabのデフォルトの辞書では上手くいきません。mecab-ipadic-neologdも試しましたが、この辞書は新語が登録されているだけなので、例のように分かち書きはできませんでした。また、Web上のテキストには、URLやメールアドレス含まれます。日本語の場合には、半角全角の英数字やカタカナ、ひらがなや漢字など様々なパターンが入り混じっているため、これらを前処理の段階で適切に処理しておかなければ、辞書の単語とマッチしないため分かち書きが上手くいきません。このことから、単語を辞書に登録することも重要ですが、形態素解析を行う前処理が重要ということが分かりました。では、どのような前処理を行っておけばよいのだろうか？と考えて調べたところ、mecab-ipadic-neologdを適用する場合のテキストの正規化のやり方が書かれているページを発見しました。この前処理は、neologdの辞書生成時に行っているものと同じなので、辞書とマッチしやすくなります。今回はneologdを利用するときに推奨されている前処理についてコードの解説をまとめておこうと思いました。

前処理のコード

Regexp.ja · neologd/mecab-ipadic-neologd Wiki · GitHubより抜粋。

# encoding: utf8
from __future__ import unicode_literals
import re
import unicodedata

def unicode_normalize(cls, s):
    pt = re.compile('([{}]+)'.format(cls))

    def norm(c):
        return unicodedata.normalize('NFKC', c) if pt.match(c) else c

    s = ''.join(norm(x) for x in re.split(pt, s))
    s = re.sub('－', '-', s)
    return s

def remove_extra_spaces(s):
    s = re.sub('[ 　]+', ' ', s)
    blocks = ''.join(('\u4E00-\u9FFF',  # CJK UNIFIED IDEOGRAPHS
                      '\u3040-\u309F',  # HIRAGANA
                      '\u30A0-\u30FF',  # KATAKANA
                      '\u3000-\u303F',  # CJK SYMBOLS AND PUNCTUATION
                      '\uFF00-\uFFEF'   # HALFWIDTH AND FULLWIDTH FORMS
                      ))
    basic_latin = '\u0000-\u007F'

    def remove_space_between(cls1, cls2, s):
        p = re.compile('([{}]) ([{}])'.format(cls1, cls2))
        while p.search(s):
            s = p.sub(r'\1\2', s)
        return s

    s = remove_space_between(blocks, blocks, s)
    s = remove_space_between(blocks, basic_latin, s)
    s = remove_space_between(basic_latin, blocks, s)
    return s

def normalize_neologd(s):
    s = s.strip()
    s = unicode_normalize('０-９Ａ-Ｚａ-ｚ｡-ﾟ', s)

    def maketrans(f, t):
        return {ord(x): ord(y) for x, y in zip(f, t)}

    s = re.sub('[˗֊‐‑‒–⁃⁻₋−]+', '-', s)  # normalize hyphens
    s = re.sub('[﹣－ｰ—―─━ー]+', 'ー', s)  # normalize choonpus
    s = re.sub('[~∼∾〜〰～]', '', s)  # remove tildes
    s = s.translate(
        maketrans('!"#$%&\'()*+,-./:;<=>?@[¥]^_`{|}~｡､･｢｣',
              '！”＃＄％＆’（）＊＋，－．／：；＜＝＞？＠［￥］＾＿｀｛｜｝〜。、・「」'))

    s = remove_extra_spaces(s)
    s = unicode_normalize('！”＃＄％＆’（）＊＋，－．／：；＜＞？＠［￥］＾＿｀｛｜｝〜', s)  # keep ＝,・,「,」
    s = re.sub('[’]', '\'', s)
    s = re.sub('[”]', '"', s)
    return

前処理の解説

上記した前処理のコードについて解説していきます。

unicode正規化

def unicode_normalize(cls, s):
    pt = re.compile('([{}]+)'.format(cls))

    def norm(c):
        return unicodedata.normalize('NFKC', c) if pt.match(c) else c

    s = ''.join(norm(x) for x in re.split(pt, s))
    s = re.sub('－', '-', s)
    return s

# main
s = unicode_normalize('０-９Ａ-Ｚａ-ｚ｡-ﾟ', s)

unicodeでは、仮名の濁音や半濁音などを表すために、合成済み文字、もしくは結合文字列（基底文字の後に１以上の結合文字を続けた文字列）を利用する。例えば、合成済み文字だと「だ」と表し、結合文字列だと「た+゛」と表すことがある。また、他の符号化された標準的な文字と実際的には同等な文字を符号化していたりと、様々な表現が混在している。このような様々な表現が混在した文字列をある基準で統一するのがunicode正規化です。正規化の方法は４種類定義されていますが、詳しくはUnicode正規化とはを参照してください。

上記のコードでは、正規表現０-９Ａ-Ｚａ-ｚ｡-ﾟで全角英数字や記号を見つけて、unicodedata.normalize('NFKC', c)でNFKCという正規化形式で正規化することで、半角英数字などに変換を行っています。

そして、最後に全角のハイフン（ー）を半角のハイフン（-）に変換しています。

余分なスペースの削除

def remove_extra_spaces(s):
    s = re.sub('[ 　]+', ' ', s)
    blocks = ''.join(('\u4E00-\u9FFF',  # CJK UNIFIED IDEOGRAPHS
                      '\u3040-\u309F',  # HIRAGANA
                      '\u30A0-\u30FF',  # KATAKANA
                      '\u3000-\u303F',  # CJK SYMBOLS AND PUNCTUATION
                      '\uFF00-\uFFEF'   # HALFWIDTH AND FULLWIDTH FORMS
                      ))
    basic_latin = '\u0000-\u007F'

    def remove_space_between(cls1, cls2, s):
        p = re.compile('([{}]) ([{}])'.format(cls1, cls2))
        while p.search(s):
            s = p.sub(r'\1\2', s)
        return s

    s = remove_space_between(blocks, blocks, s)
    s = remove_space_between(blocks, basic_latin, s)
    s = remove_space_between(basic_latin, blocks, s)
    return s

まず、全角・半角スペースが複数回連続する部分を正規表現で単一の半角スペースに置き換えています。

次にblocksとbasic_latinという変数に以下の正規表現が宣言されています。

正規表現	意味
\u4E00-\u9FFF	すべての漢字
\u3040-\u309F	全てのひらがな
\u30A0-\u30FF	全てのカタカナ
\u3000-\u303F	記号
\uFF00-\uFFEF	半角カタカナ全角英数字など
\u0000-\u007F	基本文字（制御文字、半角英数字・記号など）

それぞれの詳細はUnicodeを参照してください。

最後に、remove_space_between()関数にblocksとbasic_latinを組み合わせて渡すことで、文字と文字の間にスペースが入っていた場合に、スペースを削除しています。

neologdの正規化

def normalize_neologd(s):
    s = s.strip()
    s = unicode_normalize('０-９Ａ-Ｚａ-ｚ｡-ﾟ', s)

    def maketrans(f, t):
        return {ord(x): ord(y) for x, y in zip(f, t)}

    s = re.sub('[˗֊‐‑‒–⁃⁻₋−]+', '-', s)  # normalize hyphens
    s = re.sub('[﹣－ｰ—―─━ー]+', 'ー', s)  # normalize choonpus
    s = re.sub('[~∼∾〜〰～]', '', s)  # remove tildes
    s = s.translate(
        maketrans('!"#$%&\'()*+,-./:;<=>?@[¥]^_`{|}~｡､･｢｣',
              '！”＃＄％＆’（）＊＋，－．／：；＜＝＞？＠［￥］＾＿｀｛｜｝〜。、・「」'))

    s = remove_extra_spaces(s)
    s = unicode_normalize('！”＃＄％＆’（）＊＋，－．／：；＜＞？＠［￥］＾＿｀｛｜｝〜', s)  # keep ＝,・,「,」
    s = re.sub('[’]', '\'', s)
    s = re.sub('[”]', '"', s)
    return s

この部分はneologdで行っている正規化処理を表しています。まず、strip()で文字列の前後の空白を取り除き、unicode_normalize()でunicode正規化を行っています。次に、re.sub()を使って、ハイフンやチルダなどの記号を全角の記号に置き換えています。次に、余分なスペースを削除し、全角記号群をunicode正規化をしています。最後に、全角のクォート、ダブルクォートを半角英数字に置き換えています。

Web上のテキスト特有の処理

Web上のテキストは、URLやメールアドレス、罫線などを含んでいる場合があるため、これらを削除する前処理が必要です。以下のような正規表現でマッチングすることができます。

url_re = re.compile("https?://[\w/:%#\$&\?\(\)~\.=\+\-@]+")
mail_re = re.compile("[\w\-\.]+@[a-zA-Z0-9\-\.]+\.[a-zA-Z]+")
rule_line_re = re.compile("\-{2,}|ー{2,}|－{2,}"

参考

2019-08-27

sklearnを使ってtf-idfの勉強した

勉強

sklearnを使ってtf-idfの勉強をしたのでその内容をまとめておく。

tf-idf

tf-idfを説明するために、まずtf(term frequency)とidf(inverse document frequency)について説明します。

tfは文書 $d_j$ に単語 $t_i$ が出現する頻度のことです。次の式で表されます。

$\displaystyle tf(t_i,d_j)=\frac{文書d_j内での単語t_iの出現回数}{文書d_j内での全単語の出現回数}=\frac{f(t_i,d_j)}{\sum_{k} f(t_k,d_j)}$

tfはある単語の出現回数が多いほど大きい値となり、その単語の重要度は大きくなります。

一方で、idfは単語 $t_i$ が全文書 $N$ 中いくつの文書に含まれるかを示します。次の式で表されます。

$\displaystyle idf(t_i)=\log{}\left(\frac{全文書数N}{単語t_iが出現する文書数}\right)=\log{}\left(\frac{N}{df(t_i)}\right)$

しかし、文書中に存在しない単語のidfを計算しようとしたときに、分母が0になり、0除算が発生してしまうことから、分母に1を加えて計算することがあります。また、idfが0になるのを避けるために、全体に1を加えることもあります。 idfはある単語が他の文書に出現しているほど値は小さくなり、その単語の重要度は小さくなります。

tf-idfは文書集合中に含まれる単語の重要度をスコアリングするために利用され、 $tf \times idf$ で計算されます。そのため、tf-idfは、ある文書中で頻繁に出現する(tfが示す)が他の文書ではあまり出現しない(idfが示す)単語が重要度が高い単語としてスコアリングされます。

sklearn

sklearnはpythonの機械学習ライブラリでオープンソースとして公開されています。sklearnには、サポートベクターマシンやランダムフォレストなどの様々な機械学習の手法が実装されており、その中にtf-idfも実装されています。今回はこのsklearnを使ってtf-idfの計算を行いました。また、日本語の文章にtf-idfを適用する場合、予め形態素解析を行っておく必要があり、形態素解析にはMeCabを利用しました。

tfを計算する

次のような文章のtfを求める。この文章では、1文を1文書とみなしています。

今日はとんこつラーメンが食べたい気分だな。
でも味噌ラーメンもいいなあ。
味噌最高。

この文章をMeCabを使って形態素解析を行い、sklearnでtfを計算します。次にサンプルコード示します。

import MeCab
import codecs
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfTransformer

tagger = MeCab.Tagger('-Owakati')

with codecs.open("tfidf-doc0.txt", "r", "utf-8") as f:
    lines = f.read().splitlines()

corpus = [tagger.parse(line).strip() for line in lines]

vectorizer = CountVectorizer(token_pattern=u'(?u)\\b\\w+\\b')

tf = vectorizer.fit_transform(corpus)

# 分かち書きした単語を表示
print(vectorizer.get_feature_names())
# 単語の出現箇所
print(tf.toarray())

$ python tf.py
['いい', 'が', 'たい', 'だ', 'でも', 'とんこつ', 'な', 'なあ', 'は', 'も', 'ラーメン', '今日', '味噌', '最高', '気分', '食べ']
[[0 1 1 1 0 1 1 0 1 0 1 1 0 0 1 1]
 [1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0]
 [0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0]]

出力された行列は、行が何文書目（sample.txtにおける何行目）かを表していて、列がget_feature_names()で表示した単語に対応している。つまり、どの文書に何の単語が何回現れたか、を行列が表している。

コードの補足

CountVectorizer()
- tfを求めるクラス
- token_pattern: マッチするトークンを定義。デフォルトでは2文字以上のトークンしか扱わない
- token_pattern=u'(?u)\\b\\w+\\b'
  - これは2文字のトークンを除外しないような設定
  - 詳細：(?u):unicodeマッチング、\b:単語の先頭末尾の空白文字、\w:unicode一文字、+:直前の文字の繰り返し

tf-idfを求める

次の2つの分かち書きされた文書のtf-idfを計算する。

文書A: 無料 ランチ ラーメン ランチ
文書B: ランチ ラーメン クーポン

この文書は、wakatiというディレクトリ配下にそれぞれファイルを作っているものとする。 wakati配下のファイルを読み込み、文書集合におけるtfidfを単語ごとに計算する。

import os
from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfTransformer

vectorizer = CountVectorizer(input='filename', token_pattern=u'(?u)\\b\\w+\\b')

files = ['wakati/' + path for path in os.listdir('wakati')]

tf_vec = vectorizer.fit_transform(files).toarray()

features = vectorizer.get_feature_names()
print("features:\n{}".format(features))
print("tf:\n{}".format(tf_vec))

tfidf_transformer = TfidfTransformer(norm=None, sublinear_tf=False)

idf = tfidf_transformer.fit(tf_vec)

print("idf:\n{}".format(idf.idf_))

tfidf = tfidf_transformer.fit_transform(tf_vec)

print("tfidf:\n{}".format(tfidf.toarray()))

$ python tfidf.py
features:
['クーポン', 'ランチ', 'ラーメン', '無料']
tf:
[[1 1 1 0]
 [0 2 1 1]]
idf:
[1.40546511  1.         1.         1.40546511]
tfidf:
[[1.40546511  1.         1.         0.        ]
 [0.         2.         1.         1.40546511]]

出力結果から、まずidfが単語ごとに計算されていることが分かります。次にtfとidfのベクトルの積をとった値がtfidfとして計算されていることが分かります。ここで、tfidfを計算するクラスTfidfTransformerは設定のパラメータによって、tfidfの計算式が変化することに注意したい。今回の場合だとnorm=Noneを渡しているが、これはtfidfを正規化するかどうかの設定です。norm=l2とやると最後に結果を正規化します（デフォルト）。また、sublinear_tf=Falseはtfの値を対数で計算するかどうかです。Trueの場合はtfは対数で計算されます。計算式などの詳細はこちらをご覧ください。

コードの補足

TfidfTransformer(norm='l2', sublinear_tf=True)
- tf-idfを計算するクラス
- sublinear_tf: tfをlogを使って計算するかどうか
- norm: l2でl2正規化を行う。noneで何もしない。
  - l2正規化とはベクトルを単位ベクトルに変換すること
- smooth_idf: idfの計算方法が変化する。詳しくはsklearnのソースコードを参照
  - Trueだと文書中で発生しない単語を計算しようとしたときに分母が0になることによる0除算が発生しない

まとめ

今回はtfidfについてsklearnやMeCabを使って勉強しました。今回用意した文章は短い文章だったので、形態素解析が上手くいくものばかりでしたが、実際の文章に適用すると形態素解析が上手く行かない場合がありそうです。例えば、Web上の文書の場合、文章中にURLやメールアドレスが含まれていることが考えられます。そのため、実際の文書に適用するには、形態素解析の前処理について考える必要が出てきそうです。

参考

2019-07-29

COMPSAC2019で研究発表をしてきた

研究国際学会海外

f:id:komei22:20190729175943j:plain

7/15日から5日間に渡って開催されたCOMPSAC2019@ミルウォーキーで研究発表をしてきました。この発表は僕にとって最初の国際学会での口頭発表であり、学ぶことも多かったので、参加までやったことや参加しての感想を書き留めておこうと思います。

f:id:komei22:20190729180117j:plain

発表概要

発表内容に関しては以前投稿したエントリ第2回WSA研で「Webアプリケーションテストを用いたSQLクエリのホワイトリスト自動作成」について発表してきました - こーめいのメモ帳で書いた内容に実験を追加したり議論を再整理した内容となりますが、前回のエントリから変わっている部分も多いので、概要をまとめ直しておきます。

Webサービスでは、データベース上に保管された機密情報を保護することは重要です。しかし、攻撃者はWebアプリケーションの脆弱性をはじめとして、様々な手段を用いて機密情報の窃取を試みます。このような攻撃は、開発者の想定外のクエリ（不正クエリ）を発行することで実施されます。そのため、不正クエリの発行を検知する仕組みが必要となります。

不正クエリへの対策として、Webアプリケーションが発行する正常なクエリを手動でホワイトリストに定義し、リストにないクエリを検知する方法があります。しかし、大規模なWebアプリケーションでは、発行されるクエリ数が膨大となるため、全てのクエリをリストに定義することは難しくなります。また、Webアプリケーションの改修によって発行クエリは変化するため、ホワイトリストは継続的に更新する必要があります。このような運用者への負荷を低減するために、ホワイトリストを自動で作成する手法が2種類、提案されています。 1つ目は、Webサービスのユーザがサービスを利用する過程で発行されるクエリを用いてホワイトリストを作成します。しかし、この手法はクエリを収集している間は検知を行えません。 2つ目は、WebアプリケーションのSQLを発行する処理の解析を行い、発行されるクエリのパターンを列挙しホワイトリストを作成します。しかし、この手法は、Webサービスが複数の実装言語やフレームワークで構成されていた場合、それぞれのWebアプリケーションに対して手法を実装する必要があるため、実装の工数が多くなります。これらの課題を解決するためには、Webアプリケーションが稼働する前に、Webアプリケーションの実装に依存せず、ホワイトリストを作成する必要があります。

そこで本論文では、Webアプリケーションのテスト実行中に発行されるクエリからホワイトリストを作成する手法を提案しています。提案手法では、Webアプリケーション稼働前のテストの段階でホワイトリストを作成できるため、稼働後即座に不正クエリを検知できます。また、データベースプロキシでテスト時の発行クエリを収集しホワイトリストを作成するため、Webアプリケーションの実装に依存せずホワイトリストを作成できます。

提案手法の検知精度を評価するために、実環境のクエリログを用いて実験を行いました。実験から、提案手法では、正常なクエリを異常（False positive）、不正なクエリを正常（False negative）と判断する誤検知が発生することが分かりました。 False positiveは、テストケースの不足やテスト時のデータベースへのアクセス省略により発生することを確認しました。 False positiveへの対処としては、ホワイトリストによる検知を適用するテーブルを機密情報が保管されたテーブルに限定することが挙げられます。適用するテーブルを限定することで、検知対象となるクエリ数を削減でき、結果的にFalse positiveを低減できると考えられます。また、False negativeはテスト時のみ発行されるクエリによって発生することを確認しました。テスト時のみ発行されるクエリには、機密情報の全件削除を行うようなクエリが含まれていました。このクエリへの対処として、影響範囲が大きいクエリはブラックリストに予め定義しておき、ホワイトリストと併用することで多層的に検知できると考えられます。

スライド

当日の発表

f:id:komei22:20190729182159j:plain — 発表の様子

僕の発表は1日目の午後でまだ時差ボケが残っていましたが、かなり緊張していて直前まで発表資料や原稿を読み直していたりしたので全く眠くはなかったです。実は発表直前に、接続チェックが上手くいかない、僕の前の発表者が来なくて発表順が繰り上がるなどのトラブルがありさらに目が覚めました。また、発表中もミラーリング設定になっていて発表原稿が見れない！、マウスポインタがどっかに行って発表原稿がスクロールできない！などのトラブルがありましたが、なんとか発表を時間内に乗り切りることができました。発表練習たくさんしておいてよかった。発表後にいただいた質問内容を見た感じ、発表の要点はしっかりと伝わっていて嬉しかったです。

一方で、質疑なのですが、僕の英語力は高くないので、質疑の時間で質問内容を解釈することができず的はずれな回答を返してしまったことが反省点です。質問内容を曖昧な解釈のままにせずに、ちゃんと聞き返すことや「自分はここまで理解できました」、「質問の内容はこういうことでいいですか？」など相手とのコミュニケーションを取ることが重要だと思いました。また、ネイティブの方の英語を聞き取るのが僕には難しかったので、英語のリスニング力を付ける必要があると感じました。

会場の様子

f:id:komei22:20190729182518j:plain — マーケット大学と僕

会場であるマーケット大学は緑がたくさんあってきれいなキャンパスでした。会場には常にコーヒーとクッキーが置かれていて、お昼になるとランチボックスが運ばれてきていました。クッキーはホテルにチェックインしたときもカウンターで頂いたのですが、なにか特別な意味があったりするのかな？

セッションでは、様々な分野の発表が行われていたので、知見を広げたり、英語での発表や質疑のやり方に注力して参加しました。また、一緒に参加した方とお話をして発表で聞き逃した内容の補足や議論をさせていただきました。その議論の中で一番印象に残っているのが、Is a Smarter World a Better World? Key Questions at the Intersection of Technology, Intelligence, and EthicsというKeynoteで話された「Enhance decision-making capacity」という言葉です。この言葉は日本語でいうと、「意思決定能力を強化する」という意味で、僕たちは技術を使ってこれを達成できているのか？という問いです。この言葉を聞いて僕が一番に思い浮かべたのは最近読んだ推薦システムの論文でした。その論文では課題感として、履歴などの行動の履歴をもとにした推薦は、ユーザに与える情報の領域を狭めていて（フィルターバブル）、ユーザに新しい発見や知識を与えることができないと述べられていました。これはまさに「Enhance decision-making capacity」できていない例だと思い、すごく納得感がありました。技術を使って自動化などが進んでいくと人間の操作が減り便利になっていく反面、人間側の意思決定の広がりが制限されてしまう場合も存在することが僕が新しく得た知見です。

おわりに

今回のCOMPSAC2019への参加によって、僕は国際学会への参加の心理的ハードルを下げることができたと思います。僕の拙い英語であっても、真摯に発表を聞いて議論をしてくれることは大変ありがたかったです。最後に、ミルウォーキー楽しかったです！

おまけ

国際学会のバンケットで行ったハーレーダビットソンミュージアムが楽しかったので僕が調子に乗ってる写真を載せておきます。 f:id:komei22:20190803105726j:plain f:id:komei22:20190803105734j:plain f:id:komei22:20190803105742j:plain f:id:komei22:20190803105756j:plain

2019-06-04

Table driven testについて調べた

勉強

sql-maskのPRのレビューでgotestsというものを紹介していただき，Table driven testが気になったので調べました．今回は調べた内容をTable driven testでのテストコードの書き方を例とともに書き留めておきたいと思います．また，Table driven testでsqdとsql-maskのテストコードをリファクタリングしたので，感想をメモしておきたいと思います．

Table driven testについて

Table driven testはGoのテストプラクティスの一つで，テーブル（配列）に入力値と期待する結果のセット（テストケース）を定義します．このテーブルにはテスト名などの追加情報が含まれることもあります．このテストケースを記述したテーブルをループ処理によって各項目ごとにテストを行います．Golangでは，gotestsを利用することで，Table driven testに基づいたテーブルとテスト処理の雛形を作成することができます．

Table driven testでのテストコードの書き方

以下のようなfizzbuzzの処理を行うメソッドに対してgotestsを使ってテストを書いていきたいと思います．

package main

import (
    "fmt"
    "strconv"
)

func main() {
    for i := 1; i <= 50; i++ {
        fmt.Println(fizzbuzz(i))
    }
}

func fizzbuzz(i int) string {
    if i%15 == 0 {
        return "FizzBuzz"
    } else if i%3 == 0 {
        return "Fizz"
    } else if i%5 == 0 {
        return "Buzz"
    } else {
        return strconv.Itoa(i)
    }
}

このコードの fizzbuzz()に対して， gotestsを適用すると以下の雛形が出力されます．

package main

import "testing"

func Test_fizzbuzz(t *testing.T) {
    type args struct {
        i int
    }
    tests := []struct {
        name string
        args args
        want string
    }{
        // TODO: Add test cases.
    }
    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            if got := fizzbuzz(tt.args.i); got != tt.want {
                t.Errorf("fizzbuzz() = %v, want %v", got, tt.want)
            }
        })
    }
}

この雛形に従ってテストケースを追記していきます．

func Test_fizzbuzz(t *testing.T) {
    type args struct {
        i int
    }
    tests := []struct {
        name string
        args args
        want string
    }{
        {
            name: "Return number string",
            args: args{i: 1},
            want: "1",
        },
        {
            name: `Return "Fizz"`,
            args: args{i: 3},
            want: "Fizz",
        },
        {
            name: `Return "Buzz"`,
            args: args{i: 5},
            want: "Buzz",
        },
        {
            name: `Return "FizzBuzz"`,
            args: args{i: 15},
            want: "FizzBuzz",
        },
    }
    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            if got := fizzbuzz(tt.args.i); got != tt.want {
                t.Errorf("fizzbuzz() = %v, want %v", got, tt.want)
            }
        })
    }
}

Table driven testを書いてみて思ったこと

このTable driven testを使って，sqdとsql-maskのテストコードをリファクタリングしました．その過程でTable driven testを利用することで以下のような利点があると思いました．

テストケースの可読性が向上し管理しやすくなる
何のテスト(name)をするために，何を入力(args)して，どういう出力（want）が欲しいのかが明確になる
テーブルをループしてテストするので，テストの処理やエラー処理が共通化される

また，Table driven testが書きにくい場合は以下のようなことに原因があると感じました．

入出力が多くて複雑
出力に影響を与える要素が入力以外に含まれている
- メソッドが利用する構造体やその変数，グローバル変数など

1.はメソッドの切り分けが適切にできていない可能性があると思いました．2.は依存関係が多くなっていることからコードが複雑化しており，必要な依存関係かを確認する必要があると思いました．このようにTable driven testを使うことで，これらの問題を発見でき解消するきっかけになると思いました．