(57)【要約】  本発明のデータ分類方法を実現する情報処理装置１００は、設定する多項式関数の各項の係数を要素とする列ベクトルをａ、各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、各要素が１又は−１の値をとるバイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出するＣＰＵを備えており、キーボードを通じて入力された分類対象のデータを設定した多項式関数に従って分類する。
2007088973.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定し、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出し、算出した関数の値に基づいて前記バイナリデータの分類を行うデータ分類方法において、
前記バイナリデータを２つのクラスに分類すべく項の数が３×２n-2 より少ない多項式関数を設定することを特徴とするデータ分類方法。
【請求項２】
各要素が１又は−１の値をとるバイナリデータを分類対象とし、設定すべき多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、バイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出することを特徴とする請求項１に記載のデータ分類方法。
【請求項３】
ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定し、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出し、算出した関数の値に基づいて前記バイナリデータの分類を行うデータ分類装置において、
前記バイナリデータを２つのクラスに分類すべく項の数が３×２n-2 より少ない多項式関数を設定する手段を備えることを特徴とするデータ分類装置。
【請求項４】
各要素が１又は−１の値をとるバイナリデータを受付ける手段と、前記設定手段は、設定すべき多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、バイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出する手段とを備えることを特徴とする請求項３に記載のデータ分類装置。
【請求項５】
コンピュータに、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定させ、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出させ、算出させた関数の値に基づいて前記バイナリデータの分類を行わせるコンピュータプログラムにおいて、
コンピュータに、前記バイナリデータを２つのクラスに分類させるべく項の数が３×２n-2 より少ない多項式関数を設定させるステップを有することを特徴とするコンピュータプログラム。
【請求項６】
コンピュータに、設定させる多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、各要素が１又は−１の値をとるバイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出させるステップを有することを特徴とする請求項５に記載のコンピュータプログラム。
【請求項７】
コンピュータに、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定させ、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出させ、算出させた関数の値に基づいて前記バイナリデータの分類を行わせるコンピュータプログラムが記録されているコンピュータでの読み取りが可能な記録媒体において、
コンピュータに、前記バイナリデータを２つのクラスに分類させるべく項の数が３×２n-2 より少ない多項式関数を設定させるステップを有するコンピュータプログラムが記録されていることを特徴とする記録媒体。
【請求項８】
コンピュータに、設定させる多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、各要素が１又は−１の値をとるバイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出させるステップを有するコンピュータプログラムが記録されていることを特徴とする請求項７に記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、項数が少ない多項式関数を用いてバイナリデータを２つのクラスに分類することができるデータ分類方法、データ分類装置、コンピュータプログラム、及び記録媒体に関する。
【背景技術】
【０００２】
膨大な情報量を有するデータベースにおけるデータを、複数のクラスに分類するデータ分類方法は、近年の情報処理において欠かせない技術となっている。【０００３】
あるデータの分類について、明確に分類できるものは稀であるからすでに的確に分類がなされた学習用のデータを用いて学習させ、その学習結果に基づいて分類を行う手法が提案されている。例えば、あらかじめ正解の分かっている学習用データからデータの分類の仕方を自動的に学習する教師あり学習では、サポート・ベクトル・マシンなどのカーネル関数を用いた学習方法が知られている（例えば、特許文献１参照）。
【特許文献１】特開２０００−２９３５０２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
カーネル関数としては内積を用いたものが主流であるが、内積を用いた場合、分類にかかる時間が他の従来手法に比べて極めて遅いことが知られている。これは、一つのデータの分類に数千回から数十万回という膨大な回数の内積計算が必要なためである。【０００５】
一方、与えられたデータを２つのクラスに分類するという２クラス分類問題では多項式関数が用いられることも多い。予め閾値を設定しておき、与えられたデータを多項式関数に代入することにより、この多項式関数の値を求め、閾値との大小関係を調べることで２つのクラスに分類することが可能である。【０００６】
しかしながら、ニューラル・ネットワーク等の分野では、設定すべき多項式関数を構成する単項式の数が非常に多くなり、大容量のメモリ、高速な演算手段が必要となるという問題点を有していた。【０００７】
本発明は斯かる事情に鑑みてなされたものであり、バイナリデータを２つのクラスに分類するために、項の数が３×２n-2 個よりも少ない多項式関数を設定する構成とすることにより、２クラス分類問題を解くのに必要な単項式の数に上限を与えることができるデータ分類方法、データ分類装置、コンピュータプログラム、および記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００８】
第１発明に係るデータ分類方法は、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定し、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出し、算出した関数の値に基づいて前記バイナリデータの分類を行うデータ分類方法において、前記バイナリデータを２つのクラスに分類すべく項の数が３×２n-2 より少ない多項式関数を設定することを特徴とする。【０００９】
第２発明に係るデータ分類方法は、各要素が１又は−１の値をとるバイナリデータを分類対象とし、設定すべき多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、バイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出することを特徴とする。【００１０】
第３発明に係るデータ分類装置は、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定し、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出し、算出した関数の値に基づいて前記バイナリデータの分類を行うデータ分類装置において、前記バイナリデータを２つのクラスに分類すべく項の数が３×２n-2 より少ない多項式関数を設定する手段を備えることを特徴とする。【００１１】
第４発明に係るデータ分類装置は、各要素が１又は−１の値をとるバイナリデータを受付ける手段と、設定すべき多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、バイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出する手段とを備えることを特徴とする。【００１２】
第５発明に係るコンピュータプログラムは、コンピュータに、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定させ、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出させ、算出させた関数の値に基づいて前記バイナリデータの分類を行わせるコンピュータプログラムにおいて、コンピュータに、前記バイナリデータを２つのクラスに分類させるべく項の数が３×２n-2 より少ない多項式関数を設定させるステップを有することを特徴とする。【００１３】
第６発明に係るコンピュータプログラムは、コンピュータに、設定させる多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、各要素が１又は−１の値をとるバイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出させるステップを有することを特徴とする。【００１４】
第７発明に係る記録媒体は、コンピュータに、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定させ、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出させ、算出させた関数の値に基づいて前記バイナリデータの分類を行わせるコンピュータプログラムが記録されているコンピュータでの読み取りが可能な記録媒体において、コンピュータに、前記バイナリデータを２つのクラスに分類させるべく項の数が３×２n-2 より少ない多項式関数を設定させるステップを有するコンピュータプログラムが記録されていることを特徴とする。【００１５】
第８発明に係る記録媒体は、コンピュータに、設定させる多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤn 、各要素が１又は−１の値をとるバイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄn ａ＞０を満たす列ベクトルａを算出させるステップを有するコンピュータプログラムが記録されていることを特徴とする。【００１６】
第１発明、第３発明、第５発明、及び第７発明にあっては、バイナリデータを２つのクラスに分類する際に使用する関数を項の数が３×２n-2 個よりも少ない多項式関数に設定するため、２クラス分類問題を解くのに必要な単項式の数が抑えられる。【００１７】
第２発明、第４発明、第６発明、及び第８発明にあっては、設定すべき多項式関数の各係数を列ベクトルａ＝［ａ0 ，ａ1 ，…，ａm ］T （ｍ＝２n −１）で表し、ｄｉａｇ（ｙ）Ｄn ａ＞０の条件下で列ベクトルａを求めることにより、列ベクトルａの要素の少なくとも１／４がゼロとなる。
【発明の効果】
【００１８】
第１発明、第３発明、第５発明、及び第７発明による場合は、バイナリデータを２つのクラスに分類する際の判定基準として多項式関数を使用し、しかもその多項式関数の項数を３×２n-2 よりも少なくしている。一般的に、３×２n-2 個の単項式からなる多項式関数を用いることにより、どのような２クラス分類問題も解くことは可能であるが、本発明では、３×２n-2 個よりも少ない数の単項式を用いて多項式関数を設定することができる。そのため、大規模な問題を解く場合であっても、使用するメモリの削減、演算速度の向上を図ることができる。【００１９】
第２発明、第４発明、第６発明、及び第８発明にあっては、設定すべき多項式関数の各係数を列ベクトルａ＝［ａ0 ，ａ1 ，…，ａm ］T で表し、ｄｉａｇ（ｙ）Ｄn ａ＞０の条件下で列ベクトルａを求めることにより、列ベクトルａの要素の少なくとも１／４がゼロとなる。したがって、多項式関数の項の数が２n-2 個よりも少なく抑えられ、大規模な問題を解く場合であっても、使用するメモリの削減、演算速度の向上を図ることができる。
【図面の簡単な説明】
【００２０】
【図１】本発明に係るデータ分類装置の内部構成を示すブロック図である。
【図２】多項式関数を求める際に情報処理装置が実行する処理の手順を説明するフローチャートである。
【図３】多項式関数を求める際に情報処理装置が実行する処理の手順を説明するフローチャートである。
【図４】クラス分類問題の例題を示す図表である。
【図５】行列Ｄ3 の要素を示す図表である。
【図６】分割した行列Ｄ3 を示す図表である。
【図７】本実施の形態に係る画像認識装置の内部構成を示すブロック図である。
【図８】画像認識装置が実行する処理の手順を示すフローチャートである。
【図９】画像認識装置が取得する画像データの一例を示す模式図である。
【図１０】学習データとして用意する画像の一例を示す模式図である。
【図１１】テストデータを示す模式図である。
【符号の説明】
【００２１】
１００  情報処理装置
１０１  ＣＰＵ
１０２  ＲＯＭ
１０３  ＲＡＭ
１０４  記憶装置
１０５  入出力ＩＦ
１０６  キーボード
１０７  モニタ
１０８  補助記憶装置
１１０  記録媒体
【発明を実施するための最良の形態】
【００２２】
以下、本発明をその実施の形態を示す図面に基づいて具体的に説明する。
実施の形態１．
図１は本発明に係るデータ分類装置の内部構成を示すブロック図である。本発明に係るデータ分類装置は、パーソナルコンピュータ、ワークステーション等の情報処理装置１００により実現される。情報処理装置１００は、演算手段としてのＣＰＵ１０１を備えており、このＣＰＵ１０１には、ＲＯＭ１０２、ＲＡＭ１０３、記憶装置１０４、入出力ＩＦ１０５、補助記憶装置１０８等のハードウェアがバス１０９を介して接続されている。【００２３】
ＲＯＭ１０２には、バス１０９に接続された各種ハードウェアの動作を制御する制御プログラムが格納されている。ＣＰＵ１０１はこの制御プログラムをＲＡＭ１０３上にロードして実行することにより、ハードウェア全体の動作を制御する。【００２４】
記憶装置１０４は、ハードディスクドライブを備えており、本発明のデータ分類方法を実現するコンピュータプログラム、このコンピュータプログラムを実行する際に必要となるデータ等を記憶する。【００２５】
入出力ＩＦ１０５には、入力デバイスであるキーボード１０６、及び出力デバイスであるモニタ１０７が接続される。情報処理装置１００は、分類対象のデータ、前述したコンピュータプログラムの起動開始指示等をキーボード１０６を通じて受付ける。また、情報処理装置１００は、キーボード１０６を通じて入力されたパラメータ、前述したコンピュータプログラムの演算結果である分類結果等をモニタ１０７上に表示する。【００２６】
なお、前述のコンピュータプログラムは、必ずしも記憶装置１０４にプリインストールされている必要はなく、ＦＤ、ＣＤ−ＲＯＭ、ＤＶＤ等の記録媒体１１０により提供される形態であってもよい。そのため、情報処理装置１００は、前記コンピュータプログラムが記録された記録媒体１１０からコンピュータプログラムを読み取るためのＦＤドライブ、ＣＤ−ＲＯＭドライブ、ＤＶＤドライブ等の補助記憶装置１０８を備えている。補助記憶装置１０８により読み取られたコンピュータプログラムは記憶装置１０４に記憶される。ＣＰＵ１０１は、必要に応じて記憶装置１０４から前述のコンピュータプログラムをＲＡＭ１０３上にロードして実行することにより、情報処理装置１００を本発明に係るデータ分類装置として動作させる。【００２７】
本実施の形態では、情報処理装置１００による演算処理により、以下で説明する二クラス分類問題を解く。二クラス分類問題は、Ｃ＝（Ｓ+ ，Ｓ- ）により与えられる。ここで、Ｓ+ ，Ｓ- は、Ｓ+ ⊂｛−１，１｝n 、Ｓ- ⊂｛−１，１｝n を満たし、互いに異なるクラスを表す。ｘ∈Ｓ+ を満たすどのようなｘに対してもｆ（ｘ）＞０となり、ｘ∈Ｓ- を満たすどのようなｘに対してもｆ（ｘ）＜０となるようなｆ（ｘ）：｛−１，１｝n →Ｒ（Ｒは実数）がＣに対する解となる。【００２８】
本実施の形態では、二クラス分類問題の解として多項式関数ｐ（ｘ0 ，ｘ1 ，…，ｘn-1 ）を求める。多項式関数ｐ（ｘ0 ，ｘ1 ，…，ｘn-1 ）は次式により与えられる。【００２９】
【数１】
2007088973.tif 000003
【００３０】
ここで、Ｓi ⊂｛０，１，…，ｎ−１｝であり、全てのｉに対してｘi2＝１となる。多項式関数ｐ（ｘ0 ，ｘ1 ，…，ｘn-1 ）に関し、係数ａi を除いた各項を単項式という。【００３１】
次に、単項式と項の組合わせとの指標付けを定義する。関数Ｋ（ｍ）を次式により定義する。【００３２】
【数２】
2007088973.tif 000004
【００３３】
このとき、関数Ｋ（ｍ）は、単項式の組と｛１，２，…，２n ｝との１対１のマッピングを表す。そこで、単項式に対する指標付けを、【００３４】
【数３】
2007088973.tif 000005
【００３５】
により表す。また、係数ｍj を係数ａj と同一視する。この指標付けにより、多項式関数ｐは、ベクトル表記法によって以下の式で表される。【００３６】
【数４】
2007088973.tif 000006
【００３７】
このとき、多項式関数ｐの計算は内部的には、次式により与えられる。【００３８】
【数５】
2007088973.tif 000007
【００３９】
次に、多項式関数ｐを行列を用いて定式化する。【００４０】
【数６】
2007088973.tif 000008
【００４１】
としたとき、Ｄn ａは、多項式関数ｐの｛−１，１｝n に対する影響を表している。ここで、Ｄn は、２n ×２n の行列であり、【００４２】
【数７】
2007088973.tif 000009
【００４３】
により与えられる。ここで、Ｄn を次数ｎの代入行列といい、Ｄn aは多項式関数ｐの行列表現となっている。例えば、２次のオーダの代入行列は、以下のように表すことができる。【００４４】
【数８】
2007088973.tif 000010
【００４５】
二クラス分類問題Ｃ＝（Ｓ+ ，Ｓ- ）では、Ｄ+nａ＞０，Ｄ-nａ＜０という条件を満たすように、行列Ｄn の列を、Ｄ+nとＤ-nとに分割する。ここで、ａ＝［ａ0 ，ａ1 ，…，ａn ］T ∈Ｒn は多項式関数ｐの係数である。ここで、【００４６】
【数９】
2007088973.tif 000011
【００４７】
を定義したとき、二クラス分類問題Ｃは、ＹＤn ａ＞０となるような、ベクトルａ＝［ａ0 ，ａ1 ，…ａn ］T ∈Ｒn を求めることと等価である。【００４８】
次に、具体的なアルゴリズムについて説明する。図２及び図３は多項式関数を求める際に情報処理装置１００が実行する処理の手順を説明するフローチャートである。前述したように、どのような２クラス分類問題もｄｉａｇ（ｙ）Ｄn ｚ＞０により表すことができる。ここで、ｙ∈｛−１，１｝n であり、ベクトルｚは、求めるべき多項式関数を構成する単項式の係数を与える列ベクトルである。【００４９】
まず、情報処理装置１００のＣＰＵ１０１は、前述した不等式を２つの部分に分割する（ステップＳ１）。すなわち、ｄｉａｇ（ｙ）Ｄn ｚ＞０を、【００５０】
【数１０】
2007088973.tif 000012
【００５１】
のように表す。次に、ＣＰＵ１０１は、行列Ｆ，Ｇを初期化し、ｄ０，ｄ１ ，…，ｄm （ｍ＝２n −１）の各行を以下のように分配する（ステップＳ２）。すなわち、（ｙiu，ｙid）＝（＋１，＋１）である場合には、ｄi を行列Ｆに加え、（ｙiu，ｙid）＝（−１，−１）である場合には、−ｄi を行列Ｆに加える。また、（ｙiu，ｙid）＝（＋１，−１）である場合には、ｄｉを行列Ｇに加え、（ｙiu，ｙid）＝（−１，＋１）である場合には、−ｄｉを行列Ｇに加える。【００５２】
次に、ＣＰＵ１０１は、行列Ｆ及び行列Ｇを構成する行の数を比較し、行列Ｇを構成する行の数ｒ（Ｇ）が行列Ｆを構成する行の数ｒ（Ｇ）以上であるか否かを判断する（ステップＳ３）。【００５３】
各行列Ｆ，Ｇの数がｒ（Ｇ）≧ｒ（Ｆ）を満たす場合（Ｓ３：ＹＥＳ）、以下の処理を行う。まず、ＣＰＵ１０１は、行列Ｆを構成する行の和ｆを求める（ステップＳ４）。また、行列Ｇを還元して得られる行梯形の列Ｇ’を求める（ステップＳ５）。次いで、行列Ｇ’のｉ番目の行に最初に現れる非零の要素をコラムインデックスｉc として設定する（ステップＳ６）。更に、ν及びβを以下の式で与える。【００５４】
【数１１】
2007088973.tif 000013
【００５５】
そして、ＣＰＵ１０１は、βの各要素βi をチェックし、各要素βi が０以下であるか否かを判断する（ステップＳ７）。βi の値が０以下であると判断した場合（Ｓ７：ＹＥＳ）、ＣＰＵ１０１は、γi ＝１−βi を算出すると共に、γi ’を１に設定する（ステップＳ８）。また、βi の値が０より大きいと判断した場合（Ｓ７：ＮＯ）、ＣＰＵ１０１は、γi を１に設定すると共に、γi ’＝１＋βi を算出する（ステップＳ９）。【００５６】
このとき、ＣＰＵ１０１は、多項式関数の各係数を表すベクトルｚを、【００５７】
【数１２】
2007088973.tif 000014
【００５８】
により与える（ステップＳ１０）。ＣＰＵ１０１は、ここで本ルーチンによる演算を終了する。【００５９】
一方、各行列Ｆ，Ｇの数がｒ（Ｇ）＜ｒ（Ｆ）を満たす場合には（Ｓ３：ＮＯ）、以下の処理を行う。まず、ＣＰＵ１０１は、行列Ｇを構成する行の和ｇを求める（ステップＳ１１）。また、行列Ｆを還元して得られる行梯形の行列Ｆ’を求める（ステップＳ１２）。次いで、行列Ｆ’のｉ番目の行に最初に現れる非零の要素をコラムインデックスｉc として設定する（ステップＳ１３）。更に、ν及びβを以下の式で与える。【００６０】
【数１３】
2007088973.tif 000015
【００６１】
そして、ＣＰＵ１０１は、βの各要素βi をチェックし、各要素βi が０以下であるか否かを判断する（ステップＳ１４）。βi の値が０以下であると判断した場合（Ｓ１４：ＹＥＳ）、ＣＰＵ１０１は、αi ＝１−βi を算出すると共に、αi ’を１に設定する（ステップＳ１５）。また、βi の値が０より大きいと判断した場合（Ｓ１４：ＮＯ）、ＣＰＵ１０１は、αi を１に設定すると共に、αi ’＝１＋βi を算出する（ステップＳ１６）。【００６２】
このとき、ＣＰＵ１０１は、多項式関数の各係数を表すベクトルｚを、【００６３】
【数１４】
2007088973.tif 000016
【００６４】
により与える（ステップＳ１７）。ＣＰＵ１０１は、ここで本ルーチンによる演算を終了する。【００６５】
このアルゴリズムの演算結果であるｚは、前述した不等式ｄｉａｇ（ｙ）Ｄn ｚ＞０を満たしており、２クラス分類問題に対する解を与える。このアルゴリズムの重要かつ新規な性質は、解として求めたベクトルｚを構成する要素のうち２n ／４がゼロであるという点にある。すなわち、求めた多項式関数の項（単項式）の数は、｛−１，１｝に分類するどのような２クラス分類問題についても３×２n-2 個以下となる。その結果、分類対象のデータが与えられた場合、メモリ容量等の演算資源を低く抑えることができ、高速な分類が可能となる。【００６６】
次に、適用例について説明する。図４はクラス分類問題の例題を示す図表である。図４では、Ｘ0 ，Ｘ1 ，Ｘ2 の各要素が与えられた場合に属するべきクラスの値を定義している。要素の数は３つであるため、本発明では６つ（＝３×２n-2 ＝３×２1 ）以下の単項式で構成される多項式が求まる。【００６７】
前述したアルゴリズムを適用する場合、二クラス分類問題は、ｄｉａｇ（ｙ）Ｄ3 ｚ＞０を満たすｚを求めること等価である。ここで、ｙ＝［−１，−１，１，１，１，−１，−１，−１］であり、Ｄ3 は、図５の図表に示した要素を持つ行列として定義される。【００６８】
ステップＳ１の処理により、ベクトルｙを、ｙu ＝［−１，−１，１，１］とｙd ＝［１，−１，−１，−１］とに分割すると共に、行列Ｄn を図６に示した図表の如く分割する。【００６９】
ステップＳ２の処理により、行列Ｆ，Ｇを初期化し、行列Ｄn の各行を分配する。すなわち、（ｙ0u，ｙ0d）＝（−１，＋１）であるため、−ｄ0 を行列Ｇに加える。同様に、（ｙ1u，ｙ1d）＝（−１，−１）より、−ｄ1 を行列Ｆに加え、（ｙ2u，ｙ2d）＝（＋１，−１）より、ｄ2 を行列Ｇに加え、（ｙ3u，ｙ3d）＝（＋１，−１）より、ｄ3 を行列Ｆに加える。したがって、行列Ｆの行の数ｒ（Ｆ）は１であり、行列Ｇの行の数ｒ（Ｇ）は３になる。【００７０】
ｒ（Ｇ）≧ｒ（Ｆ）の条件を満たすため、ＣＰＵ１０１はステップＳ４の処理を実行し、行列Ｆを構成する行の和ｆを求める。その結果、ｆ＝（−１，１，−１，１）となる。また、ステップＳ１２の処理により、行列Ｇを還元して行梯形の行列Ｇ’を求める。行列Ｇ’は次式により表される。【００７１】
【数１５】
2007088973.tif 000017
【００７２】
この行列Ｇ’からコラムインデックスを１c ＝１，２c ＝２，３c ＝３に設定する。このとき、ν及びβは、以下のように計算される。【００７３】
【数１６】
2007088973.tif 000018
【００７４】
次に、βの各要素の正負を調べ、γ及びγ’を求める。それぞれ、γ＝（２，２，１）、γ’＝（１，１，２）となる。このとき、ｚ＝［ｆ＋ν，（γ＋γ’）Ｇ］で与えられるので、ｚの各要素が求まり、ｚ＝（０，０，０，４，３，−３，−９，−３）となる。【００７５】
このようにして、二クラス分類問題の解が次のように求まる。【００７６】
【数１７】
2007088973.tif 000019
【００７７】
上の式にｘ０，ｘ１，ｘ２の値を代入した場合、図４に示した定義を満たすことが分かる。また、多項式関数ｐ（ｘ０，ｘ１，ｘ２）を構成する単項式の数は５つとなり、３×２n-2 より少ない数となっていることが分かる。【００７８】
実施の形態２．
実施の形態１で説明したデータ分類装置を用いて、文字認識、パターン認識などを行う画像認識装置を構築することができる。本実施の形態では、８×８画素からなるデジタル数字を認識する画像認識装置について説明する。【００７９】
図７は本実施の形態に係る画像認識装置の内部構成を示すブロック図である。画像認識装置２００は、画像入力部２０１、前処理部２０２、特徴ベクトル抽出部２０３、モード判別部２０４、学習処理部２０５、画像判定部２０６を備える。【００８０】
画像入力部２０１は、文字、パターンなどの画像を光学的に読み取るスキャナなどの入力デバイスであり、この画像入力部２０１が取得した画像データは前処理部２０２に出力される。【００８１】
前処理部２０２は、画像入力部２０１から受け取った画像データの前処理を行う処理部である。具体的には、画像データを平滑化処理してノイズを除去した後に、これを所定の閾値で２値化して２値画像を生成する。なお、入力された画像データがモノクロ画像である場合には２値化処理を省略することができる。【００８２】
特徴ベクトル抽出部２０３は、画像の特徴を表すベクトル（以下、特徴ベクトルとする）を抽出する。特徴ベクトルを抽出する手法としては、要素が１又は−１の値をとり、決まった要素数のベクトルを出力することができる如何なる抽出手法を用いてもよい。【００８３】
画像認識装置２００は、認識対象の画像を学習するための学習モードと入力された画像について画像認識を行う判定モードとを有しており、モードを区別するための情報（モード情報）を外部から受付けるようにしている。モード判別部２０４は外部から受付けたモード情報に従って判別結果を特徴ベクトル抽出部２０３へ送出する。【００８４】
モード判別部２０４の判別結果が学習モードを示す場合、特徴ベクトル抽出部２０３は抽出した特徴ベクトルを学習データとして学習処理部２０５へ出力し、判定モードを示す場合、特徴ベクトル抽出部２０３は抽出した特徴ベクトルをテストデータとして学習処理部２０５へ出力する。【００８５】
学習処理部２０５は、入力された特徴ベクトルを用いて二クラス分類問題の解を与える多項式関数を決定する。すなわち、入力された特徴ベクトルを実施の形態１で説明したベクトルｙとみなし、前述した手法を用いて計算を行うことにより多項式関数の各係数を求める。学習処理部２０５は、決定した多項式関数を学習結果として画像判定部２０６に通知する。【００８６】
一方、画像判定部２０６は、新たに入力された画像から抽出した特徴ベクトルを学習処理部２０５で決定された多項式関数に代入することにより画像認識を行う。入力された画像が認識対象の画像であると判定される場合、多項式関数は「１」を出力し、認識対象の画像と異なると判定される場合、多項式関数は「−１」を出力する。【００８７】
以下、画像認識装置２００が実行する処理の手順について説明する。図８は画像認識装置２００が実行する処理の手順を示すフローチャートである。まず、画像認識装置２００は画像入力部２０１を通じて画像データを取得し（ステップＳ２１）、前処理を実行する（ステップＳ２２）。図９は画像認識装置２００が取得する画像データの一例を示す模式図である。この例は、８画素×８画素により構成される数字の「４」を示す２次元画像であり、各画素が２値化されている。【００８８】
次いで、画像認識装置２００の特徴ベクトル抽出部２０３は特徴ベクトルの抽出を行う（ステップＳ２３）。特徴ベクトルの抽出手法は既存の手法を用いることができる。本実施の形態では、前述した８画素×８画素の画像に対して、１又は−１を要素に持つ１０ビットの特徴ベクトルを出力する抽出手法を用いる。【００８９】
次いで、特徴ベクトル抽出部２０３はモード判別部２０４の判別結果に基づいて学習モードであるか否かを判断する（ステップＳ２４）。学習モードである場合（Ｓ２４：ＹＥＳ）、多項式関数の導出を行う（ステップＳ２５）。多項式関数の導出を行う際、認識対象の画像を複数用意することによって認識精度を高めることができる。例えば、数字の「４」の画像を認識対象とした場合、図１０の模式図に示したような画像を学習データとして用意する。実施の形態１の手法を適用することにより、二クラス分類問題の解を与える多項式関数を決定することができる。【００９０】
ステップＳ２４で学習モードでないと判断した場合（Ｓ２４：ＮＯ）、画像判定部２０６にて画像認識を実行する（ステップＳ２６）。ただし、画像認識に先立ってステップＳ２５の多項式関数の決定を行っておく必要がある。画像認識は、新たに入力された画像から抽出した特徴ベクトルを、学習処理部２０５が決定した多項式関数に代入することによって行う。例えば、図１１の模式図に示したテストデータを入力した場合、左から１列目の上から２番目の画像と５番目の画像とを数字の「４」として認識することができた。【００９１】
図１０に示した学習データを入力して多項式関数を求めた場合、従来手法では７０４個の単項式が必要となるのに対して、本発明の方法を適用した場合、３５６個の単項式で解を記述することができた。すなわち、単項式の数を約５０％以下に抑えることが可能となり、メモリ容量をおよそ半分節約することができ、約２倍の計算速度で分類を実行することができることが分かった。【００９２】
なお、本実施の形態では、数字の「４」の画像を認識する装置として説明したが、他の数字、文字、任意のパターンを認識させることができることは勿論のことである。
【図１】
2007088973.tif 000020
【図２】
2007088973.tif 000021
【図３】
2007088973.tif 000022
【図４】
2007088973.tif 000023
【図５】
2007088973.tif 000024
【図６】
2007088973.tif 000025
【図７】
2007088973.tif 000026
【図８】
2007088973.tif 000027
【図９】
2007088973.tif 000028
【図１０】
2007088973.tif 000029
【図１１】
2007088973.tif 000030
【手続補正書】
【提出日】平成19年11月30日(2007.11.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定し、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出し、算出した関数の値に基づいて前記バイナリデータの分類を行うデータ分類方法において、
各要素が１又は−１の値をとり、情報処理装置内に入力されたバイナリデータを分類対象とし、前記バイナリデータを２つのクラスに分類すべく多項式関数を前記情報処理装置内の演算手段としてのＣＰＵにより設定し、設定した多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤｎ、バイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄｎａ＞０を満たす列ベクトルａを前記ＣＰＵを用いて算出することにより、項の数が３×２ｎ−２より少ない多項式関数を求めることを特徴とするデータ分類方法。
【請求項２】
（削除）
【請求項３】
ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定し、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出し、算出した関数の値に基づいて前記バイナリデータの分類を行うデータ分類装置において、
各要素が１又は−１の値をとるバイナリデータを受付ける手段と、前記バイナリデータを２つのクラスに分類すべく多項式関数を演算手段としてのＣＰＵを用いて設定する手段と、設定した多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤｎ、バイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄｎａ＞０を満たす列ベクトルａをＣＰＵを用いて算出する手段とを備え、該手段により項の数が３×２ｎ−２より少ない多項式関数を求めるようにしてあることを特徴とするデータ分類装置。
【請求項４】
（削除）
【請求項５】
コンピュータに、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定させ、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出させ、算出させた関数の値に基づいて前記バイナリデータの分類を行わせるコンピュータプログラムにおいて、
コンピュータに、設定させる多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤｎ、各要素が１又は−１の値をとるバイナリデータが前記コンピュータ内に入力された場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄｎａ＞０を満たす列ベクトルａを前記コンピュータ内の演算手段としてのＣＰＵにより算出させるステップと、コンピュータに、前記バイナリデータを２つのクラスに分類させるべく、前記ステップにより算出された列ベクトルａを用いて項の数が３×２ｎ−２より少ない多項式関数を前記ＣＰＵにより設定させるステップとを有することを特徴とするコンピュータプログラム。
【請求項６】
（削除）
【請求項７】
コンピュータに、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定させ、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出させ、算出させた関数の値に基づいて前記バイナリデータの分類を行わせるコンピュータプログラムが記録されているコンピュータでの読み取りが可能な記録媒体において、
コンピュータに、設定させる多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤｎ、各要素が１又は−１の値をとるバイナリデータが前記コンピュータ内に入力された場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベク卜ルをｙとしたとき、ｄｉａｇ（ｙ）Ｄｎａ＞０を満たす列ベクトルａを前記コンピュータ内の演算手段としてのＣＰＵにより算出させるステップと、コンピュータに、前記バイナリデータを２つのクラスに分類させるべく、前記ステップにより算出された列ベクトルａを用いて項の数が３×２ｎ−２より少ない多項式関数を前記ＣＰＵにより設定させるステップとを有するコンピュータプログラムが記録されていることを特徴とする記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００２
【補正方法】変更
【補正の内容】
【０００２】
［０００６］
しかしながら、ニューラル・ネットワーク等の分野では、設定すべき多項式関数を構成する単項式の数が非常に多くなり、大容量のメモリ、高速な演算手段が必要となるという問題点を有していた。
［０００７］
本発明は斯かる事情に鑑みてなされたものであり、バイナリデータを２つのクラスに分類するために、項の数が３×２ｎ−２個よりも少ない多項式関数を設定する構成とすることにより、２クラス分類問題を解くのに必要な単項式の数に上限を与えることができるデータ分類方法、データ分類装置、コンピュータプログラム、および記録媒体を提供することを目的とする。
課題を解決するための手段
［０００８］
第１発明に係るデータ分類方法は、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定し、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出し、算出した関数の値に基づいて前記バイナリデータの分類を行うデータ分類方法において、各要素が１又は−１の値をとり、情報処理装置内に入力されたバイナリデータを分類対象とし、前記バイナリデータを２つのクラスに分類すべく多項式関数を前記情報処理装置内の演算手段としてのＣＰＵにより設定し、設定した多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤｎ、バイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄｎａ＞０を満たす列ベクトルａを前記ＣＰＵを用いて算出することにより、項の数が３×２ｎ−２より少ない多項式関数を求めることを特徴とする。
［０００９］
［００１０］
第２発明に係るデータ分類装置は、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定し、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出し、算出した関数の値に基づいて前記バイナリデータの分類を行うデータ分類装置において、各要素が１又は−１の値をとるバイナリデータを受付ける手段と、前記バイナリデータを２つのクラスに分類すべく多項式関数を演算手段としてのＣＰＵを用いて設定する手段と、設定した多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤｎ、バイナリデータが与えられた場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄｎａ＞０を満たす列ベクトルａをＣＰＵを用いて算出する手段とを備え、該手段により項の数が３×２ｎ−２より少ない多項式関数を求めるようにしてあることを特徴とする。
［００１１］
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００３
【補正方法】変更
【補正の内容】
【０００３】
［００１２］
第３発明に係るコンピュータプログラムは、コンピュータに、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定させ、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出させ、算出させた関数の値に基づいて前記バイナリデータの分類を行わせるコンピュータプログラムにおいて、コンピュータに、設定させる多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤｎ、各要素が１又は−１の値をとるバイナリデータが前記コンピュータ内に入力された場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄｎａ＞０を満たす列ベクトルａを前記コンピュータ内の演算手段としてのＣＰＵにより算出させるステップと、コンピュータに、前記バイナリデータを２つのクラスに分類させるべく、前記ステップにより算出された列ベクトルａを用いて項の数が３×２ｎ−２より少ない多項式関数を前記ＣＰＵにより設定させるステップとを有することを特徴とする。
［００１３］
［００１４］
第４発明に係る記録媒体は、コンピュータに、ｎ個（ｎは２以上の整数）の要素からなるバイナリデータを入力値とする関数を設定させ、与えられたバイナリデータの各要素を設定した関数に代入することにより前記関数の値を算出させ、算出させた関数の値に基づいて前記バイナリデータの分類を行わせるコンピュータプログラムが記録されているコンピュータでの読み取りが可能な記録媒体において、コンピュータに、設定させる多項式関数の各項の係数を要素とする列ベクトルをａ、前記各項がとり得る値の組み合わせに基づいて定めた行列をＤｎ、各要素が１又は−１の値をとるバイナリデータが前記コンピュータ内に入力された場合に該バイナリデータが分類されるべきクラスの値を要素とする行ベクトルをｙとしたとき、ｄｉａｇ（ｙ）Ｄｎａ＞０を満たす列ベクトルａを前記コンピュータ内の演算手段としてのＣＰＵにより算出させるステップと、コンピュータに、前記バイナリデータを２つのクラスに分類させるべく、前記ステップにより算出された列ベクトルａを用いて項の数が３×２ｎ−２より少ない多項式関数を前記ＣＰＵにより設定させるステップとを有するコンピュータプログラムが記録されていることを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０００４
【補正方法】変更
【補正の内容】
【０００４】
［００１５］
［００１６］
本発明にあっては、バイナリデータを２つのクラスに分類する際に使用する関数を項の数が３×２ｎ−２個よりも少ない多項式関数に設定するため、２クラス分類問題を解くのに必要な単項式の数が抑えられる。
［００１７］
また、本発明にあっては、設定すべき多項式関数の各係数を列ベクトルａ＝［ａ０，ａ１，…，ａｍ］Ｔ（ｍ＝２ｎ−１）で表し、ｄｉａｇ（ｙ）Ｄｎａ＞０の条件下で列ベクトルａを求めることにより、列ベクトルａの要素の少なくとも１／４がゼロとなる。
発明の効果
［００１８］
本発明による場合は、バイナリデータを２つのクラスに分類する際の判定基準として多項式関数を使用し、しかもその多項式関数の項数を３×２ｎ−２よりも少なくしている。一般的に、３×２ｎ−２個の単項式からなる多項式関数を用いることにより、どのような２クラス分類問題も解くことは可能であるが、本発明では、３×２ｎ−２個よりも少ない数の単項式を用いて多項式関数を設定することができる。そのため、大規模な問題を解く場合であっても、使用するメモリの削減、演算速度の向上を図ることができる。
［００１９］
また、本発明にあっては、設定すべき多項式関数の各係数を列ベクトルａ＝［ａ０，ａ１，…，ａｍ］Ｔで表し、ｄｉａｇ（ｙ）Ｄｎａ＞０の条件下で列ベクトルａを求めることにより、列ベクトルａの要素の少なくとも１／４がゼロとなる。したがって、多項式関数の項の数が２ｎ−２個よりも少なく抑えられ、大規模な問題を解く場合であっても、使用するメモリの削減、演算速度の向上を図ることができる。
図面の簡単な説明
［００２０］
［図１］本発明に係るデータ分類装置の内部構成を示すブロック図である。
［図２］多項式関数を求める際に情報処理装置が実行する処理の手順を説明するフローチャートである。
［図３］多項式関数を求める際に情報処理装置が実行する処理の手順を説明するフロ
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
ｚ＝［（α＋α′）Ｆ，ｇ＋ν］
［００６４］
により与える（ステップＳ１７）。ＣＰＵ１０１は、ここで本ルーチンによる演算を終了する。
［００６５］
このアルゴリズムの演算結果であるｚは、前述した不等式ｄｉａｇ（ｙ）Ｄｎｚ＞０を満たしており、２クラス分類問題に対する解を与える。このアルゴリズムの重要かつ新規な性質は、解として求めたベクトルｚを構成する要素のうち２ｎ／４がゼロであるという点にある。すなわち、求めた多項式関数の項（単項式）の数は、｛−１，１｝に分類するどのような２クラス分類問題についても３×２ｎ−２より少ない数となる。その結果、分類対象のデータが与えられた場合、メモリ容量等の演算資源を低く抑えることができ、高速な分類が可能となる。
［００６６］
次に、適用例について説明する。図４はクラス分類問題の例題を示す図表である。図４では、Ｘ０，Ｘ１，Ｘ２の各要素が与えられた場合に属するべきクラスの値を定義している。要素の数は３つであるため、本発明では６つ（＝３×２ｎ−２＝３×２１）より少ない単項式で構成される多項式が求まる。
［００６７］
前述したアルゴリズムを適用する場合、二クラス分類問題は、ｄｉａｇ（ｙ）Ｄ３ｚ＞０を満たすｚを求めること等価である。ここで、ｙ＝［−１，−１，１，１，１，−１，−１，−１］であり、Ｄ３は、図５の図表に示した要素を持つ行列として定義される。
［００６８］
ステップＳ１の処理により、ベクトルを、ｙｕ＝［−１，−１，１，１］とｙｄ＝［１，−１，−１，−１］とに分割すると共に、行列Ｄｎを図６に示した図表の如く分割する。
［００６９］
ステップＳ２の処理により、行列Ｆ，Ｇを初期化し、行列Ｄｎの各行を分配する。すなわち、（ｙ０ｕ，ｙ０ｄ）＝（−１，＋１）であるため、−ｄ０を行列Ｇに加える。同様に、（ｙ１ｕ，ｙ１ｄ）＝（−１，−１）より、−ｄ１を行列Ｆに加え、（ｙ２ｕ，ｙ２ｄ）＝（＋１，−１）より、ｄ２を行列Ｇに加え、（ｙ３ｕ，ｙ３ｄ）＝（＋１，−１）より、ｄ３を行列Ｆに加える。したがって、行列Ｆの行の数ｒ（Ｆ）は１であり、行列Ｇの行の数ｒ（Ｇ）は３になる。
［００７０］
ｒ（Ｇ）≧ｒ（Ｆ）の条件を満たすため、ＣＰＵ１０１はステップＳ４の処理を実行し、行列Ｆを構成する行の和ｆを求める。その結果、ｆ＝（−１，１，−１，１）となる。また、ステッ
【国際調査報告】
2007088973.tif 000031
2007088973.tif 000032
2007088973.tif 000033