決定木とサポートベクターマシン：分ける手法の考え方

ねらい

このレッスンでは、教師あり学習の代表的な手法のうち、データを分けて予測する2つを学びます。

基礎

質問を重ねて分ける決定木（けっていぎ）と、境界線でくっきり分けるサポートベクターマシンの大枠を健康診断の例でつかみます。

1. 質問の枝分かれで結論にたどり着く決定木

1つ目の分け方が、決定木です。質問を次々に重ねて、枝分かれをたどりながら結論に向かう手法です。

最初の質問が「熱は38度以上ですか」だとします。答えがはいの人といいえの人で、データは2つに分かれます。はいの側ではさらに「せきは出ますか」とたずね、また2つに分かれます。質問のたびに枝が増えていく形は、さかさまにした木のように見えます。そのため決定木と呼ばれます。

決定木の強みは、判断の道すじを目で追えることです。どの質問にどう答えたからこの結論になった、と人に説明できます。また、数値を当てる回帰問題にも、種類を当てる分類問題にも使えます。

ここで、機械の側の事情に目を向けます。健康診断の問診で医師が最初に熱の有無をたずねるのは、その一問が診断を大きく前へ進めると経験から知っているからです。機械には経験も勘もなく、あるのは過去のデータと計算の力だけです。数えきれない質問の候補の中から、機械は何を手がかりに最初の一問を選ぶのでしょうか。枝分かれの良し悪しは、どの質問を選ぶかで決まります。機械は経験も勘も持たないのに、何を手がかりに質問を選ぶのでしょうか。答えの核心を先に言うと、機械は、分けたあとの2つのグループが最もきれいにそろう質問を計算で選び出しています。この計算の中身が、深掘り層の主題になります。

2. 集まりの間に余裕のある境界線を引くサポートベクターマシン

2つ目の分け方が、サポートベクターマシン（SVM）です。質問を重ねる代わりに、データを地図のように並べて、種類の違う集まりの間に境界線を1本引きます。

検査値を軸にした地図の上に、過去の診断データを点で置いたとします。健康な人の点が集まる一画と、病気の人の点が集まる一画に分かれました。サポートベクターマシンは、この2つの集まりの間を通る境界線を引きます。新しい人が来たら、その人の点が線のどちら側に落ちるかで判定します。

大切なのは、線の引き方です。2つの集まりを分けられる線は何本でも引けます。サポートベクターマシンはその中から、両側の集まりからできるだけ離れた、真ん中を通る線を選びます。

理由は単純です。集まりのすれすれを通る線は、新しいデータが少しずれただけで判定を間違えます。余裕のある線なら、多少のずれにも持ちこたえられます。線の引き方にも、決定木の質問選びと同じように、はっきりした計算の基準があるのです。

ここまでの要点

• 決定木は、質問を重ねた枝分かれで判断し、道すじを目で追えます。
• 決定木の質問は当てずっぽうではなく、分けたあとが最もきれいにそろうものが計算で選ばれます。
• サポートベクターマシンは、2つの集まりから最も離れた、余裕のある境界線を引きます。

まずは全体像をつかめれば十分という人は、ここで区切って大丈夫です。「決定木は計算で選んだ質問の枝分かれ、サポートベクターマシンは余裕を最大にした境界線」と押さえられていれば、この先の深掘りに進む土台はできています。

発展

ここからは、決定木が最適な質問を選ぶ計算の基準と、直線では分けられないデータまで分けてしまうサポートベクターマシンの数理的な工夫を掘り下げます。

3. 決定木が最適な質問を選ぶ基準になる不純度

決定木の枝分かれは、質問しだいで良くも悪くもなります。コンピュータは、この質問を当てずっぽうで選んでいません。候補になる質問を片っ端から試し、その結果を数値で比べています。

比べる基準は、分けたあとのグループのごちゃ混ぜ具合です。1つのグループに病気の人と健康な人が半々で混ざっていれば、ごちゃ混ぜの度合いは最大になります。全員がどちらか一方にそろっていれば、度合いはゼロです。この混ざり具合を数値で表したものを不純度（ふじゅんど）と呼びます。

不純度のはかり方にはいくつかの決め方があり、よく使われるのがジニ不純度（ジニふじゅんど）です。式で書くと、ジニ不純度 ＝ 1 − （各区分の割合を二乗したものの合計）となります。読み下すと、そのグループの中で各区分が占める割合をそれぞれ二乗して足し合わせ、その合計を1から引く、という意味です。全員が同じ区分なら割合は1で、二乗しても1のまま、1から引いてゼロになります。病気と健康が半々なら、0.5の二乗が2つで合計0.5、1から引いて0.5になります。これが区分が2つのときのいちばん大きな値です。混ざっているほど大きく、そろっているほどゼロに近づくという、言葉で述べたとおりの動きをします。

たとえば「熱は38度以上ですか」という質問でデータを2つに分けたとします。はい側がほとんど病気の人に、いいえ側がほとんど健康な人になったなら、不純度は分ける前より大きく下がっています。分けたあとも両側が半々のままなら、その質問は診断を少しも前へ進めていません。

決定木は、候補の質問ごとに、分けたあとの不純度がどれだけ下がるかを計算します。そのうえで、不純度が最も下がる質問を1つ選びます。分かれた先のそれぞれのグループでも同じ計算を繰り返し、枝を伸ばしていきます。

医師の経験と勘に見えた良い質問選びの正体は、不純度の減少という一貫した計算です。「機械は何を手がかりに質問を選ぶのか」という問いには、この計算が答えになります。

4. 境界線の位置を決めるマージン最大化とサポートベクトル

サポートベクターマシンに話を移します。基礎層で見た境界線の余裕には、マージンという名前が付いています。マージンとは、境界線と、それに最も近いデータ点との間の余白のことです。

サポートベクターマシンは、この余白をできるだけ大きく取るように境界線の位置を決めます。この考え方をマージン最大化と呼びます。余白の大きい境界線ほど、新しいデータが多少ずれて現れても正しい側にとどめられるからです。

余白のふちに接する、境界線に最も近いデータ点をサポートベクトルと呼びます。境界線の位置は、このサポートベクトルだけで決まります。集まりの奥のほうにある点は、境界の決定に影響しません。少数の点が境界線を支えているので、サポートベクターマシンという名前が付いています。

理解の確認

マージンは境界線と最も近い点との余白、マージン最大化はその余白を最大にする考え方です。境界線を支えているのは、余白のふちに接する少数のサポートベクトルだけです。この2つの関係を自分の言葉で言い直せるか、確かめてみてください。

5. 直線で分けられないデータを高い次元へ持ち上げる発想

ここまでは、1本のまっすぐな境界線で分けられる場合を考えてきました。しかし現実のデータには、直線1本では絶対に2つに分けられない並び方があります。

たとえば、地図の内側に病気の人の点がかたまり、その周りを取り囲むように健康な人の点が散らばっているとします。この内と外は、どの向きにどんな直線を引いても分けられません。どこに引いても、線の両側に2種類の点が残ってしまいます。

サポートベクターマシンは、この行き詰まりを発想の転換で乗りこえます。平らな地図の上で分けられないなら、より高い次元の立体的な空間へ、データを配置し直せばよいのです。

先ほどの例なら、中心からの距離という新しい軸を1本加えます。中心に近い内側の点は低いまま残り、中心から遠い外側の点は高く持ち上がります。平面に張り付いていた点の集まりが、立体空間に浮かび上がるイメージです。

高さの差がつけば、あとは簡単です。低い内側の点と高い外側の点の間に、平らな面を1枚差し込みます。曲がりくねった境界線を探し回らなくても、内と外はスパッと分かれます。このように、データを高い次元へ写して、まっすぐな線や平面で分けられるようにする工夫をカーネルと呼びます。

6. 高い次元へ移さずに近さだけを計算するカーネルトリック

持ち上げる作戦には、重大な弱点があります。計算の量です。

すべてのデータ点について、持ち上げた先の座標を実際に計算し直すとします。次元の数を増やすほど、扱う数値の量はふくれあがります。分けやすさを求めて次元を高くするほど計算は重くなり、やがて現実的な時間では終わらなくなります。発想は正しいのに、まともに計算すると破綻してしまうのです。

ここで、サポートベクターマシンの計算の性質が味方になります。境界の面を決めるために本当に必要なのは、持ち上げた先での点どうしの近さだけです。1点1点の新しい座標そのものは、実は使いません。この近さは、数学の言葉で内積（ないせき）と呼ばれます。

そして、この内積には抜け道があります。高い次元へ実際に持ち上げなくても、元の次元の計算だけで、持ち上げた先での内積を直接求められる式があるのです。座標の計算を丸ごと飛ばして、ほしい答えだけを手に入れられます。

重い引っ越しをせずに、引っ越し先での答えだけを受け取る。これがカーネルトリックという数理的な近道です。この近道があるからこそ、サポートベクターマシンは、直線で分けられない複雑なデータも現実的な計算量で分けられます。

理解度の確認