(57)【要約】貨幣のアイテムを分類するための関数を導く方法。該方法は、複数の貨幣アイテムの特徴に対応するトレーニング・データ・ベクトルを処理することを含み、複数の支持ベクトルを含む支持ベクトル機構分類関数を導く。
2005530271.tif 000002
【特許請求の範囲】
【請求項１】
貨幣のアイテムを分類するための関数を導く方法であって、複数の貨幣アイテムの特徴に対応するトレーニング・データ・ベクトルを処理し、複数の支持ベクトルを含む支持ベクトル機構分類関数を導くことを含む方法。
【請求項２】
トレーニング・データ・ベクトルの部分集合によって支持ベクトル機構分類関数を表すことを含み、部分集合は支持ベクトルと異なるか、または前記部分集合のサイズは支持ベクトルの集合のサイズより小さい方法。
【請求項３】
支持ベクトル分類関数は、
【数１】
2005530271.tif 000045
の形をとる請求項１および２のいずれかに記載の方法。
【請求項４】
支持ベクトル機構分類関数は、入力データの空間に対応する第１の空間の第２の空間への写像に対応し、その第２の空間における画像が第２の空間におけるトレーニング・データの画像を表すトレーニング・データ・ベクトルの部分集合を決定するカーネル関数を含み、支持ベクトル機構分類関数は、前記部分集合によって表される請求項１乃至３のいずれかに記載の方法。
【請求項５】
部分集合は、トレーニング・データ集合の各要素の画像を、部分集合の要素の画像の直線的組合せとして概算的に表すことができるものである請求項４に記載の方法。
【請求項６】
部分集合は、概算の測定値が所定の条件を満たすものである請求項５に記載の方法。
【請求項７】
部分集合を選択する工程は、
（ａ）一時的部分集合を導くこと、
（ｂ）一時的部分集合の画像によって、データ集合の残りの要素の画像の概算値の正確さを表す適合関数の値を計算すること、
（ｃ）他の一時的部分集合を導き、工程（ｂ）を繰り返すこと、および
（ｄ）一時的部分集合毎に適合関数の値を比較し、適合関数の値が最も正確な概算値を示す一時的部分集合を選択することを含む請求項４乃至６のいずれか１項に記載の方法。
【請求項８】
工程（ａ）から（ｄ）を繰り返して、サイズの大きさの順に並んだ一時的部分集合の列を形成する請求項７に記載の方法。
【請求項９】
適合関数が、所定の条件、例えば、適合関数の値が所定の値以下である、または所定の値以上である、かつ／または部分集合が所定のサイズを表すという条件を満たすまで、かつ／または先述のＫＳ，Ｓが数字的に反転不可能になるまでといったような所定の条件が満たされるまで、工程（ａ）から（ｄ）を繰り返す請求項７または８に記載の方法。
【請求項１０】
適合関数は、カーネル関数を用いる請求項８乃至１２のいずれか１項に記載の方法。
【請求項１１】
支持ベクトル分類関数は、
【数２】
2005530271.tif 000046
の形をとる請求項４乃至１０のいずれか１項に記載の方法。
【請求項１２】
少なくとも１つの貨幣センサおよび複数の貨幣アイテムから複数の測定値を導き、測定値からトレーニング・データ集合を形成することを含む請求項１乃至１１のいずれかに記載の方法。
【請求項１３】
データ集合の個々の要素は、感知項目の複数の特性に対応する複数の測定値を含む請求項１乃至１２のいずれか１項に記載の方法。
【請求項１４】
貨幣センサは書類センサである請求項１２または１３に記載の方法。
【請求項１５】
書類センサは銀行券センサである請求項１４に記載の方法。
【請求項１６】
貨幣センサは硬貨センサである請求項１２または１３に記載の方法。
【請求項１７】
カーネル関数は、ガウス、多項式、Ｓ字形、双曲線タンジェントまたはスプライン・カーネルである請求項４乃至１６のいずれか１項に記載の方法。
【請求項１８】
請求項１乃至１７のいずれかに記載の方法によって導かれる分類関数。
【請求項１９】
少なくともカーネル関数を表す定数、重み、および支持ベクトルの集合、またはカーネル関数に対応する写像の画像によるデータを表す支持ベクトルの部分集合を含む支持ベクトル機構の形の分類関数。
【請求項２０】
以下のいずれかの形をとる請求項１８または１９に記載の分類関数。
【数３】
2005530271.tif 000047
【請求項２１】
請求項１８乃至２０のいずれか１項に記載の分類関数を記憶することを含む、貨幣評価装置を適応させる方法。
【請求項２２】
請求項１８乃至２０のいずれか１項に記載の分類関数を用いて、貨幣アイテムを分類する少なくとも１つの貨幣センサから貨幣アイテムの少なくとも１つの測定値を導くことを含む、貨幣選別器で貨幣アイテムを分類する方法。
【請求項２３】
貨幣アイテムを感知して、貨幣アイテムの特性を表す測定値を生成する手段と、
請求項１８乃至２０のいずれか１項に記載の関数を記憶する手段と、
測定値および関数を用いて貨幣アイテムを評価する手段とを備えた貨幣評価装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、貨幣評価装置、および貨幣評価装置を適応させ、動作させるための方法に関する。本明細書において、貨幣および貨幣アイテムという用語は、硬貨、代用硬貨等、銀行券および紙幣、小切手や商品券や債券のような他の有価シートを含み、また本物のアイテムと、金属片や座金のような偽物との両方を含むものとする。
【背景技術】
【０００２】
貨幣アイテムの種類を判断し、本物の貨幣アイテムと偽物の貨幣アイテムとを区別するための多くの知られた方法が存在する。一般に、硬貨の厚さ、硬貨の材質、または銀行券の模様のような貨幣アイテムの特定の特性を示す信号を生成する磁気または光センサのような１つまたは複数のセンサによって貨幣アイテムを感知する。次いで、それらの測定信号と、知られている貨幣アイテムを示す記憶基準データとを比較し、比較の結果に応じて、測定された貨幣アイテムを、例えば、特定の種類の本物の貨幣アイテム、知られている偽物または単に知られていないものに分類する。
【０００３】
例えば、知られている貨幣アイテムに対する基準データを、上限および下限よりなる「ウィンドウ」の集合の形で記憶することが知られている。特定のアイテムに対する測定信号の各々が、特定の種類に対する対応するウィンドウの各々に当てはまる場合は、それは特定の種類に属するものとして分類される。この手法は、一般的に、線形の受容境界として知られる、測定された特性に対応する軸を有する空間内の境界を用いるものと見なすことができる。
【０００４】
通常、特定の種類の貨幣アイテムの個体群の分布は非線形で、その場合、線形の受容境界は、異なる種類を区別するのに十分に正確でないこともある。他の知られている方法は、特定の種類の貨幣アイテムに対応する楕円形の境界を示す基準データを記憶する。上述の手法と同様に、測定された特性がそれらの楕円形の境界の中にあるか、外にあるかに応じて、測定された貨幣アイテムを分類する。当該方法は、例えば、ＧＢ２２５４９４９Ａに記載されている。
【０００５】
【非特許文献１】ＧＢ２２５４９４９Ａ
【特許文献１】同時係属出願ＥＰ００３１１２５３．９
【非特許文献２】「A tutorial on support vector machines for pattern recognition」、C.J.C. Burges、 Data mining and knowledge discovery 1998、121〜167頁
【特許文献２】ＷＯ００／３３２６２
【発明の開示】
【発明が解決しようとする課題】
【０００６】
多くの場合、異なる種類の貨幣アイテムの間の境界は複雑で、線形または楕円形の境界によって十分正確に表すことができない。非線形境界を検出するための知られている方法は、貨幣評価装置としては理想的な結果をもたらすことができない。明らかに、例えば、潜在的な収益の損失が生じる自動販売機において貨幣のアイテムを正確に分類、評価できることが特に重要である。
【課題を解決するための手段】
【０００７】
本発明は、特に貨幣のアイテムを分類するための分類関数を導き、使用する代替的な方法を提供する。
【０００８】
本発明は、その要素が第１の空間における点に対応するデータ集合を用いて分類関数を導き、第１の空間の第２の空間への写像に対応するカーネル関数を選択し、第２の空間における写像による部分集合の画像が第２の空間における写像によるデータ集合の画像を表すように、データ集合の部分集合を導き、特徴ベクトルの前記部分集合によって表現される支持ベクトル機構分類関数の形の分類関数を導く方法を提供する。
【０００９】
あるいは、本発明は、第１の空間における点に対応するトレーニング・データを処理することによって分類関数を導く方法であって、前記トレーニング・データを用いて支持ベクトル機構分類関数を導くことを含み、第１の空間から第２の空間への写像に対応するカーネル関数を選択することをさらに含み、第２の空間における部分集合の画像が第２の空間におけるトレーニング・データ集合の画像を表すトレーニング・データ集合の部分集合を選択し、部分集合によって支持ベクトル機構分類関数を表現することを含む方法。
【００１０】
例えば、該方法は、少なくとも１つの貨幣センサからの複数の測定値を導き、その要素が前記第１の空間における点に対応するデータ集合を測定値から形成することを含むことができる。
【００１１】
本発明は、また、対応する分類関数、分類方法および選別機（分類装置）を提供する。
【００１２】
好ましくは、本発明の態様は、貨幣評価装置のような装置の製造、適応または動作に使用する関数を導くのに用いられる。
【００１３】
本発明は、特に、貨幣アイテムに対しての使用、分類関数の誘導、貨幣アイテムの分類、特定または評価（方法および装置）を目的とする。そのような場合、例えば、貨幣アイテムの１つまたは複数の特性の測定値、または貨幣アイテムを感知するための１つまたは複数のセンサからデータを導くことができる。
【００１４】
本発明は、また、貨幣アイテムを分類するための支持ベクトル機構の使用法を提供する。
【００１５】
本発明の他の態様は、添付の請求項に記載されている。
【発明を実施するための最良の形態】
【００１６】
添付の図面を参照しながら、本発明の実施形態を説明する。
【００１７】
好ましい実施形態によれば、本発明は、貨幣アイテムおよび貨幣センサから導かれたデータを解析して、評価装置についての分類関数または受容境界を導くためにカーネル関数を使用する。より具体的には、データは、硬貨および銀行券のような貨幣アイテムから導かれた測定データで、データは、硬貨の厚さ、材質、重量、幅、銀行券の模様のような硬貨アイテムの特性を表す。
【００１８】
明確かつ容易に理解できるように、比較的短銃なデータ分布を参照しながら、本発明を支える理論の全体的な説明から始める。次いで、貨幣アイテムの分類および評価に関する実施形態について、より詳細に本発明を説明する。
【００１９】
本発明の一態様は、カーネル関数手法の脈絡において、データ集合を表す部分集合をデータ集合から選択するためのカーネル関数の使用に関する。より具体的には、部分集合は、カーネル関数ｋに対応する写像φの画像空間におけるデータ集合を表す。この本発明の態様は、カーネル関数を用いたデータ解析を、より少ないデータを用いて実施することを可能にし、解析の複雑さを緩和し、評価装置についての分類関数を導くときの演算労力、およびそれに伴う費用を低減する。
【００２０】
本発明の他の態様は、以下に説明するように、支持ベクトル機構の使用に関する。
【００２１】
以下の説明において、ベクトル量が文脈から暗示される場合を除いて、ベクトル量を示すために下線が用いられ、ベクトルという用語は、一般に、スカラー量を含むことを意図するものである（すなわち、一次元ベクトル）。
【００２２】
まず、ベクトルの集合の代表的な部分集合の選択について説明する。
【００２３】
ＸをサイズＭのベクトルの集合とする。
Ｘ＝｛ｘ１，ｘ２，・・・，ｘＭ｝
【００２４】
非線形写像関数φを介して、入力空間Ｘからヒルベルト空間に任意のベクトルを写像するとする。
φ：Ｘ→Ｆ
ｘ→φ（ｘ）
【００２５】
カーネル関数は、マーサーの定理に従うスカラー価関数である。
【００２６】
カーネル関数は、入力空間データのみを用いて、Ｆにおけるドット積を計算する直接的な方法を提供する。式を簡単にするために、φｉ＝φ（ｘｉ）を使用する。次いで、カーネル関数ｋに対して、以下のような対応する写像φが存在することを証明できる。
【数１】
2005530271.tif 000003
【００２７】
カーネル関数の例を以下に示す。
【数２】
2005530271.tif 000004
このプロパティの意義は、アルゴリズムをドット積のみで表現できる場合は、φ（ｘ）を知らなくても、入力空間Ｘからのデータのみを用いて、Ｆにおけるデータの画像を解析できることである。
【００２８】
ガウス形のようないくつかのカーネルを用いると、Ｆの次元数は無限になる。ＸからＦへの変換は非線形的で、Ｆの次元数は、しばしばＸよりはるかに大きい。
【００２９】
ここで、ＳをサイズＬのＸの部分集合とする。
Ｓ＝｛ｘｓ，１，ｘｓ２，・・・，ｘｓ，Ｌ｝
【００３０】
ＦにおけるＸの要素の画像を近似または復元できる部分集合Ｓが存在すると仮定する。換言すれば、Ｓは、Ｆ空間におけるＸを表すベースのような働きをする。したがって、
【数３】
2005530271.tif 000005
【数４】
2005530271.tif 000006
は、ＦにおけるＳの画像を使用したφ（ｘｉ）の概算値である）
【００３１】
簡素化するために、以下の式を用いる。
φｉ＝φ（ｘｉ）
φｓ，ｉ＝φ（ｘｓ，ｉ）
【００３２】
次に、式（１）を以下のように表すことができる。
【数５】
2005530271.tif 000007
【００３３】
ただし、
ΦＳ＝｜φｓ，１，φｓ，２，・・・，φｓ，Ｌ｜（ＦにおけるＳの画像から形成される行列）。
【００３４】
ａｉ＝［ａｉ１，ａｉ２，・・・，ａｉＬ］ｔ（ＦにおけるＳの画像を使用してφｉを表すベクトル）
【００３５】
Ｘのｉ番目の要素の画像φｉと集合Ｓを使用したその再現φ＾ｉとの相対的な差δｉを最小限にするａｉの値を見いだしたい。
【数６】
2005530271.tif 000008
【００３６】
δｉを最小化すると、以下の式が導かれる。
【数７】
2005530271.tif 000009
【００３７】
ＦにおけるＳの画像の要素が直線的に独立している場合は、（ΦＳｔΦＳ）−１が存在する。換言すると、ΦＳのランクはＬである。
【００３８】
式（３）および（４）を用いて、以下の式を導くことができる。
【数８】
2005530271.tif 000010
【００３９】
βｉが、ベクトルφｉと（φｉ＾）の間の角度であれば、これは、｜βｉ｜も最小にしたことを意味する。
【００４０】
ここで、カーネル式を導入すると、以下のようになる。
ｋ（ｘｐ，ｘｑ）＝φｔｐ・φｑ
【００４１】
次に、式（５）を以下のように表すことができる。
【数９】
2005530271.tif 000011
ただし、
【数１０】
2005530271.tif 000012
（ＦにおけるＳの画像のドット積のＬ×Ｌ平方行列）
【数１１】
2005530271.tif 000013
（Ｆにおける画像Ｓとｘｉとのドット積のベクトル）
【００４２】
知られているように、また上述したように、カーネル関数ｋは、Ｆにおけるドット積をＸによって表している。
【００４３】
以下の式を最大にすることによってδｉを最小にすることができる。
【数１２】
2005530271.tif 000014
Ｊｉは、要素ｘｉに対する再現の質を推定する局部適合関数と見なすことができる。
【００４４】
発見法を用いて好適な集合Ｓを構築する。一例において、これは、Ｓの画像がＦにおけるＸの画像全体を以下に厳密に表現するかを示す全体適合関数ＪＳを用いて実行される。全体適合関数の例を以下に示す。
【数１３】
2005530271.tif 000015
【００４５】
以下に、Ｓを構成する方法をより詳細に示す。
まず、最良の全体適合結果を与えるＸの要素を選択する。換言すれば、本例において、式（８）を用いて、最大の全体適合値ＪＳを有する要素を選択する。あるいは、第１の要素を無作為、または測定によって選択して、Ｓの第１の要素ｘＳ，１を形成することができる。
【００４６】
次に、Ｘの要素を選択し、Ｓの一時的メンバーとし、それを基にＸの他の要素すべてに対してＪＳの値を計算する。次いで、Ｓの一時的メンバーをＸの他のメンバーと交換し、再びＪＳを計算する。Ｘの残りの要素のすべてに対してそれらの工程を繰り返す。全体適合関数が最大になるＸの要素をＳの永久的な第２のメンバーとして選択する。
【００４７】
適合関数のより大きい値を探す毎に、先のパラグラフに記載した工程を繰り返して、Ｓの次のメンバーを見いだす。適合関数が所定の値を超えたときにその手順を停止する。あるいは、Ｓが所定数の要素を有するとき、またはＳがＦにおけるＸの画像に対する完全なベースとなったときに、手順を停止する。ＫＳ，Ｓ行列のランクをチェックして、それを反転させることが可能であることを確認する。ＫＳ，Ｓが反転不可能になったときにその手順を停止することも可能である。
【００４８】
他のより複雑な発見法を用いることもできる。また、代替的な適合関数を用いることもできる。例えば、全体適合関数は、局部適合関数の平均値、中間値または最小値、あるいは他の手段を用いることができる。あるいは、式（６）を用いて全体または局部適合関数を「誤差」に基づくものとすることができ、その場合は、Ｓの最適化は、全体誤差の低減によって示される。しかし、いずれの場合も、式（７）に示されるようなカーネル式が用いられる。
【００４９】
上記の技術は「前方」選択であるが、「後方」選択を含むもののような他の技術を用いてもよい。他の例として、所定サイズＬのすべての部分集合を考慮し、最良の適合を選択することが可能である。一般的に、任意の好適な適合ベースの選択アルゴリズムを用いることができる。
【００５０】
このように、写像oによるＦにおけるＸの全要素の画像を、ＦにおけるＳの要素の画像の直線的組合せとして概算で表すことができる場合は、Ｘの部分集合Ｓを見いだすことができる。
【００５１】
選択された集合Ｓは一意的ではないが、Ｆにおけるデータの構造を維持する所定サイズＬの集合を与える。多項式のようないくつかのカーネル式については、選択された数個のベクトルだけでＪＳの最適値が得られることを証明できる。
【００５２】
Ｘにおけるすべてのサンプルまたはトレーニング・データをＦにおけるＳの画像上に投影させることができる。
【００５３】
サンプルｘｉの変換は、ドット積投影によって与えられる。
（９）ｚｉ＝ΦＳｔφｉ
ｚｉは線形変換によって得られることに留意されたい。他の変換、特に、より多くの計算を必要とし、変換データに適用される多くのアルゴリズムに不必要な直角投影ｚｉ＝（ΦＳｔΦＳ）−１ΦＳｔΦｉも考えられる。
【００５４】
その内容が参照により本明細書に組み込まれている本願の同時係属出願ＥＰ００３１１２５３．９に記載されているカーネルＰＣＡおよびカーネルＧＤＡのような、データ解析のための様々なカーネル関数に必要とされる計算を低減するために、集合Ｓを用いることができる。ＥＰ００３１１２５３．９は、様々なデータ分布およびカーネル関数に対する上記技術に従って選択されたデータ部分集合の例を示している。
【００５５】
次の支持ベクトル機構（以後ＳＶＭと称する）を説明した後で、Ｓを支持ベクトル機構と併用する方法について述べる。
【００５６】
支持ベクトル機構の使用は、データの分類および分別のための知られている技術である。基礎となる技術についての十分な説明は、教科書、および「A tutorial on support vector machines for pattern recognition」、C.J.C. Burges、 Data mining and knowledge discovery 1998、121〜167頁のような学術文献に見いだすことができる。基本的な特徴を以下に要約する。
【００５７】
支持ベクトル機構（以後ＳＶＭと称する）は、トレーニング・データを使用し、構造リスク最小化（ＳＲＭ）誘導スキームを具体化する。一般的に、ＳＶＭは、図１に示すように、一定の差によって２つのクラスのデータを分別する超平面を含む２クラス線形選別器である。
【００５８】
図１は、分離可能なデータに対するＳＶＭの基本例を示す図である。
【００５９】
式（１０）は、ｗが超平面（ＨＰ）に直角のベクトルで、ｂが傾きで、ｘがサンプルベクトルである識別関数を与える。
（１０）  ｇ（ｘ）＝ｗＴｘ＋ｂ
クラスタ＃１に属するサンプルはレベル＋１を有するが、クラスタ＃２ではレベルは−１である。
【００６０】
トレーニング・サンプルの集合およびそれらのラベルは、以下の式で定義づけられる。
【数１４】
2005530271.tif 000016
【００６１】
次いで、データが分別可能であると想定し、最適なＨＰ（ｗ０，ｂ０）に対して以下の条件が成立する。
【数１５】
2005530271.tif 000017
【００６２】
関係式（１１）を以下のようによりコンパクトな形で表すことができる。
（１２）ｄｉ（ｗＴｘｉ＋ｂ）≧＋１    ｉ＝１、２、３、．．．、Ｎの場合
第１または第２の関係式（１１）が等式である特別なサンプルを支持ベクトル（ＳＶ）と呼ぶ。
【００６３】
Ｎ個の要素を有するトレーニング・データの集合、および一般関係式（１２）が与えられると、目標は、集団を分ける差を最大にするｗおよびｂの値を見いだすことである。
【００６４】
これを以下に示す。
ｘＳをｄＳに伴う支持ベクトルとすると、そのクラス（＋／−１）は以下のようになる。
【数１６】
2005530271.tif 000018
【００６５】
式（１３）によって、ＳＶからＨＰまでのユークリッド距離｜｜ｒ｜｜を計算することができる。
【数１７】
2005530271.tif 000019
【００６６】
したがって、差は以下のようになる。
【数１８】
2005530271.tif 000020
関係式（１２）の条件に従って、差を最大にするとｗの長さが最小になる。
【００６７】
この問題は、二次最適化（または二次計画法ＱＰ）として知られる。それは、費用関数がｗについての二次式で、条件は一次式である場合の非線形計画法である。その問題を以下のように表すことができる。
【００６８】
所与のトレーニング集合
【数１９】
2005530271.tif 000021
に対して、費用関数を最小にする重みベクトルｗおよび傾きｂを求める。
【数２０】
2005530271.tif 000022
【００６９】
ここでは、係数１／２は、説明のために示されたものである（導関数）。その問題は、一次的問題と呼ばれる。それを双対問題に関連づけることができ、この問題は、入力サンプルのドット積だけで解を表す方法を提供する。ラグランジェ乗数の方法を用いて一次的問題を解くことができる。Ｊをラグランジェ関数と呼ぶ。
【数２１】
2005530271.tif 000023
【００７０】
αｉは、非負ラグランジェ乗数である。Ｊについて、ｗおよびｂが最小になると、αｉが最大になる（鞍点）ことを証明することができる。微分を行い、結果をゼロに設定すると、以下の式が得られる。
【数２２】
2005530271.tif 000024
【００７１】
解ベクトルｗ０は、Ｎ個のトレーニング・サンプルを含む展開式で定められる。
【００７２】
しかし、まだαｉ係数を求めなければならず、これは、クーン・タッカー条件［７］を用いて行うことができる。
（２０）αｉ［ｉ（ｗ０Ｔｘｉ＋ｂ）−］０    ｉ＝１，２，３，．．．，Ｎの場合
単に式１１を満たすラグランジェ関数は、非ゼロ値をとることができる。ここで、双対定理を用いて、それらの係数を求めることができる。式（１８）および（１９）により、式（１７）を書き換えることができる。
【００７３】
【数２３】
2005530271.tif 000025
これもＱＰ問題である。
【００７４】
所与のトレーニング集合
【数２４】
2005530271.tif 000026
に対して、費用関数を最大にするラグランジェ乗数
【数２５】
2005530271.tif 000027
を求める。
【００７５】
【数２６】
2005530271.tif 000028
これは以下の式に従う。
【数２７】
2005530271.tif 000029
【００７６】
双対問題は、トレーニング・サンプルのみを用いる。費用関数は、サンプルのドット積にのみ依存する。これは、ＳＶＭを非線形問題に一般化することを可能にする極めて重要な特性である。ラグランジェ係数が求められると、以下のような最適な重みベクトルを表すことができる。
【数２８】
2005530271.tif 000030
【００７７】
非ゼロラグランジェ係数に関連づけられたｘｉはＳＶである。概して、ＳＶはＮより少ない。したがって、展開式１３はすべての項を必要としない。任意のＳＶおよび式（１２）を用いて最適な傾きｂを求めることができる。
【数２９】
2005530271.tif 000031
【００７８】
次に、識別関数は以下のようになる。
ｇ（ｘ）＝  ｗ０Ｔｘｉ＋ｂ０、または
【数３０】
2005530271.tif 000032
ここで、ＳＶＳは支持ベクトルの集合。
【００７９】
上式は、データが分離可能な場合である。ＳＶＭは、データが重複する場合も対応できる。解析の詳細は、上述のＢｕｒｇｅｓの論文のような該当文献に見いだすことができ、簡単明解にするために、ここでは繰り返して説明しない。
ＳＶＭの上記例は、線形分類を示す。
【００８０】
非線形ＳＶＭを構築するためには、Ｓの選択について上述したようにカーネル関数を用いる。
【００８１】
非線形問題に対処するために、カーネル関数と線形ＳＶＭを併せる。式（２１）は、サンプルのドット積のみを用いる。したがって、それをカーネルによって書き換えることができ、特徴空間Ｆへのデータの間接的な写像を用いて非線形ＳＶＭとする。
【００８２】
次いで、以下のように、その最適なＨＰ（線形分離）に着目して、ＱＰ法をＦに直接適用する。
【００８３】
所与のトレーニング集合
【数３１】
2005530271.tif 000033
に対して、費用関数を最大にするラグランジェ乗数
【数３２】
2005530271.tif 000034
を求める。
【００８４】
【数３３】
2005530271.tif 000035
これは以下の式に従う。
【数３４】
2005530271.tif 000036
【００８５】
重みベクトルｗを直接表すことができなくても、Ｆにおける任意のサンプルでそのドット積を計算することができる。したがって、以下のような識別関数を得ることができる（ｂ０が存在すれば、通常通り式（２３）を用いてそれを推定する）。
【数３５】
2005530271.tif 000037
【００８６】
展開式（２６）は、非ゼロラグランジェ乗数に限定されることに留意されたい。したがって、それは、全ＳＶ集合（ＳＶＳ）のみに対して定義され、通常は学習集合（Ｎ）より少ない項を用いる。
【数３６】
2005530271.tif 000038
【００８７】
ＳＶＳの基数Ｎが概してＮより小さくても、まだ極めて大きく、それは、コスト、メモリおよび演算力の観点で重要である。
【００８８】
本発明の基本的な特徴は、ＳＶＭと選択された部分集合Ｓとの併用である。以下の説明において、Ｓの要素を特徴ベクトル（ＦＶ）と記載し、Ｓの選択を特徴ベクトル選択（ＦＶＳ）と記載する。
【００８９】
支持ベクトルはトレーニング・データに属するため、Ｓの画像を用いてＦで表すことができるということを念頭において、以下のように、Ｆで処理し、Ｓを用い、式（９）に従ってトレーニング・データを投影して、式（２７）を修正することができる。Ｆで処理すると、ＳＶＭは線形ＳＶＭになる。
【００９０】
最初に、式（２７）をＦ、あるいは換言すればデータの画像およびＦにおける支持ベクトルで表す。
【００９１】
【数３７】
2005530271.tif 000039
ここで、ＳＶＳｚは、ＦにおけるＳＶＳの各々の画像を示す。
【００９２】
ラグランジェ乗数ｄｉおよびｚｉは、直接的な最適重みベクトルｗｚ０を定める。したがって、式（２８）を任意のサンプルｘのＦＶへの投影ｚのみによって表すことができ、以下のようになる。
【数３８】
2005530271.tif 000040
【００９３】
その式を式（６）に従って用いると、以下のようになる。
【数３９】
2005530271.tif 000041
【００９４】
識別式（３０）は、しばしば支持ベクトルの数よりはるかに少ないＬ個の項（Ｓのサイズ）しか含まないことに留意すべきである。したがって、識別関数の計算に関わる演算および処理が、著しく低減され、より迅速になる。
【００９５】
図２および３は、それぞれ、入力空間に正規分布を有する２つのデータ集団を示す図である。それらの図において、十字形は一方のデータ集団のデータを示し、点は他方のデータ集団のデータを示し、点または十字形の周囲の円は、サンプル間の特徴ベクトルを示す。
【００９６】
わずかに異なる基準を用いて、ＦＶＳとＳＶＭを組み合わせる上記の技術をデータに適用した。より具体的には、図２に示される場合では、ＪＳ＝０．８の適合値を設定し、１２のＦＶを選択した。図３に示される場合では、適合値をＪＳ＝０．９９９に設定し、３８のＦＶを選択した。
【００９７】
いずれの場合も、ＳＶの数は５２である。換言すれば、標準的な非線形ＳＶＭ手法を用いると、識別関数は、５２項の展開式を必要とする。ＦＶＳを用いると、わずか１２のＦＶを用いて、識別関数を十分に表すことができる。
【００９８】
黒の実線は、入力空間Ｘ（ＦにおけるＨＰの画像）における識別関数（ｇ（ｘ）＝０の場合）の軌跡である。
【００９９】
様々なデータに対する実験によって、標準的な非線形ＳＶＭを用いた識別性能を上記のＳＶＭおよびＦＶＳ技術と比較した。それらの実験は、ＳＶＭおよびＦＶＳを用いた識別は、非線形ＳＶＭを用いる場合と同等か、またはより良好であることを証明していた。
【０１００】
以下の表１は、学習機を試験するのに広く使用されているデータベースからのガウス・カーネルおよびデータを用いた実生活における性能のいくつかの例を示している。データは以下の書庫から検索した。http://ida.first.gmd.de/〜raetsch/data/benchmarks.htm
【０１０１】
【表１】
2005530271.tif 000042
【０１０２】
Ｆにおけるドット積を表し、本発明に用いることができる、マーセルの定理（ＷＯ００／３３２６２を参照）を満たす多くのカーネル関数が存在する。いくつかのさらなる例を以下に示す。
【０１０３】
ｘおよびｙがスカラーであるスプライン・カーネルは以下のように表される。
【数４０】
2005530271.tif 000043
【０１０４】
ｓ字形カーネルｋ（ｘ，ｙ）＝
【数４１】
2005530271.tif 000044
【０１０５】
三次多項式カーネル：ｋ（ｘ，ｙ）＝（ｘｔ・ｙ）ｄ（ｄ＝３，Ｃ＝０）
先述の例は、良好な一般化性能を示し、それは、それらが本来のデータ集合Ｘに存在しなかった新しいベクトルに十分対処することを意味している。
【０１０６】
この目標を達成するためには、カーネル、そのパラメータ（σなど）および誤差レベルを慎重に選択する必要がある。
【０１０７】
どれが、解析によるデータに対して最良の結果を与えるかを確認するための試験を行う実験および試行錯誤によって、適切なカーネルを選択することができる。あるいは、経験、およびデータの分布の調査によって選択することもできる。
【０１０８】
例えば、多項式型分布を有するデータについては、多項式カーネルは良好な結果を与えることができる。ガウス・カーネルにおけるσのような様々なパラメータ、および適合関数に対する所定のレベルを慎重に選択する必要もある。ここでも、実験、経験およびデータの形が指針になる。
【０１０９】
本発明の好ましい実施形態によれば、上述の手法の一般的な原理が、貨幣アイテムおよび貨幣評価装置に適用される。還元すれば、それらの手法は、貨幣アイテムの特性を表す測定値を導くセンサから導かれるデータに適用される。例えば、図２を参照すると、図２の軸は、２つの異なる種類の硬貨、または１つの本物と１つの偽物についての硬貨の厚さおよび硬貨の材質を表すものと見なすことが可能であるが、実際は、示される分布は、必ずしも実生活分布を表すことができない。銀行券の場合のような、多くの場合は、銀行券の測定値を組み合わせることにより形成される特徴ベクトルの次元は、３よりはるかに大きいため、図示することができない。
【０１１０】
本発明の実施形態は、図４の概略図形式で示されるような硬貨評価装置に関する。
【０１１１】
図４において、ボックス１は、入口２、サンプル３を供給するための硬貨入口および硬貨輸送経路（不図示）の形の輸送システム、およびサンプルの物理的量を測定するためのセンサ・システム（不図示）を含む測定システムを示す。測定システム１は、データ・バス５によって処理システム４に接続される。処理システム４は、データ・バス７によって選別器６に接続される。選別器６の出力は、データ出力バス９によって利用システム８に接続される。利用システム８は、本例では自動販売機であるが、例えば両替機であってもよい。
【０１１２】
測定システム１は、投入された硬貨３の特徴を測定する。測定した特徴を、各要素が処理システム４による測定された特徴に対応するｎ個の要素を有する特徴ベクトルに集約する。本例では、センサ・システムは、知られている技術（例えばＧＢ２２５４９４９Ａを参照）を用いて、投入された硬貨の材質、厚さおよび直径を表す値を測定し、それらの値は、対応する特徴ベクトルの３つの要素である。簡単に言えば、各センサは、自己発振回路に１つまたは複数の硬貨を含む。直径および厚さセンサの場合は、投入された硬貨の接近によって引き起こされる各コイルのインダクタンスの変化が、発振器の周波数を変化させることによって、硬貨のそれぞれの特性のデジタル表現を導くことができる。導電率センサの場合は、投入された硬貨の接近によって引き起こされるコイルのＱの変化が、コイルの電圧を変化させることによって、硬貨の導電率のデジタル出力表現を導くことができる。各コイルの構造、位置および方位、ならびにコイルに印加される電圧の周波数は、コイルが、導電率、直径および厚さの特性の特定の１つに著しく左右される出力を提供するように調整されるが、各測定値は、他の硬貨特性にある程度影響されることが理解されるであろう。
【０１１３】
勿論、光センサ、磁気センサ、および当該技術分野でよく知られている他の種類のセンサを使用して、貨幣のアイテムを表す多くの異なる特徴を測定し、特徴ベクトルの要素として利用することができる。例えば、銀行券の場合は、測定される特徴としては、例えば、銀行券の幅、銀行券の長さ、および銀行券の全体または一部に対する反射または透過光の強度を挙げることができる。例として、光センサを使用して、Ｎ本のラインに沿って銀行券を走査するように測定システムを構成することができる。各走査ラインは、順次走査されるＬ個の個別的な領域を含む。各領域では、Ｍ個の異なる特徴の測定が存在する。より具体的には、各領域毎に、赤色光、緑色光および赤外線の反射強度の測定が行われる。したがって、銀行券に対する全測定値の数は、Ｌ×Ｍ×Ｎである。これらの測定値は、それぞれの検体に対する特徴ベクトルの成分を形成するため、特徴ベクトルはＬ×Ｍ×Ｎ個の成分を有することになる。あるいは、それらの測定値を異なる方法で処理して、測定された検体を表す特徴ベクトルを得ることができる。例えば、各測定領域に対する局部特徴ベクトルを、各局部特徴ベクトルがＭ個の成分を有するように、その領域に対するＭ個の測定値で構成することができる。次いで、それらの局部ベクトルを銀行券の領域に対して合計して、全検体を表すＭ次元の特徴ベクトルを得ることができる。
【０１１４】
次いで、特徴ベクトルを選別器６に入力する。選別器６は、特徴ベクトル、および識別関数を含む所定の分類基準を用いて、サンプルが所定のクラスのいずれか１つの属するかどうかを判断する。サンプルが、受容できる種類に属することが明確になると、それを受け入れ、対応する値を承認する。サンプルが、知られている偽物グループの属することが明確になると、それを拒絶する。
【０１１５】
本例では、該システムは、２種類の硬貨および１つの偽物を分類するためのシステムである。
【０１１６】
識別関数の導出について以下に説明する。
【０１１７】
貨幣の個体群分布を下記のように解析する。
【０１１８】
最初に、対象となる貨幣の各々のサンプル、および知られている偽物の各々のサンプルを測定し、対応する特徴ベクトルを形成する。対象となる評価装置のセンサ・システムを使用してサンプルを形成することができるが、本実施形態では、販売され、現場に設置される異なる評価装置のセンサ・システムにおけるばらつきおよび製造公差を考慮して、複数の対応するセンサ・システムからサンプルを導く。サンプルからの特徴ベクトルは、例えばｎ次元の撒布図表（ｎは測定特徴の数）にプロットされると、概ね集団を成す。次いで、これらの測定サンプルを解析し、分離関数を導くのに利用する。本例では、貨幣毎の５０のサンプル、および５０の偽物のサンプルを使用し、センサ・システムの１０のサンプルに対して測定する。得られた集団データを解析し、上述の手法を用いて、分類関数または識別関数を導くのに利用する。より具体的には、サンプルまたはトレーニング・データを処理し、集合ＳまたはＦＶＳ、およびｗｚ０，ｊおよびｂ０の値を導いて、式（３０）における識別関数ｇ（ｘ）を生成するのに利用する。ここで、閾値をゼロに設定する。次いで、分類関数を特定の評価装置の処理システム４のメモリに記憶する。
【０１１９】
次いで、未知の種類の硬貨に対する分類を以下のように実施する。硬貨を評価装置に投入する。投入した硬貨を感知し、その材質、厚さおよび直径を表す測定値を得る。次いで、処理システムは、以下の工程を実施する。特徴ベクトルｘを測定値から導く。式（３０）を用いて、ｇ（ｘ）の値を計算する。本例では、ｇ（ｘ）＞０であれば、硬貨は本物と分類され、ｇ（ｘ）＜０であれば、硬貨は偽物と分類される。
【０１２０】
この手法によれば、評価装置は、高精度で分類作業を行うのに極めて小量のデータしか記憶する必要がない（例えば式（３０）で必要とされるデータ、すなわちＳ、ｋ、ｗｚ０およびｂ０および閾値）。これにより、コストおよび演算労力が削減され、分類速度が高められる。
【０１２１】
ＳＶＭは、本質的に二クラス評価装置である。複数種の貨幣を評価するための貨幣評価装置では、いくつかのＳＶＭの組合せが必要とされる場合がある。例えば、各貨幣について、貨幣の本物のアイテムと偽物のアイテムの２つの集団を分類するのにＳＶＭを用いることができ、あるいは二進木構造においてＳＶＭを組み合わせることができる。ＳＶＭを他の試験と組み合わせることができる。例えば、予備試験では、貨幣のアイテムの種類を特定するための様々な知られた技術の１つを用い、続いてＳＶＭを用いた好適な評価技術により、貨幣アイテムの種類を判断することができる。
【０１２２】
上記の例では、識別閾値をゼロに設定したが、＋／−０．５のような他の閾値を用いてもよい。
【０１２３】
例えばマイクロプロセッサを使用して、最初のデータ解析に対するサンプル値の解析、および識別関数の導出を行うことができる。同様に、選別器６はマイクロプロセッサであってもよい。
【０１２４】
上記の実施形態の方法は、銀行券または他のアイテム、あるいは、実際に、測定値を生成するためにアイテム・センサにより感知される他の種類のアイテムの分類に等しく適用可能である。
【０１２５】
記載の実施形態では、分類関数を導くために対象となる貨幣のサンプルが使用される。代用貨幣またはワッシャのような他のアイテムを使用することもできる。
【０１２６】
上記の技術は、他のデータに対しても使用することができ、貨幣アイテムから導かれる分類データに限定されない。
【０１２７】
上述の詳細な説明は、分離可能なデータに関するものであるが、本発明はそのような構成に限定されない。例えば、トレーニング・データが重複する「ソフト」な差に対する当該技術分野で知られている技術を用いて、本発明に変更を加えることができる。
【図面の簡単な説明】
【０１２８】
【図１】支持ベクトル機構を示すグラフである。
【図２】データ分布、および本発明の実施形態に従って導かれた識別関数を示すグラフである。
【図３】他の識別関数を示すグラフである。
【図１】
2005530271.tif 000048
【図２】
2005530271.tif 000049
【図３】
2005530271.tif 000050
【図４】
2005530271.tif 000051
【国際調査報告】
2005530271.tif 000052
2005530271.tif 000053
2005530271.tif 000054