分類問題
内山将夫@NICT
mutiyama@nict.go.jp

1

分類問題とは何か？
非常に一般的には，入力 x に対して，出力 y を与えること．自然言語処理においては，y は名義尺度であることが多い．
分類問題の例• 2 値分類問題• 多値分類問題• 複雑な出力に対する分類問題(内山は，分類問題については，それほど 良く知らないため，そのつもりで，この資料を読んで下さい．)
4 つの尺度について簡単に• 名義尺度 (黒か白かなど ．異なるクラスは互いに異なるということが言える)• 順序尺度 (1 番，2 番，．
．
．順番があるので，大小比較ができる)• 間隔尺度 (温度など ．間隔が同じなので，足し算と引き算ができる)• 比尺度 (長さなど ．0 点が定まるので，かけ算と割り算ができる)

2

テキスト に関係する 2 値分類問題の例• マーケティングにおいて，ある製品について，自由回答アンケートをとったとき，あるアンケート x が，その製品について– 不満を述べているか– 述べていないかを判定する．これを知ることは，ユーザーの不満を解消し，満足度を向上させるために，必要である．

• メールについて，– 迷惑メールか– そうでないかを判定する．これは，現代社会において，必須である．

3

多値分類の例• ある記事があったとして，それが– 経済– 政治– スポーツ...のいずれのジャンルに属するかを判定する．これは，Web 上から様々な記事を集め，それらから新聞を作りたいときなどに必要である．

• Web ページを記述するには，様々な言語がある．それらの言語のうちで，当該のページは，– 日本語で記述されているか– 英語で記述されているか– 中国語で記述されているか ...
を判定する．これは，Web ブラウザなどで，正しくページを表示するために必要である．

4

複雑な出力の分類• 構文解析等では，入力した文の構文構造という，複雑な出力が必要になる
自然言語処理や生物情報学等では，複雑な出力の分類が必要になる．

5

2 値分類問題の表現形式の例• 入力ベクトル x = [x1, x2, ..., xn−1]
• 出力




+1 望みのクラスのとき
y = 
 −1 それ以外のとき• 重みベクトル w = [w1, w2, ...., wn−1]• 閾値 b判定法
w · x = Pn−1
i=1 wi xi ≥ b のとき +1 を出力し，w · x < b のとき −1 を出力する．
説明のときには，b を特別扱いすると面倒なので，xn =−1, wn = b とすることにより，w · x ≥ 0 のとき，+1 を出力し，w · x < 0 のとき −1 を出力する．
つまり• 入力ベクトル x• 出力値 y• 重みベクトル w
により (線形な問題については )2 値分類を定式化できる．

6

迷惑メールの判定
分類対象のメール x について，そのベクトル表現を x =[x1, x2, x3] とする．ここで，

1 if 「お金」という言葉を含む
 0 上記以外

x1 = 

1 if 何らかの URL を含む
x2 = 
 0 上記以外


1 if ac.jp アドレスから発信されている
x3 = 
 0 上記以外のとき w = [1, 1, −2] とする．w · x ≥ 0 のとき，迷惑メールと判定する．
さて，• x1 = [1, 0, 1], x2 = [1, 1, 0]とする．つまり，x1 は，「お金」という言葉を含み，「 ac.jp 」から発信されている．また，x2 は，「 お金」という言葉を含み，何らかの URL がある．
このとき w · x1 = 1 − 2 = −1, w · x2 = 1 + 1 = 2 である．つまり，x1 は迷惑メールでなく，x2 は迷惑メールであると判定する．

7

分類器を使うときに注意しないといけないこと
分類器の性能は 100%ではないので，誤ったときにど うするかを考えておかないといけない．誤りには次の 2 通りがある• 誤検出：普通のメールを迷惑メールとして判定する
こと• 見逃し：迷惑メールを普通のメールと判定すること
迷惑メールの判定のときには，誤検出をなるべく少なくする必要がある．一方では，見逃しは多少は許容できる．
なぜなら，普通のメールが迷惑メールとして誤検出されるとすると，そのメールは，読まれない可能性が高いからである．もし ，そのメールに重要なことが書いてあったとすると，それが読まれないことによる損失は，多大なものになる可能性がある．
一方，迷惑メールを普通のメールとして見逃して，ユーザーに配送したときには，ユーザーは，即座に，そのメールが迷惑メールであることを判定できる可能性が高い．そのため，迷惑メールがユーザーに配送されても，その量が多くなければ，それほどは困らない．
誤検出と見逃しのどちらを重視すべきかは，アプリケーションにより異なる．
8

分類問題において何が問題か• ど ういう分類問題を解くべきか．
手持ちの問題があるとして，それをどのようにして分類問題として定式化するか．

• 入力をどのようなベクトルとして表現するか• 重みベクトルをど う設定するか

9

手持ちの問題をどう分類問題として定式化するか• 実際の問題は，普通は，非常に複雑である• 一方，2 値分類問題は，入力を +1 か -1 の 2 値にわけるだけの単純な問題にしか適用できない• そのため，2 値分類問題を複雑な問題に適用するためには，元の問題の中で適切な抽象化をする必要がある．

10

例：アマゾンのレビューより「ぐりとぐら」は子供の頃に叔母からプレゼントされた絵本の中の一冊。
「しろくまちゃんのほっとけーき」と並んで料理する楽しさに目覚めるきっかけになりました。母に毎日「読んで〜」とせがみ、2 歳半からはお菓子作りの好きな父と一緒に台所で手伝うように…。懐かし くて大人になった今でももう一度読みたくなって買ってしまいました。リズムや美味しい匂いがしてきそうな絵が何度読んでも楽しいです。子供ができたらその子にもぜひ読んであげたい…私の大切な絵本です。
(By 蜜花)================のような書評について，これは，結局，• 「ぐ りとぐら」を勧めているのか，そうでないのかを判定するのが，2 値分類問題である．これだけでは，このレビューに含まれる情報の極くわずかしか伝えていないのは，間違いないと思われる．しかし ，「 勧めているのか」「いないのか」という重要情報が取り出されることも確かである．
一方，迷惑メールの判定のときには，対象が迷惑メー
ルかど うかさえ判定できれば ，十分である．迷惑メールの内容には興味はない．
分類問題を取り扱うときには，それにより，取り扱いたい問題が適切に取り扱えているかに注意する必要がある．
11

入力ベクト ル x をどうつくるかベクトルの要素としては，任意のものが考えられるが，テキストが入力のときには，単語 i が入力テキスト x 中に存在するときに，xi = 1 とし ，そうでないときに，xi = 0 としたり，あるいは，良く使われるものとして，

xi = tfi × idfiがある．ただし，ni を単語 i が，入力テキスト中に出現する回数としたとき，tfi = niやtfi = log(ni + 1)としたり，N を訓練データにおける文書の総数とし，diを単語 i が出現する文書の数とするとき，Nidfi = log
diが利用されることが多い．

12

tf × idf について
tf × idf には，さまざ まな変種があるが，その源流は非常に古い．idf は，以下がオリジナルである．
• Karen Spärck Jones, A statistical interpretation of term
specificity and its application in retrieval. Journal ofDocumentation 28, 11-21, 1972.
また tf については，以下に記述があるらしい (上記論文からの孫引き)．

• Salton, G., 1968. Automatic Information Organization
and Retrieval, McGraw-Hill
tf × idf は，テキスト中の単語の重要度を表すと考えられている．tf は，テキスト中に出現する回数が多い単語ほど 大きくなる．idf は，コーパス全体で出現する回数が小さい単語ほど 大きくなる．したがって，tf × idf は，コーパス中では余り出現しないが，そのテキストに限っては，良く出現するような単語で大きくなる．このような単語は，そのテキストのキーワード と言えるだろう．

13

w をどう設定するか問題が定義でき，入力がベクトルに変換できれば，あとは重み w があれば，分類問題を解くことができる．この重み w は，訓練データから決めることができる．
一般的に(x1, y1), (x2, y2), ...
が訓練データとして与えられたとき，そこから，w を学習することが考えられる．
様々な学習法があるが，簡単なものとして，• Naive Bayes モデル• パーセプトロンを説明する．

14

Naive Bayes モデル
Naive Bayes では，w = [1, 1, ..., 1] と固定されていて，xを工夫していると考えることができる．
Naive Bayes による 2 値分類器は以下のように導出可能
である．
P (+1|x) と P (−1|x) を，入力 x を条件とする，クラス +1と −1 の確率とする．このとき，
P (+1|x) ≥ P (−1|x)すなわち，P (+1|x)log≥0
P (−1|x)のときには，+1 と判定する．これは，次のように展開できる．

15

Naive Bayes モデル
P (+1|x)P (x| + 1)P (+1)
log
= log
P (−1|x)P (x| − 1)P (−1)
ここで，x 中に単語 i が ni 回出現するとすると，P (x| + 1) =Yi

P (wi| + 1)ni

ただし，P (wi|+1) =クラスが +1 の訓練テキスト中での wi の総頻度
クラスが +1 の訓練テキストの総単語数

これらは，P (x| − 1) や P (wi| − 1) についても同様．よって，log

P (wi| + 1)
P (+1)
P (+1|x)X= ni log+ logi
P (−1|x)
P (wi| − 1)
P (−1)(+1)
は訓練テキスト中での +1 のテキストと −1 のテlog PP (−1)
キストの比から計算可能であるが，通常は，この項は，テストにおいては無視する．その理由は，テストにおける +1 と −1 の比は，訓練における比と違うことが多いからである．しかし ，もし ，両者の比が同じであれば ，この項を残しておいた方が良い．以下では，この項は残しておかないものとする．

16

Naive Bayes モデル
以上より，

w = [1, 1, ..., 1]
x = [x1, x2, ..., xn]
P (wi| + 1)
xi = ni log
P (wi| − 1)とすれば，P (x| + 1)
P (+1|x)
P (wi| + 1)
= log
∼ log
w·x = ni log
i
P (wi| − 1)
P (x| − 1)
P (−1|x)Xであり，w · x ≥ 0 のときに，クラス +1 が事後確率が高くなるので，クラス +1 を選択する．
Naive Bayes という名の由来は，

P (x| + 1) =Yi

P (wi| + 1)niというように，単語間の条件付きの独立性を仮定しているところからのようである．
Naive Bayes モデルは，簡単で，かつ，性能も，他の複雑なモデルと比べて，大きく劣るというわけではない．
また，訓練データが少ないときには，他のモデルよりも良い性能を示すこともある．そのため，Naive Bayesはベースラインとして使われることが多い．

17

スムージングについて
P (wi|+1) =クラスが +1 の訓練テキスト中での wi の総頻度
クラスが +1 の訓練テキストの総単語数としたが，これでは，クラス +1 にはでたが，−1 にはでない単語などの扱いに苦労する． xi の重みとしては，
P (wi| + 1)
xi = ni log
P (wi| − 1)なので，スムージングなしだと，n(wi| + 1) を，クラスが +1 の訓練テキスト中での wi の総頻度としてn(wi| + 1)
xi = ni log
n(wi| − 1)となる．これにスムージングをするとすると，n(wi| + 1) + 0.5
xi = ni logn(wi| − 1) + 0.5とするとかが考えられる．

18

パーセプト ロン
x を Naive Bayes により，xi = ni log

P (wi| + 1)
P (wi| − 1)としたとする．次に，w を訓練することが考えられる．
もし，Naive Bayes モデルにおける独立性の仮定が正しければ，w の最適値は，[1, 1, 1, .., 1] である．しかし，実際には，独立性の仮定は，正しくないことが多いので，重みを適切に変更することにより，分類精度が向上する可能性が高い．
重みの推定方法には，• SVM (Support Vector Machine)• Boosting• Logistic regression• Perceptronなどの様々な方法があるが，ここでは，簡単で，かつ，性能もほどほどに良く，複雑な問題にも応用が可能なパーセプトロンについて説明する．

19

パーセプト ロンのアルゴリズム
訓練データ (x1, y1), (x2, y2), ..., (xn, yn) に対して，T 回の繰り返しにより，重み w を推定する場合

w = [0, 0, ...]
for t = 1..Tfor i = 1..nŷ = sign(w · xi)
if yi 6= ŷ thenw = w + yi · xi
end
endendyi 6= ŷ のときにのみ，w を変更する．さて，yi = 1 のときに，重みが変更されたとすると，w0 を新しい重みとすると，w0 · xi = (w + x) · x = w · x + x · x．つまり，+1 のクラスを誤って，−1 と分類した場合には，wを w0 に更新することにより，x · x > 0 のだけの重みが加算されることになり，少しだけ，+1 に有利な重みになる．
同様に，yi = −1 のときには，w0 · xi = (w − x) · x =w · x − x · x なので，x · x だけ少なくなり，クラス −1に分類されやすくなる．

20

平均化したパーセプト ロン
w = [0, 0, ...]
v = [0, 0, ...]
for t = 1..Tfor i = 1..nŷ = sign(w · xi)
if yi 6= ŷ thenw = w + yi · xi
endv+ = w
endendv
w = nT

(A)

(B)

(C)

(A),(B),(C) の部分を除くと，最初のアルゴ リズムと変わらない．しかし ，こうすることにより，性能が向上することが知られている．
これは，全ての訓練データにおける重みの平均を重みとしている．
平均化しないパーセプトロンの性能は，それほど 高くないが，平均化することにより，性能が高くなることが知られている．
一番性能が高い類器には性能は及ばないが，それに近い性能がでる．また，非常に簡単なモデルなので，ハードウェア化もできるため，大量データを処理したい場合には，有効であると思われる．
21多値分類
多値分類は，2 値分類器を利用するとできる．
one-vs-rest 法
n 個のクラスがあるときには，n 個の 2 値分類問題を考える．w(i) が，クラス i とそれ以外のクラスとを分類す
る重みベクトルとすると，

arg max w(i) · xiなる．クラス i に分類する．このとき，w(i) · w(i) = 1 となるように，重みベクトルの長さを正規化しておく．
pairwise 法
n 個のクラスがあるときに，n(n−1)
個の 2 値分類問題を考2える．w(i,j) が，クラス i と j を分類する重みベクトルとすると w(i,j) · x > 0 のとき i に分類されるとして，w(i,j) ·x < 0 は w(j,i) = −w(i,j) と考えて，w(j,i) · x > 0 とす
ると，
Xarg max [w(i,j) · x > 0]ij

ただし，[事象] は事象が正のときに 1 ，そうでないときに 0.
これは，クラス i のスコアとして，クラス i とその他のクラスとを全部比較して，クラス i として判定された個数を利用する．

22

複雑な出力の分類
入力が x のとき，その出力の候補を Gen(x) とする．y ∈Gen(x) について，ベクトル Φ(x, y) を割当てられるとする．このとき，ŷ = arg

max w · Φ(x, y)y∈Gen(x)なる ŷ を出力とする．
つまり，複雑な出力については，• まず，解候補集合 Gen(x) を得る．
• 次に，スコアが最大の解を得る．という 2 段階のステップを踏む．その理由は，出力が複雑になると，解候補の数が非常に多くなり，絞り込みをしてからでないと，上手くいかないからである．

23

複雑な出力と，そのベクト ル化の例
たとえば，入力 x がthe man saw the dogのとき，出力候補として• y1 = the/D man/N saw/V the/D dog/N• y2 = the/D man/N saw/N the/D dog/Nの 2 つがあるとする．このとき，• 第 1 要素を D の数
• 第 2 要素を N の数
• 第 3 要素を V の数とすると，• Φ(x, y1) = [2, 2, 1]• Φ(x, y1) = [2, 3, 0]
である．このとき，重みとして，文には V が必ず必要なので，少し，それの重みを重くしたベクトル w = [1, 1, 2]を利用するとすると，w · Φ(x, y1) = 6 と w · Φ(x, y2) = 5
なので，y1 が優先される．

24平均化したパーセプト ロン
w = [0, 0, ...]
v = [0, 0, ...]
for t = 1..Tfor i = 1..nŷ = arg maxy∈Gen(x) w · Φ(x, y)
if yi 6= ŷ thenw = w + Φ(xi, yi) − Φ(xi, ŷ)
endv+ = w
endendv
w = nT
2 値分類問題と，ほとんど 同じ 方法で学習できることがわかる．Φ(xi, yi) − Φ(xi, ŷ) に注目すると，あるベクトル要素について，Φ(xi, yi) における値の方が，予測値Φ(xi, ŷ) よりも大きければ，その要素については，差分だけを w に加える．これにより，予測値よりも少し 重みを加算する．

25

構造が複雑な問題の例• 形態素解析• 構文解析
• 機械翻訳
これらについても，入力 x と出力 y の組をベクトルΦ(x, y) で表現することができれば，機械学習により，重み w を適切に調整することができる．
しかし，この方法により調整した重み w を利用したとしても，元々の解候補 Gen(x) にある解を劇的に向上することはできないようで，少し向上するくらいのようだ．
その理由は，出力が複雑になると，そもそも，それをベクトル表現したときに，その表現が適切かど うかという問題がある．さらに，出力が複雑になると解空間が非常に大きくなるので，Gen(x) によりカバーできる解候補が解空間に比べて，相対的に少なくもなる．

26

まとめ
訓練データ (x1, y1), (x2, y2), ... から重みベクトル w を推定する方法として，パーセプトロンを紹介した．
難しい問題• 手持ちの問題を，意味のある分類問題として定式化すること• 訓練データを収集すること課題• テキスト処理に関係する面白い分類問題を探してみて下さい．
• 分類問題のためのソフトウェアなどを利用して，その問題を解いて下さい．

27

分類問題のためのソフト ウェア• Weka (http://www.cs.waikato.ac.nz/ml/weka/)• Mallet (http://mallet.cs.umass.edu/index.php/Main Page)• SVMlight (http://svmlight.joachims.org/)• libsvm (http://www.csie.ntu.edu.tw/˜cjlin/libsvm/)• BBR (http://www.stat.rutgers.edu/˜madigan/BBR/)• BACT (http://chasen.org/˜taku/software/bact/)28