my memorandum blog

日々勉強したことを備忘録として記していきます

スパースモデリングについて勉強してみた(1)

目次

本記事について

はじめに

 今回初めてブログを書くことにしたのでかなり緊張していますが頑張って書いていきます。
 内容には間違いが無いように細心の注意を払いましたが、もし間違いや不適切な記述があればどうかご指摘頂ければと思うのでその時は申し訳ありませんが宜しくお願いいたします。

本記事の内容

 本記事はスパースモデリングについて勉強したものを自分の備忘録としてまとめていく予定ですが、その際下記2つの文献には大変お世話になりました。私の拙い文章では分かりづらい点も下記文献は補ってくださると思います。

スパースモデリング について

スパースモデリング (Sparse Modeling)とは

 まず、スパース(Sparse)とは「疎」とか「まだら」という意味です。機械学習の分野では要素のほとんどの値が「0」の表現をスパースな表現といいます。 スパースモデリングでいうスパース性とは「そのデータの本質部分はスパースな表現で表せる」、つまりデータの本質的な特徴を表す要素はわずかであるという性質を指します。この性質を利用して複雑なデータから本質部分に寄与するものを自動で抽出することで複雑で大量のデータがどのような構造をしているのかを解明しわかりやすいモデルとして表現するモデリング技術をスパースモデリングといいます。 例をあげると変数が複数あるような重回帰においてはその変数の中から少数の重要な変数を自動で取り出すモデリング技術のことをいいます。

スパースモデリング の用途

 上で述べたスパースモデリング技術は下記のような用途が考えられます。

  1. 大量のデータに対して大量データをあえて使用せず解析効率を向上させる
  2. 複雑な構造を持つデータからその本質部分の構造を捉えることでモデルを単純化する
  3. 大量のデータが取得できない問題に対して少量データからデータの不足部分を補う

 1.については、スパース性が仮定できる問題では敢えて大量のデータを使用せずデータ全体の本質的な特徴を表すデータのみを使用することで大量データの解析にかかっていた時間を短縮することができるということです。また、そもそも大量データを取得することをやめて敢えて間引いてデータを取得し間引いた部分をスパースモデリング により推定することができればデータの取得時間を削減することもできます。
 2. についてはデータの本質的な特徴を表す要素を明らかにすることでモデルは単純化されその説明性を向上させることができます。
 3.については、実環境下では解析に十分なデータが得られないという問題によく遭遇しますが、このような場合に不足するデータをスパースモデリングにより推定することが解決手段の一つになるのではと思います。

 これまで説明してきましたスパースモデリングですが、同じような処理が実は私たち人間の脳内でも無意識のうちに行われています。 例えば会話の最中に言葉が省略されたり情報の不足があっても会話の内容の前提知識がある場合は内容を補完し問題なく理解することができますし、なにかある物を観察した時にもその観察対象全体を確認しなくても一部分だけを見ただけで対象はなんなのか識別することができます。これは限られた主要な情報から残りの部分の情報を補完することができているということです。

それじゃスパースモデリングって具体的にどうやるの

 これがこれから書いていこうと思っているスパースモデリングに関する記事の主内容になります。 前置きが長くなりました。

スパースモデリングの実現方法

 それでは、実際にスパースな解を得る方法について考えていきます。
 まず、次ような方程式について考えます。

              2x - 6y + 1 = 0

 この式ですが、そのままではいわゆる不定というやつで条件不足のため一つの解に定めることができません。 しかし、条件が足りていないのでもう少し(この場合あと1つ)条件があれば解は求めることができそうです。
 そこで、もし取り扱っている対象がスパース性を持つことが分かっていた場合はどうでしょうか。
 スパース性とはほとんどの要素が0であるという性質でした。 今は変数が2つしかありませんのでこの場合はx=0の場合とy=0の場合でそれぞれ解は簡単に求まりますね。
 このようにそのままでは解けない問題もスパース性があると分かれば解くことができるのです。
 では、次のような連立方程式はどうでしょうか。

              x - 2y + 4z + 1 = 0
              3x - 7y + 2z + 3 = 0

 これもそのままでは解くことはできませんが、先程と同様にスパース性を仮定すれば上手く解を求めることができそうです。
 もう少し詳細を考えます。 上記の連立方程式に関してはおそらくどの成分を0にするか、そしてその0の個数をいくつにするかによって複数の解が求まると思います(今は解を求めることは目的ではないので導出は行いません)。 このように、実際にいくつかの成分を0にし連立方程式の解を求めスパースな解を得る方法を l_{0} ノルム最小化といいます。
 これは確かに、0が1つの場合、0が2つの場合、・・・と場合分けし計算していけば最もスパースな解を求めることができるかもしれません。 しかし、実問題ではその未知数は膨大であるため組み合わせ爆発が起きてしまい莫大な計算量が必要となってしまうため現実的ではありません。
 そこで、実際には次に説明する l_{1}ノルム最小化という手法でスパースな解を求めていきます。

 l_{1}ノルム最小化

 まず、 l_{1}とはベクトルの各要素の絶対値の総和のことであり、 l_{1}ノルム最小化は各要素の絶対値の総和が最も小さい解を求めることを言います。
 先程の l_{0} ノルム最小化は0ではない要素の個数が最も少ない(最もスパースな)解を探すものでした。これに対し、 l_{1}ノルム最小化は総和の最小化であるため確かに計算量は大幅に削減できそうです。 しかしスパースな解を求めることはできるのでしょうか。
 結論から言うと l_{1}ノルム最小化によりスパースな解を求めることはできます。
 このことは次のように説明されます。
 今、変数がxとyの2つのみの一次方程式の解について l_{1}ノルム最小化による解の導出を考えます。この時、xy平面上での l_{1}ノルムの等高線は図1の青線で示されるような正方形になります。
 一次方程式を満たす解は直線であるので、 l_{1}ノルム最小化によって得られる解は図1のように方程式の直線と交わる正方形のうち最も小さい正方形との交点になります。 この等高線で表された正方形はx軸とy軸の方向に尖っているのでx, y軸いずれかの軸上で直線との交点を持ちます。軸上はいずれかの値が0であるためこれはスパースな解を持つことを示します。

f:id:kiga90:20181219220447p:plain:w400
 図1. l_{1}ノルム最小化の様子
 

ノイズありの場合のスパースな解の算出

 今までは単純な方程式について考えてきましたが、実際の観測においては一般的にノイズや観測誤差はつきものです。 つまり、実際の観測で得られるデータについてはこれまで扱ってきた等式が成り立たない場合があります。 例えば、線形変換で表現される観測を行った場合に得られる信号は

              y = Ax + σ_{0}w

と記述できます。ここで x N次元の実数値ベクトル、 y M次元の実数値ベクトル、 A M × N行列、 wはノイズを表す M次元のベクトル、 σ_{0}はノイズの強度を表します。 今考えているようなノイズが存在する場合は、y = Axの条件でスパースな解を選択することは適切ではありません。
 そこで、 y Axの差を小さくしつつ l_{1}ノルムを小さくするということを考えます。 式で表すと次式に示す最小化問題を解くことでスパースな解を求めようとします。

              \displaystyle\min_{x} \{ ||Ax - y||^2 + λ||x||_{1} \}

ここで ||x||の添字の1は l_{1}ノルムを表します。
 この方法はLASSO(Least Absolute Shrinkage and Selection Operators)と呼ばれます。
 上式について、第一項は二乗誤差、第二項は正則化項を表し、上式のλは正則化パラメータと呼ばれます。 二乗誤差により解の候補を選び、正則化項により解を絞るというような役割があり、正則化パラメータはこの役割のどちらを優先するかを決める定数です。このように観測誤差がある場合には真実の解と寸分の誤差のない解を求めることはできませんがそれと近い解を求めることがこのLASSOを用いることにより可能であることが知られています。
 このように解の選び方に制約条件(正則化)を儲けることで解の推定と共に未知のパラメータ数を削減することでスパースな解を推定する手法がスパース推定です。

急ですが疲れてしまったので今回はここで終わります。 次回は実践的な内容も書いていきたいです。

自分的総括

 近年はビッグデータを用いたAI技術が流行っていますが、ビッグデータは解析にかかるコストも非常に大きいものですしそもそもビッグデータの収集にも大きなコストが掛かります(もちろん、最近は自動で大量のデータを収集できる仕組みは多々ありますが)。
 そこで本記事で紹介しましたスパースモデリングの技術があれば大量データの中から人間への説明性の高い答えを導き出したり、そもそも大量のデータを集めなくてもデータの本質を捉えることができるようになれば応用先は広いと思いますのでこれからも時間を見つけて勉強していこうと思います。

終わりに

 自分的に記念すべき初ブログは非常に拙い文章で内容の薄いものになってしまいましたが、自分で書いてみて普段読ませて頂いている技術ブログを書いている方々の凄さが改めて実感することができました。 自分もその方達に近づけるように精進します。
次の目標は本記事の続きを書くことです。頑張ります。