(57)【要約】  イジングマシンを用いて、選択する特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる特徴量選択装置等を提供する。特徴量選択装置は、二値変数を引数とする目的関数を最小化又は最大化する二値変数の値を確率的に求めるイジングマシンを用いて特徴量を選択する特徴量選択装置であって、複数の特徴量のうち、１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数を表す第２正則化項を目的関数に設定する第３設定部と、イジングマシンにより求められた第１二値変数の値に基づいて、複数の特徴量から１又は複数の特徴量を選択する選択部と、を備える。
2018235568.tif 000002
【特許請求の範囲】
【請求項１】
二値変数を引数とする目的関数を最小化又は最大化する前記二値変数の値を確率的に求めるイジングマシンを用いて特徴量を選択する特徴量選択装置であって、
複数の特徴量の全部又は一部を入力とする複数の弱学習器のうち、第１二値変数により選択される１又は複数の弱学習器の出力を統合した強学習器の出力の誤差を表す項を前記目的関数に設定する第１設定部と、
前記１又は複数の弱学習器の数を表す第１正則化項を前記目的関数に設定する第２設定部と、
前記複数の特徴量のうち、前記１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数を表す第２正則化項を前記目的関数に設定する第３設定部と、
前記イジングマシンにより求められた、前記目的関数を最小化又は最大化する前記第１二値変数の値を取得する取得部と、
前記第１二値変数の値に基づいて、前記複数の特徴量から１又は複数の特徴量を選択する選択部と、
を備える特徴量選択装置。
【請求項２】
前記複数の特徴量をｘｉ（ｉ＝１〜Ｍ）と表し、前記複数の弱学習器をｈｊ（ｘ）（ｊ＝１〜Ｎ）と表し、前記第１二値変数をｗｊ（ｊ＝１〜Ｎ）と表し、ｊ番目の弱学習器ｈｊ（ｘ）がｉ番目の特徴量ｘｉを入力とする場合に１となり、ｊ番目の弱学習器ｈｊ（ｘ）がｉ番目の特徴量ｘｉを入力としない場合に０となる行列をＦｉｊと表すとき、
前記第２正則化項は、Σｊ＝１ＮＦｉｊｗｊのＬ０ノルムにより表される項を含む、
請求項１に記載の特徴量選択装置。
【請求項３】
前記第１二値変数ｗｊのビットフリップを¬ｗｊにより表すとき、
前記第２正則化項は、Σｉ＝１Ｍ［１−Πｊ＝１Ｎ（¬ｗｊ）Ｆｉｊ］により表される項を含む、
請求項２に記載の特徴量選択装置。
【請求項４】
前記第２正則化項は、前記第１二値変数のビットフリップが第２二値変数に等しくなるように拘束する第１拘束条件を表す項を含む、
請求項３に記載の特徴量選択装置。
【請求項５】
前記第２二値変数をｖｊ（ｊ＝１〜Ｎ）と表すとき、
前記第１拘束条件は、Σｊ＝１Ｎ［（ｖｊ−（１−ｗｊ）］２により表される項を含む、
請求項４に記載の特徴量選択装置。
【請求項６】
前記第３設定部は、前記第２正則化項に前記第１二値変数のビットフリップの３次以上の積が含まれる場合に、２の前記第１二値変数のビットフリップの積を１の第３二値変数に置換する、
請求項３から５のいずれか１項に記載の特徴量選択装置。
【請求項７】
前記第２正則化項は、前記第３設定部により置換された２の前記第１二値変数のビットフリップの積と１の前記第３二値変数とが等しくなるように拘束する第２拘束条件を表す項を含む、
請求項６に記載の特徴量選択装置。
【請求項８】
前記第３二値変数をｕｌ（ｌ＝１〜Ｌ）と表すとき、
前記第２拘束条件は、Σ［（¬ｗｊ）（¬ｗｋ）−２（¬ｗｊ＋¬ｗｋ）ｕｌ＋３ｕｌ］により表される項を含み、
和は、前記第３設定部により置換が行われたｊ，ｋ，ｌの組について行われる、
請求項７に記載の特徴量選択装置。
【請求項９】
二値変数を引数とする目的関数を最小化又は最大化する前記二値変数の値を確率的に求めるイジングマシンを用いて特徴量を選択する特徴量選択方法であって、
複数の特徴量の全部又は一部を入力とする複数の弱学習器のうち、第１二値変数により選択される１又は複数の弱学習器の出力を統合した強学習器の出力の誤差を表す項を前記目的関数に設定することと、
前記１又は複数の弱学習器の数を表す第１正則化項を前記目的関数に設定することと、
前記複数の特徴量のうち、前記１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数を表す第２正則化項を前記目的関数に設定することと、
前記イジングマシンにより求められた前記目的関数を最小化又は最大化する前記第１二値変数の値を取得することと、
前記第１二値変数の値に基づいて、前記複数の特徴量から１又は複数の特徴量を選択することと、
を含む特徴量選択方法。
【請求項１０】
二値変数を引数とする目的関数を最小化又は最大化する前記二値変数の値を確率的に求めるイジングマシンを用いて特徴量を選択する特徴量選択装置に備えられたコンピュータを、
複数の特徴量の全部又は一部を入力とする複数の弱学習器のうち、第１二値変数により選択される１又は複数の弱学習器の出力を統合した強学習器の出力の誤差を表す項を前記目的関数に設定する第１設定部、
前記１又は複数の弱学習器の数を表す第１正則化項を前記目的関数に設定する第２設定部、
前記複数の特徴量のうち、前記１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数を表す第２正則化項を前記目的関数に設定する第３設定部、
前記イジングマシンにより求められた前記目的関数を最小化又は最大化する前記第１二値変数の値を取得する取得部、及び
前記第１二値変数の値に基づいて、前記複数の特徴量から１又は複数の特徴量を選択する選択部、
として機能させる特徴量選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特徴量選択装置、特徴量選択方法及び特徴量選択プログラムに関する。
【背景技術】
【０００２】
従来、多数の特徴量を用いて学習モデルによる分析を行う場合に、冗長な特徴量を除外し、一部の特徴量を選択することで、学習モデルの分析精度を向上させる研究が行われている。例えば、ウェブサイトのアクセス履歴から購買動向等を分析する場合、特徴量は、ユーザのプロフィール、ブラウザの種類、ユーザ端末の種類、ＯＳ（Operating System）の種類及びタイムスタンプ等、多岐にわたる。【０００３】
特徴量の数が例えば１００である場合、特徴量の組み合わせの数はおおよそ１０３０となり、単純な全探索によって最適な特徴量の組み合わせを見つけることは事実上不可能である。そのため、従来、Ｌ１正則化により特徴量の数を減らしたり、ランダムフォレスト法により最適な特徴量の組み合わせを近似的に探索したりする場合がある。【０００４】
下記非特許文献１には、Ｍ次元の入力データをｘと表し、入力データｘに関する二値分類をｙ（ｙ＝１又は−１）と表し、それぞれが分類器である弱学習器をｈｉ（ｘ）（ｉ＝１〜Ｎ）と表し、いずれの弱学習器を採用するか表す二値変数をｗｉ（ｗｉ＝０又は１）と表し、強学習器をＨ（ｘ）と表すとき、ｙ＝Ｈ（ｘ）＝ｓｉｇｎ（Σｉ＝１Ｎｗｉｈｉ（ｘ））によって入力データｘに関する二値分類を行う技術が記載されている。ここで、ｗｉは、二値分類の二乗誤差とｗｉのＬ０正則化項の和を含む目的関数を最小化するように定められる。非特許文献１では、そのようなｗｉを、量子アニーリングマシンによって求めている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】H.Neven,他５名, "NIPS 2009 Demonstration: Binary Classification using Hardware Implementation of Quantum Annealing", 2009, Advances in Neural Information Processing Systems 22 (NIPS 2009)
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１では、目的関数を最小化又は最大化する二値変数の値を確率的に求めるイジングマシンの一種である量子アニーリングマシンを用いて、弱学習器の最適な組み合わせを求めている。ここで、非特許文献１で用いられている目的関数は、Ｌ０正則化項を含み、１の値を取るｗｉの数を減らしつつ、二値分類の二乗誤差を最小化するようなｗｉを求めている。【０００７】
しかしながら、弱学習器は、Ｍ次元の入力データｘ（Ｍ種類の特徴量）の全部又は一部を用いるものであり、非特許文献１の目的関数では、強学習器により用いられる特徴量の数が必ずしも少なくならず、冗長な特徴量が除外されない場合がある。【０００８】
そこで、本発明は、イジングマシンを用いて、選択する特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる特徴量選択装置、特徴量選択方法及び特徴量選択プログラムを提供する。
【課題を解決するための手段】
【０００９】
本発明の一態様に係る特徴量選択装置は、二値変数を引数とする目的関数を最小化又は最大化する二値変数の値を確率的に求めるイジングマシンを用いて特徴量を選択する特徴量選択装置であって、複数の特徴量の全部又は一部を入力とする複数の弱学習器のうち、第１二値変数により選択される１又は複数の弱学習器の出力を統合した強学習器の出力の誤差を表す項を目的関数に設定する第１設定部と、１又は複数の弱学習器の数を表す第１正則化項を目的関数に設定する第２設定部と、複数の特徴量のうち、１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数を表す第２正則化項を目的関数に設定する第３設定部と、イジングマシンにより求められた、目的関数を最小化又は最大化する第１二値変数の値を取得する取得部と、第１二値変数の値に基づいて、複数の特徴量から１又は複数の特徴量を選択する選択部と、を備える。【００１０】
この態様によれば、目的関数に第２正則化項を設定することで、冗長な特徴量を用いる弱学習器が除外され、強学習器により冗長な特徴量が用いられないようにすることができる。そのため、イジングマシンを用いて、選択する特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる。【００１１】
上記態様において、複数の特徴量をｘｉ（ｉ＝１〜Ｍ）と表し、複数の弱学習器をｈｊ（ｘ）（ｊ＝１〜Ｎ）と表し、第１二値変数をｗｊ（ｊ＝１〜Ｎ、ｗｊ＝０又は１）と表し、ｊ番目の弱学習器ｈｊ（ｘ）がｉ番目の特徴量ｘｉを入力とする場合に１となり、ｊ番目の弱学習器ｈｊ（ｘ）がｉ番目の特徴量ｘｉを入力としない場合に０となる行列をＦｉｊと表すとき、第２正則化項は、Σｊ＝１ＮＦｉｊｗｊのＬ０ノルムにより表される項を含んでもよい。【００１２】
この態様によれば、第２正則化項によって、複数の特徴量が弱学習器に入力されるか否かを表す二値を複数の弱学習器にわたって論理和した値を求めることができる。これにより、１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数が求められる。【００１３】
上記態様において、第１二値変数ｗｊのビットフリップを¬ｗｊにより表すとき、第２正則化項は、Σｉ＝１Ｍ［１−Πｊ＝１Ｎ（¬ｗｊ）Ｆｉｊ］により表される項を含んでもよい。【００１４】
この態様によれば、複数の特徴量が弱学習器に入力されるか否かを表す二値を複数の弱学習器にわたって論理和した値を、ド・モルガンの法則により否定の論理積に書き換えることで、第２正則化項を第１二値変数のビットフリップの多項式で表すことができ、イジングマシンへの実装に適した表式とすることができる。【００１５】
上記態様において、第２正則化項は、第１二値変数のビットフリップが第２二値変数に等しくなるように拘束する第１拘束条件を表す項を含んでもよい。【００１６】
この態様によれば、第１二値変数のビットフリップを第２二値変数に置き換えることができ、第２正則化項を第２二値変数の多項式によって表して、イジングマシンへの実装に適した表式とすることができる。【００１７】
上記態様において、第２二値変数をｖｊ（ｊ＝１〜Ｎ、ｖｊ＝０又は１）と表すとき、第１拘束条件は、Σｊ＝１Ｎ［（ｖｊ−（１−ｗｊ）］２により表される項を含んでもよい。【００１８】
この態様によれば、第１二値変数のビットフリップが第２二値変数と等しくなり、第２正則化項を第２二値変数によって表した場合であっても、選択される特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる。【００１９】
上記態様において、第３設定部は、第２正則化項に第１二値変数のビットフリップの３次以上の積が含まれる場合に、２の第１二値変数のビットフリップの積を１の第３二値変数に置換してもよい。【００２０】
この態様によれば、目的関数に含まれる二値変数の次数を２以下とすることができ、第２正則化項を第１二値変数のビットフリップと第３二値変数の二次式で表し、イジングマシンへの実装に適した表式とすることができる。【００２１】
上記態様において、第２正則化項は、第３設定部により置換された２の第１二値変数のビットフリップの積と１の第３二値変数とが等しくなるように拘束する第２拘束条件を表す項を含んでもよい。【００２２】
この態様によれば、２の第１二値変数のビットフリップの積を第３二値変数に置き換えることができ、第２正則化項を第１二値変数のビットフリップと第３二値変数の２次式によって表して、イジングマシンへの実装に適した表式とすることができる。【００２３】
上記態様において、第３二値変数をｕｌ（ｌ＝１〜Ｌ、ｕｌ＝０又は１）と表すとき、第２拘束条件は、Σ［（¬ｗｊ）（¬ｗｋ）−２（¬ｗｊ＋¬ｗｋ）ｕｌ＋３ｕｌ］により表される項を含み、和は、第３設定部により置換が行われたｊ，ｋ，ｌの組について行われてもよい。【００２４】
この態様によれば、２の第１二値変数のビットフリップの積が第３二値変数と等しくなり、第２正則化項を第３二値変数によって表した場合であっても、選択される特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる。【００２５】
本発明の他の態様に係る特徴量選択方法は、二値変数を引数とする目的関数を最小化又は最大化する二値変数の値を確率的に求めるイジングマシンを用いて特徴量を選択する特徴量選択方法であって、複数の特徴量の全部又は一部を入力とする複数の弱学習器のうち、第１二値変数により選択される１又は複数の弱学習器の出力を統合した強学習器の出力の誤差を表す項を目的関数に設定することと、１又は複数の弱学習器の数を表す第１正則化項を目的関数に設定することと、複数の特徴量のうち、１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数を表す第２正則化項を目的関数に設定することと、イジングマシンにより求められた目的関数を最小化又は最大化する第１二値変数の値を取得することと、第１二値変数の値に基づいて、複数の特徴量から１又は複数の特徴量を選択することと、を含む。【００２６】
この態様によれば、目的関数に第２正則化項を設定することで、冗長な特徴量を用いる弱学習器が除外され、強学習器により冗長な特徴量が用いられないようにすることができる。そのため、イジングマシンを用いて、選択する特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる。【００２７】
本発明の他の態様に係る特徴量選択プログラムは、二値変数を引数とする目的関数を最小化又は最大化する二値変数の値を確率的に求めるイジングマシンを用いて特徴量を選択する特徴量選択装置に備えられたコンピュータを、複数の特徴量の全部又は一部を入力とする複数の弱学習器のうち、第１二値変数により選択される１又は複数の弱学習器の出力を統合した強学習器の出力の誤差を表す項を目的関数に設定する第１設定部、１又は複数の弱学習器の数を表す第１正則化項を目的関数に設定する第２設定部、複数の特徴量のうち、１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数を表す第２正則化項を目的関数に設定する第３設定部、イジングマシンにより求められた目的関数を最小化又は最大化する第１二値変数の値を取得する取得部、及び第１二値変数の値に基づいて、複数の特徴量から１又は複数の特徴量を選択する選択部、として機能させる。【００２８】
この態様によれば、目的関数に第２正則化項を設定することで、冗長な特徴量を用いる弱学習器が除外され、強学習器により冗長な特徴量が用いられないようにすることができる。そのため、イジングマシンを用いて、選択する特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる。
【発明の効果】
【００２９】
本発明によれば、イジングマシンを用いて、選択する特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる特徴量選択装置、特徴量選択方法及び特徴量選択プログラムが提供される。
【図面の簡単な説明】
【００３０】
【図１】本発明の実施形態に係る特徴量選択システムの概要を示す図である。
【図２】本実施形態に係る特徴量選択装置の機能ブロックを示す図である。
【図３】本実施形態に係る特徴量選択装置の物理的構成を示す図である。
【図４】本実施形態に係る特徴量選択装置により扱われる弱学習器と特徴量の関係の一例を示す図である。
【図５】本実施形態に係る特徴量選択装置により実行される特徴量選択処理のフローチャートである。
【発明を実施するための形態】
【００３１】
以下、本発明の一側面に係る実施の形態（以下、「本実施形態」と表記する。）を、図面に基づいて説明する。なお、各図において、同一の符号を付したものは、同一又は同様の構成を有する。
【００３２】
図１は、本発明の実施形態に係る特徴量選択システム１００の概要を示す図である。特徴量選択システム１００は、特徴量選択装置１０と、イジングマシン２０と、データベース４０とを備える。特徴量選択装置１０、イジングマシン２０及びデータベース４０は、互いに通信ネットワークＮを介して接続される。なお、同図に示す構成は特徴量選択システム１００の一例であり、特徴量選択装置１０、イジングマシン２０及びデータベース４０は必ずしも別体の装置でなくてもよく、これらの一部が１つの装置により構成されてもよい。
【００３３】
特徴量選択装置１０は、二値変数を引数とする目的関数を最小化又は最大化する二値変数の値を確率的に求めるイジングマシン２０を用いて特徴量を選択する。特徴量選択装置１０は、従来のコンピュータ、すなわちノイマン型コンピュータで構成されてよい。本明細書では、特徴量選択装置１０によって、二値変数を引数とする目的関数を最小化する二値変数の値を確率的に求めるイジングマシン２０を設定する場合について説明する。しかしながら、目的関数全体の符号を逆にすれば、二値変数を引数とする目的関数を最大化する二値変数の値を確率的に求めるイジングマシン２０を設定することもできる。
【００３４】
イジングマシン２０は、二値変数を引数とする目的関数を最小化又は最大化する二値変数の値を確率的に求める装置であってよく、二値変数は、古典ビットや量子ビットで実現されてよい。イジングマシン２０は、非ノイマン型コンピュータであってよく、自然計算（Natural computing）を実行する計算機であってもよい。イジングマシン２０は、量子アニーリングマシンやＦＰＧＡ（Field-Programmable Gate Array）、ＣＭＯＳ（Complementary Metal Oxide Semiconductor）、ＡＳＩＣ（Application Specific Integrated Circuit）等によって構成されてよく、二値変数を引数とする目的関数を最小化又は最大化する二値変数の値を確率的に求めるものであればどのようなハードウェアによって構成されるものであってもよく、目的関数の最小又は最大を求める過程において量子現象を利用していてもよいし、利用していなくてもよい。目的関数は、二値変数の１次関数と２次関数とを含んでよく、特徴量選択装置１０は、用途に応じて１次関数の係数と２次関数の係数とを設定してよい。
【００３５】
データベース４０は、特徴量選択装置１０による選択の対象となる複数の特徴量を記憶する。複数の特徴量は、任意のデータであってよいが、例えば、ウェブサイトを通じた電子商取引の特徴を表す特徴量の場合、ユーザのプロフィール、ブラウザの種類、ユーザ端末の種類、ＯＳの種類、タイムスタンプ、アクセス地域、インターネット広告の種類、インターネット広告の内容、購入金額及び購入商品名等のデータを含んでよい。また、複数の特徴量は、例えば、ウェブサイトを通じた宿泊予約の特徴を表す特徴量の場合、ユーザのプロフィール、ブラウザの種類、ユーザ端末の種類、ＯＳの種類、タイムスタンプ、アクセス地域、インターネット広告の種類、インターネット広告の内容、宿泊金額及び宿泊施設名等のデータを含んでよい。
【００３６】
図２は、本実施形態に係る特徴量選択装置１０の機能ブロックを示す図である。特徴量選択装置１０は、第１設定部１１、第２設定部１２、第３設定部１３、取得部１４及び選択部１５を備える。
【００３７】
第１設定部１１は、複数の特徴量の全部又は一部を入力とする複数の弱学習器のうち、第１二値変数により選択される１又は複数の弱学習器の出力を統合した強学習器の出力の誤差を表す項を、イジングマシン２０の目的関数に設定する。より具体的には、複数の特徴量をｘｉ（ｉ＝１〜Ｍ）と表し、複数の弱学習器をｈｊ（ｘ）（ｊ＝１〜Ｎ）と表し、第１二値変数をｗｊ（ｊ＝１〜Ｎ、ｗｊ＝０又は１）と表すとき、例えば二値分類を行う強学習器Ｈ（ｘ）の出力は、ｙ＝Ｈ（ｘ）＝ｓｉｇｎ（Σｊ＝１Ｎｗｊｈｊ（ｘ））と定義されてよい。強学習器Ｈ（ｘ）の出力は、Σｊ＝１Ｎｗｊｈｊ（ｘ）の関数であってよく、多値分類や回帰を行うものであってもよい。強学習器の出力の誤差を表す項は、Ｍ次元ベクトルである特徴量ｘが合計Ｓセット用意された学習用データを用いる場合、Σｓ＝１Ｓ（Ｎ−１Σｊ＝１Ｎｗｊｈｊ（ｘ（ｓ））−ｔ（ｓ））２で表される項であってよい。ここで、ｔ（ｓ）（ｓ＝１〜Ｓ）は、強学習器が出力すべき値を表す。データベース４０は、学習用データとして、（ｘ（ｓ），ｔ（ｓ））というデータをＳセット記憶していてよい。
【００３８】
第２設定部１２は、第１二値変数により選択される１又は複数の弱学習器の数を表す第１正則化項をイジングマシン２０の目的関数に設定する。第１二値変数により選択される１又は複数の弱学習器の数は、１の値をとる第１二値変数の数を数え上げることで表すことができる。すなわち、第１正則化項は、λ｜｜ｗ｜｜０であってよい。ここで、｜｜・｜｜０はＬ０ノルムを表し、λは未定乗数を表す。より具体的には、成分が全て１であるＮ次元ベクトルをＩｊ（ｊ＝１〜Ｎ）と表すとき、第１正則化項は、λΣｊ＝１ＮｗｊＩｊによって表される項であってよい。
【００３９】
強学習器の出力の誤差を表す項が、上記のように二乗誤差の形式で表され、第１正則化項が、上記のようにＬ０ノルムによって表される場合、目的関数は、Ｎ−２Σｓ＝１ＳΣｊ＝１ＮΣｋ＝１Ｎｗｊｈｊ（ｘ（ｓ））ｗｋｈｋ（ｘ（ｓ））＋Σｊ＝１Ｎｗｊ（λＩｊ−２Ｎ−１Σｓ＝１Ｓｈｊ（ｘ（ｓ））ｔ（ｓ））という項を含んでよい。ここで、強学習器の出力の誤差を表す項のうち、第１二値変数の最小化又は最大化に関係しない定数項（Σｓ＝１Ｓ（ｔ（ｓ））２）は除外している。
【００４０】
第３設定部１３は、複数の特徴量のうち、第１二値変数により選択される１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数を表す第２正則化項を、イジングマシン２０の目的関数に設定する。より具体的には、ｊ番目の弱学習器ｈｊ（ｘ）がｉ番目の特徴量ｘｉを入力とする場合に１となり、ｊ番目の弱学習器ｈｊ（ｘ）がｉ番目の特徴量ｘｉを入力としない場合に０となる行列をＦｉｊと表すとき、第２正則化項は、｜｜Σｊ＝１ＮＦｉｊｗｊ｜｜０と表される項を含んでよい。ここで、Σｊ＝１ＮＦｉｊｗｊはＭ次元のベクトルであり、ｉ番目の特徴量が、第１二値変数により選択される１又は複数の弱学習器によって何度用いられるかを表す。そして、Σｊ＝１ＮＦｉｊｗｊのＬ０ノルムは、第１二値変数により選択される１又は複数の弱学習器により用いられる１又は複数の特徴量の重複を除いた数を表す。このように、第２正則化項によって、複数の特徴量が弱学習器に入力されるか否かを表す第１二値変数を複数の弱学習器にわたって論理和した値を求めることができる。これにより、１又は複数の弱学習器に入力される１又は複数の特徴量の重複を除いた数が求められる。
【００４１】
強学習器の出力の誤差を表す項、第１正則化項及び第２正則化項を含む目的関数は、Ｎ−２Σｓ＝１ＳΣｊ＝１ＮΣｋ＝１Ｎｗｊｈｊ（ｘ（ｓ））ｗｋｈｋ（ｘ（ｓ））＋Σｊ＝１Ｎｗｊ（λＩｊ−２Ｎ−１Σｓ＝１Ｓｈｊ（ｘ（ｓ））ｔ（ｓ））＋λ１｜｜Σｊ＝１ＮＦｉｊｗｊ｜｜０によって表されてよい。ここで、λ１は未定乗数である。
【００４２】
取得部１４は、イジングマシン２０により求められた、目的関数を最小化又は最大化する第１二値変数の値を取得する。イジングマシン２０は、例えば、強学習器の出力の誤差を表す項、第１正則化項及び第２正則化項を含む目的関数を最小化する第１二値変数の値を求めてよく、取得部１４は、イジングマシン２０により求められた、目的関数を最小化する第１二値変数の値を取得してよい。
【００４３】
選択部１５は、取得された第１二値変数の値に基づいて、複数の特徴量から１又は複数の特徴量を選択する。選択部１５は、イジングマシン２０により求められた目的関数を最小化する第１二値変数の値ｗｊに基づいて、ｗｊ＝１となるｊについて弱学習器ｈｊ（ｘ）に入力される１又は複数の特徴量を選択してよい。反対に、選択部１５は、イジングマシン２０により求められた目的関数を最小化する第１二値変数の値ｗｊに基づいて、ｗｊ＝０となるｊについて弱学習器ｈｊ（ｘ）に入力される１又は複数の特徴量を選択しないこととしてよい。イジングマシン２０に設定された目的関数は、強学習器により用いられる特徴量の数を表す第２正則化項を含むため、強学習器により用いられる特徴量の数が少なくなるような、第１二値変数の値を求めることになる。このように、目的関数に第２正則化項を設定することで、冗長な特徴量を用いる弱学習器が除外され、強学習器により冗長な特徴量が用いられないようにすることができる。そのため、イジングマシン２０を用いて、選択する特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる。
【００４４】
第１二値変数ｗｊのビットフリップを¬ｗｊにより表すとき、第２正則化項は、Σｉ＝１Ｍ［１−Πｊ＝１Ｎ（¬ｗｊ）Ｆｉｊ］により表される項を含んでよい。ここで、第１二値変数ｗｊのビットフリップを¬ｗｊは、¬ｗｊ＝１−ｗｊであってよい。このように、複数の特徴量が弱学習器に入力されるか否かを表す二値を複数の弱学習器にわたって論理和した値を、ド・モルガンの法則により否定の論理積に書き換えることで、第２正則化項を第１二値変数のビットフリップの多項式で表すことができ、イジングマシン２０への実装に適した表式とすることができる。
【００４５】
ここで、第２正則化項は、第１二値変数のビットフリップが第２二値変数に等しくなるように拘束する第１拘束条件を表す項を含んでよい。これにより、第１二値変数のビットフリップを第２二値変数に置き換えることができ、第２正則化項を第２二値変数の多項式によって表して、イジングマシンへの実装に適した表式とすることができる。この場合、イジングマシン２０は、目的関数を最小化又は最大化する第１二値変数の値及び第２二値変数の値を求める。
【００４６】
より具体的には、第２二値変数をｖｊ（ｊ＝１〜Ｎ、ｖｊ＝０又は１）と表すとき、第１拘束条件は、Σｊ＝１Ｎ［（ｖｊ−（１−ｗｊ）］２により表される項を含んでよい。このとき、目的関数は、Ｎ−２Σｓ＝１ＳΣｊ＝１ＮΣｋ＝１Ｎｗｊｈｊ（ｘ（ｓ））ｗｋｈｋ（ｘ（ｓ））＋Σｊ＝１Ｎｗｊ（λＩｊ−２Ｎ−１Σｓ＝１Ｓｈｊ（ｘ（ｓ））ｔ（ｓ））＋λ１Σｉ＝１Ｍ［１−Πｊ＝１Ｎ（¬ｗｊ）Ｆｉｊ］＋αΣｊ＝１Ｎ［（ｖｊ−（１−ｗｊ）］２によって表される関数であってよい。ここで、αは未定乗数である。第１拘束条件によって、第１二値変数のビットフリップが第２二値変数と等しくなり、第２正則化項を第２二値変数によって表した場合であっても、選択される特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる。
【００４７】
第３設定部１３は、第２正則化項に第１二値変数のビットフリップの３次以上の積が含まれる場合に、２の第１二値変数のビットフリップの積を１の第３二値変数に置換してもよい。これにより、目的関数に含まれる二値変数の次数を２以下とすることができ、第２正則化項を第１二値変数のビットフリップと第３二値変数の二次式で表し、イジングマシン２０への実装に適した表式とすることができる。この場合、イジングマシン２０は、目的関数を最小化又は最大化する第１二値変数の値、第２二値変数の値及び第３二値変数の値を求める。
【００４８】
より具体的には、第２正則化項は、第３設定部１３により置換された２の第１二値変数のビットフリップの積と１の第３二値変数とが等しくなるように拘束する第２拘束条件を表す項を含んでよい。これにより、２の第１二値変数のビットフリップの積を第３二値変数に置き換えることができ、第２正則化項を第１二値変数のビットフリップと第３二値変数の２次式によって表して、イジングマシン２０への実装に適した表式とすることができる。ここで、第３二値変数をｕｌ（ｌ＝１〜Ｌ、ｕｌ＝０又は１）と表すとき、第２拘束条件は、Σ［（¬ｗｊ）（¬ｗｋ）−２（¬ｗｊ＋¬ｗｋ）ｕｌ＋３ｕｌ］により表される項を含んでよい。和は、第３設定部１３により置換が行われたｊ，ｋ，ｌの組について行われる。これにより、２の第１二値変数のビットフリップの積が第３二値変数と等しくなり、第２正則化項を第３二値変数によって表した場合であっても、選択される特徴量の数を少なくしつつ、強学習器の分析精度を向上させるような特徴量を選択することができる。２の第１二値変数のビットフリップの積を１の第３二値変数に置換する処理については、図４を用いてより詳細に説明する。
【００４９】
目的関数は、Ｎ−２Σｓ＝１ＳΣｊ＝１ＮΣｋ＝１Ｎｗｊｈｊ（ｘ（ｓ））ｗｋｈｋ（ｘ（ｓ））＋Σｊ＝１Ｎｗｊ（λＩｊ−２Ｎ−１Σｓ＝１Ｓｈｊ（ｘ（ｓ））ｔ（ｓ））＋λ１Σｉ＝１Ｍ［１−Πｊ＝１Ｎ（¬ｗｊ）Ｆｉｊ］＋α｛Σｊ＝１Ｎ［（ｖｊ−（１−ｗｊ）］２＋Σ（ｊ，ｋ，ｌ）［（¬ｗｊ）（¬ｗｋ）−２（¬ｗｊ＋¬ｗｋ）ｕｌ＋３ｕｌ］｝によって表される関数であってよい。ここで、αは未定乗数である。また、Σ（ｊ，ｋ，ｌ）は、第３設定部１３により置換が行われたｊ，ｋ，ｌの組に関する和を表す。
【００５０】
図３は、本実施形態に係る特徴量選択装置１０の物理的構成を示す図である。特徴量選択装置１０は、ノイマン型コンピュータで構成されてよく、演算部に相当するＣＰＵ（Central Processing Unit）１０ａと、記憶部に相当するＲＡＭ（Random Access Memory）１０ｂと、記憶部に相当するＲＯＭ（Read only Memory）１０ｃと、通信部１０ｄと、入力部１０ｅと、表示部１０ｆと、を有する。これらの各構成は、バスを介して相互にデータ送受信可能に接続される。なお、本例では特徴量選択装置１０が一台のコンピュータで構成される場合について説明するが、特徴量選択装置１０は、複数のコンピュータが組み合わされて実現されてもよい。また、図２で示す構成は一例であり、特徴量選択装置１０はこれら以外の構成を有してもよいし、これらの構成のうち一部を有さなくてもよい。
【００５１】
ＣＰＵ１０ａは、ＲＡＭ１０ｂ又はＲＯＭ１０ｃに記憶されたプログラムの実行に関する制御やデータの演算、加工を行う制御部である。ＣＰＵ１０ａは、イジングマシン２０を用いて特徴量を選択するプログラム（特徴量選択プログラム）を実行する演算部である。ＣＰＵ１０ａは、入力部１０ｅや通信部１０ｄから種々のデータを受け取り、データの演算結果を表示部１０ｆに表示したり、ＲＡＭ１０ｂやＲＯＭ１０ｃに格納したりする。
【００５２】
ＲＡＭ１０ｂは、記憶部のうちデータの書き換えが可能なものであり、例えば半導体記憶素子で構成されてよい。ＲＡＭ１０ｂは、ＣＰＵ１０ａが実行する特徴量選択プログラム等のデータを記憶してよい。なお、これらは例示であって、ＲＡＭ１０ｂには、これら以外のデータが記憶されていてもよいし、これらの一部が記憶されていなくてもよい。
【００５３】
ＲＯＭ１０ｃは、記憶部のうちデータの読み出しが可能なものであり、例えば半導体記憶素子で構成されてよい。ＲＯＭ１０ｃは、例えば特徴量選択プログラムや、書き換えが行われないデータを記憶してよい。
【００５４】
通信部１０ｄは、特徴量選択装置１０を他の機器に接続するインターフェースである。通信部１０ｄは、イジングマシン２０及びデータベース４０と有線又は無線通信により接続されて、種々のデータを送受信してよい。また、通信部１０ｄは、インターネット等の通信ネットワークＮに接続されてもよい。
【００５５】
入力部１０ｅは、ユーザからデータの入力を受け付けるものであり、例えば、キーボード及びタッチパネルを含んでよい。
【００５６】
表示部１０ｆは、ＣＰＵ１０ａによる演算結果を視覚的に表示するものであり、例えば、ＬＣＤ（Liquid Crystal Display）により構成されてよい。表示部１０ｆは、例えばイジングマシン２０に設定する目的関数や選択された特徴量に関する情報を表示したりしてよい。
【００５７】
特徴量選択プログラムは、ＲＡＭ１０ｂやＲＯＭ１０ｃ等のコンピュータによって読み取り可能な記憶媒体に記憶されて提供されてもよいし、通信部１０ｄにより接続される通信ネットワークＮを介して提供されてもよい。特徴量選択装置１０では、ＣＰＵ１０ａが特徴量選択プログラムを実行することにより、図１を用いて説明した様々な動作が実現される。なお、これらの物理的な構成は例示であって、必ずしも独立した構成でなくてもよい。例えば、特徴量選択装置１０は、ＣＰＵ１０ａとＲＡＭ１０ｂやＲＯＭ１０ｃが一体化したＬＳＩ（Large-Scale Integration）を備えていてもよい。
【００５８】
図４は、本実施形態に係る特徴量選択装置１０により扱われる弱学習器と特徴量Ｆの関係の一例を示す図である。本例では、簡単のため、特徴量の次元が４（Ｍ＝４）であり、データセットの数が３（Ｓ＝３）であり、弱学習器の数が３（Ｎ＝３）である場合について説明する。
【００５９】
特徴量Ｆは、第１ユーザ（Ｕｓｅｒ  １）、第２ユーザ（Ｕｓｅｒ  ２）及び第３ユーザ（Ｕｓｅｒ  ３）についてそれぞれ１つずつ記憶されており、その値はｘ１（ｓ），ｘ２（ｓ），ｘ３（ｓ），ｘ４（ｓ）（ｓ＝１〜３）である。弱学習器ｈ１（ｘ）は、これらの特徴量のうち、ｘ１（ｓ），ｘ３（ｓ），ｘ４（ｓ）を用いる。また、弱学習器ｈ２（ｘ）は、ｘ１（ｓ），ｘ４（ｓ）を用いる。また、弱学習器ｈ３（ｘ）は、ｘ２（ｓ），ｘ３（ｓ），ｘ４（ｓ）を用いる。
【００６０】
この場合、行列Ｆｉｊは、例えばＦ１ｊ＝（１，１，０）である。すなわち、特徴量ｘ１（ｓ）は、１番目の弱学習器ｈ１（ｘ）と１番目の弱学習器ｈ２（ｘ）とに入力され、３番目の弱学習器ｈ３（ｘ）に入力されない。同様に、Ｆ２ｊ＝（０，０，１）、Ｆ３ｊ＝（１，０，１）、Ｆ４ｊ＝（１，１，１）である。
【００６１】
この場合、第２正則化項は、（１−（¬ｗ１）（¬ｗ２））＋（１−（¬ｗ３））＋（１−（¬ｗ１）（¬ｗ３））＋（１−（¬ｗ１）（¬ｗ２）（¬ｗ３））と表される。第３設定部１３は、（１−（¬ｗ１）（¬ｗ２）（¬ｗ３））という項に第１二値変数のビットフリップの３次の積が含まれるため、２の第１二値変数のビットフリップの積を１の第３二値変数に置換する。第３設定部１３は、例えば、（¬ｗ１）（¬ｗ２）をｕ１に置換してよい。これにより、第２正則化項は、第２拘束条件を加えて、（１−（¬ｗ１）（¬ｗ２））＋（１−（¬ｗ３））＋（１−（¬ｗ１）（¬ｗ３））＋（１−ｕ１（¬ｗ３））＋α［（¬ｗ１）（¬ｗ２）−２（¬ｗ１＋¬ｗ２）ｕ１＋３ｕ１］と表される。さらに、第１二値変数のビットフリップが第２二値変数に等しくなるように拘束する第１拘束条件を加えて、第２正則化項は、（１−ｖ１ｖ２）＋（１−ｖ３）＋（１−ｖ１ｖ３）＋（１−ｕ１ｖ３）＋α｛Σｊ＝１３［（ｖｊ−（１−ｗｊ）］２＋［（¬ｗ１）（¬ｗ２）−２（¬ｗ１＋¬ｗ２）ｕ１＋３ｕ１］｝と表される。なお、［（¬ｗ１）（¬ｗ２）−２（¬ｗ１＋¬ｗ２）ｕ１＋３ｕ１］という項は、［（１−ｗ１）（１−ｗ２）−２（２−ｗ１−ｗ２）ｕ１＋３ｕ１］と表してもよいし、［ｖ１ｖ２−２（ｖ１＋ｖ２）ｕ１＋３ｕ１］と表してもよい。
【００６２】
図５は、本実施形態に係る特徴量選択装置１０により実行される特徴量選択処理のフローチャートである。特徴量選択装置１０は、はじめに、強学習器の出力の誤差を表す項を目的関数に設定する（Ｓ１０）。また、特徴量選択装置１０は、第１正則化項を目的関数に設定する（Ｓ１１）。そして、特徴量選択装置１０は、第２正則化項を目的関数に設定する（Ｓ１２）。ここで、強学習器の出力の誤差を表す項及び第１正則化項は、第１二値変数の関数であり、第２正則化項は、第１拘束条件及び第２拘束条件を含んでよく、第１二値変数、第２二値変数及び第３二値変数の関数であってよい。また、特徴量選択装置１０によりイジングマシン２０に設定される二値変数を引数とする目的関数は、二値変数について微分可能でなくてもよい。従来の目的関数は、確率的勾配降下法等によって最小又は最大を求めることが通常であるため、目的関数が微分可能である必要があったが、イジングマシン２０に設定する目的関数についてそのような制約はなく、より柔軟な目的関数の設定が行える。
【００６３】
その後、特徴量選択装置１０は、イジングマシン２０により求められた、目的関数を最小化する第１二値変数の値を取得する（Ｓ１３）。そして、特徴量選択装置１０は、取得した第１二値変数の値に基づいて、複数の特徴量から１又は複数の特徴量を選択する（Ｓ１４）。以上により、特徴量選択処理が終了する。
【００６４】
以上説明した実施形態は、本発明の理解を容易にするためのものであり、本発明を限定して解釈するためのものではない。実施形態が備える各要素並びにその配置、材料、条件、形状及びサイズ等は、例示したものに限定されるわけではなく適宜変更することができる。また、異なる実施形態で示した構成同士を部分的に置換し又は組み合わせることが可能である。
【符号の説明】
【００６５】
１０…特徴量選択装置、１０ａ…ＣＰＵ、１０ｂ…ＲＡＭ、１０ｃ…ＲＯＭ、１０ｄ…通信部、１０ｅ…入力部、１０ｆ…表示部、１１…第１設定部、１２…第２設定部、１３…第３設定部、２０…イジングマシン、３０…ユーザ端末、４０…データベース、１００…特徴量選択システム
【図１】
2018235568.tif 000003
【図２】
2018235568.tif 000004
【図３】
2018235568.tif 000005
【図４】
2018235568.tif 000006
【図５】
2018235568.tif 000007
【国際調査報告】
2018235568.tif 000008
2018235568.tif 000009
2018235568.tif 000010
2018235568.tif 000011