パターン認識方法、装置及びプログラム
【課題】大次元の入力変数（特徴量）を有するパターンの識別を高速に実現することのできる方法、装置およびプログラムを提供する。
【解決手段】この方法を適法可能な装置１は、識別対象となる入力変数を入力する入力部２と、この入力変数からパターンの識別に使用する特徴量を選別するコンピュータ３の入力データ処理部３１ｂとを備え、この入力データ処理部３１ｂは、特徴量を予め削減するプリセレクション部３１ｂ１と、前記特徴量をさらに一度に追加するブロック追加・削除部３１ｂ２とを備えている。
【解決手段】この方法を適法可能な装置１は、識別対象となる入力変数を入力する入力部２と、この入力変数からパターンの識別に使用する特徴量を選別するコンピュータ３の入力データ処理部３１ｂとを備え、この入力データ処理部３１ｂは、特徴量を予め削減するプリセレクション部３１ｂ１と、前記特徴量をさらに一度に追加するブロック追加・削除部３１ｂ２とを備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン認識方法、装置及びプログラムに関するものである。
【背景技術】
【０００２】
パターン認識とは、データをあらかじめ与えられたいくつかのクラスのうちの１つに分類する処理である。パターン認識において入力変数を特徴量という。そのパターン認識問題に対して優れた汎化能力（認識能力）を示す識別器の１つにサポートベクトルマシン（以下、ＳＶＭという。）がある（例えば特許文献１や非特許文献１，２を参照）。ＳＶＭは入力を高次元特徴空間に写像することによって線形分離可能にし、この空間上で分離超平面と各クラスの最近傍ベクトルとの距離で定義されるマージンが最大となるように最適分離超平面を決める。
【０００３】
しかし、冗長な特徴量が多く含まれていると計算量の増加や、汎化能力の低下といった問題が起こる。この問題を解決するために、冗長な特徴量を削減する特徴選択を行う。特徴選択には、識別器を使わずに相互情報量などを用いて特徴量の良し悪しを判断するフィルター（ｆｉｌｔｅｒ）法や、識別器を用いて特徴量を評価し、それを基準として特徴量の良し悪しを判断するラッパー（ｗｒａｐｐｅｒ）法がある。フィルター法は識別器を使わないので計算コストは小さくなるが、汎化性に欠ける。ラッパー法は識別器を使うので計算コストは大きくなるが、汎化能力の高い特徴量集合を選ぶことができる。
【０００４】
また特徴選択の手法として順方向選択と逆方向選択とがある（例えば非特許文献２，３を参照）。順方向選択は空集合に特徴量を１つ追加し、認識率が特徴選択の終了条件である閾値を上回るまで特徴量を１つずつ追加する。逆方向選択では初期特徴量集合から特徴量を１つ削除し、閾値を下回るまで特徴量を１つずつ削除する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来手法では、特徴量を１つずつ追加または削除するので時間がかかってしまうといった問題があった。一方、本発明者は、関数近似問題では入力変数を一度に追加または削除するブロック追加・削除や、関数近似用線形計画サポートベクトルマシンを用いて入力データにかかる重みを計算し、重みの値が小さい入力変数を不必要な入力変数としてあらかじめ削除するプリセレクションを行ってからブロック追加・削除を行う手法を提案しているところ、かかる手法をパターン認識に適用することは困難であった。その主な理由は以下に示すとおりである。
【０００６】
（１）関数近似の出力は連続量であって目標値との誤差でよさを判定し、この誤差が小さければよいとするが、パターン認識では与えられたクラスのどれに属するかの出力（離散量）をし、そのよさは通常は認識率で評価して認識率が高ければよいとする。
【０００７】
（２）関数近似では通常出力は１個であるが、パターン認識では複数個のクラスのどれに属するかを判定するために出力は複数であり、しかも与えられた入力に対して出力の最も高いクラスにその入力が属すると判定する。
【０００８】
（３）関数近似での出力は連続量のため、変数を減らしたときに誤差が同じになることを考えなくてもよいが、パターン認識では変数を減らしたときも、認識率が１００％で変わらないときがあり、このときに順序付けを導入することが必要である。
【０００９】
本発明は、かかる事情に鑑みてなされたものであって、その目的とするところは、関数近似問題における上記手法をパターン認識に適用するように工夫することで、大次元の入力変数（特徴量）を有するパターンの識別を高速に実現することのできる方法、装置およびプログラムを提供することである。
【課題を解決するための手段】
【００１０】
本発明（方法）は、入力装置が、識別対象となる入力変数を入力する入力工程と、演算装置が、サポートベクトルマシンを用いて、この入力変数からパターンの識別に使用する特徴量を選別する選別工程とを備えたパターン認識方法であって、前記選別工程は、前記演算装置が、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除工程を備えたことを特徴とするものである。
【００１１】
本発明（方法）によれば、前記選別工程は、前記演算装置が、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除工程を備えたので、特徴量を１つずつ追加または削除するので時間がかかってしまうという不具合を、前記関数近似問題で用いたそれらの手法をパターン認識に適用して解消することができる。これにより、特徴量を迅速に削除して、大次元の特徴量を有するパターンの識別を高速に実現することができるようになる。
【００１２】
請求項２記載の発明のように、前記ブロック追加・削除工程は、前記演算装置が、前記初期の特徴量集合の認識率を閾値としておき、空集合に一時的に特徴量を１つ追加したときの該空集合の認識率を計算して、認識率の高い順に特徴量を順位付けたランキングを生成し、ランキングの上位の特徴量を前記空集合に追加したときの該空集合の認識率が前記閾値よりも大きいときに、特徴量の追加が成功したとして、該特徴量のみを前記特徴量集合に残し、その他の特徴量を該特徴量集合から削除するものであることが好ましい。
【００１３】
請求項２記載の発明によれば、前記ブロック追加・削除工程は、前記演算装置が、前記初期の特徴量集合の認識率を閾値としておき、空集合に一時的に特徴量を１つ追加したときの該空集合の認識率を計算して、認識率の高い順に特徴量を順位付けたランキングを生成し、ランキングの上位の特徴量を前記空集合に追加したときの該空集合の認識率が前記閾値よりも大きいときに、特徴量の追加が成功したとして、該特徴量のみを前記特徴量集合に残し、その他の特徴量を該特徴量集合から削除するものであるので、特徴量を迅速に削除することができる。
【００１４】
請求項３記載の発明のように、前記閾値は固定値であることが好ましい。
【００１５】
請求項３記載の発明によれば、前記閾値は固定値であるので、簡単な構成となる。
【００１６】
請求項４記載の発明のように、前記閾値は前記認識率に基づいて更新可能であることが好ましい。
【００１７】
請求項４記載の発明によれば、前記閾値は前記認識率に基づいて更新可能であるので、特徴量を追加・削除していくときに認識率の計算の精度が閾値を上回れば、そのつど閾値を更新して、より有用な特徴量を選択することができる。
【００１８】
ところで、通常のサポートベクトルマシンでは、２次計画問題を解くことによって学習を行うが、この学習に時間がかかるという問題がある。これに対して、最小自乗サポートベクトルマシンでは、線形連立方程式を解くことによって学習を行うので、通常のサポートベクトルマシンに比べて学習時間を短縮することができる。そこで、請求項５記載の発明のように、前記サポートベクトルマシンとして、最小自乗サポートベクトルマシンを備えており、前記演算装置は、この最小自乗サポートベクトルマシンで前記認識率を計算するものであることが好ましい。
【００１９】
請求項５記載の発明によれば、前記サポートベクトルマシンとして、最小自乗サポートベクトルマシンを備えており、前記演算装置は、この最小自乗サポートベクトルマシンで前記認識率を計算するものであるので、学習時間を短縮して、特徴量をより迅速に削除することができる。
【００２０】
また、データの次元数が大きいときには、１つずつ特徴量を追加・削除していては時間がかかるので、事前に多くの特徴量を削除するプリセレクションの必要性がある。さらに、線形計画サポートベクトルマシンでは、重みがゼロになれば、対応する入力データの次元は識別と無関係になるので、そのような次元を不必要な次元として削除することができる。そこで、請求項６記載の発明のように、前記サポートベクトルマシンとして、線形計画サポートベクトルマシンをも備えており、前記選別工程は、前記演算装置が、前記ブロック追加・削除工程を実行する前に、前記初期の特徴量集合を用いて、前記線形計画サポートベクトルマシンを学習させることにより、該特徴量集合に対応する重みを計算し、この重みの大きさに基づいて特徴量を前記初期の特徴量集合から予め削除しておくプリセレクション工程を備えることが好ましい。
【００２１】
請求項６記載の発明によれば、前記サポートベクトルマシンとして、線形計画サポートベクトルマシンをも備えており、前記選別工程は、前記演算装置が、前記ブロック追加・削除工程を実行する前に、前記初期の特徴量集合を用いて、前記線形計画サポートベクトルマシンを学習させることにより、該特徴量集合に対応する重みを計算し、この重みの大きさに基づいて特徴量を前記初期の特徴量集合から予め削除しておくプリセレクション工程を備えたので、データ数が少なくて、高次元のデータに対して、より多くの特徴量を削減できる。
【００２２】
一方、サポートベクトルマシンを学習するために変数をワーキング集合と固定集合とに分けて、ワーキング集合を繰り返して解く分割法があり、そこでのサポートベクトルマシンの学習は制約条件を満たすようにして行うことで最終解を得るのが通常であるが、この最終解を得るためには途中段階では必ずしも制約条件を満たす必要性がない。そこで、請求項７記載の発明のように、前記演算装置が、前記ブロック追加・削除工程で、入力変数をワーキング集合と固定集合とに分けて、ワーキング集合を繰り返して解く分割法の最適化問題において途中段階では制約条件を満たさないことを許すように前記サポートベクトルマシンを学習させることが好ましい。なお、本手法は、前記最小自乗サポートベクトルマシンに置き換わるものである。
【００２３】
請求項７記載の発明によれば、前記演算装置が、前記ブロック追加・削除工程で、入力変数をワーキング集合と固定集合とに分けて、ワーキング集合を繰り返して解く分割法の最適化問題において途中段階では制約条件を満たさないことを許すように前記サポートベクトルマシンを学習させるので、分割法を用いて、より迅速に最終解を得ることができる。
【００２４】
また、前記学習において最適化問題を解く主問題を用いることがあるが、このときには特徴空間を直接扱うこととなり、写像関数が線形以外ではその最適化問題を解くのが難しくなる。そこで、請求項８記載の発明のように、前記演算装置が、前記ブロック追加・削除工程で、前記最適化問題にラグランジェ乗数を適用した双対問題を用いて前記サポートベクトルマシンを学習させることが好ましい。
【００２５】
請求項８記載の発明によれば、前記演算装置が、前記ブロック追加・削除工程で、前記最適化問題にラグランジェ乗数を適用した双対問題を用いて前記サポートベクトルマシンを学習させるので、特徴空間を直接扱うことがなくなる。したがって、写像関数が線形以外であっても、その最適化問題を容易に解くことができて、より安定した収束と、より早い学習とが可能となる。
【００２６】
請求項９記載の発明のように、前記演算装置が、前記ブロック追加・削除工程で、前記双対問題を用いて前記サポートベクトルマシンを学習させる際に、初期変数集合から出発して解を求め、この解の中で正となる変数を残し、正しく分離されている変数、前記および零または負になる変数を削除し、さらに正しく分離されていない変数、あるいはマージンが不足している変数を追加して解を求めることを、同じ解が求まるまで繰り返すことが好ましい。
【００２７】
請求項９記載の発明によれば、前記演算装置が、前記ブロック追加・削除工程で、前記双対問題を用いて前記サポートベクトルマシンを学習させる際に、初期変数集合から出発して解を求め、この解の中で正となる変数を残し、正しく分離されている変数、前記および零または負になる変数を削除し、さらに正しく分離されていない変数、あるいはマージンが不足している変数を追加して解を求めることを、同じ解が求まるまで繰り返すので、より安定した収束と、より早い学習とが可能となる。
【００２８】
ただし、途中段階で制約を満たさないで双対問題を解いた場合には、制約を満たした条件で解く場合のように確実に収束しないことがある。そこで、請求項１０記載の発明のように、前記演算装置は、前記ブロック追加・削除工程で、前記繰り返し数が設定回数を超える、あるいは違反数が増加あるいは振動すると、制約を満たすように変数の修正量を制限して、前記サポートベクトルマシンを学習させることが好ましい。
【００２９】
請求項１０記載の発明によれば、前記演算装置が、前記ブロック追加・削除工程で、前記繰り返し数が設定回数を超える、あるいは違反数が増加あるいは振動すると、制約を満たすように変数の修正量を制限して、前記サポートベクトルマシンを学習させるものであるので、例えば１０回の繰り返し数を超えると、制約を満たすように変数の修正量を制限することで、確実に収束させることができる。
【００３０】
請求項１１記載の発明は、識別対象となる入力変数を入力するための入力手段と、サポートベクトルマシンを用いて、この入力変数からパターンの識別に使用する特徴量を選別する選別手段とを備えたパターン認識装置であって、前記選別手段は、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除手段を備えたことを特徴とするものである。
【００３１】
請求項１１記載の発明（装置）によれば、前記選別手段は、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除手段を備えたので、本発明（方法）と同様の作用効果を奏する。
【００３２】
請求項１２記載の発明は、入力装置により入力された入力変数からパターンの識別に使用する特徴量を選別するに際し、サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、前記特徴量集合から特徴量を一度に削除するブロック追加・削除機能をコンピュータに実現させることを特徴とするパターン認識プログラムに係るものである。
【００３３】
請求項１２記載の発明（プログラム）によれば、入力装置により入力された入力変数からパターンの識別に使用する特徴量を選別するに際し、サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、前記特徴量集合から特徴量を一度に削除するブロック追加・削除機能をコンピュータに実現させるので、本発明（方法）と同様の作用効果を奏する。
【発明の効果】
【００３４】
本発明（方法）によれば、前記選別工程は、前記演算装置が、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除工程を備えたので、特徴量を１つずつ追加または削除するので時間がかかってしまうという不具合を、前記関数近似問題で用いたそれらの手法をパターン認識に適用して解消することができる。これにより、特徴量を迅速に削除して、大次元の特徴量を有するパターンの識別を高速に実現することができるようになる。
【００３５】
請求項１１記載の発明（装置）によれば、前記選別手段は、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除手段を備えたので、本発明（方法）と同様の作用効果を奏する。
【００３６】
請求項１２記載の発明（プログラム）によれば、入力装置により入力された入力変数からパターンの識別に使用する特徴量を選別するに際し、サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、前記特徴量集合から特徴量を一度に削除するブロック追加・削除機能をコンピュータに実現させるので、本発明（方法）と同様の作用効果を奏する。
【図面の簡単な説明】
【００３７】
【図１】本発明の実施形態１に係るパターン認識方法を適用可能な装置の全体構成を示すブロック図である。
【図２】本実施形態１に係るパターン認識方法を適用可能な装置の概略動作を示すフローチャートである。
【図３】本実施形態１に係るパターン認識方法のアルゴリズム（１）を示すフローチャートである。
【図４】本実施形態１に係るパターン認識方法のアルゴリズム（２）を示すフローチャートである。
【図５】本実施形態２に係るパターン認識方法の学習アルゴリズム（１）を示すフローチャートである。
【図６】本実施形態２に係るパターン認識方法の学習アルゴリズム（２）を示すフローチャートである。
【発明を実施するための形態】
【００３８】
（実施形態１）
図１は本発明の実施形態１に係るパターン認識方法を適用可能な装置（以下、「本装置」という。）１の全体構成を示すブロック図である。図１に示すように、本装置１は、コンピュータ（演算装置に相当する。）３を備えている。
【００３９】
例えばコンピュータ３は、各種演算等を実行するＣＰＵ（Ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）３１と、各種基本プログラム等を予め記憶しておくＲＯＭ（Ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ）３２と、各種応用プログラム、各種データ等を一時的に記憶するＲＡＭ（Ｒａｎｄｏｍ−ａｃｃｅｓｓ ｍｅｍｏｒｙ）３３とを備えたパーソナルコンピュータであり、これにキーボードやマウスやＣＤ／ＤＶＤドライブなどの入力部（入力装置、入力手段に相当する。）２と、ＣＲＴや液晶やプリンタなどの表示部４とがそれぞれ電気的に接続されている。
【００４０】
そして、前記ＲＡＭ３３に記憶しておいたパターン認識プログラムを含む各種プログラム等を前記ＣＰＵ３１に読み込んで実行することで、学習部３１ａと、入力データ処理部（選別手段に相当する。）３１ｂと、パターン認識部３１ｃがそれぞれ構築されるようになっている。
【００４１】
学習部３１ａは、学習データを用いてＳＶＭを学習させるものである。入力データ処理部３１ｂは、識別対象である入力変数からパターンの識別に使用する特徴量を選別するものであって、前記入力変数を前記学習したＳＶＭに代入したときの値が閾値を越えたときに、当該入力変数を特徴量として選別するものである。そして、入力データ処理部３１ｂは、プリセレクション部３１ｂ１と、前記特徴量を一度に削除するブロック追加・削除部（ブロック追加・削除手段に相当する。）３１ｂ２を備えている。この入力データ処理部３１ｂのブロック追加・削除部３１ｂ２がパターン認識プログラムのブロック追加・削除機能を、コンピュータ３に実現させるものである。パターン認識部３１は、前記選別された特徴量に基づいてパターンの識別を行うものである。
【００４２】
本装置１の動作について説明する。図２は本装置１の概略動作を示すフローチャートである。なお、コンピュータ３には、入力部２から必要な学習データなどをあらかじめ入力しているもとする。
【００４３】
図２において、まず学習部３１ａは学習データを用いてＳＶＭを学習させる（ステップＳ１００）。次いで入力部２から識別対象となる入力変数を入力すると、入力データ処理部３１ｂはこの入力変数からパターンの識別に使用する特徴量を選別するが、その際にプリセレクション部３１ｂ１で特徴量を予め削除した上で、さらにブロック追加・削除部３１ｂ１で前記特徴量を一度に削除する（ステップＳ２００：入力工程、選別工程、プリセレクション工程、ブロック追加・削除工程）。そして、パターン認識部３１ｃは、この選別された特徴量に基づいてパターンの認識を行い、その識別結果を表示部４で表示させる（ステップＳ３００）。各ステップの具体的なアルゴリズムについては後述する。
【００４４】
以下、本発明の理解の便宜上、基本的なＳＶＭについて簡単に説明したうえで、パターン認識において認識率を求めるときに使う最小自乗サポートベクトルマシン（以下、ＬＳ−ＳＶＭという。）、多クラス問題、クロスバリデーション、特徴選択、順方向選択、逆方向選択についてそれぞれ説明する。
【００４５】
（ＳＶＭ）
Ｍ個のｍ次元教師データｘｉ（ｉ＝１，・・・，Ｍ）がクラス１またはクラス２に属しており、クラス１ならｙｉ＝１、クラス２ならｙｉ＝―１とする。この教師データｘｉを、写像関数ｇ（ｘ）を用いて、ｍ次元入力空間からｌ次元空間（ｌ＞ｍ）に写像することによって線形分離性能を高める。このとき決定関数は次式のようになる。
【００４６】
【数１】
ただし、ｗはｌ次元重みベクトル、ｂはバイアス項である。Ｄ（ｘ）＞０ならクラス１、Ｄ（ｘ）＜０ならクラス２に分類される。Ｄ（ｘ）＝０となる場合は分離不可能であるが、線形分離可能の条件ならＤ（ｘ）＝０となるデータは存在しない。よって次式を考える。
【００４７】
【数２】
この式（数２）は次式に変換できる。
【００４８】
【数３】
このとき次式
【数４】
がデータｘｉ（ｉ＝１，・・・，Ｍ）を分離する分離超平面である。ｃ＝０のとき分離超平面はｃ＝１と、ｃ＝−１の２つの超平面の中央となる。
【００４９】
分離超平面から最も近いデータまでの距離をマージンと呼び、超平面Ｄ（ｘ）＝１と、Ｄ（ｘ）＝−１がそれぞれ少なくとも１つの教師データを含むと仮定すると、超平面Ｄ（ｘ）＝０は、−１＜ｃ＜１について最大マージンを持つ。特徴空間上のある点ｇ（ｘ）とＤ（ｘ）＝０との距離は｜Ｄ（ｘ）｜／‖ｗ‖で与えられるので、マージンδは、
【数５】
と定義される。
【００５０】
しかし、線形分離不可能な場合に許容解が常に存在するように、ｘｉに対して非負のスラック変数ξｉを用いて前記式（数３）を次のように変換する。
【００５１】
【数６】
前記式（数１）を得るためにＳＶＭは以下の最適化問題を解く。
【００５２】
【数７】
ただし、Ｃはマージンパラメータといい、マージンの最大化と誤認識の最小化とのトレードオフを決めるものである。ｐ＝１のときをＬ１−ＳＶＭ、ｐ＝２のときをＬ２−ＳＶＭと呼ぶ。
【００５３】
（ＬＳ−ＳＶＭ）
ＳＶＭでは、２次元計画問題を解くことによって学習を行うが学習に時間がかかる。そこで、線形連立方程式を解くことによって学習を行うＬＳ−ＳＶＭについて述べる。
【００５４】
ＬＳ−ＳＶＭの最適化問題は以下のようにＳＶＭの制約条件の不等式を等式にしたものとなる。
【００５５】
【数８】
これらの２つの式（数８）の最適化問題を直接解くと特徴空間の変数を扱わなければならないので、非負のラグランジェ乗数αｉを導入し、次のような無制約の目的関数とする。
【００５６】
【数９】
この式（数９）の最適解は勾配が０となるときに得られる。したがって、同式（数９）をｗ，ｂ，α，ξで偏微分し、それぞれが０となるとすると、以下のような最適条件が得られる。
【００５７】
【数１０】
これら４つの式（数１０）をまとめると以下のように表せる。
【００５８】
【数１１】
ここで、ｌはＭ次元のベクトルであって、
【数１２】
であり、ｇＴ（ｘ）ｇ（ｘ’）はカーネル関数を用いてＨ（ｘ，ｘ’）と表される。またここで用いるカーネル関数はＲＢＦカーネルであり、以下のように定義される。
【００５９】
【数１３】
ここでγは傾きを制御する正の整数である。αとｂは以下のようになる。
【００６０】
【数１４】
このようにして、ＬＳ−ＳＶＭでは最適化問題をｌ次の連立方程式を解くことによって解が得られることが分かる。
【００６１】
（多クラス問題）
実際のパターン認識問題では、多クラスになることが多いため、２クラス問題から多クラス問題への拡張が必須となる。そこで、２クラス問題から多クラス問題に拡張するための手法の１つであるペアワイズを用いたペアワイズＳＶＭについて説明する。
【００６２】
このペアワイズＳＶＭでは、クラスのペアの全ての組み合わせについて決定関数を求める。１つのクラスのペアについての決定関数を決める際に、対応する２クラスの教師データを用いる。よって、ｎクラス問題に対し決定関数の数はｎ（ｎ−１）／２個となる。クラスｉのｊに対する決定関数を以下のように定義する。
【００６３】
【数１５】
ただし、ｗｉｊはｌ次元ベクトル、ｇ（ｘ）は写像関数、ｂｉｊはバイアス項を表しており、またＤｉｊ（ｘ）＝−Ｄｊｉ（ｘ）となる。クラスｉの領域は次式で表され、
【数１６】
オーバーラップしない。そして、ｘがＲｉに含まれれば、ｘをクラスｉに分類し、ｘがＲｉに含まれなければｘを投票で分類する。すなわち、入力データｘに対して次式を求める。
【００６４】
【数１７】
ここで、
【数１８】
このとき、ｘは次式で分類される。
【００６５】
【数１９】
もしＤｉ（ｘ）＝ｎ−１かつＤｋ（ｘ）＜ｎ−１（ｉ≠ｋ）であれば、ｘはクラスｉに分類される。しかしどのＤｉ（ｘ）のｎ−１でないとき、この式は複数のｉについて成立する。このときｘは未分類領域である。未分類領域はファジィメンバーシップ関数を導入することにより解消できる（例えば非特許文献２）。またここではペアワイズＳＶＭについて説明したが、1対多ＳＶＭ、同時定式化ＳＶＭ等（例えば非特許文献２）を適用することも可能である。
【００６６】
（クロスバリデーション）
ＳＶＭを学習させるためには、マージンパラメータＣやＲＢＦカーネルのパラメータγなどの値を設定しなければならない。最適なパラメータの組み合わせを決定するためにｋ分割クロスバリデーションを用いる。このｋ分割クロスバリデーションでは教師データをほぼ均一なｋ個の部分集合に分割し、ｋ−１個の部分集合で学習し、残りの１つでテストする。学習ｋ回繰り返し、テストに使用したｋ個の部分集合に対する全体の認識率を計算する。そして一番認識率の高かったパラメータの組み合わせを決定する。ＳＶＭでは教師データでの学習に基づいてテストデータにおける汎化能力をみるので、ｋ分割クロスバリデーションを行うときも教師データを分割して教師データとテストデータに分けたほうが、信頼性の高いパラメータを選ぶことができる。
【００６７】
（特徴選択）
特徴量の削減はパターン認識において重要な課題である。なぜなら冗長な特徴量が多いと次のような問題が起こる。１つめは特徴量の増加に対して指数関数的に増加する計算量の増加である。２つめは本来有用でない特徴量も学習に使用してしまうことによる汎化能力の低下である。３つめは冗長な特徴量も有用な特徴量として学習に使用されてしまうことによる汎化能力の低下である。
【００６８】
このような問題を解決するために特徴選択が行われる。特徴選択はある評価基準に基づいて不要な特徴量を選び出して削除することである。特徴選択の代表的な手法としてフィルター法とラッパー法があることは既に説明したとおりである。ここでは、フィルター法に比べて計算コストは大きくなるものの、汎化性が大きくなるラッパー法を用いることとする。ただし、フィルター法に対しても同様に発明の特徴選択法を適用することが可能である。引き続き、パターン認識で用いられている特徴選択の手法である順方向選択と逆方向選択とについて説明する。
【００６９】
（順方向選択）
ここでは認識率を基準とした順方向選択について説明する。まず特徴量の数をｍとし、初期特徴量集合をＩｍとし、Ｉｍにおける認識率をＲｍとしてこれを特徴選択の終了条件の閾値とする。空集合Ｉ０にｉ番目（ｉ＝１，・・・，ｍ）の特徴量を一時的に追加する。そのときの認識率をＲｉａｄｄとする。ただし、ｉａｄｄはｉ番目の特徴量を追加することを表す。Ｒ１ａｄｄからＲｍａｄｄの中で一番値が大きかったものをＲｋａｄｄ（ｋ＝１，・・・，ｍ）として、
【数２０】
を満たせば特徴選択を終了する。この式（数２０）を満たさなければ精度が上がるまで同様の手順を繰り返す。
【００７０】
（逆方向選択）
ここでは認識率を基準とした逆方向選択について説明する。まず特徴量の数をｍとし、初期特徴量集合をＩｍとし、Ｉｍにおける認識率をＲｍとしてこれを特徴選択の終了条件の閾値とする。Ｉｍから一時的にｉ番目（ｉ＝１，・・・，ｍ）の特徴量を削減し、そのときの認識率をＲｍｍｄｅｌとする。ただし、ｉｄｅｌはｉ番目の特徴量を削減することを表す。Ｒｍ１ｄｅｌからＲｍｍｄｅｌの中で一番値が大きかったのをＲｍｋｄｅｌと（ｋ＝１，・・・，ｍ）として、
【数２１】
を満たせば、ｋ番目を削除する。閾値を上回る限り同様の手順を繰り返す。
【００７１】
以下、本発明の特徴をなす、閾値設定方式、２クラスのブロック追加・削除による特徴選択、２クラスの線形計画サポートベクトルマシン（以下、ＬＰ−ＳＶＭという。）を用いたブロック追加・削除による特徴選択および多クラスへの拡張について説明する。ブロック追加・削除による特徴選択は、順方向選択や逆方向選択のように特徴量を１つずつ追加・削徐していては時間がかかるので、ブロック追加・削除で特徴量を一度に追加・削除する手法である。この方法は順方向選択や逆方向選択等の認識率で高速に特徴量を選択することが目的である。また、ＬＰ−ＳＶＭを用いたブロック追加・削除による特徴選択は、データの次元数が非常に多いと、順方向選択や逆方向選択のように特徴量を１つずつ追加・削除して評価していては時間がかかるので、事前に不要な特徴量をまとめて削除してからブロック追加・削除を行う手法である。ただし、評価基準となる認識率は前記ＬＳ−ＳＶＭで求めてもよいし、後で述べる学習を高速化したＬ２−ＳＶＭで求めてもよい。
【００７２】
（閾値設定方式）
ここでは特徴選択の終了条件を特徴選択後の認識率が設定した閾値よりも悪くなることとしている。閾値の設定方式として閾値固定方式と閾値更新方式を用いる。閾値固定方式は閾値を最初に設定した値のまま最後まで固定して特徴選択を行う方式である。閾値更新方式は特徴量を追加・削除したときに精度が閾値を上回れば、その都度閾値を更新しながら特徴選択を行っていく方式である。その都度閾値を更新する閾値更新方式の方がより有用な特徴量を選択できる。
【００７３】
（２クラスのブロック追加・削除による特徴選択）
順方向選択や逆方向選択では、特徴量を１ずつ追加・削除していくが、これでは不要な特徴量が多いとき時間がかかる。そこで特徴量を一度に追加・削除するブロック追加・削除を用いる。本手法は、高速で特徴選択を行いなおかつ初期特徴量集合と同等の精度を得るのが目的である。
【００７４】
そして、閾値固定方式では、まず初期特徴量集合をＩｍとして、Ｉｍにおけるバリデーションセットの認識率Ｒｍを閾値Ｔとする。ただしｍは初期特徴量集合の次元数である。空集合Ｉ０に一時的にｉ番目の特徴量を１つ追加し、そのときの認識率Ｒ０ｉａｄｄを計算し、追加候補集合を作成し、認識率の高い順に特徴量を順位づけたランキング（ｖａｒｉａｂｌｅ ｒａｎｋｉｎｇ）を生成する。なお、認識率が同じでランキングができないときは、前記式（数５）のマージンの大きい順にランキングを行う。このランキングの上位２ｋ個（ｋ＝０，・・・，Ａ）を空集合に追加する。ここで、Ａは追加候補数を制限するユーザパラメータである。追加したときの認識率Ｒ２ｋと閾値Ｔを比較し、
【数２２】
となれば、そのときの特徴量を追加する。
【００７５】
ｋ＝Ａまで（数２２）式を満たさないとき、Ｒ２０，Ｒ２１，・・・，Ｒ２Ａの中で認識率の最も高いときの特徴量集合を空集合に追加する。次に新たな追加候補を選択するために、一時的追加を行う。そのときの特徴量集合にｉ番目の特徴量を追加し、そのときの認識率を基にして新たなランキングを構成し、先ほどと同様にして特徴量の追加判定を行う。先ほどと同様に、認識率が同じでランキングができないときは、前記式（数５）のマージンの大きい順にランキングを行う。追加が成功すれば、そのときの特徴量集合からブロック削除を行い、余分な特徴量を削除する。もし、追加したときに前回の認識率を下回れば追加失敗として、初期特徴量集合からのブロック削除に切り替える。追加失敗が続くと特徴量選択の効率が落ちるので、１回の失敗で追加を終了する。
【００７６】
一方、閾値更新方式では、追加時に精度が向上する場合に閾値をそのときの認識率に更新することで、精度の高い特徴量集合を求める。
【００７７】
図３は本実施形態１に係るパターン認識方法のアルゴリズム（１）を示すフローチャートであって、前記図２におけるステップＳ２００を具体化するものである。なお、この図３における閾値固定方式と閾値更新方式との違いはステップＳ３ａ，Ｓ３ｂと、ステップＳ７ａ，Ｓ７ｂとだけであるので、以下では、その部分のみ場合分けをして説明する。
【００７８】
ステップＳ１：初期特徴量集合をＩｍとし、Ｉｍにおけるバリデーションセットの認識率をＲｍとし、これを閾値Ｔとする。ただしｍは初期特徴量集合の次元数である。
【００７９】
ステップＳ２：空集合Ｉ０にｉ番目（ｉ＝１，・・・，ｍ）の特徴量を追加し、追加したときの認識率をＲ０ｉａｄｄとする。これは空集合にｉ番目の特徴量を追加した集合における認識率である。
【００８０】
ステップＳ３：Ｒ０ｉａｄｄ（ｉ＝Ｉ，・・・，ｍ）を大きい順に特徴量を順位づけたランキングを生成する。その上位２ｋ個（ｋ＝０，・・・，Ａ）の特徴量を空集合に追加していく。
【００８１】
ステップＳ３ａ（閾値固定方式の場合）：追加したときの認識率が閾値Ｔを上回れば追加成功としてその特徴量集合のままステップＳ４へ進み、ｋ＝Ａまで成功しない場合はｋ＝Ａまで追加していったなかで一番高かった認識率Ｒｍａｘ（ｋ＝０，・・・，Ａ）を求め、追加前の特徴量集合における認識率を上回れば、その２ｋ個を追加してステップＳ２に戻る。上回らなければ初期特徴量集合に戻してステップＳ４へ進む。
【００８２】
ステップＳ３ｂ（閾値更新方式の場合）：上記閾値固定方式と同じようにＲｍａｘを求め、追加前の特徴量集合における認識率を上回れば、２ｋ個を追加してステップＳ２に戻る。上回らない場合、追加前の特徴量集合における認識率が閾値Ｔを上回れば閾値を追加前の特徴量集合における認識率に更新してステップＳ４に進む。満たさなければ初期特徴量集合に戻してステップＳ４へ進む。
【００８３】
ステップＳ４：この時点での特徴量集合をＩｊとし、Ｉｊにおける認識率をＲｊとし、閾値更新方式ではこれを新たに閾値Ｔとする。ただしｊはこの時点での次元数である。
【００８４】
ステップＳ５：Ｉｊからｉ番目（ｉ＝０、…、ｊ）の特徴量を削除し、そのときの認識率をＲｊｉｄｅlとする。
【００８５】
ステップＳ６，Ｓ６ａ：Ｒｊｉｄｅｌ（ｉ＝０，・・・，ｊ）のなかで閾値を上回ったものの中でランキングを生成し、なければ特徴選択を終了する。
【００８６】
ステップＳ７：Ｉｊからランキングにある特徴量をすべて削除し認識率を求める。
【００８７】
ステップＳ７ａ（閾値固定方式の場合）：閾値を上回れば削除後の特徴量集合でステップＳ５へ進み、閾値を上回らなければステップＳ８へ進む。
【００８８】
ステップＳ７ｂ（閾値更新方式の場合）：閾値を上回れば閾値を更新して削除後の特徴量集合でステップＳ５へ進み、閾値を上回らなければステップＳ８へ進む。
【００８９】
ステップＳ８：Ｉｊからランキングの上位半分を削除し、閾値を上回ればその削除後の特徴量集合でステップＳ５へ進み、満たされなければ、満たすまで削除候補を上位半分にしていく。なお、ランキングが生成されたため、このステップでは１個は必ず削除される。
【００９０】
（２クラスのＬＰ−ＳＶＭを用いたブロック追加・削除による特徴選択）
データの次元数が大きいとき、１つずつ特徴量を追加、削除していては時間がかかるので、事前に多くの特徴量を削除するプリセレクションの必要性がある。本手法ではＬＰ―ＳＶＭによる特徴選択をプリセレクションとして用いる。ＬＰ−ＳＶＭはＬＩ−ＳＶＭの目的関数の‖ｗ‖２２＝ｗ２１＋ｗ２２＋…＋ｗ２ｍを‖ｗ‖１＝｜ω１｜＋｜ω２｜＋…＋｜ωｍ｜に置き換えることによって線形計画問題として定式化できる。いわゆる単体法で解くためには、変数が非負である必要があるためωｉ＝ωｉ＋−ωｉー、ｂ＝ｂ＋−ｂ−として次式の線形計画問題とする。
【００９１】
【数２３】
ＬＰ−ＳＶＭでは、Ｍをデータ数、ｍを次元数とすると目的関数の変数がＮ＝２ｍ＋Ｍ＋２となり、制約条件の数はＭ本となるので、少なくともＮ−Ｍ個の変数は０になる。重みベクトルが０になれば対応する入力データの次元は識別とは無関係になる。このような次元を不必要な次元として削除する。次元数が多いとＮ−Ｍの値が大きくなる。よって、データ数が少なくて高次元のデータに対して、多くの特徴量を削除できる。
【００９２】
そして、閾値固定方式では、初めに初期特徴量集合Ｉｍを用いてバリデーションセットの認識率Ｒｍを閾値Ｔとする。ここでｍは初期特徴量集合の次元数である。次にＬＰ−ＳＶＭの学習によって各特徴量に対応する重みの値｜ωｉ｜を求め、最大値のμ％以下の値を持つ特徴量をすべて特徴量集合から削除する。ここでμはユーザパラメータである。
【００９３】
プリセレクション後の特徴量の数をｊＬＰとしたとき、このときの認識率ＲｊＬＰと閾値Ｔと比較して、
【数２４】
となれば、さらに削除できる特徴量を探すためにブロック削除を行う。精度が低下したら、削除時の特徴量集合に有用な特徴量を追加する。追加候補となるのは追加したときにＬＰ−ＳＶＭでの学習後の特徴量集合の認識率ＲｊＬＰより精度を向上させるものである。これらの特徴量でランキングを構成し、ブロック追加・削除を行う。
【００９４】
一方、閾値更新方式では、プリセレクション後の認識率が閾値よりも小さくなっていれば、それを新たな閾値とする。また、ブロック追加を行う際も追加前より精度が向上していれば、そのときの認識率を閾値にする。
【００９５】
図４は本実施形態１に係るパターン認識方法のアルゴリズム（２）を示すフローチャートであって、これも前記図２におけるステップＳ２００を具体化するものである。なお、図４における閾値固定方式と閾値更新方式との違いはステップＳ１３ａ，Ｓ１３ｂ、ステップＳ１５ａ，Ｓ１５ｂ、ステップＳ１９ａ，Ｓ１９ｂだけであるので、以下では、それらの部分だけ場合分けをして説明する。
【００９６】
ステップＳ１１：初期特徴量集合をＩｍとし、Ｉｍにおけるバリデーションセットの認識率をＲｍとし、これを閾値Ｔとする。ただしｍは初期特徴量集合の次元数である。
【００９７】
ステップＳ１２：初期特徴量集合Ｉｍを用いて、ＬＰ−ＳＶＭで学習し、重みωｉ（ｉ＝１，・・・，ｍ）を求める。求めた重みの絶対値の最大値｜ωｉ｜ｍａｘを求めて、｜ωｉ｜≦μ｜ωｉ｜ｍａｘとなる特徴量をＩｍから削除する（ステップＳ１２）。ただしμはユーザパラメータである。
【００９８】
ステップＳ１３：削除後に認識率を求め、閾値Ｔと比較する。
【００９９】
ステップＳ１３ａ（閾値固定方式の場合）：閾値を上回れば削除成功となり削除後の特徴量集合でステップＳ１６へ進む。
【０１００】
ステップＳ１３ｂ（閾値更新方式の場合）：閾値を上回れば閾値を更新して削除後の特徴量集合でステップＳ１６へ進む。上回らなければ削除後の特徴量集合でステップＳ１４へ進む。
【０１０１】
ステップＳ１４：削除後の特徴量集合に削除された特徴の中からｉ番目（ｉ＝１，・・・，ｎ）の特徴量を追加し、追加したときの認識率をＲｉａｄｄとする。
【０１０２】
ステップＳ１５：Ｒｉａｄｄ（ｉ＝１，・・・，ｎ）を大きい順に特徴量を順位づけたランキングを生成する上位２ｋ個（ｋ＝０，・・・，Ａ）の特徴量を追加していく。
【０１０３】
ステップＳ１５ａ（閾値固定方式の場合）：追加したときの認識率が閾値Ｔを上回れば追加成功としてその特徴量集合のままステップＳ１４へ進む。ｋ＝Ａまで成功しない場合はｋ＝Ａまで追加したなかで一番高かった認識率Ｒｍａｘ（ｋ＝０，・・・，Ａ）を求め、追加前の特徴量集合における認識率を上回れば、その２ｋ個を追加してその集合でステップＳ１２に戻る。上回らなければ初期特徴量集合に戻してステップＳ１６へ進む。
【０１０４】
ステップＳ１５ｂ（閾値更新方式の場合）：前記閾値固定方式と同じように認識率Ｒｍａｘを求め、追加前の特徴量集合における認識率を上回れば、その２ｋ個を追加してその集合でステップＳ１４へ進む。上回らない場合、追加前の特徴量集合における認識率が閾値Ｔを上回れば閾値を追加前の特徴量集合における認識率に更新してステップＳ１６へ進み、満たさなければ初期特徴量集合に戻してステップＳ１６へ進む。
【０１０５】
ステップＳ１６：この時点での特徴量集合をＩｊとし、Ｉｊにおける認識率をＲｊとし、これを閾値Ｔとする。ただしｊはこの時点での特徴量集合の次元数である。
【０１０６】
ステップＳ１７：Ｉｊからｉ番目（ｉ＝０，・・・，ｊ）の特徴量を削除し、そのときの認識率をＲｊｉｄｅｌとする。
【０１０７】
ステップＳ１８，Ｓ１８ａ：Ｒｊｉｄｅｌ（ｉ＝０，・・・，ｊ）のなかで閾値を上回ったものの中でランキングを生成する。もし閾値を上回るものがなければ処理を終了する。
【０１０８】
ステップＳ１９：Ｉｊからランキングにある特徴量をすべて削除し認識率を求める。
【０１０９】
ステップＳ１９ａ（閾値固定方式の場合）：閾値を上回れば削除後の特徴量集合でステップＳ１７へ進み、閾値を上回らなければステップＳ２０へ進む。
【０１１０】
ステップＳ１９ｂ（閾値更新方式の場合）：閾値を上回れば閾値を更新して削除後の特徴量集合でステップＳ１７へ進み、閾値を上回らなければステップＳ２０へ進む。
【０１１１】
ステップ２０：Ｉｊからランキングの上位半分を削除し、閾値を上回ればその削除後の特徴量集合でステップＳ１７へ進む。満たされなければ、満たすまで削除候補を上位半分にしていく。
【０１１２】
（多クラスへの拡張）
多クラスの場合も２クラスの場合と同様の流れでブロック追加・削除による特徴選択を行う。例えばブロック削除の削除候補を選ぶ際、まず一時的に特徴量集合から特徴量を１つ削除し、ペアワイズ方式を用いて認識率を計算し、削除した際に閾値を上回った特徴量すべて削除する。異なる点は認識率を求めるのにペアワイズ方式を用いることだけである。ただし、認識率によるランキングで順序付けられないときにマージンを用いるときは、各ペアのクラスに対応するマージンの平均値、最大値、あるいは最小値をとるようにする。
【０１１３】
以下、本装置１を用いたシミュレーション結果について説明する。なお、ここでは２クラスと多クラスのベンチマークデータとＵＣＩベンチマークデータ、２クラスの高次元データのマイクロアレイデータを用いて実験を行い、特徴選択前と特徴選択後で認識率を比較した結果を示すものとする。
【０１１４】
（実験方法）
２クラスおよび多クラスのベンチマークデータとＵＣＩベンチマークデータはブロック追加・削除で実験を行い、マイクロアレイデータは高次元データであるのでＬＰ−ＳＶＭでプリセレクションを行ってからブロック追加・削除を行う。ＬＳ−ＳＶＭのマージンパラメータとＲＢＦカーネルのパラメータ、ＬＰ−ＳＶＭのマージンパラメータ、プリセレクションに使用するμは５分割クロスバリデーションで１ファイルごとに決定している。
【０１１５】
ＬＳ−ＳＶＭのマージンパラメータＣ、ＲＢＦカーネルのパラメータγは、Ｃ＝｛１,１０,５０，１００，５００,１０００,５０００,１００００，５００００，１０００００｝、γ＝｛０．０００１，０．００１，０．０１，０．１，０．５，１．０，５．０，１０，１５｝から最適なパラメータの組み合わせを選択する。またＬＰ−ＳＶＭのマージンパラメータＣとμはＣ＝｛１０，１００００｝μ＝｛０,０．０５，０．１，０．１５，０．２｝から最適なパラメータの組み合わせを選択する。
【０１１６】
特徴選択途中の認識率を求める際はマージンパラメータのみをクロスバリデーションで決定し、Ｃ＝｛１,１０,５０，１００，５００,１０００,５０００,１００００，５００００，１０００００｝から最適なパラメータを選択する。（表１）にはＩＤＡの２クラスベンチマークデータ、（表２）には多クラスベンチマークデータ、（表３）にはマイクロアレイデータ、（表４）にはＵＣＩベンチマークデータについて記す。
【０１１７】
各表の“Ｉｎｐｕｔｓ”はデータの次元数、“Ｔｒａｉｎ”は教師データ数、“Ｔｅｓｔ”はテストデータ数、“Ｃｌａｓｓ”はクラス数を表す。ただしマイクロアレイデータ、ＵＣＩベンチマークデータはすべて２クラスである。またＵＣＩベンチマークデータは教師データのみである。実験結果は２クラスベンチークデータのＩｍａｇｅとＳｐｌｉｃｅ以外は１００ファイル、Ｉｍａｇｅ、Ｓｐｌｉｃｅとマイクロアレイデータは２０ファイルの平均である。なおシミュレーションにおけるコンピュータ３としては、Ｉｎｔｅｌ Ｃｏｒｅ（ＴＭ）２Ｄｕｏ ３．１８ＧＨｚ １．９９ＧＢ ＲＡＭを使用した。
【０１１８】
【表１】
【表２】
【表３】
【表４】
（２クラスベンチマークデータでの実験結果）
２クラスベンチマークデータを用いた、閾値固定方式と閾値更新方式での実験結果を（表５）に示す。実験結果の表の“Ｄａｔａ”は用いたデータセット、“Ｂｅｆｏｒｅ”と“Ａｆｔｅｒ”は特徴選択の前と後の結果を表す。“Ｖａｌ”はバリデーションセットのテストデータの認識率、“Ｔｅｓｔ”はテストデータの認識率、“Ｄｅｌｅｔｅｄ”は削除次元数、“Ｔｉｍｅ”は特徴選択にかかった時間である。２行になっているのは、上段が閾値固定方式での実験結果、下段が閾値更新方式での実験結果を表しているからである。特徴線選択前の結果はどちらも変わらないので１段になっている。特徴選択後にテストデータの認識率がよくなった場合は＊で表している。
【０１１９】
（表５）より、バリデーションセットのテストデータの認識率は全データで特徴選択後の方がよくなっている。これはバリデーションセットのテストデータの認識率が向上するように特徴量を選んでいるからである。Ｆ．Ｓｏｌａｒ，Ｉｍａｇｅ，Ｓｐｌｉｃｅ，Ｔｉｔａｎｉｃに関してはテストデータでも認識率の向上がみられ、他のデータでも認識率が大幅に低下したデータはなくほぼ同等の認識率が得られたので、特徴選択の効果が出ているといえる。ＢａｎａｎａはＤｅｌｅｔｅｄが０なのでどの特徴量を削除しても認識率が向上しなかったことを示している。時間の標準偏差が大きいデータがいくつかみられるが、ブロック削除を行う際、削除候補となる特徴量の数の違いによってブロック削除を繰り返す回数に違いが生じることが原因と考えられる。
【０１２０】
また閾値固定方式と閾値更新方式を比べたところほとんどのデータで閾値更新方式の方が認識率がよくなっており、時間も早くなっているので、閾値を更新する方が有用な特徴量を高速に選ぶことができるといえる。しかし、次元数が最も多いＳｐｌｉｃｅだけは閾値更新方式の方が時間がかかる結果となった。これはブロック削除を行う際に閾値を更新した方が削除候補となる特徴量の数が少なく、ブロック追加を繰り返す回数が多くなるということが考えられる。
【０１２１】
【表５】
（マイクロアレイデータでの実験結果）
マイクロアレイデータを用いた、閾値固定方式と閾値更新方式での実験結果を（表６）に示す。同表より、バリデーションセットのテストデータの認識率は全データで特徴選択後の方がよくなっており、テストデータの認識率もＢ．ｃａｎｃｅｒ１とＢ．ｃａｎｃｅｒ２以外のデータでは特徴選択前と後とではほぼ同等の認識率を得ている。特にＧｏｌｕｂは認識率が向上した。特徴選択後の特徴量の数は全データで２から３個程度である。よって、数個の特徴量でも特徴選択前と同等のも認識率を得ることができるといえる。
【０１２２】
しかし、Ｂ．ｃａｎｃｅｒ１とＢ．ｃａｎｃｅｒ２では大幅に認識率が低下している。これは両方のデータがともにテストデータ数が８なので１つの認識を誤ると１２．５％も認識率が低下することが原因と考えられる。Ｖａｎｔｖｅｅｒ以外で特徴選択後のテストデータの認識率の標準偏差が大きくなった。これはテストデータ数が少なく、１つの誤認識で認識率が大幅に低下してしまい、２０ファイル中数ファイルでそのようなことが起こったことが原因と考えられる。Ｓｐｏｒａｄｉｃ以外で時間の標準偏差が非常に大きくなっている。これはプリセレクションを行った際、いくつかのファイルで精度が低下してブロック追加を行ったため余分に時間がかかってしまったことと、２クラスベンチマークデータ同様ブロック削除を繰り返す回数の違いが原因と考えられる。
【０１２３】
また閾値固定方式と閾値更新方式を比べたところ、Ｓｐｏｒａｄｉｃ、Ｖａｎｔｖｅｅｒ以外のデータは閾値更新方式の方が認識率が良くなっており、より有用な特徴量を選んでくる閾値更新方式の特徴が表れているが、Ｓｐｏｒａｄｉｃ、Ｖａｎｔｖｅｅｒは閾値固定方式の方が認識率が良くなった。時間に関してはＡｌｏｎ、Ｓｐｏｒａｄｉｃ、Ｖａｎｔｖｅｅｒは閾値固定方式の方が早いがＢ．ｃａｎｃｅｒ１、Ｂ．ｃａｎｃｅｒ２、Ｇｏｌｕｂ、Ｉｉｚｕｋａは閾値更新方式の方が速かった。閾値を更新した方が選んでくる特徴量は多少少ないが、ブロック削除で削除候補となる特徴量も少なくなり、次元数が多いとブロック削除を繰り返す回数が多くなるので、どちらがよいとはいえない。
【０１２４】
【表６】
（多クラスベンチマークデータでの実験結果）
多クラスベンチマークデータを用いた、閾値固定方式と閾値更新方式での実験結果を（表７）に示す。同表より、バリデーションセットのテストデータの認識率は２クラスベンチマークデータとマイクロアレイデータ同様全データ特徴選択後の方がよくなっており、テストデータの認識率も全データ特徴選択前と後とでほぼ同等の認識率が得られている。ＩｒｉｓとＢｌｏｏｄ ｃｅｌｌは削除された特徴量が０なのでどの特徴量を削除しても認識率が向上しなかったことを表す。Ｔｈｙｒｏｉｄは特徴選択前と同等の認識率を得るのに３つの特徴量しか必要とせず、しかもテストデータの認識率が向上する結果となった。
【０１２５】
閾値固定方式と閾値更新方式を比べたところ、全データ認識率が変わらないという結果となった。これは、多クラスベンチマークデータは特徴選択をする前から非常に高い認識率が出ているので、特徴量を削除しても認識率がそれほど向上しないことが原因と考えられる。また、時間に関しては全データとも閾値更新方式の方が速かった。よって多クラスベンチマークデータに関しては閾値更新方式の方が有用な特徴量を高速に選択できるといえる。
【０１２６】
【表７】
（ＵＣＩベンチマークデータでの実験結果）
ＵＣＩベンチマークデータを用いたときの閾値固定方式と閾値更新方式での実験結果を（表８）に示す。ＵＣＩベンチマークデータは教師データのみ用いるのであって、“Ｔｒａ”は教師データの認識率である。同表より、Ｐｒｉｍａｉｎｄｉａｎｓは特徴選択後大幅に識別力が低下してしまっている。Ｂｕｐａｌｉｖｅｒは削除数が０なので、特徴量を削減しても認識率が向上しなくなったことを示す。
【０１２７】
閾値固定方式と閾値作成新方式を比べたところ、認識率はＰｉｍａｉｎｄｉａｎｓでは閾値更新方式の方が高かったが、他の２つでは変わらなかった。時間においてはＢｕｐａｌｉｖｅｒは変わらなかったが、他の２つでは閾値更新方式の方が速かった。よって、ＵＣＩベンチマークデータでは閾値更新方式の方が有用な特徴量を高速に選択できるといえる。
【０１２８】
【表８】
以上説明したように、本実施形態１では、パターン認識におけるブロック追加・削除による特徴選択と、ＬＰ−ＳＶＭを用いたブロック追加・削除による特徴選択を説明した。ブロック追加・削除は特徴量を１つずつ追加・削除する順方向選択や逆方向選択と違い、追加・削除したときに精度が上がる特徴量を一度に追加・削除するので高速な特徴選択が可能である。また、ブロック追加・削除を行う前にＬＰ−ＳＶＭを用いて、各データにかかる重みを計算し、重みが０に近い特徴量をあらかじめ削除することによって、次元数の多いデータに対して高速に特徴選択を行うことができる。
【０１２９】
２クラスベンチマークデータと多クラスベンチャーマークデータはブロック追加・削除による特徴選択、マイクロアレイデータはＬＰ−ＳＶＭを用いたブロック追加・削除による特徴選択を用いた。特徴選択の終了条件である閾値はバリデーションセットのテストデータの認識率を用い、閾屋を固定しないまま特徴選択を行う閾値固定方式と精度が上がるたびに閾値を更新する閾値更新方式で実験を行った。
【０１３０】
２クラスベンチマークデータと多クラスベンチマークを用いたシミュレーション実験より、本手法が初期特徴量集合と同等の精度を保ちながら有用な特徴量を選択できていることが示された。また閾値固定方式より閾値更新方式の方がより有用な特徴量を高速に選択できることが示された。マイクロアレイデータを用いたシミュレーション実験では、殆どのデータでベンチマークデータ同様有用な特徴量を選択できていたが、テストデータ数が少ないこともあり、一部のデータで認識率が非常に低下した。また閾値固定方式と閾値更新方式を比較したところ、時間にしてはどちらが優れているかは判断できなかったが、閾値更新方式の方が、有用な特徴量を確保できた。
【０１３１】
（実施形態２）
この実施形態２では、前記装置１における学習部３１ａおよびブロック追加・削除部３１ｂ２におけるＬＰ−ＳＶＭのかわりに用いることができるＬ２−ＳＶＭの学習について説明するが、これも本発明の特徴をなすものである。ＳＶＭの学習において、次の最適化問題を解く。
【０１３２】
【数２５】
ただしｗは重みベクトル、φ（ｘ）は多次元入力ベクトルｘを特徴空間に写像する関数、ｂはバイアス項、（ｘｉ，ｙｉ）（ｉ＝１，・・・，Ｍ）はＭ個の教師データ対でｘｉがクラス１に属するときにｙｉ＝１で、ｘｉがクラス２に属するときにｙｉ＝−１である。Ｃはマージンの最大化と教師データに対する誤認識のトレードオフを決定するマージンパラメータ、ξｉはｘｉに対する非負のスラック変数でＬ１−ＳＶＭのときｐ＝１で、Ｌ２−ＳＶＭのときｐ＝２とする。ｙｉ（ｗＴφ（ｘｉ）＋ｂ）をｘに対するマージンという。
【０１３３】
これら２つの式（数２５）のままでは、特徴空間を直接扱うことになり、写像関数が線形以外は解くのは難しい。このためにラグランジェ乗数αｉを導入することでＬ１−ＳＶＭに対して次の双対問題を得た。
【０１３４】
【数２６】
そして、Ｌ２−ＳＶＭに対しては、
【数２７】
なる双対問題を得た。ただしＫ（ｘ，ｘ’）は、カーネル方程式であり、Ｋ（ｘ，ｘ’）＝φＴ（ｘ）φ（ｘ‘）、ｉ＝ｊでδｉｊ＝１、ｉ≠ｊで０である。
【０１３５】
ここでは、多項式カーネルであるＫ（ｘ，ｘ’）＝（ｘＴ，ｘ’＋１）ｄと、ＲＢＦカーネルであるＫ（ｘ，ｘ’）＝ｅｘｐ（−γ‖ｘ−ｘ’‖２）を使用する。ただし、ｄは正の整数であり、γは傾きを制御するための正のパラメータである。Ｌ１−ＳＶＭに対するＫＫＴ条件が次式で与えられる。
【０１３６】
【数２８】
【０１３７】
前記２つの式（数２６）の解に対して、もしαｉ＞０であれば、ｘｉはサポートベクトルという。特にαｉ＝Ｃであれば、ｘｉは上限に達したサポートベクトル、０＜αｉ＜Ｃであれば、ｘｉは上限に達していないサポートベクトルという。Ｌ２−ＳＶＭに対するＫＫＴ条件が次式で与えられる。
【０１３８】
【数２９】
ここで、αｉ＝Ｃξｉである。
【０１３９】
（主問題におけるＳＶＭの学習）
前記２つの式（数２５）で与えられた最適化問題は、次の拘束なしの最適化問題に変換される。
【０１４０】
【数３０】
ただし、ｗは次式で表すものと仮定する。
【０１４１】
【数３１】
ここで、βｉ（ｉ＝１，・・・，ｍ）は定数である。この式（数３１）を前記式（数３０）に代入して、次式が得られる。
【０１４２】
【数３２】
Ｌ１−ＳＶＭに対する最適解を与えるデータに関連するインデックスの１セットを定義する。
【０１４３】
【数３３】
ただしＤ（ｘ）は決定方程式であり、Ｄ（ｘ）＝ｗＴφ（ｘ）＋ｂで与えられる。Ｌ２−ＳＶＭに対しては、
【数３４】
を定義する。ただしαｉ＝Ｃξｉであるから、等号は含まない。
【０１４４】
学習データをＳに関連するデータに限定するような解が得られるか否かを考える。前記式（数３２）は次式とされる。
【０１４５】
【数３５】
Ｌ１−ＳＶＭ（ｐ＝１）に対して、ＫＫＴ条件の２つの式（数２８）から、上限に達していないサポートベクトルｘ（ｉ∈Ｓ）に関連するスラック変数ξは０である。しかし、この式（数３５）において、スラック変数の合計は最小化される。このようにして、各拘束は必ずしも０になるわけでない。加えて、ｂに対する二次項がないから、ｂはこの公式によって決定されない。それゆえ、前記式（数３５）を解くことで、解を得ることはできない。この問題を解くために、チャペルはフーバーのロス関数を使用しており、そこでは線形ロスが二次ロスと組み合わさっている（非特許文献４参照）。しかし、この方式はＬ１−ＳＶＭに対する概略解を与えるから、主問題においてＬ１−ＳＶＭを解くものと考えていないことは明らかである。
【０１４６】
Ｌ２−ＳＶＭに対して、前記式（数３４）から、サポートベクトルｘｉ（ｉ∈Ｓ）に対応したξｉは正の値である。このとき前記式（数３２）は、ｉ∈Ｓという制約でもって、（数３５）と等しい。β’Ｓ＝（βTＳ，ｂ）Tとすると、ここで、βＳ＝｛βｉ｜ｉ∈Ｓ｝である。
【０１４７】
すると、式（数３５）は、
【数３６】
となる。ここで、ＫＳは（｜Ｓ｜＋１）×（｜Ｓ｜＋１）のマトリックスである。ｃＳは（｜Ｓ｜＋１）次元ベクトルである。
【０１４８】
すると、
【数３７】
となる。∂Ｑ／∂β’Ｓ＝０を解くと、最適解は次のようになる。
【０１４９】
【数３８】
ここで、ＫＳは正定である。もしＫＳが特異であれば、通常は小さな値が対角の各要素に追加される。しかし、これがサポートベクトルの数を増加するから、ワーキングセットからマトリックスの特異性を引き起こすデータを削除する。
【０１５０】
以下、主問題と双対問題とにおける学習ＳＶＭの比較を行う。
【０１５１】
（主問題における学習）
この主問題ＳＶＭの学習方式では、前記チャペルの方式と異なり、少ないチャンキングデータ（分割したデータ）でもって学習を開始する。そして、小さな値をＫＳの対角の各要素に追加する代わりに、コレスキー分解法によりＫＳを分解したときの関連した列と行を削除することで、ＫＳの特異性を回避する。ここでは、可変サイズのチャンキングアルゴリズムを使用する。すなわち、初期のワーキングセットに対して前記式（数３８）を解き、ワーキングセットから、ゼロスラック変数（関連するマージンが１以上である）を含むデータを削除する。ワーキングセットに、正のスラック変数（関連するマージンが１未満である）を含むデータを追加する。そして同式（数３８）を解く。そして、同じワーキングセットが得られるまで上記過程を繰り返す。チャンクサイズをｈとする。ここで、ｈは正の整数である。図５は本実施形態２に係るパターン認識方法の学習アルゴリズム（１）を示すフローチャートであって、前記図２におけるステップＳ１００を具体化するものである。
【０１５２】
ステップＳ２１：ｈ学習データをワーキングセットにセットして、次のステップＳ２２に進む。
【０１５３】
ステップＳ２２：ここでは、コレスキー分解法によりワーキングセットに対して前記式（数３８）を解く。もし対角要素が予め定められた値よりも小さければ、関連する列と行とを削除する。次のデータサンプルを用いて列と行とを書き直し、コレスキー分解することにより、β’Ｓを得る。
【０１５４】
ステップＳ２３：ワーキングセットからゼロスラック変数（すなわち、ｙｉＤ（ｘｉ）≧１を満たすｘｉである。）を含むデータを削除する。
【０１５５】
ステップＳ２４：ワーキングセットに最も違反したものから最大でｈ個のデータを追加する。すなわち最小のｙｉＤ（ｘｉ）から順に、ｙｉＤ（ｘｉ）＜１を満たすｘｉを追加する。
【０１５６】
ステップＳ２５：もし得られたワーキングセットが先に記載したものと同じであるとすると、学習を止める。その他はステップＳ２２に進む。
【０１５７】
（双対問題における学習）
主問題ＳＶＭと同様に、双対問題ＳＶＭを学習させる。この考えは、１つの変数に対してそれを解くことで、前記式（数２７）の後段に示す同等の拘束を削除し、それを同式（数２７）の前段に代入するものである。それから、問題は、正の拘束を含む最大化された問題に限定される。正の拘束を含むことを考えないサブ問題を解き、ワーキングセットから負の変数を削除する。他の過程は主問題ＳＶＭのそれと同じである。インデックスセットＳに対して前記２つの式（数２７）を解くことを考える。αＳ（ｓ∈Ｓ）に対する同式（数２７）の後段における等価制約を解くことで、次式を得る。
【０１５８】
【数３９】
この式（数３９）を前記式（数２７）の後段に代入して、次の最適化問題を得る。
【０１５９】
【数４０】
ここに、αＳ＝｛αｉ｜ｉ∈Ｓ｝、α’Ｓ＝｛αｉ｜ｉ≠ｓ，ｉ∈Ｓ｝、ｃＳは（｜Ｓ｜−１）次元ベクトルである。ＫＳは（｜Ｓ｜−１）×（｜Ｓ｜−１）の正の有限マトリックスである。
【０１６０】
すると、
【数４１】
図６は本実施形態２に係るパターン認識方法の学習アルゴリズム（２）を示すフローチャートであって、これも前記図２におけるステップＳ１００を具体化するものである。なお、図５と同様のステップは、同一番号を付すものとする。
【０１６１】
ステップＳ２１：ｈ学習データをワーキングセットにセットして、ステップＳ２２ａへ進む。
【０１６２】
ステップＳ２２ａ：ここではαＣに対してＫＳα’Ｓ＝ｃＳを解き、前記式（数３９）を用いてαＳを得る。次式よりｂを決定する。
【０１６３】
【数４２】
【０１６４】
ステップＳ２３：ワーキングセットから、ｙｉＤ（ｘｉ）＞１を満たすｘｉと同様の負の変数を含むデータを削除する。そして、ワーキングセットに最も違反したものから最大でｈ個のデータを追加する。すなわち最小のｙｉＤ（ｘｉ）から順に、ｙｉＤ（ｘｉ）＜１を満たすｘｉを追加する。
【０１６５】
ステップＳ２４：もし得られたワーキングセットが、先に記載したものと同じであると学習を止める。その他はステップＳ２２ａに進む。
【０１６６】
ステップＳ２２ａにおいて負のαＳがあるにもかかわらず、前記式（数２９）における最初の方程式は満たされている。線形方程式を解くことで、αＳが得られるからである。このようにして、いかなるｉ（∈Ｓ）が同じ値を与える。ＫＳα’Ｓ＝ｃＳを解き、後述する負の変数を削除するときに、正の制約を無視するので、上記アルゴリズムの収束性は保障されていない。
【０１６７】
双対問題ＳＶＭと主問題ＳＶＭとの差異は、次に要約するとおりである。
（１）双対問題ＳＶＭに対するマトリックスＫＳは、正定である。一方、主問題ＳＶＭに対するそれは、準正定である。式（数３７）と、式（数４１）を比較して、双対問題ＳＶＭに対するＫＳとｃＳは、主問題ＳＶＭよりも要するカーネル方程式が少なくて済む。よって、双対問題ＳＶＭはより安定、より少ない計算時間を与える。
【０１６８】
（２）主問題ＳＶＭに対して特徴空間に写像されたサポートベクトルは、標本特徴空間を張る一次独立なデータとして解釈される。このような線形カーネルに対しては、線形の主問題ＳＶＭに対するサポートベクトルの数は、多くても入力変数の数である。そして、どのデータも標本特徴空間を張る限り、サポートベクトルとなりうる。
【０１６９】
（３）プラットが開発したＳＭＯのような分解の技術に基づく従来の学習方法とは異なり、主問題・双対問題ＳＶＭとに対する学習は、単調な収束を保障しない。或いは収束しない。これは、先に記載したように、目標関数は単調であることを保障しないからである。これを避けるためには、各繰り返し計算においてＫＫＴ条件を違反するデータの数を監視して、違反数が増加する、あるいは振動する場合、変数の修正幅を制約条件を満たす範囲に制約すればよい。これにより、単調性が保証される。
【０１７０】
次いで、性能評価を行う。ここでは（表９）（そのリストは、多くの入力、クラス、学習データ、テストデータを使用している。）に示したようなベンチマーク データセットを用いて、主問題ＳＶＭのそれを含む提案した双対問題ＳＶＭの性能評価をした。同表は、五重のクロスデバリデーションによって決定されるＬ２−ＳＶＭに対するパラメータ値をも示している。例えばｄ４とγ１０は、カーネルが次元４を含む多項式カーネルと、γ＝１０を含むＲＢＦカーネルとを意味する。そして、Ｃ１０５は、マージンパラメータの値が１０５であることを意味する。すべてのＳＶＭに対して多クラスの未分類領域の解消にファジィメンバーシップ関数を使用した。そして、パーソナルコンピュータ（３ＧＨｚ，２ＧＢメモリ，ウインドウズＸＰ オペレーティングシステム）を使用して学習時間を測定した。従来例におけるように、カーネルマトリックスと等価なサイズのキャッシュメモリを用意した。
【０１７１】
【表９】
（表１０）はＵＳＰＳデータセットに対する主問題・双対問題ＳＶＭの性能に基づくチャンクサイズの効果を示す。同表において、“Ｃｈｕｎｋ”，“ＳＶｓ”，“Ｉｔｅｒａｔｉｏｎｓ”，“Ｋｅｒｎｅｌｓ”，“Ｒｅｃ．”，“Ｔｉｍｅ”は、それぞれ、チャンクサイズ、決定関数当たりのサポートベクトルの平均数、繰り返し数、カーネルのアクセス数、テスト（学習）データセットの認識率、そして学習時間を示す。ここでカーネルのアクセス数はカーネル値が必要になった回数で、カーネル値がキャッシュメモリにあるときは、キャッシュメモリの内容が読み出され、カーネル値がキャッシュメモリにないときはカーネル値を計算することを意味する。
【０１７２】
“ＳＶｓ”，“Ｉｔｅｒａｔｉｏｎｓ”，“Ｋｅｒｎｅｌｓ”，“Ｒｅｃ．”，“Ｔｉｍｅ”欄に対しては、よりよい値が双対問題と主問題との間の太字で示している。同表より、双対問題ＳＶＭに対するサポートベクトルの数は５ケースについて同じであるが、主問題ＳＶＭに対しては、チャンクサイズが増加するにつれて徐々に増加している。主問題ＳＶＭに対する繰り返し数がより小さいにもかかわらず、カーネルアクセス数はより小さく、学習時間は双対問題ＳＶＭよりも短い。これは、主問題ＳＶＭに対する繰り返し当たりの計算負荷が先に記述したように大きいことを意味する。主問題ＳＶＭに対して、たとえ対角要素に小さい値を追加したとしても結果は変化していない。
【０１７３】
【表１０】
マトリックスが特異になるケースの性能試験を行った。（表１１）は線形カーネルでＣ＝１００の場合の血球細胞のデータセットに対する結果を示す。主問題ＳＶＭに対して、主問題としての０．００００１を対角要素に追加したときの結果をも含めた。“ＳＶｓ”欄における（ ）内の数字は、ワーキングセットの学習後のサイズを示す。このようにして、例えば、５０のチャンクサイズに対して、４９７のデータ間で１５のデータのみがサポートベクトルであり、残りのデータはマトリックスの特異性ゆえに削除された。
【０１７４】
同表より、双対問題ＳＶＭの学習は、すべてのチャンクサイズに対して最も早かった。追加したものを含む主問題ＳＶＭに対する結果を比較すると、追加した主問題ＳＶＭに対する学習はより早いが、解は異なりサポートベクトルの数は、チャンクサイズの数が増加するにつれて増加した。この結果は、小さな正の値の対角要素への追加はマトリックスの特異性を回避する策としてはよくないことを明らかに示す。
【０１７５】
（表１２）はベンチマーク データセットを用いたときの主問題・双対問題ＳＶＭに対する結果をリストにしている。５０のチャンクサイズをすべてのケースにセットした。甲状腺のデータセットに対して、双対問題ＳＶＭの学習はとても遅かった。そして、主問題ＳＶＭに対して、ワーキングセットのサイズはかなり変動した。そして、学習は１０，０００回以内の繰り返し数では収束しながった。ひらがな−１３とひらがな−１５のデータセットを除き、双対問題ＳＶＭはより早く、ひらがな−５０のデータセットを除き、双対問題ＳＶＭに対するサポートベクトルの数はより小さいものであった。
【０１７６】
【表１１】
実験より、安定した収束と早い学習という点から、双対問題ＳＶＭが主問題ＳＶＭよりもよいことが明らかになった。
【０１７７】
以上説明したように、本実施形態２では、双対問題の形式によるＳＶＭ（双対問題ＳＶＭ）に対する学習方法を説明した。すなわち、初期のワーキングセットから始まって、ニュートン法による双対問題の形式で表されたサブ問題を解いた。もし関連したラグランジェ乗数が非正であるとすると、ゼロスラック変数を含むデータの場合と同様に、データを削除し、正のスラック変数を含むデータを加え、同じワーキングセットが得られるまで、サブ問題を解くことを繰り返した。
【０１７８】
マトリックスの正定性の点から、主問題ＳＶＭよりも双対問題ＳＶＭが有利であることを明らかにした。コンピュータでの実験により、双対問題ＳＶＭの学習が主問題ＳＶＭのそれよりも早くなり、通常はサポートベクトルの数はより小さいものとなったことを示している。また、主問題ＳＶＭの対角要素に小さな値を追加することは、サポートベクトルの数がより大きくなり、チャンクサイズの変化に対して異なる解を与えることをも示している。
【０１７９】
ところで、双対問題ＳＶＭを用いた場合に収束しにくいことがある。その場合には、繰り返し計算の回数が設定値を超えた段階、あるいはＫＫＴ違反数増加あるいは振動する段階で制約を満たす範囲に変数の修正量を制限することにより、確実に収束させることができる。
【０１８０】
【表１２】
【０１８１】
なお、上記実施形態１，２では、カーネルとして、ＲＢＦカーネルや多項式カーネルを用いているが、その他のカーネル（例えば線形カーネルなど。）を用いてもよい。
【符号の説明】
【０１８２】
１ パターン認識装置
２ 入力部（入力装置、入力手段に相当する。）
３ パーソナルコンピュータ（演算装置に相当する。）
３１ ＣＰＵ
３１ａ 学習部
３１ｂ 入力データ処理部（選別手段に相当する。）
３１ｂ１ プリセレクション部
３１ｂ２ ブロック追加・削除部（ブロック追加・削除手段に相当する。）
３１ｃ パターン認識部
３２ ＲＯＭ
３３ ＲＡＭ
４ 表示部
【先行技術文献】
【特許文献】
【０１８３】
【特許文献１】特開２００５−３３９１８６号公報
【非特許文献】
【０１８４】
【非特許文献１】Ｖ．Ｖａｐｎｉｋ，Ｓｔａｔｉｓｔｉｃａｌ Ｌｅａｒｎｉｎｇ Ｔｈｅｏｒｙ，Ｊｏｈｎ．Ｗｉｌｅｙ＆Ｓｏｎｓ，１９９６
【非特許文献２】Ｓ．Ａｂｅ，Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅｓ ｆｏｒ Ｐａｔｔｅｒｎ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ，Ｓｐｒｉｎｇｅｒ，Ｌｏｎｄｏｎ，２００５
【非特許文献３】Ａ．Ｗ．Ｗｈｉｔｎｅｙ，“Ａ Ｄｉｒｅｃｔ Ｍｅｔｈｏｄ ｏｆ Ｎｏｎｐａｒａｍｅｔｒｉｃ Ｍｅａｓｕｒｅｍｅｎｔ Ｓｅｌｅｃｔｉｏｎ，”ＩＥＥＥ Ｔｒａｎｓ．Ｃｏｍｐｕｔｅｒｓ，ｖｏｌ．２０，ｎｏ．９，ｐｐ．１１００−１１０３，１９７１
【非特許文献４】Ｏ．Ｃｈａｐｅｌｌｅ，Ｔｒａｉｎｉｎｇ ａ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｉｎ ｐｒｉｍａｌ，Ｌａｒｇｅ−Ｓｃａｌｅ Ｋｅｒｎｅｌ Ｍａｃｈｉｎｅｓ，ｐｐ．２９−５０．ＭＩＴ Ｐｒｅｓｓ，２００７
【技術分野】
【０００１】
本発明は、パターン認識方法、装置及びプログラムに関するものである。
【背景技術】
【０００２】
パターン認識とは、データをあらかじめ与えられたいくつかのクラスのうちの１つに分類する処理である。パターン認識において入力変数を特徴量という。そのパターン認識問題に対して優れた汎化能力（認識能力）を示す識別器の１つにサポートベクトルマシン（以下、ＳＶＭという。）がある（例えば特許文献１や非特許文献１，２を参照）。ＳＶＭは入力を高次元特徴空間に写像することによって線形分離可能にし、この空間上で分離超平面と各クラスの最近傍ベクトルとの距離で定義されるマージンが最大となるように最適分離超平面を決める。
【０００３】
しかし、冗長な特徴量が多く含まれていると計算量の増加や、汎化能力の低下といった問題が起こる。この問題を解決するために、冗長な特徴量を削減する特徴選択を行う。特徴選択には、識別器を使わずに相互情報量などを用いて特徴量の良し悪しを判断するフィルター（ｆｉｌｔｅｒ）法や、識別器を用いて特徴量を評価し、それを基準として特徴量の良し悪しを判断するラッパー（ｗｒａｐｐｅｒ）法がある。フィルター法は識別器を使わないので計算コストは小さくなるが、汎化性に欠ける。ラッパー法は識別器を使うので計算コストは大きくなるが、汎化能力の高い特徴量集合を選ぶことができる。
【０００４】
また特徴選択の手法として順方向選択と逆方向選択とがある（例えば非特許文献２，３を参照）。順方向選択は空集合に特徴量を１つ追加し、認識率が特徴選択の終了条件である閾値を上回るまで特徴量を１つずつ追加する。逆方向選択では初期特徴量集合から特徴量を１つ削除し、閾値を下回るまで特徴量を１つずつ削除する。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来手法では、特徴量を１つずつ追加または削除するので時間がかかってしまうといった問題があった。一方、本発明者は、関数近似問題では入力変数を一度に追加または削除するブロック追加・削除や、関数近似用線形計画サポートベクトルマシンを用いて入力データにかかる重みを計算し、重みの値が小さい入力変数を不必要な入力変数としてあらかじめ削除するプリセレクションを行ってからブロック追加・削除を行う手法を提案しているところ、かかる手法をパターン認識に適用することは困難であった。その主な理由は以下に示すとおりである。
【０００６】
（１）関数近似の出力は連続量であって目標値との誤差でよさを判定し、この誤差が小さければよいとするが、パターン認識では与えられたクラスのどれに属するかの出力（離散量）をし、そのよさは通常は認識率で評価して認識率が高ければよいとする。
【０００７】
（２）関数近似では通常出力は１個であるが、パターン認識では複数個のクラスのどれに属するかを判定するために出力は複数であり、しかも与えられた入力に対して出力の最も高いクラスにその入力が属すると判定する。
【０００８】
（３）関数近似での出力は連続量のため、変数を減らしたときに誤差が同じになることを考えなくてもよいが、パターン認識では変数を減らしたときも、認識率が１００％で変わらないときがあり、このときに順序付けを導入することが必要である。
【０００９】
本発明は、かかる事情に鑑みてなされたものであって、その目的とするところは、関数近似問題における上記手法をパターン認識に適用するように工夫することで、大次元の入力変数（特徴量）を有するパターンの識別を高速に実現することのできる方法、装置およびプログラムを提供することである。
【課題を解決するための手段】
【００１０】
本発明（方法）は、入力装置が、識別対象となる入力変数を入力する入力工程と、演算装置が、サポートベクトルマシンを用いて、この入力変数からパターンの識別に使用する特徴量を選別する選別工程とを備えたパターン認識方法であって、前記選別工程は、前記演算装置が、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除工程を備えたことを特徴とするものである。
【００１１】
本発明（方法）によれば、前記選別工程は、前記演算装置が、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除工程を備えたので、特徴量を１つずつ追加または削除するので時間がかかってしまうという不具合を、前記関数近似問題で用いたそれらの手法をパターン認識に適用して解消することができる。これにより、特徴量を迅速に削除して、大次元の特徴量を有するパターンの識別を高速に実現することができるようになる。
【００１２】
請求項２記載の発明のように、前記ブロック追加・削除工程は、前記演算装置が、前記初期の特徴量集合の認識率を閾値としておき、空集合に一時的に特徴量を１つ追加したときの該空集合の認識率を計算して、認識率の高い順に特徴量を順位付けたランキングを生成し、ランキングの上位の特徴量を前記空集合に追加したときの該空集合の認識率が前記閾値よりも大きいときに、特徴量の追加が成功したとして、該特徴量のみを前記特徴量集合に残し、その他の特徴量を該特徴量集合から削除するものであることが好ましい。
【００１３】
請求項２記載の発明によれば、前記ブロック追加・削除工程は、前記演算装置が、前記初期の特徴量集合の認識率を閾値としておき、空集合に一時的に特徴量を１つ追加したときの該空集合の認識率を計算して、認識率の高い順に特徴量を順位付けたランキングを生成し、ランキングの上位の特徴量を前記空集合に追加したときの該空集合の認識率が前記閾値よりも大きいときに、特徴量の追加が成功したとして、該特徴量のみを前記特徴量集合に残し、その他の特徴量を該特徴量集合から削除するものであるので、特徴量を迅速に削除することができる。
【００１４】
請求項３記載の発明のように、前記閾値は固定値であることが好ましい。
【００１５】
請求項３記載の発明によれば、前記閾値は固定値であるので、簡単な構成となる。
【００１６】
請求項４記載の発明のように、前記閾値は前記認識率に基づいて更新可能であることが好ましい。
【００１７】
請求項４記載の発明によれば、前記閾値は前記認識率に基づいて更新可能であるので、特徴量を追加・削除していくときに認識率の計算の精度が閾値を上回れば、そのつど閾値を更新して、より有用な特徴量を選択することができる。
【００１８】
ところで、通常のサポートベクトルマシンでは、２次計画問題を解くことによって学習を行うが、この学習に時間がかかるという問題がある。これに対して、最小自乗サポートベクトルマシンでは、線形連立方程式を解くことによって学習を行うので、通常のサポートベクトルマシンに比べて学習時間を短縮することができる。そこで、請求項５記載の発明のように、前記サポートベクトルマシンとして、最小自乗サポートベクトルマシンを備えており、前記演算装置は、この最小自乗サポートベクトルマシンで前記認識率を計算するものであることが好ましい。
【００１９】
請求項５記載の発明によれば、前記サポートベクトルマシンとして、最小自乗サポートベクトルマシンを備えており、前記演算装置は、この最小自乗サポートベクトルマシンで前記認識率を計算するものであるので、学習時間を短縮して、特徴量をより迅速に削除することができる。
【００２０】
また、データの次元数が大きいときには、１つずつ特徴量を追加・削除していては時間がかかるので、事前に多くの特徴量を削除するプリセレクションの必要性がある。さらに、線形計画サポートベクトルマシンでは、重みがゼロになれば、対応する入力データの次元は識別と無関係になるので、そのような次元を不必要な次元として削除することができる。そこで、請求項６記載の発明のように、前記サポートベクトルマシンとして、線形計画サポートベクトルマシンをも備えており、前記選別工程は、前記演算装置が、前記ブロック追加・削除工程を実行する前に、前記初期の特徴量集合を用いて、前記線形計画サポートベクトルマシンを学習させることにより、該特徴量集合に対応する重みを計算し、この重みの大きさに基づいて特徴量を前記初期の特徴量集合から予め削除しておくプリセレクション工程を備えることが好ましい。
【００２１】
請求項６記載の発明によれば、前記サポートベクトルマシンとして、線形計画サポートベクトルマシンをも備えており、前記選別工程は、前記演算装置が、前記ブロック追加・削除工程を実行する前に、前記初期の特徴量集合を用いて、前記線形計画サポートベクトルマシンを学習させることにより、該特徴量集合に対応する重みを計算し、この重みの大きさに基づいて特徴量を前記初期の特徴量集合から予め削除しておくプリセレクション工程を備えたので、データ数が少なくて、高次元のデータに対して、より多くの特徴量を削減できる。
【００２２】
一方、サポートベクトルマシンを学習するために変数をワーキング集合と固定集合とに分けて、ワーキング集合を繰り返して解く分割法があり、そこでのサポートベクトルマシンの学習は制約条件を満たすようにして行うことで最終解を得るのが通常であるが、この最終解を得るためには途中段階では必ずしも制約条件を満たす必要性がない。そこで、請求項７記載の発明のように、前記演算装置が、前記ブロック追加・削除工程で、入力変数をワーキング集合と固定集合とに分けて、ワーキング集合を繰り返して解く分割法の最適化問題において途中段階では制約条件を満たさないことを許すように前記サポートベクトルマシンを学習させることが好ましい。なお、本手法は、前記最小自乗サポートベクトルマシンに置き換わるものである。
【００２３】
請求項７記載の発明によれば、前記演算装置が、前記ブロック追加・削除工程で、入力変数をワーキング集合と固定集合とに分けて、ワーキング集合を繰り返して解く分割法の最適化問題において途中段階では制約条件を満たさないことを許すように前記サポートベクトルマシンを学習させるので、分割法を用いて、より迅速に最終解を得ることができる。
【００２４】
また、前記学習において最適化問題を解く主問題を用いることがあるが、このときには特徴空間を直接扱うこととなり、写像関数が線形以外ではその最適化問題を解くのが難しくなる。そこで、請求項８記載の発明のように、前記演算装置が、前記ブロック追加・削除工程で、前記最適化問題にラグランジェ乗数を適用した双対問題を用いて前記サポートベクトルマシンを学習させることが好ましい。
【００２５】
請求項８記載の発明によれば、前記演算装置が、前記ブロック追加・削除工程で、前記最適化問題にラグランジェ乗数を適用した双対問題を用いて前記サポートベクトルマシンを学習させるので、特徴空間を直接扱うことがなくなる。したがって、写像関数が線形以外であっても、その最適化問題を容易に解くことができて、より安定した収束と、より早い学習とが可能となる。
【００２６】
請求項９記載の発明のように、前記演算装置が、前記ブロック追加・削除工程で、前記双対問題を用いて前記サポートベクトルマシンを学習させる際に、初期変数集合から出発して解を求め、この解の中で正となる変数を残し、正しく分離されている変数、前記および零または負になる変数を削除し、さらに正しく分離されていない変数、あるいはマージンが不足している変数を追加して解を求めることを、同じ解が求まるまで繰り返すことが好ましい。
【００２７】
請求項９記載の発明によれば、前記演算装置が、前記ブロック追加・削除工程で、前記双対問題を用いて前記サポートベクトルマシンを学習させる際に、初期変数集合から出発して解を求め、この解の中で正となる変数を残し、正しく分離されている変数、前記および零または負になる変数を削除し、さらに正しく分離されていない変数、あるいはマージンが不足している変数を追加して解を求めることを、同じ解が求まるまで繰り返すので、より安定した収束と、より早い学習とが可能となる。
【００２８】
ただし、途中段階で制約を満たさないで双対問題を解いた場合には、制約を満たした条件で解く場合のように確実に収束しないことがある。そこで、請求項１０記載の発明のように、前記演算装置は、前記ブロック追加・削除工程で、前記繰り返し数が設定回数を超える、あるいは違反数が増加あるいは振動すると、制約を満たすように変数の修正量を制限して、前記サポートベクトルマシンを学習させることが好ましい。
【００２９】
請求項１０記載の発明によれば、前記演算装置が、前記ブロック追加・削除工程で、前記繰り返し数が設定回数を超える、あるいは違反数が増加あるいは振動すると、制約を満たすように変数の修正量を制限して、前記サポートベクトルマシンを学習させるものであるので、例えば１０回の繰り返し数を超えると、制約を満たすように変数の修正量を制限することで、確実に収束させることができる。
【００３０】
請求項１１記載の発明は、識別対象となる入力変数を入力するための入力手段と、サポートベクトルマシンを用いて、この入力変数からパターンの識別に使用する特徴量を選別する選別手段とを備えたパターン認識装置であって、前記選別手段は、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除手段を備えたことを特徴とするものである。
【００３１】
請求項１１記載の発明（装置）によれば、前記選別手段は、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除手段を備えたので、本発明（方法）と同様の作用効果を奏する。
【００３２】
請求項１２記載の発明は、入力装置により入力された入力変数からパターンの識別に使用する特徴量を選別するに際し、サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、前記特徴量集合から特徴量を一度に削除するブロック追加・削除機能をコンピュータに実現させることを特徴とするパターン認識プログラムに係るものである。
【００３３】
請求項１２記載の発明（プログラム）によれば、入力装置により入力された入力変数からパターンの識別に使用する特徴量を選別するに際し、サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、前記特徴量集合から特徴量を一度に削除するブロック追加・削除機能をコンピュータに実現させるので、本発明（方法）と同様の作用効果を奏する。
【発明の効果】
【００３４】
本発明（方法）によれば、前記選別工程は、前記演算装置が、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除工程を備えたので、特徴量を１つずつ追加または削除するので時間がかかってしまうという不具合を、前記関数近似問題で用いたそれらの手法をパターン認識に適用して解消することができる。これにより、特徴量を迅速に削除して、大次元の特徴量を有するパターンの識別を高速に実現することができるようになる。
【００３５】
請求項１１記載の発明（装置）によれば、前記選別手段は、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除手段を備えたので、本発明（方法）と同様の作用効果を奏する。
【００３６】
請求項１２記載の発明（プログラム）によれば、入力装置により入力された入力変数からパターンの識別に使用する特徴量を選別するに際し、サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、前記特徴量集合から特徴量を一度に削除するブロック追加・削除機能をコンピュータに実現させるので、本発明（方法）と同様の作用効果を奏する。
【図面の簡単な説明】
【００３７】
【図１】本発明の実施形態１に係るパターン認識方法を適用可能な装置の全体構成を示すブロック図である。
【図２】本実施形態１に係るパターン認識方法を適用可能な装置の概略動作を示すフローチャートである。
【図３】本実施形態１に係るパターン認識方法のアルゴリズム（１）を示すフローチャートである。
【図４】本実施形態１に係るパターン認識方法のアルゴリズム（２）を示すフローチャートである。
【図５】本実施形態２に係るパターン認識方法の学習アルゴリズム（１）を示すフローチャートである。
【図６】本実施形態２に係るパターン認識方法の学習アルゴリズム（２）を示すフローチャートである。
【発明を実施するための形態】
【００３８】
（実施形態１）
図１は本発明の実施形態１に係るパターン認識方法を適用可能な装置（以下、「本装置」という。）１の全体構成を示すブロック図である。図１に示すように、本装置１は、コンピュータ（演算装置に相当する。）３を備えている。
【００３９】
例えばコンピュータ３は、各種演算等を実行するＣＰＵ（Ｃｅｎｔｒａｌ ｐｒｏｃｅｓｓｉｎｇ ｕｎｉｔ）３１と、各種基本プログラム等を予め記憶しておくＲＯＭ（Ｒｅａｄ−ｏｎｌｙ ｍｅｍｏｒｙ）３２と、各種応用プログラム、各種データ等を一時的に記憶するＲＡＭ（Ｒａｎｄｏｍ−ａｃｃｅｓｓ ｍｅｍｏｒｙ）３３とを備えたパーソナルコンピュータであり、これにキーボードやマウスやＣＤ／ＤＶＤドライブなどの入力部（入力装置、入力手段に相当する。）２と、ＣＲＴや液晶やプリンタなどの表示部４とがそれぞれ電気的に接続されている。
【００４０】
そして、前記ＲＡＭ３３に記憶しておいたパターン認識プログラムを含む各種プログラム等を前記ＣＰＵ３１に読み込んで実行することで、学習部３１ａと、入力データ処理部（選別手段に相当する。）３１ｂと、パターン認識部３１ｃがそれぞれ構築されるようになっている。
【００４１】
学習部３１ａは、学習データを用いてＳＶＭを学習させるものである。入力データ処理部３１ｂは、識別対象である入力変数からパターンの識別に使用する特徴量を選別するものであって、前記入力変数を前記学習したＳＶＭに代入したときの値が閾値を越えたときに、当該入力変数を特徴量として選別するものである。そして、入力データ処理部３１ｂは、プリセレクション部３１ｂ１と、前記特徴量を一度に削除するブロック追加・削除部（ブロック追加・削除手段に相当する。）３１ｂ２を備えている。この入力データ処理部３１ｂのブロック追加・削除部３１ｂ２がパターン認識プログラムのブロック追加・削除機能を、コンピュータ３に実現させるものである。パターン認識部３１は、前記選別された特徴量に基づいてパターンの識別を行うものである。
【００４２】
本装置１の動作について説明する。図２は本装置１の概略動作を示すフローチャートである。なお、コンピュータ３には、入力部２から必要な学習データなどをあらかじめ入力しているもとする。
【００４３】
図２において、まず学習部３１ａは学習データを用いてＳＶＭを学習させる（ステップＳ１００）。次いで入力部２から識別対象となる入力変数を入力すると、入力データ処理部３１ｂはこの入力変数からパターンの識別に使用する特徴量を選別するが、その際にプリセレクション部３１ｂ１で特徴量を予め削除した上で、さらにブロック追加・削除部３１ｂ１で前記特徴量を一度に削除する（ステップＳ２００：入力工程、選別工程、プリセレクション工程、ブロック追加・削除工程）。そして、パターン認識部３１ｃは、この選別された特徴量に基づいてパターンの認識を行い、その識別結果を表示部４で表示させる（ステップＳ３００）。各ステップの具体的なアルゴリズムについては後述する。
【００４４】
以下、本発明の理解の便宜上、基本的なＳＶＭについて簡単に説明したうえで、パターン認識において認識率を求めるときに使う最小自乗サポートベクトルマシン（以下、ＬＳ−ＳＶＭという。）、多クラス問題、クロスバリデーション、特徴選択、順方向選択、逆方向選択についてそれぞれ説明する。
【００４５】
（ＳＶＭ）
Ｍ個のｍ次元教師データｘｉ（ｉ＝１，・・・，Ｍ）がクラス１またはクラス２に属しており、クラス１ならｙｉ＝１、クラス２ならｙｉ＝―１とする。この教師データｘｉを、写像関数ｇ（ｘ）を用いて、ｍ次元入力空間からｌ次元空間（ｌ＞ｍ）に写像することによって線形分離性能を高める。このとき決定関数は次式のようになる。
【００４６】
【数１】
ただし、ｗはｌ次元重みベクトル、ｂはバイアス項である。Ｄ（ｘ）＞０ならクラス１、Ｄ（ｘ）＜０ならクラス２に分類される。Ｄ（ｘ）＝０となる場合は分離不可能であるが、線形分離可能の条件ならＤ（ｘ）＝０となるデータは存在しない。よって次式を考える。
【００４７】
【数２】
この式（数２）は次式に変換できる。
【００４８】
【数３】
このとき次式
【数４】
がデータｘｉ（ｉ＝１，・・・，Ｍ）を分離する分離超平面である。ｃ＝０のとき分離超平面はｃ＝１と、ｃ＝−１の２つの超平面の中央となる。
【００４９】
分離超平面から最も近いデータまでの距離をマージンと呼び、超平面Ｄ（ｘ）＝１と、Ｄ（ｘ）＝−１がそれぞれ少なくとも１つの教師データを含むと仮定すると、超平面Ｄ（ｘ）＝０は、−１＜ｃ＜１について最大マージンを持つ。特徴空間上のある点ｇ（ｘ）とＤ（ｘ）＝０との距離は｜Ｄ（ｘ）｜／‖ｗ‖で与えられるので、マージンδは、
【数５】
と定義される。
【００５０】
しかし、線形分離不可能な場合に許容解が常に存在するように、ｘｉに対して非負のスラック変数ξｉを用いて前記式（数３）を次のように変換する。
【００５１】
【数６】
前記式（数１）を得るためにＳＶＭは以下の最適化問題を解く。
【００５２】
【数７】
ただし、Ｃはマージンパラメータといい、マージンの最大化と誤認識の最小化とのトレードオフを決めるものである。ｐ＝１のときをＬ１−ＳＶＭ、ｐ＝２のときをＬ２−ＳＶＭと呼ぶ。
【００５３】
（ＬＳ−ＳＶＭ）
ＳＶＭでは、２次元計画問題を解くことによって学習を行うが学習に時間がかかる。そこで、線形連立方程式を解くことによって学習を行うＬＳ−ＳＶＭについて述べる。
【００５４】
ＬＳ−ＳＶＭの最適化問題は以下のようにＳＶＭの制約条件の不等式を等式にしたものとなる。
【００５５】
【数８】
これらの２つの式（数８）の最適化問題を直接解くと特徴空間の変数を扱わなければならないので、非負のラグランジェ乗数αｉを導入し、次のような無制約の目的関数とする。
【００５６】
【数９】
この式（数９）の最適解は勾配が０となるときに得られる。したがって、同式（数９）をｗ，ｂ，α，ξで偏微分し、それぞれが０となるとすると、以下のような最適条件が得られる。
【００５７】
【数１０】
これら４つの式（数１０）をまとめると以下のように表せる。
【００５８】
【数１１】
ここで、ｌはＭ次元のベクトルであって、
【数１２】
であり、ｇＴ（ｘ）ｇ（ｘ’）はカーネル関数を用いてＨ（ｘ，ｘ’）と表される。またここで用いるカーネル関数はＲＢＦカーネルであり、以下のように定義される。
【００５９】
【数１３】
ここでγは傾きを制御する正の整数である。αとｂは以下のようになる。
【００６０】
【数１４】
このようにして、ＬＳ−ＳＶＭでは最適化問題をｌ次の連立方程式を解くことによって解が得られることが分かる。
【００６１】
（多クラス問題）
実際のパターン認識問題では、多クラスになることが多いため、２クラス問題から多クラス問題への拡張が必須となる。そこで、２クラス問題から多クラス問題に拡張するための手法の１つであるペアワイズを用いたペアワイズＳＶＭについて説明する。
【００６２】
このペアワイズＳＶＭでは、クラスのペアの全ての組み合わせについて決定関数を求める。１つのクラスのペアについての決定関数を決める際に、対応する２クラスの教師データを用いる。よって、ｎクラス問題に対し決定関数の数はｎ（ｎ−１）／２個となる。クラスｉのｊに対する決定関数を以下のように定義する。
【００６３】
【数１５】
ただし、ｗｉｊはｌ次元ベクトル、ｇ（ｘ）は写像関数、ｂｉｊはバイアス項を表しており、またＤｉｊ（ｘ）＝−Ｄｊｉ（ｘ）となる。クラスｉの領域は次式で表され、
【数１６】
オーバーラップしない。そして、ｘがＲｉに含まれれば、ｘをクラスｉに分類し、ｘがＲｉに含まれなければｘを投票で分類する。すなわち、入力データｘに対して次式を求める。
【００６４】
【数１７】
ここで、
【数１８】
このとき、ｘは次式で分類される。
【００６５】
【数１９】
もしＤｉ（ｘ）＝ｎ−１かつＤｋ（ｘ）＜ｎ−１（ｉ≠ｋ）であれば、ｘはクラスｉに分類される。しかしどのＤｉ（ｘ）のｎ−１でないとき、この式は複数のｉについて成立する。このときｘは未分類領域である。未分類領域はファジィメンバーシップ関数を導入することにより解消できる（例えば非特許文献２）。またここではペアワイズＳＶＭについて説明したが、1対多ＳＶＭ、同時定式化ＳＶＭ等（例えば非特許文献２）を適用することも可能である。
【００６６】
（クロスバリデーション）
ＳＶＭを学習させるためには、マージンパラメータＣやＲＢＦカーネルのパラメータγなどの値を設定しなければならない。最適なパラメータの組み合わせを決定するためにｋ分割クロスバリデーションを用いる。このｋ分割クロスバリデーションでは教師データをほぼ均一なｋ個の部分集合に分割し、ｋ−１個の部分集合で学習し、残りの１つでテストする。学習ｋ回繰り返し、テストに使用したｋ個の部分集合に対する全体の認識率を計算する。そして一番認識率の高かったパラメータの組み合わせを決定する。ＳＶＭでは教師データでの学習に基づいてテストデータにおける汎化能力をみるので、ｋ分割クロスバリデーションを行うときも教師データを分割して教師データとテストデータに分けたほうが、信頼性の高いパラメータを選ぶことができる。
【００６７】
（特徴選択）
特徴量の削減はパターン認識において重要な課題である。なぜなら冗長な特徴量が多いと次のような問題が起こる。１つめは特徴量の増加に対して指数関数的に増加する計算量の増加である。２つめは本来有用でない特徴量も学習に使用してしまうことによる汎化能力の低下である。３つめは冗長な特徴量も有用な特徴量として学習に使用されてしまうことによる汎化能力の低下である。
【００６８】
このような問題を解決するために特徴選択が行われる。特徴選択はある評価基準に基づいて不要な特徴量を選び出して削除することである。特徴選択の代表的な手法としてフィルター法とラッパー法があることは既に説明したとおりである。ここでは、フィルター法に比べて計算コストは大きくなるものの、汎化性が大きくなるラッパー法を用いることとする。ただし、フィルター法に対しても同様に発明の特徴選択法を適用することが可能である。引き続き、パターン認識で用いられている特徴選択の手法である順方向選択と逆方向選択とについて説明する。
【００６９】
（順方向選択）
ここでは認識率を基準とした順方向選択について説明する。まず特徴量の数をｍとし、初期特徴量集合をＩｍとし、Ｉｍにおける認識率をＲｍとしてこれを特徴選択の終了条件の閾値とする。空集合Ｉ０にｉ番目（ｉ＝１，・・・，ｍ）の特徴量を一時的に追加する。そのときの認識率をＲｉａｄｄとする。ただし、ｉａｄｄはｉ番目の特徴量を追加することを表す。Ｒ１ａｄｄからＲｍａｄｄの中で一番値が大きかったものをＲｋａｄｄ（ｋ＝１，・・・，ｍ）として、
【数２０】
を満たせば特徴選択を終了する。この式（数２０）を満たさなければ精度が上がるまで同様の手順を繰り返す。
【００７０】
（逆方向選択）
ここでは認識率を基準とした逆方向選択について説明する。まず特徴量の数をｍとし、初期特徴量集合をＩｍとし、Ｉｍにおける認識率をＲｍとしてこれを特徴選択の終了条件の閾値とする。Ｉｍから一時的にｉ番目（ｉ＝１，・・・，ｍ）の特徴量を削減し、そのときの認識率をＲｍｍｄｅｌとする。ただし、ｉｄｅｌはｉ番目の特徴量を削減することを表す。Ｒｍ１ｄｅｌからＲｍｍｄｅｌの中で一番値が大きかったのをＲｍｋｄｅｌと（ｋ＝１，・・・，ｍ）として、
【数２１】
を満たせば、ｋ番目を削除する。閾値を上回る限り同様の手順を繰り返す。
【００７１】
以下、本発明の特徴をなす、閾値設定方式、２クラスのブロック追加・削除による特徴選択、２クラスの線形計画サポートベクトルマシン（以下、ＬＰ−ＳＶＭという。）を用いたブロック追加・削除による特徴選択および多クラスへの拡張について説明する。ブロック追加・削除による特徴選択は、順方向選択や逆方向選択のように特徴量を１つずつ追加・削徐していては時間がかかるので、ブロック追加・削除で特徴量を一度に追加・削除する手法である。この方法は順方向選択や逆方向選択等の認識率で高速に特徴量を選択することが目的である。また、ＬＰ−ＳＶＭを用いたブロック追加・削除による特徴選択は、データの次元数が非常に多いと、順方向選択や逆方向選択のように特徴量を１つずつ追加・削除して評価していては時間がかかるので、事前に不要な特徴量をまとめて削除してからブロック追加・削除を行う手法である。ただし、評価基準となる認識率は前記ＬＳ−ＳＶＭで求めてもよいし、後で述べる学習を高速化したＬ２−ＳＶＭで求めてもよい。
【００７２】
（閾値設定方式）
ここでは特徴選択の終了条件を特徴選択後の認識率が設定した閾値よりも悪くなることとしている。閾値の設定方式として閾値固定方式と閾値更新方式を用いる。閾値固定方式は閾値を最初に設定した値のまま最後まで固定して特徴選択を行う方式である。閾値更新方式は特徴量を追加・削除したときに精度が閾値を上回れば、その都度閾値を更新しながら特徴選択を行っていく方式である。その都度閾値を更新する閾値更新方式の方がより有用な特徴量を選択できる。
【００７３】
（２クラスのブロック追加・削除による特徴選択）
順方向選択や逆方向選択では、特徴量を１ずつ追加・削除していくが、これでは不要な特徴量が多いとき時間がかかる。そこで特徴量を一度に追加・削除するブロック追加・削除を用いる。本手法は、高速で特徴選択を行いなおかつ初期特徴量集合と同等の精度を得るのが目的である。
【００７４】
そして、閾値固定方式では、まず初期特徴量集合をＩｍとして、Ｉｍにおけるバリデーションセットの認識率Ｒｍを閾値Ｔとする。ただしｍは初期特徴量集合の次元数である。空集合Ｉ０に一時的にｉ番目の特徴量を１つ追加し、そのときの認識率Ｒ０ｉａｄｄを計算し、追加候補集合を作成し、認識率の高い順に特徴量を順位づけたランキング（ｖａｒｉａｂｌｅ ｒａｎｋｉｎｇ）を生成する。なお、認識率が同じでランキングができないときは、前記式（数５）のマージンの大きい順にランキングを行う。このランキングの上位２ｋ個（ｋ＝０，・・・，Ａ）を空集合に追加する。ここで、Ａは追加候補数を制限するユーザパラメータである。追加したときの認識率Ｒ２ｋと閾値Ｔを比較し、
【数２２】
となれば、そのときの特徴量を追加する。
【００７５】
ｋ＝Ａまで（数２２）式を満たさないとき、Ｒ２０，Ｒ２１，・・・，Ｒ２Ａの中で認識率の最も高いときの特徴量集合を空集合に追加する。次に新たな追加候補を選択するために、一時的追加を行う。そのときの特徴量集合にｉ番目の特徴量を追加し、そのときの認識率を基にして新たなランキングを構成し、先ほどと同様にして特徴量の追加判定を行う。先ほどと同様に、認識率が同じでランキングができないときは、前記式（数５）のマージンの大きい順にランキングを行う。追加が成功すれば、そのときの特徴量集合からブロック削除を行い、余分な特徴量を削除する。もし、追加したときに前回の認識率を下回れば追加失敗として、初期特徴量集合からのブロック削除に切り替える。追加失敗が続くと特徴量選択の効率が落ちるので、１回の失敗で追加を終了する。
【００７６】
一方、閾値更新方式では、追加時に精度が向上する場合に閾値をそのときの認識率に更新することで、精度の高い特徴量集合を求める。
【００７７】
図３は本実施形態１に係るパターン認識方法のアルゴリズム（１）を示すフローチャートであって、前記図２におけるステップＳ２００を具体化するものである。なお、この図３における閾値固定方式と閾値更新方式との違いはステップＳ３ａ，Ｓ３ｂと、ステップＳ７ａ，Ｓ７ｂとだけであるので、以下では、その部分のみ場合分けをして説明する。
【００７８】
ステップＳ１：初期特徴量集合をＩｍとし、Ｉｍにおけるバリデーションセットの認識率をＲｍとし、これを閾値Ｔとする。ただしｍは初期特徴量集合の次元数である。
【００７９】
ステップＳ２：空集合Ｉ０にｉ番目（ｉ＝１，・・・，ｍ）の特徴量を追加し、追加したときの認識率をＲ０ｉａｄｄとする。これは空集合にｉ番目の特徴量を追加した集合における認識率である。
【００８０】
ステップＳ３：Ｒ０ｉａｄｄ（ｉ＝Ｉ，・・・，ｍ）を大きい順に特徴量を順位づけたランキングを生成する。その上位２ｋ個（ｋ＝０，・・・，Ａ）の特徴量を空集合に追加していく。
【００８１】
ステップＳ３ａ（閾値固定方式の場合）：追加したときの認識率が閾値Ｔを上回れば追加成功としてその特徴量集合のままステップＳ４へ進み、ｋ＝Ａまで成功しない場合はｋ＝Ａまで追加していったなかで一番高かった認識率Ｒｍａｘ（ｋ＝０，・・・，Ａ）を求め、追加前の特徴量集合における認識率を上回れば、その２ｋ個を追加してステップＳ２に戻る。上回らなければ初期特徴量集合に戻してステップＳ４へ進む。
【００８２】
ステップＳ３ｂ（閾値更新方式の場合）：上記閾値固定方式と同じようにＲｍａｘを求め、追加前の特徴量集合における認識率を上回れば、２ｋ個を追加してステップＳ２に戻る。上回らない場合、追加前の特徴量集合における認識率が閾値Ｔを上回れば閾値を追加前の特徴量集合における認識率に更新してステップＳ４に進む。満たさなければ初期特徴量集合に戻してステップＳ４へ進む。
【００８３】
ステップＳ４：この時点での特徴量集合をＩｊとし、Ｉｊにおける認識率をＲｊとし、閾値更新方式ではこれを新たに閾値Ｔとする。ただしｊはこの時点での次元数である。
【００８４】
ステップＳ５：Ｉｊからｉ番目（ｉ＝０、…、ｊ）の特徴量を削除し、そのときの認識率をＲｊｉｄｅlとする。
【００８５】
ステップＳ６，Ｓ６ａ：Ｒｊｉｄｅｌ（ｉ＝０，・・・，ｊ）のなかで閾値を上回ったものの中でランキングを生成し、なければ特徴選択を終了する。
【００８６】
ステップＳ７：Ｉｊからランキングにある特徴量をすべて削除し認識率を求める。
【００８７】
ステップＳ７ａ（閾値固定方式の場合）：閾値を上回れば削除後の特徴量集合でステップＳ５へ進み、閾値を上回らなければステップＳ８へ進む。
【００８８】
ステップＳ７ｂ（閾値更新方式の場合）：閾値を上回れば閾値を更新して削除後の特徴量集合でステップＳ５へ進み、閾値を上回らなければステップＳ８へ進む。
【００８９】
ステップＳ８：Ｉｊからランキングの上位半分を削除し、閾値を上回ればその削除後の特徴量集合でステップＳ５へ進み、満たされなければ、満たすまで削除候補を上位半分にしていく。なお、ランキングが生成されたため、このステップでは１個は必ず削除される。
【００９０】
（２クラスのＬＰ−ＳＶＭを用いたブロック追加・削除による特徴選択）
データの次元数が大きいとき、１つずつ特徴量を追加、削除していては時間がかかるので、事前に多くの特徴量を削除するプリセレクションの必要性がある。本手法ではＬＰ―ＳＶＭによる特徴選択をプリセレクションとして用いる。ＬＰ−ＳＶＭはＬＩ−ＳＶＭの目的関数の‖ｗ‖２２＝ｗ２１＋ｗ２２＋…＋ｗ２ｍを‖ｗ‖１＝｜ω１｜＋｜ω２｜＋…＋｜ωｍ｜に置き換えることによって線形計画問題として定式化できる。いわゆる単体法で解くためには、変数が非負である必要があるためωｉ＝ωｉ＋−ωｉー、ｂ＝ｂ＋−ｂ−として次式の線形計画問題とする。
【００９１】
【数２３】
ＬＰ−ＳＶＭでは、Ｍをデータ数、ｍを次元数とすると目的関数の変数がＮ＝２ｍ＋Ｍ＋２となり、制約条件の数はＭ本となるので、少なくともＮ−Ｍ個の変数は０になる。重みベクトルが０になれば対応する入力データの次元は識別とは無関係になる。このような次元を不必要な次元として削除する。次元数が多いとＮ−Ｍの値が大きくなる。よって、データ数が少なくて高次元のデータに対して、多くの特徴量を削除できる。
【００９２】
そして、閾値固定方式では、初めに初期特徴量集合Ｉｍを用いてバリデーションセットの認識率Ｒｍを閾値Ｔとする。ここでｍは初期特徴量集合の次元数である。次にＬＰ−ＳＶＭの学習によって各特徴量に対応する重みの値｜ωｉ｜を求め、最大値のμ％以下の値を持つ特徴量をすべて特徴量集合から削除する。ここでμはユーザパラメータである。
【００９３】
プリセレクション後の特徴量の数をｊＬＰとしたとき、このときの認識率ＲｊＬＰと閾値Ｔと比較して、
【数２４】
となれば、さらに削除できる特徴量を探すためにブロック削除を行う。精度が低下したら、削除時の特徴量集合に有用な特徴量を追加する。追加候補となるのは追加したときにＬＰ−ＳＶＭでの学習後の特徴量集合の認識率ＲｊＬＰより精度を向上させるものである。これらの特徴量でランキングを構成し、ブロック追加・削除を行う。
【００９４】
一方、閾値更新方式では、プリセレクション後の認識率が閾値よりも小さくなっていれば、それを新たな閾値とする。また、ブロック追加を行う際も追加前より精度が向上していれば、そのときの認識率を閾値にする。
【００９５】
図４は本実施形態１に係るパターン認識方法のアルゴリズム（２）を示すフローチャートであって、これも前記図２におけるステップＳ２００を具体化するものである。なお、図４における閾値固定方式と閾値更新方式との違いはステップＳ１３ａ，Ｓ１３ｂ、ステップＳ１５ａ，Ｓ１５ｂ、ステップＳ１９ａ，Ｓ１９ｂだけであるので、以下では、それらの部分だけ場合分けをして説明する。
【００９６】
ステップＳ１１：初期特徴量集合をＩｍとし、Ｉｍにおけるバリデーションセットの認識率をＲｍとし、これを閾値Ｔとする。ただしｍは初期特徴量集合の次元数である。
【００９７】
ステップＳ１２：初期特徴量集合Ｉｍを用いて、ＬＰ−ＳＶＭで学習し、重みωｉ（ｉ＝１，・・・，ｍ）を求める。求めた重みの絶対値の最大値｜ωｉ｜ｍａｘを求めて、｜ωｉ｜≦μ｜ωｉ｜ｍａｘとなる特徴量をＩｍから削除する（ステップＳ１２）。ただしμはユーザパラメータである。
【００９８】
ステップＳ１３：削除後に認識率を求め、閾値Ｔと比較する。
【００９９】
ステップＳ１３ａ（閾値固定方式の場合）：閾値を上回れば削除成功となり削除後の特徴量集合でステップＳ１６へ進む。
【０１００】
ステップＳ１３ｂ（閾値更新方式の場合）：閾値を上回れば閾値を更新して削除後の特徴量集合でステップＳ１６へ進む。上回らなければ削除後の特徴量集合でステップＳ１４へ進む。
【０１０１】
ステップＳ１４：削除後の特徴量集合に削除された特徴の中からｉ番目（ｉ＝１，・・・，ｎ）の特徴量を追加し、追加したときの認識率をＲｉａｄｄとする。
【０１０２】
ステップＳ１５：Ｒｉａｄｄ（ｉ＝１，・・・，ｎ）を大きい順に特徴量を順位づけたランキングを生成する上位２ｋ個（ｋ＝０，・・・，Ａ）の特徴量を追加していく。
【０１０３】
ステップＳ１５ａ（閾値固定方式の場合）：追加したときの認識率が閾値Ｔを上回れば追加成功としてその特徴量集合のままステップＳ１４へ進む。ｋ＝Ａまで成功しない場合はｋ＝Ａまで追加したなかで一番高かった認識率Ｒｍａｘ（ｋ＝０，・・・，Ａ）を求め、追加前の特徴量集合における認識率を上回れば、その２ｋ個を追加してその集合でステップＳ１２に戻る。上回らなければ初期特徴量集合に戻してステップＳ１６へ進む。
【０１０４】
ステップＳ１５ｂ（閾値更新方式の場合）：前記閾値固定方式と同じように認識率Ｒｍａｘを求め、追加前の特徴量集合における認識率を上回れば、その２ｋ個を追加してその集合でステップＳ１４へ進む。上回らない場合、追加前の特徴量集合における認識率が閾値Ｔを上回れば閾値を追加前の特徴量集合における認識率に更新してステップＳ１６へ進み、満たさなければ初期特徴量集合に戻してステップＳ１６へ進む。
【０１０５】
ステップＳ１６：この時点での特徴量集合をＩｊとし、Ｉｊにおける認識率をＲｊとし、これを閾値Ｔとする。ただしｊはこの時点での特徴量集合の次元数である。
【０１０６】
ステップＳ１７：Ｉｊからｉ番目（ｉ＝０，・・・，ｊ）の特徴量を削除し、そのときの認識率をＲｊｉｄｅｌとする。
【０１０７】
ステップＳ１８，Ｓ１８ａ：Ｒｊｉｄｅｌ（ｉ＝０，・・・，ｊ）のなかで閾値を上回ったものの中でランキングを生成する。もし閾値を上回るものがなければ処理を終了する。
【０１０８】
ステップＳ１９：Ｉｊからランキングにある特徴量をすべて削除し認識率を求める。
【０１０９】
ステップＳ１９ａ（閾値固定方式の場合）：閾値を上回れば削除後の特徴量集合でステップＳ１７へ進み、閾値を上回らなければステップＳ２０へ進む。
【０１１０】
ステップＳ１９ｂ（閾値更新方式の場合）：閾値を上回れば閾値を更新して削除後の特徴量集合でステップＳ１７へ進み、閾値を上回らなければステップＳ２０へ進む。
【０１１１】
ステップ２０：Ｉｊからランキングの上位半分を削除し、閾値を上回ればその削除後の特徴量集合でステップＳ１７へ進む。満たされなければ、満たすまで削除候補を上位半分にしていく。
【０１１２】
（多クラスへの拡張）
多クラスの場合も２クラスの場合と同様の流れでブロック追加・削除による特徴選択を行う。例えばブロック削除の削除候補を選ぶ際、まず一時的に特徴量集合から特徴量を１つ削除し、ペアワイズ方式を用いて認識率を計算し、削除した際に閾値を上回った特徴量すべて削除する。異なる点は認識率を求めるのにペアワイズ方式を用いることだけである。ただし、認識率によるランキングで順序付けられないときにマージンを用いるときは、各ペアのクラスに対応するマージンの平均値、最大値、あるいは最小値をとるようにする。
【０１１３】
以下、本装置１を用いたシミュレーション結果について説明する。なお、ここでは２クラスと多クラスのベンチマークデータとＵＣＩベンチマークデータ、２クラスの高次元データのマイクロアレイデータを用いて実験を行い、特徴選択前と特徴選択後で認識率を比較した結果を示すものとする。
【０１１４】
（実験方法）
２クラスおよび多クラスのベンチマークデータとＵＣＩベンチマークデータはブロック追加・削除で実験を行い、マイクロアレイデータは高次元データであるのでＬＰ−ＳＶＭでプリセレクションを行ってからブロック追加・削除を行う。ＬＳ−ＳＶＭのマージンパラメータとＲＢＦカーネルのパラメータ、ＬＰ−ＳＶＭのマージンパラメータ、プリセレクションに使用するμは５分割クロスバリデーションで１ファイルごとに決定している。
【０１１５】
ＬＳ−ＳＶＭのマージンパラメータＣ、ＲＢＦカーネルのパラメータγは、Ｃ＝｛１,１０,５０，１００，５００,１０００,５０００,１００００，５００００，１０００００｝、γ＝｛０．０００１，０．００１，０．０１，０．１，０．５，１．０，５．０，１０，１５｝から最適なパラメータの組み合わせを選択する。またＬＰ−ＳＶＭのマージンパラメータＣとμはＣ＝｛１０，１００００｝μ＝｛０,０．０５，０．１，０．１５，０．２｝から最適なパラメータの組み合わせを選択する。
【０１１６】
特徴選択途中の認識率を求める際はマージンパラメータのみをクロスバリデーションで決定し、Ｃ＝｛１,１０,５０，１００，５００,１０００,５０００,１００００，５００００，１０００００｝から最適なパラメータを選択する。（表１）にはＩＤＡの２クラスベンチマークデータ、（表２）には多クラスベンチマークデータ、（表３）にはマイクロアレイデータ、（表４）にはＵＣＩベンチマークデータについて記す。
【０１１７】
各表の“Ｉｎｐｕｔｓ”はデータの次元数、“Ｔｒａｉｎ”は教師データ数、“Ｔｅｓｔ”はテストデータ数、“Ｃｌａｓｓ”はクラス数を表す。ただしマイクロアレイデータ、ＵＣＩベンチマークデータはすべて２クラスである。またＵＣＩベンチマークデータは教師データのみである。実験結果は２クラスベンチークデータのＩｍａｇｅとＳｐｌｉｃｅ以外は１００ファイル、Ｉｍａｇｅ、Ｓｐｌｉｃｅとマイクロアレイデータは２０ファイルの平均である。なおシミュレーションにおけるコンピュータ３としては、Ｉｎｔｅｌ Ｃｏｒｅ（ＴＭ）２Ｄｕｏ ３．１８ＧＨｚ １．９９ＧＢ ＲＡＭを使用した。
【０１１８】
【表１】
【表２】
【表３】
【表４】
（２クラスベンチマークデータでの実験結果）
２クラスベンチマークデータを用いた、閾値固定方式と閾値更新方式での実験結果を（表５）に示す。実験結果の表の“Ｄａｔａ”は用いたデータセット、“Ｂｅｆｏｒｅ”と“Ａｆｔｅｒ”は特徴選択の前と後の結果を表す。“Ｖａｌ”はバリデーションセットのテストデータの認識率、“Ｔｅｓｔ”はテストデータの認識率、“Ｄｅｌｅｔｅｄ”は削除次元数、“Ｔｉｍｅ”は特徴選択にかかった時間である。２行になっているのは、上段が閾値固定方式での実験結果、下段が閾値更新方式での実験結果を表しているからである。特徴線選択前の結果はどちらも変わらないので１段になっている。特徴選択後にテストデータの認識率がよくなった場合は＊で表している。
【０１１９】
（表５）より、バリデーションセットのテストデータの認識率は全データで特徴選択後の方がよくなっている。これはバリデーションセットのテストデータの認識率が向上するように特徴量を選んでいるからである。Ｆ．Ｓｏｌａｒ，Ｉｍａｇｅ，Ｓｐｌｉｃｅ，Ｔｉｔａｎｉｃに関してはテストデータでも認識率の向上がみられ、他のデータでも認識率が大幅に低下したデータはなくほぼ同等の認識率が得られたので、特徴選択の効果が出ているといえる。ＢａｎａｎａはＤｅｌｅｔｅｄが０なのでどの特徴量を削除しても認識率が向上しなかったことを示している。時間の標準偏差が大きいデータがいくつかみられるが、ブロック削除を行う際、削除候補となる特徴量の数の違いによってブロック削除を繰り返す回数に違いが生じることが原因と考えられる。
【０１２０】
また閾値固定方式と閾値更新方式を比べたところほとんどのデータで閾値更新方式の方が認識率がよくなっており、時間も早くなっているので、閾値を更新する方が有用な特徴量を高速に選ぶことができるといえる。しかし、次元数が最も多いＳｐｌｉｃｅだけは閾値更新方式の方が時間がかかる結果となった。これはブロック削除を行う際に閾値を更新した方が削除候補となる特徴量の数が少なく、ブロック追加を繰り返す回数が多くなるということが考えられる。
【０１２１】
【表５】
（マイクロアレイデータでの実験結果）
マイクロアレイデータを用いた、閾値固定方式と閾値更新方式での実験結果を（表６）に示す。同表より、バリデーションセットのテストデータの認識率は全データで特徴選択後の方がよくなっており、テストデータの認識率もＢ．ｃａｎｃｅｒ１とＢ．ｃａｎｃｅｒ２以外のデータでは特徴選択前と後とではほぼ同等の認識率を得ている。特にＧｏｌｕｂは認識率が向上した。特徴選択後の特徴量の数は全データで２から３個程度である。よって、数個の特徴量でも特徴選択前と同等のも認識率を得ることができるといえる。
【０１２２】
しかし、Ｂ．ｃａｎｃｅｒ１とＢ．ｃａｎｃｅｒ２では大幅に認識率が低下している。これは両方のデータがともにテストデータ数が８なので１つの認識を誤ると１２．５％も認識率が低下することが原因と考えられる。Ｖａｎｔｖｅｅｒ以外で特徴選択後のテストデータの認識率の標準偏差が大きくなった。これはテストデータ数が少なく、１つの誤認識で認識率が大幅に低下してしまい、２０ファイル中数ファイルでそのようなことが起こったことが原因と考えられる。Ｓｐｏｒａｄｉｃ以外で時間の標準偏差が非常に大きくなっている。これはプリセレクションを行った際、いくつかのファイルで精度が低下してブロック追加を行ったため余分に時間がかかってしまったことと、２クラスベンチマークデータ同様ブロック削除を繰り返す回数の違いが原因と考えられる。
【０１２３】
また閾値固定方式と閾値更新方式を比べたところ、Ｓｐｏｒａｄｉｃ、Ｖａｎｔｖｅｅｒ以外のデータは閾値更新方式の方が認識率が良くなっており、より有用な特徴量を選んでくる閾値更新方式の特徴が表れているが、Ｓｐｏｒａｄｉｃ、Ｖａｎｔｖｅｅｒは閾値固定方式の方が認識率が良くなった。時間に関してはＡｌｏｎ、Ｓｐｏｒａｄｉｃ、Ｖａｎｔｖｅｅｒは閾値固定方式の方が早いがＢ．ｃａｎｃｅｒ１、Ｂ．ｃａｎｃｅｒ２、Ｇｏｌｕｂ、Ｉｉｚｕｋａは閾値更新方式の方が速かった。閾値を更新した方が選んでくる特徴量は多少少ないが、ブロック削除で削除候補となる特徴量も少なくなり、次元数が多いとブロック削除を繰り返す回数が多くなるので、どちらがよいとはいえない。
【０１２４】
【表６】
（多クラスベンチマークデータでの実験結果）
多クラスベンチマークデータを用いた、閾値固定方式と閾値更新方式での実験結果を（表７）に示す。同表より、バリデーションセットのテストデータの認識率は２クラスベンチマークデータとマイクロアレイデータ同様全データ特徴選択後の方がよくなっており、テストデータの認識率も全データ特徴選択前と後とでほぼ同等の認識率が得られている。ＩｒｉｓとＢｌｏｏｄ ｃｅｌｌは削除された特徴量が０なのでどの特徴量を削除しても認識率が向上しなかったことを表す。Ｔｈｙｒｏｉｄは特徴選択前と同等の認識率を得るのに３つの特徴量しか必要とせず、しかもテストデータの認識率が向上する結果となった。
【０１２５】
閾値固定方式と閾値更新方式を比べたところ、全データ認識率が変わらないという結果となった。これは、多クラスベンチマークデータは特徴選択をする前から非常に高い認識率が出ているので、特徴量を削除しても認識率がそれほど向上しないことが原因と考えられる。また、時間に関しては全データとも閾値更新方式の方が速かった。よって多クラスベンチマークデータに関しては閾値更新方式の方が有用な特徴量を高速に選択できるといえる。
【０１２６】
【表７】
（ＵＣＩベンチマークデータでの実験結果）
ＵＣＩベンチマークデータを用いたときの閾値固定方式と閾値更新方式での実験結果を（表８）に示す。ＵＣＩベンチマークデータは教師データのみ用いるのであって、“Ｔｒａ”は教師データの認識率である。同表より、Ｐｒｉｍａｉｎｄｉａｎｓは特徴選択後大幅に識別力が低下してしまっている。Ｂｕｐａｌｉｖｅｒは削除数が０なので、特徴量を削減しても認識率が向上しなくなったことを示す。
【０１２７】
閾値固定方式と閾値作成新方式を比べたところ、認識率はＰｉｍａｉｎｄｉａｎｓでは閾値更新方式の方が高かったが、他の２つでは変わらなかった。時間においてはＢｕｐａｌｉｖｅｒは変わらなかったが、他の２つでは閾値更新方式の方が速かった。よって、ＵＣＩベンチマークデータでは閾値更新方式の方が有用な特徴量を高速に選択できるといえる。
【０１２８】
【表８】
以上説明したように、本実施形態１では、パターン認識におけるブロック追加・削除による特徴選択と、ＬＰ−ＳＶＭを用いたブロック追加・削除による特徴選択を説明した。ブロック追加・削除は特徴量を１つずつ追加・削除する順方向選択や逆方向選択と違い、追加・削除したときに精度が上がる特徴量を一度に追加・削除するので高速な特徴選択が可能である。また、ブロック追加・削除を行う前にＬＰ−ＳＶＭを用いて、各データにかかる重みを計算し、重みが０に近い特徴量をあらかじめ削除することによって、次元数の多いデータに対して高速に特徴選択を行うことができる。
【０１２９】
２クラスベンチマークデータと多クラスベンチャーマークデータはブロック追加・削除による特徴選択、マイクロアレイデータはＬＰ−ＳＶＭを用いたブロック追加・削除による特徴選択を用いた。特徴選択の終了条件である閾値はバリデーションセットのテストデータの認識率を用い、閾屋を固定しないまま特徴選択を行う閾値固定方式と精度が上がるたびに閾値を更新する閾値更新方式で実験を行った。
【０１３０】
２クラスベンチマークデータと多クラスベンチマークを用いたシミュレーション実験より、本手法が初期特徴量集合と同等の精度を保ちながら有用な特徴量を選択できていることが示された。また閾値固定方式より閾値更新方式の方がより有用な特徴量を高速に選択できることが示された。マイクロアレイデータを用いたシミュレーション実験では、殆どのデータでベンチマークデータ同様有用な特徴量を選択できていたが、テストデータ数が少ないこともあり、一部のデータで認識率が非常に低下した。また閾値固定方式と閾値更新方式を比較したところ、時間にしてはどちらが優れているかは判断できなかったが、閾値更新方式の方が、有用な特徴量を確保できた。
【０１３１】
（実施形態２）
この実施形態２では、前記装置１における学習部３１ａおよびブロック追加・削除部３１ｂ２におけるＬＰ−ＳＶＭのかわりに用いることができるＬ２−ＳＶＭの学習について説明するが、これも本発明の特徴をなすものである。ＳＶＭの学習において、次の最適化問題を解く。
【０１３２】
【数２５】
ただしｗは重みベクトル、φ（ｘ）は多次元入力ベクトルｘを特徴空間に写像する関数、ｂはバイアス項、（ｘｉ，ｙｉ）（ｉ＝１，・・・，Ｍ）はＭ個の教師データ対でｘｉがクラス１に属するときにｙｉ＝１で、ｘｉがクラス２に属するときにｙｉ＝−１である。Ｃはマージンの最大化と教師データに対する誤認識のトレードオフを決定するマージンパラメータ、ξｉはｘｉに対する非負のスラック変数でＬ１−ＳＶＭのときｐ＝１で、Ｌ２−ＳＶＭのときｐ＝２とする。ｙｉ（ｗＴφ（ｘｉ）＋ｂ）をｘに対するマージンという。
【０１３３】
これら２つの式（数２５）のままでは、特徴空間を直接扱うことになり、写像関数が線形以外は解くのは難しい。このためにラグランジェ乗数αｉを導入することでＬ１−ＳＶＭに対して次の双対問題を得た。
【０１３４】
【数２６】
そして、Ｌ２−ＳＶＭに対しては、
【数２７】
なる双対問題を得た。ただしＫ（ｘ，ｘ’）は、カーネル方程式であり、Ｋ（ｘ，ｘ’）＝φＴ（ｘ）φ（ｘ‘）、ｉ＝ｊでδｉｊ＝１、ｉ≠ｊで０である。
【０１３５】
ここでは、多項式カーネルであるＫ（ｘ，ｘ’）＝（ｘＴ，ｘ’＋１）ｄと、ＲＢＦカーネルであるＫ（ｘ，ｘ’）＝ｅｘｐ（−γ‖ｘ−ｘ’‖２）を使用する。ただし、ｄは正の整数であり、γは傾きを制御するための正のパラメータである。Ｌ１−ＳＶＭに対するＫＫＴ条件が次式で与えられる。
【０１３６】
【数２８】
【０１３７】
前記２つの式（数２６）の解に対して、もしαｉ＞０であれば、ｘｉはサポートベクトルという。特にαｉ＝Ｃであれば、ｘｉは上限に達したサポートベクトル、０＜αｉ＜Ｃであれば、ｘｉは上限に達していないサポートベクトルという。Ｌ２−ＳＶＭに対するＫＫＴ条件が次式で与えられる。
【０１３８】
【数２９】
ここで、αｉ＝Ｃξｉである。
【０１３９】
（主問題におけるＳＶＭの学習）
前記２つの式（数２５）で与えられた最適化問題は、次の拘束なしの最適化問題に変換される。
【０１４０】
【数３０】
ただし、ｗは次式で表すものと仮定する。
【０１４１】
【数３１】
ここで、βｉ（ｉ＝１，・・・，ｍ）は定数である。この式（数３１）を前記式（数３０）に代入して、次式が得られる。
【０１４２】
【数３２】
Ｌ１−ＳＶＭに対する最適解を与えるデータに関連するインデックスの１セットを定義する。
【０１４３】
【数３３】
ただしＤ（ｘ）は決定方程式であり、Ｄ（ｘ）＝ｗＴφ（ｘ）＋ｂで与えられる。Ｌ２−ＳＶＭに対しては、
【数３４】
を定義する。ただしαｉ＝Ｃξｉであるから、等号は含まない。
【０１４４】
学習データをＳに関連するデータに限定するような解が得られるか否かを考える。前記式（数３２）は次式とされる。
【０１４５】
【数３５】
Ｌ１−ＳＶＭ（ｐ＝１）に対して、ＫＫＴ条件の２つの式（数２８）から、上限に達していないサポートベクトルｘ（ｉ∈Ｓ）に関連するスラック変数ξは０である。しかし、この式（数３５）において、スラック変数の合計は最小化される。このようにして、各拘束は必ずしも０になるわけでない。加えて、ｂに対する二次項がないから、ｂはこの公式によって決定されない。それゆえ、前記式（数３５）を解くことで、解を得ることはできない。この問題を解くために、チャペルはフーバーのロス関数を使用しており、そこでは線形ロスが二次ロスと組み合わさっている（非特許文献４参照）。しかし、この方式はＬ１−ＳＶＭに対する概略解を与えるから、主問題においてＬ１−ＳＶＭを解くものと考えていないことは明らかである。
【０１４６】
Ｌ２−ＳＶＭに対して、前記式（数３４）から、サポートベクトルｘｉ（ｉ∈Ｓ）に対応したξｉは正の値である。このとき前記式（数３２）は、ｉ∈Ｓという制約でもって、（数３５）と等しい。β’Ｓ＝（βTＳ，ｂ）Tとすると、ここで、βＳ＝｛βｉ｜ｉ∈Ｓ｝である。
【０１４７】
すると、式（数３５）は、
【数３６】
となる。ここで、ＫＳは（｜Ｓ｜＋１）×（｜Ｓ｜＋１）のマトリックスである。ｃＳは（｜Ｓ｜＋１）次元ベクトルである。
【０１４８】
すると、
【数３７】
となる。∂Ｑ／∂β’Ｓ＝０を解くと、最適解は次のようになる。
【０１４９】
【数３８】
ここで、ＫＳは正定である。もしＫＳが特異であれば、通常は小さな値が対角の各要素に追加される。しかし、これがサポートベクトルの数を増加するから、ワーキングセットからマトリックスの特異性を引き起こすデータを削除する。
【０１５０】
以下、主問題と双対問題とにおける学習ＳＶＭの比較を行う。
【０１５１】
（主問題における学習）
この主問題ＳＶＭの学習方式では、前記チャペルの方式と異なり、少ないチャンキングデータ（分割したデータ）でもって学習を開始する。そして、小さな値をＫＳの対角の各要素に追加する代わりに、コレスキー分解法によりＫＳを分解したときの関連した列と行を削除することで、ＫＳの特異性を回避する。ここでは、可変サイズのチャンキングアルゴリズムを使用する。すなわち、初期のワーキングセットに対して前記式（数３８）を解き、ワーキングセットから、ゼロスラック変数（関連するマージンが１以上である）を含むデータを削除する。ワーキングセットに、正のスラック変数（関連するマージンが１未満である）を含むデータを追加する。そして同式（数３８）を解く。そして、同じワーキングセットが得られるまで上記過程を繰り返す。チャンクサイズをｈとする。ここで、ｈは正の整数である。図５は本実施形態２に係るパターン認識方法の学習アルゴリズム（１）を示すフローチャートであって、前記図２におけるステップＳ１００を具体化するものである。
【０１５２】
ステップＳ２１：ｈ学習データをワーキングセットにセットして、次のステップＳ２２に進む。
【０１５３】
ステップＳ２２：ここでは、コレスキー分解法によりワーキングセットに対して前記式（数３８）を解く。もし対角要素が予め定められた値よりも小さければ、関連する列と行とを削除する。次のデータサンプルを用いて列と行とを書き直し、コレスキー分解することにより、β’Ｓを得る。
【０１５４】
ステップＳ２３：ワーキングセットからゼロスラック変数（すなわち、ｙｉＤ（ｘｉ）≧１を満たすｘｉである。）を含むデータを削除する。
【０１５５】
ステップＳ２４：ワーキングセットに最も違反したものから最大でｈ個のデータを追加する。すなわち最小のｙｉＤ（ｘｉ）から順に、ｙｉＤ（ｘｉ）＜１を満たすｘｉを追加する。
【０１５６】
ステップＳ２５：もし得られたワーキングセットが先に記載したものと同じであるとすると、学習を止める。その他はステップＳ２２に進む。
【０１５７】
（双対問題における学習）
主問題ＳＶＭと同様に、双対問題ＳＶＭを学習させる。この考えは、１つの変数に対してそれを解くことで、前記式（数２７）の後段に示す同等の拘束を削除し、それを同式（数２７）の前段に代入するものである。それから、問題は、正の拘束を含む最大化された問題に限定される。正の拘束を含むことを考えないサブ問題を解き、ワーキングセットから負の変数を削除する。他の過程は主問題ＳＶＭのそれと同じである。インデックスセットＳに対して前記２つの式（数２７）を解くことを考える。αＳ（ｓ∈Ｓ）に対する同式（数２７）の後段における等価制約を解くことで、次式を得る。
【０１５８】
【数３９】
この式（数３９）を前記式（数２７）の後段に代入して、次の最適化問題を得る。
【０１５９】
【数４０】
ここに、αＳ＝｛αｉ｜ｉ∈Ｓ｝、α’Ｓ＝｛αｉ｜ｉ≠ｓ，ｉ∈Ｓ｝、ｃＳは（｜Ｓ｜−１）次元ベクトルである。ＫＳは（｜Ｓ｜−１）×（｜Ｓ｜−１）の正の有限マトリックスである。
【０１６０】
すると、
【数４１】
図６は本実施形態２に係るパターン認識方法の学習アルゴリズム（２）を示すフローチャートであって、これも前記図２におけるステップＳ１００を具体化するものである。なお、図５と同様のステップは、同一番号を付すものとする。
【０１６１】
ステップＳ２１：ｈ学習データをワーキングセットにセットして、ステップＳ２２ａへ進む。
【０１６２】
ステップＳ２２ａ：ここではαＣに対してＫＳα’Ｓ＝ｃＳを解き、前記式（数３９）を用いてαＳを得る。次式よりｂを決定する。
【０１６３】
【数４２】
【０１６４】
ステップＳ２３：ワーキングセットから、ｙｉＤ（ｘｉ）＞１を満たすｘｉと同様の負の変数を含むデータを削除する。そして、ワーキングセットに最も違反したものから最大でｈ個のデータを追加する。すなわち最小のｙｉＤ（ｘｉ）から順に、ｙｉＤ（ｘｉ）＜１を満たすｘｉを追加する。
【０１６５】
ステップＳ２４：もし得られたワーキングセットが、先に記載したものと同じであると学習を止める。その他はステップＳ２２ａに進む。
【０１６６】
ステップＳ２２ａにおいて負のαＳがあるにもかかわらず、前記式（数２９）における最初の方程式は満たされている。線形方程式を解くことで、αＳが得られるからである。このようにして、いかなるｉ（∈Ｓ）が同じ値を与える。ＫＳα’Ｓ＝ｃＳを解き、後述する負の変数を削除するときに、正の制約を無視するので、上記アルゴリズムの収束性は保障されていない。
【０１６７】
双対問題ＳＶＭと主問題ＳＶＭとの差異は、次に要約するとおりである。
（１）双対問題ＳＶＭに対するマトリックスＫＳは、正定である。一方、主問題ＳＶＭに対するそれは、準正定である。式（数３７）と、式（数４１）を比較して、双対問題ＳＶＭに対するＫＳとｃＳは、主問題ＳＶＭよりも要するカーネル方程式が少なくて済む。よって、双対問題ＳＶＭはより安定、より少ない計算時間を与える。
【０１６８】
（２）主問題ＳＶＭに対して特徴空間に写像されたサポートベクトルは、標本特徴空間を張る一次独立なデータとして解釈される。このような線形カーネルに対しては、線形の主問題ＳＶＭに対するサポートベクトルの数は、多くても入力変数の数である。そして、どのデータも標本特徴空間を張る限り、サポートベクトルとなりうる。
【０１６９】
（３）プラットが開発したＳＭＯのような分解の技術に基づく従来の学習方法とは異なり、主問題・双対問題ＳＶＭとに対する学習は、単調な収束を保障しない。或いは収束しない。これは、先に記載したように、目標関数は単調であることを保障しないからである。これを避けるためには、各繰り返し計算においてＫＫＴ条件を違反するデータの数を監視して、違反数が増加する、あるいは振動する場合、変数の修正幅を制約条件を満たす範囲に制約すればよい。これにより、単調性が保証される。
【０１７０】
次いで、性能評価を行う。ここでは（表９）（そのリストは、多くの入力、クラス、学習データ、テストデータを使用している。）に示したようなベンチマーク データセットを用いて、主問題ＳＶＭのそれを含む提案した双対問題ＳＶＭの性能評価をした。同表は、五重のクロスデバリデーションによって決定されるＬ２−ＳＶＭに対するパラメータ値をも示している。例えばｄ４とγ１０は、カーネルが次元４を含む多項式カーネルと、γ＝１０を含むＲＢＦカーネルとを意味する。そして、Ｃ１０５は、マージンパラメータの値が１０５であることを意味する。すべてのＳＶＭに対して多クラスの未分類領域の解消にファジィメンバーシップ関数を使用した。そして、パーソナルコンピュータ（３ＧＨｚ，２ＧＢメモリ，ウインドウズＸＰ オペレーティングシステム）を使用して学習時間を測定した。従来例におけるように、カーネルマトリックスと等価なサイズのキャッシュメモリを用意した。
【０１７１】
【表９】
（表１０）はＵＳＰＳデータセットに対する主問題・双対問題ＳＶＭの性能に基づくチャンクサイズの効果を示す。同表において、“Ｃｈｕｎｋ”，“ＳＶｓ”，“Ｉｔｅｒａｔｉｏｎｓ”，“Ｋｅｒｎｅｌｓ”，“Ｒｅｃ．”，“Ｔｉｍｅ”は、それぞれ、チャンクサイズ、決定関数当たりのサポートベクトルの平均数、繰り返し数、カーネルのアクセス数、テスト（学習）データセットの認識率、そして学習時間を示す。ここでカーネルのアクセス数はカーネル値が必要になった回数で、カーネル値がキャッシュメモリにあるときは、キャッシュメモリの内容が読み出され、カーネル値がキャッシュメモリにないときはカーネル値を計算することを意味する。
【０１７２】
“ＳＶｓ”，“Ｉｔｅｒａｔｉｏｎｓ”，“Ｋｅｒｎｅｌｓ”，“Ｒｅｃ．”，“Ｔｉｍｅ”欄に対しては、よりよい値が双対問題と主問題との間の太字で示している。同表より、双対問題ＳＶＭに対するサポートベクトルの数は５ケースについて同じであるが、主問題ＳＶＭに対しては、チャンクサイズが増加するにつれて徐々に増加している。主問題ＳＶＭに対する繰り返し数がより小さいにもかかわらず、カーネルアクセス数はより小さく、学習時間は双対問題ＳＶＭよりも短い。これは、主問題ＳＶＭに対する繰り返し当たりの計算負荷が先に記述したように大きいことを意味する。主問題ＳＶＭに対して、たとえ対角要素に小さい値を追加したとしても結果は変化していない。
【０１７３】
【表１０】
マトリックスが特異になるケースの性能試験を行った。（表１１）は線形カーネルでＣ＝１００の場合の血球細胞のデータセットに対する結果を示す。主問題ＳＶＭに対して、主問題としての０．００００１を対角要素に追加したときの結果をも含めた。“ＳＶｓ”欄における（ ）内の数字は、ワーキングセットの学習後のサイズを示す。このようにして、例えば、５０のチャンクサイズに対して、４９７のデータ間で１５のデータのみがサポートベクトルであり、残りのデータはマトリックスの特異性ゆえに削除された。
【０１７４】
同表より、双対問題ＳＶＭの学習は、すべてのチャンクサイズに対して最も早かった。追加したものを含む主問題ＳＶＭに対する結果を比較すると、追加した主問題ＳＶＭに対する学習はより早いが、解は異なりサポートベクトルの数は、チャンクサイズの数が増加するにつれて増加した。この結果は、小さな正の値の対角要素への追加はマトリックスの特異性を回避する策としてはよくないことを明らかに示す。
【０１７５】
（表１２）はベンチマーク データセットを用いたときの主問題・双対問題ＳＶＭに対する結果をリストにしている。５０のチャンクサイズをすべてのケースにセットした。甲状腺のデータセットに対して、双対問題ＳＶＭの学習はとても遅かった。そして、主問題ＳＶＭに対して、ワーキングセットのサイズはかなり変動した。そして、学習は１０，０００回以内の繰り返し数では収束しながった。ひらがな−１３とひらがな−１５のデータセットを除き、双対問題ＳＶＭはより早く、ひらがな−５０のデータセットを除き、双対問題ＳＶＭに対するサポートベクトルの数はより小さいものであった。
【０１７６】
【表１１】
実験より、安定した収束と早い学習という点から、双対問題ＳＶＭが主問題ＳＶＭよりもよいことが明らかになった。
【０１７７】
以上説明したように、本実施形態２では、双対問題の形式によるＳＶＭ（双対問題ＳＶＭ）に対する学習方法を説明した。すなわち、初期のワーキングセットから始まって、ニュートン法による双対問題の形式で表されたサブ問題を解いた。もし関連したラグランジェ乗数が非正であるとすると、ゼロスラック変数を含むデータの場合と同様に、データを削除し、正のスラック変数を含むデータを加え、同じワーキングセットが得られるまで、サブ問題を解くことを繰り返した。
【０１７８】
マトリックスの正定性の点から、主問題ＳＶＭよりも双対問題ＳＶＭが有利であることを明らかにした。コンピュータでの実験により、双対問題ＳＶＭの学習が主問題ＳＶＭのそれよりも早くなり、通常はサポートベクトルの数はより小さいものとなったことを示している。また、主問題ＳＶＭの対角要素に小さな値を追加することは、サポートベクトルの数がより大きくなり、チャンクサイズの変化に対して異なる解を与えることをも示している。
【０１７９】
ところで、双対問題ＳＶＭを用いた場合に収束しにくいことがある。その場合には、繰り返し計算の回数が設定値を超えた段階、あるいはＫＫＴ違反数増加あるいは振動する段階で制約を満たす範囲に変数の修正量を制限することにより、確実に収束させることができる。
【０１８０】
【表１２】
【０１８１】
なお、上記実施形態１，２では、カーネルとして、ＲＢＦカーネルや多項式カーネルを用いているが、その他のカーネル（例えば線形カーネルなど。）を用いてもよい。
【符号の説明】
【０１８２】
１ パターン認識装置
２ 入力部（入力装置、入力手段に相当する。）
３ パーソナルコンピュータ（演算装置に相当する。）
３１ ＣＰＵ
３１ａ 学習部
３１ｂ 入力データ処理部（選別手段に相当する。）
３１ｂ１ プリセレクション部
３１ｂ２ ブロック追加・削除部（ブロック追加・削除手段に相当する。）
３１ｃ パターン認識部
３２ ＲＯＭ
３３ ＲＡＭ
４ 表示部
【先行技術文献】
【特許文献】
【０１８３】
【特許文献１】特開２００５−３３９１８６号公報
【非特許文献】
【０１８４】
【非特許文献１】Ｖ．Ｖａｐｎｉｋ，Ｓｔａｔｉｓｔｉｃａｌ Ｌｅａｒｎｉｎｇ Ｔｈｅｏｒｙ，Ｊｏｈｎ．Ｗｉｌｅｙ＆Ｓｏｎｓ，１９９６
【非特許文献２】Ｓ．Ａｂｅ，Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅｓ ｆｏｒ Ｐａｔｔｅｒｎ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ，Ｓｐｒｉｎｇｅｒ，Ｌｏｎｄｏｎ，２００５
【非特許文献３】Ａ．Ｗ．Ｗｈｉｔｎｅｙ，“Ａ Ｄｉｒｅｃｔ Ｍｅｔｈｏｄ ｏｆ Ｎｏｎｐａｒａｍｅｔｒｉｃ Ｍｅａｓｕｒｅｍｅｎｔ Ｓｅｌｅｃｔｉｏｎ，”ＩＥＥＥ Ｔｒａｎｓ．Ｃｏｍｐｕｔｅｒｓ，ｖｏｌ．２０，ｎｏ．９，ｐｐ．１１００−１１０３，１９７１
【非特許文献４】Ｏ．Ｃｈａｐｅｌｌｅ，Ｔｒａｉｎｉｎｇ ａ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ ｉｎ ｐｒｉｍａｌ，Ｌａｒｇｅ−Ｓｃａｌｅ Ｋｅｒｎｅｌ Ｍａｃｈｉｎｅｓ，ｐｐ．２９−５０．ＭＩＴ Ｐｒｅｓｓ，２００７
【特許請求の範囲】
【請求項１】
入力装置が、識別対象となる入力変数を入力する入力工程と、演算装置が、サポートベクトルマシンを用いて、この入力変数からパターンの識別に使用する特徴量を選別する選別工程とを備えたパターン認識方法であって、
前記選別工程は、前記演算装置が、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除工程を備えたことを特徴とするパターン認識方法。
【請求項２】
前記ブロック追加・削除工程は、前記演算装置が、前記初期の特徴量集合の認識率を閾値としておき、空集合に一時的に特徴量を１つ追加したときの該空集合の認識率を計算して、認識率の高い順に特徴量を順位付けたランキングを生成し、ランキングの上位の特徴量を前記空集合に追加したときの該空集合の認識率が前記閾値よりも大きいときに、特徴量の追加が成功したとして、該特徴量のみを前記特徴量集合に残し、その他の特徴量を該特徴量集合から削除するものであることを特徴とする請求項１記載のパターン認識方法。
【請求項３】
前記閾値は固定値であることを特徴とする請求項１又は２記載のパターン認識方法。
【請求項４】
前記閾値は前記認識率に基づいて更新可能であることを特徴とする請求項１又は２記載のパターン認識方法。
【請求項５】
前記サポートベクトルマシンとして、最小自乗サポートベクトルマシンを備えており、
前記演算装置は、この最小自乗サポートベクトルマシンで前記認識率を計算することを特徴とする請求項１〜４のいずれか１項に記載のパターン認識方法。
【請求項６】
前記サポートベクトルマシンとして、線形計画サポートベクトルマシンをも備えており、
前記選別工程は、前記演算装置が、前記ブロック追加・削除工程を実行する前に、前記初期の特徴量集合を用いて、前記線形計画サポートベクトルマシンを学習させることにより、該特徴量集合に対応する重みを計算し、この重みの大きさに基づいて特徴量を前記初期の特徴量集合から予め削除しておくプリセレクション工程を備えたことを特徴とする請求項５記載のパターン認識方法。
【請求項７】
前記演算装置が、前記ブロック追加・削除工程で、入力変数をワーキング集合と固定集合とに分けて、ワーキング集合を繰り返して解く分割法の最適化問題において途中段階では制約条件を満たさないことを許すように前記サポートベクトルマシンを学習させることを特徴とする請求項１〜４のいずれか１項に記載のパターン認識方法。
【請求項８】
前記演算装置が、前記ブロック追加・削除工程で、前記最適化問題にラグランジェ乗数を適用した双対問題を用いて前記サポートベクトルマシンを学習させることを特徴とする請求項７記載のパターン認識方法。
【請求項９】
前記演算装置は、前記ブロック追加・削除工程で、前記双対問題を用いて前記サポートベクトルマシンを学習させる際に、初期変数集合から出発して解を求め、この解の中で正となる変数を残し、正しく分離されている変数、および零または負になる変数を削除し、さらに正しく分離されていない変数、あるいはマージンが不足している変数を追加して解を求めることを、同じ解が求まるまで繰り返すことを特徴とする請求項８記載のパターン認識方法。
【請求項１０】
前記演算装置は、前記ブロック追加・削除工程で、前記繰り返し数が設定回数を超える、あるいは違反数が増加あるいは振動すると、制約を満たすように変数の修正量を制限して、前記サポートベクトルマシンを学習させることを特徴とする請求項９記載のパターン認識方法。
【請求項１１】
識別対象となる入力変数を入力するための入力手段と、サポートベクトルマシンを用いて、この入力変数からパターンの識別に使用する特徴量を選別する選別手段とを備えたパターン認識装置であって、
前記選別手段は、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除手段を備えたことを特徴とするパターン認識装置。
【請求項１２】
入力装置により入力された入力変数からパターンの識別に使用する特徴量を選別するに際し、サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、前記特徴量集合から特徴量を一度に削除するブロック追加・削除機能をコンピュータに実現させることを特徴とするパターン認識プログラム。
【請求項１】
入力装置が、識別対象となる入力変数を入力する入力工程と、演算装置が、サポートベクトルマシンを用いて、この入力変数からパターンの識別に使用する特徴量を選別する選別工程とを備えたパターン認識方法であって、
前記選別工程は、前記演算装置が、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除工程を備えたことを特徴とするパターン認識方法。
【請求項２】
前記ブロック追加・削除工程は、前記演算装置が、前記初期の特徴量集合の認識率を閾値としておき、空集合に一時的に特徴量を１つ追加したときの該空集合の認識率を計算して、認識率の高い順に特徴量を順位付けたランキングを生成し、ランキングの上位の特徴量を前記空集合に追加したときの該空集合の認識率が前記閾値よりも大きいときに、特徴量の追加が成功したとして、該特徴量のみを前記特徴量集合に残し、その他の特徴量を該特徴量集合から削除するものであることを特徴とする請求項１記載のパターン認識方法。
【請求項３】
前記閾値は固定値であることを特徴とする請求項１又は２記載のパターン認識方法。
【請求項４】
前記閾値は前記認識率に基づいて更新可能であることを特徴とする請求項１又は２記載のパターン認識方法。
【請求項５】
前記サポートベクトルマシンとして、最小自乗サポートベクトルマシンを備えており、
前記演算装置は、この最小自乗サポートベクトルマシンで前記認識率を計算することを特徴とする請求項１〜４のいずれか１項に記載のパターン認識方法。
【請求項６】
前記サポートベクトルマシンとして、線形計画サポートベクトルマシンをも備えており、
前記選別工程は、前記演算装置が、前記ブロック追加・削除工程を実行する前に、前記初期の特徴量集合を用いて、前記線形計画サポートベクトルマシンを学習させることにより、該特徴量集合に対応する重みを計算し、この重みの大きさに基づいて特徴量を前記初期の特徴量集合から予め削除しておくプリセレクション工程を備えたことを特徴とする請求項５記載のパターン認識方法。
【請求項７】
前記演算装置が、前記ブロック追加・削除工程で、入力変数をワーキング集合と固定集合とに分けて、ワーキング集合を繰り返して解く分割法の最適化問題において途中段階では制約条件を満たさないことを許すように前記サポートベクトルマシンを学習させることを特徴とする請求項１〜４のいずれか１項に記載のパターン認識方法。
【請求項８】
前記演算装置が、前記ブロック追加・削除工程で、前記最適化問題にラグランジェ乗数を適用した双対問題を用いて前記サポートベクトルマシンを学習させることを特徴とする請求項７記載のパターン認識方法。
【請求項９】
前記演算装置は、前記ブロック追加・削除工程で、前記双対問題を用いて前記サポートベクトルマシンを学習させる際に、初期変数集合から出発して解を求め、この解の中で正となる変数を残し、正しく分離されている変数、および零または負になる変数を削除し、さらに正しく分離されていない変数、あるいはマージンが不足している変数を追加して解を求めることを、同じ解が求まるまで繰り返すことを特徴とする請求項８記載のパターン認識方法。
【請求項１０】
前記演算装置は、前記ブロック追加・削除工程で、前記繰り返し数が設定回数を超える、あるいは違反数が増加あるいは振動すると、制約を満たすように変数の修正量を制限して、前記サポートベクトルマシンを学習させることを特徴とする請求項９記載のパターン認識方法。
【請求項１１】
識別対象となる入力変数を入力するための入力手段と、サポートベクトルマシンを用いて、この入力変数からパターンの識別に使用する特徴量を選別する選別手段とを備えたパターン認識装置であって、
前記選別手段は、前記サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、該特徴量集合から特徴量を一度に削除するブロック追加・削除手段を備えたことを特徴とするパターン認識装置。
【請求項１２】
入力装置により入力された入力変数からパターンの識別に使用する特徴量を選別するに際し、サポートベクトルマシンを用いて、前記入力変数からなる初期の特徴量集合における認識率を計算し、この計算された認識率に基づいて、前記特徴量集合から特徴量を一度に削除するブロック追加・削除機能をコンピュータに実現させることを特徴とするパターン認識プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−４３９８８（Ｐ２０１１−４３９８８Ａ）
【公開日】平成２３年３月３日（２０１１．３．３）
【国際特許分類】
【出願番号】特願２００９−１９１７３９（Ｐ２００９−１９１７３９）
【出願日】平成２１年８月２１日（２００９．８．２１）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 「ブロック追加・削除による特徴量の選択」の卒業論文とそのパワーポイントで発表
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ウィンドウズ
【出願人】（５０４１５０４５０）国立大学法人神戸大学 (421)
【Ｆターム（参考）】
【公開日】平成２３年３月３日（２０１１．３．３）
【国際特許分類】
【出願日】平成２１年８月２１日（２００９．８．２１）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 「ブロック追加・削除による特徴量の選択」の卒業論文とそのパワーポイントで発表
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ウィンドウズ
【出願人】（５０４１５０４５０）国立大学法人神戸大学 (421)
【Ｆターム（参考）】
[ Back to top ]