混合整数計画法による変数選択

混合整数計画法による変数選択です。 MLSE 2018アドベントカレンダー 12/3の記事です。

この記事は、機械学習工学 / MLSE Advent Calendar 2018 12/3 の記事です。

はじめに

Convergence Lab. の木村優志です。

コンラボのメンバーから、「機械学習工学でアドベントカレンダーやってるみたいです。アドベントカレンダーって集客できるらしいです。」といわれて、気軽にやってみるかと思い引き受けました。結果として、12/3のお昼(現在 13時)にやっとプログラムが完成して、ひいひい言いながら記事を書いています。

機械学習はまだまだ職人技なところが多く、これが以下に工学的に体系化されるのかは私も興味があるところです。特に前処理に関する技術で機械学習の性能は大きく変わります。しかし、うまく体系化されていないように思います。今回は、そんな前処理の技術の一つである、変数選択について書きます。また、変数選択法の一つである、混合整数計画法に基づく変数選択を実装し、試してみます。

変数選択

機械学習を仕事で行うとき、研究で行う場合とことなり、まずはデータの整理から始めなければなりません。目的変数の予測に関係ありそうなんだけれど、どれを使うのが正しいのかわからない、というときには変数選択を行うことになります。変数選択は特徴選択と言われることもあります。こっちのほうがメジャーな名前なのかもしれません。

変数選択の目的はWikipedia によると以下のようにあります。(https://ja.wikipedia.org/wiki/%E7%89%B9%E5%BE%B4%E9%81%B8%E6%8A%9E)

  • 次元の呪いの効果を緩和する。
  • 汎化性能を向上させる。
  • 学習を高速化する。
  • モデルの可読性を改善する

他に、何が説明変数の予測因子として効いているのかが知りたいと言うときもあると思います。

次に、具体的手法について見ていきましょ。変数選択の手法は主に3つあります。

  • Filter法
  • Wrapper法
  • Embedded法

Filter法

Filter は何らかの統計や情報量的な性質をつかって、変数を選択する手法です。主には以下のような特徴を利用します。

  • 情報利得
  • χ2スコア
  • フィッシャースコア
  • 相関係数
  • 分散

比較的選択にかかる時間が短いです。

Wrapper法

Wrapper法は何らかの機械学習モデルをつかって変数を選択する方法です。

  • recursive feature elimination (RFE)
  • sequential feature selection algorithms
  • genetic algorithms

たとえば、RFEでは以下のような手順で変数を選択します。まず、すべての変数でモデルを学習します。つぎに、ひとつだけ変数を削除したモデルを生き残っている全変数について作ります。このなかで、予測精度に影響の少ない変数を削除します。この手順を再帰的に行います。

非常に時間がかかる方法です。

Embedded法

Embbed 法は学習プロセスのなかで変数を選択します。Wrapper法が学習と変数選択が分離されているのにたいして、Embedded法ではこれらを協調的に動かします。

  • L1 (LASSO) regularization
  • decision tree

選択にかかる時間は真ん中ぐらいです。

混合整数計画法に基づく変数選択

さて、今回の本題です。この記事では、混合整数計画法に基づく変数選択について紹介します。

実装したのは、以下の論文の手法です。

Ana Kenney, Francesca Chiaromonte, Giovanni Felici, Efficient and Effective L0 Feature Selection, arXiv:1808.02526 [stat.ME]

JSM 2018 (Vancouver, Canada), ISNPS 2018 (Salerno, Italy)などの国際会議で発表された手法のようです。

今回はこの論文の手法を実装シてみました。実装は以下にあります。

https://github.com/convergence-lab/bffs

これは、Embedded法の一つに当たります。Lassoによる変数選択は非常に高速だけれど多くの false positive が検出されます。つまり、余計な変数が選ばれてしまいます。一方、混合整数計画法(Mixed Integer Programming) は精度が高いのですが、時間がかかります。そこで、著者らは両者のメリットを合わせるられないかと考えたというわけです。今回は、LASSOとの融合までは試せませんでしたが、著者らの提案する他の高速化法である Bisection with Feeleers を実装しました。

Bisection with Feeleers は 混合整数計画法で選んだ変数で予測した予測誤差(MSE)にエルボーが見られることを利用しています。つまり、2分探索してこのエルボーの位置をみつければいいんじゃない?という手法です。

MIP_BFFS.png

変数を増やしていくと、黒色の線の予測誤差 MSEが途中で平坦にになることが解ると思います。この位置を探せば良いというわけです。

混合整数計画法のソルバーには miosqp を利用しました。

https://github.com/oxfordcontrol/miosqp 

さて、肝心の実装は以下のようになっています。

def fit(self, X, y):
        if len(X.shape) != 2:
            raise ValueError("the dimension of X should be 2.")

        self._X = X
        self._y = y

        self._data_len = len(X)
        a = 1
        c = X.shape[1]

        for i in range(self._itermax):
            b = (a + c) //2
            while a != b:
                b = (a + c) //2
                fa, _, _ = self._solve_MIQP(a)
                fb, _, _ = self._solve_MIQP(b)
                fc, coef, argx = self._solve_MIQP(c)
                rdab = (fa - fb) / (fa * abs(b-a + self._eps))
                rdbc = (fb - fc) / (fb * abs(b-c + self._eps))
                if rdbc > self._delta and rdab > -self._delta:
                    a = b
                else:
                    c = b
            if c == 1:
                k0 = c + 1
                fk0 = c + 1
            else:
                k0 = c
                fk0 = c
            fk0m1, _, _ = self._solve_MIQP(k0-1)
            fk0p1, _, _ = self._solve_MIQP(k0+1)
            rdm1_0 = abs((fk0m1 - fk0) / (fk0m1 * abs(fk0 - fk0m1)))
            rd0_p1 = abs((fk0 - fk0p1) / (fk0 * abs(fk0p1 - fk0)))
            cost = min(rdm1_0, rd0_p1)
            if self._verbose:
                print(f"iteration {i}: cost {cost}")
            if cost >= self._eps:
                break
            else:
                a = 1
        self._cost = cost
        self._selected_x = argx
        self._coef = coef[argx]
        return c

こんな感じの比較的短いコードになりました。基本的には二分探索を動かしているだけですね。

self._solve_MIQP()でソルバーを動かしています。今回はここには触れません。詳しくは実装をご覧ください。

フィッシャーのアヤメの分類データを用いて、変数選択を動かしてみます。コードは test_run.pyになります。

分類器にはロジスティック回帰を用いました。

import numpy as np
import pandas as pd
from bffs.bf import BF
from sklearn import datasets
from sklearn.linear_model import LogisticRegression

import warnings
warnings.filterwarnings('ignore')

def name(num):
    if num == 0:
        return 'Setosa'
    elif num == 1:
        return 'Veriscolour'
    else:
        return 'Virginica'


if __name__ == "__main__":
    selector = BF(verbose=True)
    data = datasets.load_iris()
    dataX = pd.DataFrame(data=data.data,columns=data.feature_names)
    dataY = pd.DataFrame(data=data.target)
    dataY = dataY.rename(columns={0: 'Species'})
    # dataY['Species'] = dataY['Species'].apply(name)
    X = dataX.values
    y = dataY.values.squeeze(1)

    print()
    model1 = LogisticRegression()
    model1.fit(X, y)
    acc1 = model1.score(X, y)
    print("All Feature Acc", acc1)
    print()

    print("Apply Feature Selection by MIP")
    newX = selector.fit_transform(X, y)
    print(f"Selected {newX.shape[1]} features")
    print(selector.selected())
    print(selector.coef())
    model2 = LogisticRegression()
    model2.fit(newX, y)
    acc2 = model2.score(newX, y)
    print("Selected Feature Acc", acc2)

実行結果はいかになります。シードによって結果が変わるこがあるようですね。

All Feature Acc 0.96

Apply Feature Selection by MIP
iteration 0: cost 0.004134697136279429
Selected 2 features
[3 1]
[2.51867191 0.06904307]
Selected Feature Acc 0.9466666666666667

すべての特徴を使うと 96% です。

変数選択によって2つの特徴が選択され、94.7%の精度が出ています。

まとめ

今回は、変数選択について紹介しました。また、混合整数計画法に基づく変数選択法を実装し、簡単な評価を行いました。

Convergence Lab. もよろしくおねがいします。

ドキュメントアクション