スパースモデリングはなぜ生まれたか？ 代表的なアルゴリズム「LASSO」の登場

本連載は「これから機械学習に取り組みたい」「ディープラーニングや機械学習を使った経験がある」といったエンジニアに向けて、データ量が少なくても分析が実現できる「スパースモデリング」という手法を紹介します。今回は、スパースモデリングの歴史を紐解きながら、その代表的なアルゴリズムであるLASSOについて解説します。

スパースモデリングの基本アイデア

オッカムの剃刀

2010年代初頭にバズワードにまでなったビッグデータ。今では当時の過熱ぶりはなくなり、ハードウェアやクラウド環境の充実とともに活用が広がっています。ビッグデータには一つの明確に定まった定義はありませんが、RDBMSでは扱いづらくなるほどの大量データであるという量的側面と、データの出処やその種類が多種多様であるという質的側面などが特徴として挙げられます。ビッグデータが手元にあり、解きたいビジネス課題にそのビッグデータを使うのが適当である場合は、問題に応じてディープラーニングを使うなり、データをサンプリングして適当な機械学習アルゴリズムを使うなりすればよいと思います。

ただ、現実的には質の良いビッグデータが手元になく、また集めるにも時間がかかったり、集めること自体が難しかったりすることも多いです。当然問題によってはビッグデータを必要としないことも多いでしょう。そういうケースであってもなお、十分な量のデータを集めるのが難しいことは少なくありません。このようなときに問題になりやすいのが過学習です。少し極端な例ではありますが、例えば以下のように、十分なデータがある場合と、十分なデータからいくつかサンプリングしてデータを少なくした場合とを見比べてみてください。

十分なデータがある場合においては、データが密集しているあたりに以下の図のように1本の直線が引けそうです。

十分データがある場合

一方、データが少ない場合においては、そのデータを近似する関数にはいろいろな可能性があり、極端な話、以下の図のようなすべての点を通るような複雑な関数を定義することも可能です。しかし、もともとはサンプリングして得られたデータですので、このような複雑な関数を定義することは明らかに過学習であり、より真の姿に近いのは十分なデータから得られた直線の方です。

データが少ない場合

なぜこのようなことが起こるのでしょうか？ やはりデータがたくさんないと正しい答えを導き出すのは難しいのでしょうか？

現実の世界においては、ある結果を引き起こすためにはさまざまな要因が複雑に絡み合っています。

例えば一定の高さからボールを落下させて、地面につくまでの時間を計測するということを考えます。大きな要因として考えられるのは引力と地面からの距離です。比較的軽いボールですと重量や直径なども考慮したほうが良さそうです。これだけが要因だと距離が同じ場合には計測結果は常に一定になりそうですがおそらくそうはなりません。微小な気温や湿度の変化によってボールが受ける抵抗が変化することもあるでしょうし、近くを通るものが起こす風の影響を受けるかもしれません。非常に厳密に計測できる場合は近くの重量物の位置の変化の影響を受けることがあるかもしれません。ときには計測システムに影響を及ぼす要因もあるでしょう。

このように大小さまざまな要因の影響を受けることでデータにばらつきが出ます。データが少ない場合にはこのデータのばらつきが真の姿をより見えにくくし、過学習を引き起こす原因となります。

ここでオッカムの剃刀という概念を紹介しましょう。オッカムの剃刀とは、14世紀の神学者オッカムが提唱した「ある事柄を説明するのに必要以上に多くのものを仮定すべきではない」という考え方です。このオッカムの剃刀に倣い、ばらつきを引き起こすような要因（先のボールの落下の例でいうと、近くを通るものが起こす風の影響といった些細なもの）は排除し、重要な要因だけでモデリングするのが良さそうです。そうすることで、仮にデータ量が少なくとも、真の姿に近いものが見えるのではないか、これがスパースモデリングの根底にある考え方です。

スパースモデリングの歴史

スパースモデリングの始まりには諸説ありますが、1996年にRobert Tibshirani（スタンフォード大学）が提唱したLASSOなどを契機としてデータサイエンスなどの分野でその有用性が広く認知されるようになりました（LASSOについて詳細は後述します）。LASSOはその後さまざまな形でその発展形が提唱されることになります。

その後、顕微鏡や望遠鏡などさまざまな計測に革命をもたらす圧縮センシング（Compressed Sensing）が、2006年にDavid L. Donoho（スタンフォード大学）より提唱されました。圧縮センシングを応用することでこれまでより高速に精度の高い計測結果を得ることができるようになり、医療分野や天文分野などで活用されはじめています。

圧縮センシングが少ない観測データからスパースな元のデータを推定するデコーディング手法であるのに対し、元のデータを辞書と呼ばれる基底ベクトルとスパースなベクトルで表現するためのエンコーディング手法であるスパースコーディングも2000年代に提唱されています。スパースコーディングを使うことによりデータの圧縮を行えるだけでなく、画像からノイズを除去したり、画像の解像度を上げる超解像などさまざまな応用が可能です。

アカデミアの世界においてスパースモデリングの研究は進んでいますが、スパースモデリングをビジネスに応用しているという事例はまだまだ少ないというのが現状です。今後ますますデータが蓄積される速度は加速し、大量のデータを扱う必要に迫られる場面が多くなることが予想される中、ディープラーニングを中心とした手法に注目が集まっているのも事実です。

しかし第一回で述べたような解釈性に対する課題や、冒頭で述べた良質なデータを集めることが難しいビジネスユースケースの存在も数多く認識されてきており、今後はスパースモデリングのビジネスへの応用も増えていくでしょう。

線形回帰とスパースモデリング

ここからは前節で紹介したスパースモデリングの代表的な手法であるLASSOについて、その背景にある考え方も含めて具体例とともに紹介していきます。サンプルコードはGitHubに公開しています。

• hacarus/codezine-sparse-modeling（GitHub）

線形回帰モデルと最適化問題

前回「未知数が二つだけれども方程式が一つしかない」ため答えを求められない場合にどうするかということを例に上げ、スパースモデリングの説明をしました。このようにスパースモデリングには、方程式よりも未知数、つまりデータ数よりも説明変数の数のほうが少ない場合にも使うことができるという側面がありますが、説明変数の多くがスパースであるという仮定をすることで説明変数、特徴量の選択をしているという側面もあります。実際の用途としてはこの特徴量選択のためにスパースモデリングを使うケースのほうが多いでしょう。

具体例として店舗別の売上データ（sales.csv）を使って考えます。このデータには、以下の5つの説明変数と、売上のデータが含まれています。

• 店舗の面積
• 駅からの距離
• 周辺人口
• 競合店数
• 商品点数

通常は基本統計データや相関係数などをみて必要に応じて変数選択をしたりしますが、今回は比較のためあえて特に何も考えず重回帰分析にかけてみます。

これを実行すると以下の結果を得ます。

売上を$y$、面積を$x_1$、駅からの距離を $x_2$、周辺人口を $x_3$、競合店数を$x_4$、商品点数を$x_5$とすると回帰式は以下のようになります。

学習に使ったデータから得られた値であるため少し高めの数値がでる傾向にありますが、決定係数（R square）も0.95で悪くない値です。ただ、一方で仮に真実の解がスパースだとすると、すべての変数が使われていることは、先に述べたオッカムの剃刀の考え方からは外れます。また、この例ですとまだ説明変数が少ないので実感しにくいかもしれませんが、入力する説明変数が多くなればなるほど、すべての変数が目的変数を求めるのに一定以上寄与することは考えづらいです。求める精度にもよりますが、大抵の場合はシンプルなモデルで十分実用に足ることが多いでしょう。

L₀ノルム最適化

スパースモデリングを使うことで説明変数の選択をすると同時に係数を求めることができます。スパースモデリングにはさまざまな手法がありますが、真実の解が十分にスパースであれば、真実の解が得られることが知られている$L_0$最適化を最初に紹介します。

売上のベクトルを$y$、説明変数となるデータの行列を$\Phi$、求める係数のベクトルを$x$とすると以下の式を解けばよいことになります。

$L_0$最適化は$x$の$L_0$ノルム^[1]を最小化するというものです。ベクトル$x$の$L_0$ノルムとは$x$の非ゼロ要素の個数です。つまり$L_0$最適化とは$x$の非ゼロ要素の個数ができるだけ少ないものを求めるというものです。この問題の最も直接的な解き方は以下で説明する総当たり法です。ここで、最もスパースな解を$x^{\ast }$とし、その時の$L_0$ノルム  を$k$とします。

1. もし$y=0$なら$x^{\ast }=0$として終了
3. となる全ての$x$について$y=\Phi x$が解を持つか調べ、もし解を持つならそれを解として終了
4. として 3. に戻る

このようにアルゴリズムそのものは非常に単純ではありますが、これは組合せ最適化でありベクトル$x$の次元数が多くなると組合せ爆発が発生し、現実的な時間内に計算が終わらない可能性が高くなります。

L₁ノルム最適化とLASSO

$L_0$最適化において組合せ爆発が生じるのは$L_0$ノルムを使っているからです。この$L_0$ノルムは以下の式で定義される${\mathrm{L1}}^{}$ノルムで近似することができます。

式から分かる通り$L_1$ノルムは$x$の要素の絶対値の総和であり、マンハッタン距離と呼ばれるものと同じです。

近似により$L_0$ノルム最小化問題はn次元空間内の超平面$y=\Phi x$上の点のうち$L_1$ノルム最小となる点を求める問題となります。$x$が 2次元のとき図で表すと以下のようになります。

$L_1$ノルム最適化

$L_1$ノルムが一定となる点を結ぶと頂点が座標軸の上にあるひし形になります。このひし形を面積がゼロとなる中心点から徐々に大きくしていって最初に直線とぶつかる点が最適解となります。大抵の場合は座標軸上のひし形の頂点とぶつかるため、どちらかの座標がゼロとなりスパースな解が得られます。

ここまではデータにノイズが混入していないことを前提に説明をしてきましたが、現実の世界においてはデータにノイズが混入していることが普通です。近似曲線を計算するのに最小二乗法を使うのはよく知られた方法です。しかしノイズの混入したデータにおいては冒頭で説明したように過学習が起こることがあります。詳細な説明は省きますが、この過学習を防ぐために正則化項として$L_1$ノルムを使うことができます。問題としては以下の式の値を最小化する最適化問題となります。

この最適化問題のことをLASSOといいます。LASSOは、スパースモデリングが広く知られるきっかけになったアルゴリズムです。LASSOの実装はscikit learnにありますので、重回帰分析にかけたデータをLASSOを使って線形回帰分析してみます。

実行結果は以下のとおりです。

5つめの変数の重みがゼロになっておりスパースモデリングの特徴の一つである変数選択されていることがわかります。決定係数も変数をすべて使っている重回帰の場合とほとんど変わりません。

L₀ノルム最適化を貪欲に解くOrthogonal Matching Pursuit

$L_0$最適化問題で総当たり法を使うと組合せ爆発が発生して実用に耐えないことを説明しました。このような場合には貪欲法（greedy method）が有効です。貪欲法では問題をいくつかの部分問題に分割し、部分問題の解のうち最も良いものを選択するという方法です。

$L_0$最適化問題を貪欲法で解く代表的な手法にOMP（Orthogonal Matching Pursuit）があります。OMPは非ゼロとなるベクトル$x$の要素を指すインデックス集合Sを見つけ出すアルゴリズムです。この非ゼロ係数のインデックス集合をサポートといいます。初めはサポートは空集合であるとして、$x$を基底$\Phi$の線型結合で近似した時の残差を最小にするように新たな基底をサポート集合に一つ一つ追加していき、サポートに含まれる基底のみで$x$を近似した時の残差がしきい値以下になったら停止するというものです。残差の低減に寄与する基底を順次選択していく貪欲法であり、解の最適性は保証されませんが、多くの場合優れた近似値が得られます。OMPを売上データに適用したコードを以下に示します。

これを実行すると以下の出力を得ます。

OrthogonalMatchingPursuitでは係数が非ゼロとなる特徴量の数は自動で計算されず、コンストラクタ引数にn_nonzero_coefs=4のようにして渡します。指定しない場合は特徴量の数の10％がデフォルト値として使われます。決定係数を見ながら調整していくのが良いでしょう。