図面 (/)

技術 情報処理装置、情報処理方法、およびプログラム

出願人 ソニー株式会社
発明者 小林由幸
出願日 2007年10月18日 (13年2ヶ月経過) 出願番号 2007-270931
公開日 2009年5月7日 (11年7ヶ月経過) 公開番号 2009-098999
状態 特許登録済
技術分野 学習型計算機 検索装置
主要キーワード 不偏分散 類似度計算式 線形結合係数 交差処理 最終世代 仕様テーブル 自動構築 現世代
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2009年5月7日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (14)

課題

任意の種類の複数のデータの類似度をその特徴量に基づいて判定できるアルゴリズムを自動的に構築する。

解決手段

類似度判定機構築システム10は、特徴量抽出式リストを生成、更新する特徴量抽出式リスト生成部11、生成された特徴量抽出式教師データ代入して特徴量を計算する特徴量計算部12、特徴量計算部12による計算結果を教師データに基づいて各特徴量抽出式評価値を計算する評価値計算部13、および、最終的に更新された特徴量抽出式リストに基づいて類似度計算式を生成する類似度計算式生成部14から構成される。なお、特徴量抽出式リスト生成部11は、作成した現世代の特徴量抽出式リストを遺伝的アルゴリズムに従って更新することにより、次世代の特徴量抽出式リストを生成する。本発明は、例えば、音楽データや画像データの類似度を判定する機能を動的に構築する必要のある機器に適用することができる。

概要

背景

従来、画像データや音楽データなどの類似度を判定する手法が数多く提案されている(例えば、特許文献1および2参照)。

例えば、複数の音楽データの類似度を判定する場合には、特徴量として複数の音楽データそれぞれからリズムテンポなどを抽出し、抽出したリズムどうし、あるいはテンポどうしを比較する方法が用いられたりする。

また例えば、複数の画像データの類似度を判定する場合には、特徴量として画素ヒストグラムなどを抽出し、抽出したヒストグラムどうしを比較する方法が用いられたりする。

すなわち、複数のデータの類似度を判定する従来の手法では、類似度の判定対象とする複数のデータそれぞれから特徴量を抽出し、抽出した特徴量どうしを比較することが一般的である。

特開2006−285615号公報
特開2005−77865号公報

概要

任意の種類の複数のデータの類似度をその特徴量に基づいて判定できるアルゴリズムを自動的に構築する。類似度判定機構築システム10は、特徴量抽出式リストを生成、更新する特徴量抽出式リスト生成部11、生成された特徴量抽出式教師データ代入して特徴量を計算する特徴量計算部12、特徴量計算部12による計算結果を教師データに基づいて各特徴量抽出式評価値を計算する評価値計算部13、および、最終的に更新された特徴量抽出式リストに基づいて類似度計算式を生成する類似度計算式生成部14から構成される。なお、特徴量抽出式リスト生成部11は、作成した現世代の特徴量抽出式リストを遺伝的アルゴリズムに従って更新することにより、次世代の特徴量抽出式リストを生成する。本発明は、例えば、音楽データや画像データの類似度を判定する機能を動的に構築する必要のある機器に適用することができる。

目的

効果

実績

技術文献被引用数
0件
牽制数
1件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

データ対類似度を判定するための類似度判定アルゴリズムを生成する情報処理装置において、複数の演算子から成る特徴量抽出式を複数含む特徴量抽出式リストを、前世代の前記特徴量抽出式の評価値に基づいて前世代の前記特徴量抽出式リストを更新することにより生成する特徴量抽出式リスト生成手段と、前記特徴量抽出式リストに含まれる各特徴量抽出式に、教師データとして与えられた第1および第2のデータを入力して、前記第1および第2のデータのそれぞれに対応する特徴量を計算する手段と、前記特徴量抽出式リストに含まれる各特徴量抽出式の前記評価値を、計算された前記特徴量と、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を用いて計算する評価値計算手段と、計算された前記特徴量を用いて、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を計算するための類似度計算式推定する類似度計算式推定手段とを含むことを特徴とする情報処理装置。

請求項2

前記特徴量抽出式リスト生成手段は、第1世代の前記特徴量抽出式リストに含まれる複数の前記特徴量抽出式をランダムに生成し、第2世代以降の前記特徴量抽出式リストを、前世代の前記特徴量抽出式リストに含まれる複数の特徴量抽出式を遺伝子とみなし、前記特徴量抽出式の評価値に基づく、選択処理交差処理、または突然変異処理の少なくとも1つを含む遺伝的アルゴリズムを用いて前世代の前記特徴量抽出式リストを更新することにより生成することを特徴とする請求項1に記載の情報処理装置。

請求項3

前記評価値計算手段は、前記特徴量抽出式リストに含まれる各特徴量抽出式の前記評価値として、計算された前記第1のデータに対応する特徴量と第2のデータに対応する特徴量との距離を用いて、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を推定した場合の精度を計算することを特徴とする請求項1に記載の情報処理装置。

請求項4

前記類似度計算式推定手段は、前記最終世代の特徴量抽出式リストに含まれる複数の特徴量抽出式を使用または不使用に分類した使用テーブルを複数含む使用テーブル群を生成し、各使用テーブルによって使用に分類された特徴量抽出式に、教師データとして与えられた第1および第2のデータを入力して得られた前記第1のデータに対応する特徴量と前記第2のデータに対応する特徴量との距離から、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を計算するための類似度計算式を回帰または判別によって推定するとともに、推定結果の情報量基準を前記使用テーブルの評価値として算出し、前記使用テーブルを遺伝子とみなした遺伝的アルゴリズムを用いて前記使用テーブル群を更新することを特徴とする請求項1に記載の情報処理装置。

請求項5

データ対の類似度を判定するための類似度判定アルゴリズムを生成する情報処理装置の情報処理方法において、複数の演算子から成る特徴量抽出式を複数含む第1世代の特徴量抽出式リストをランダムに生成し、前記特徴量抽出式リストに含まれる各特徴量抽出式に、教師データとして与えられた第1および第2のデータを入力して、前記第1および第2のデータのそれぞれに対応する特徴量を計算し、計算された前記特徴量を用いて、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を計算するための類似度計算式を推定し、前記特徴量抽出式リストに含まれる各特徴量抽出式の前記評価値を、計算された前記特徴量と、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を用いて計算し、第2世代以降の前記特徴量抽出式リストを、前世代の前記特徴量抽出式の評価値に基づいて前世代の前記特徴量抽出式リストを更新することにより生成するステップを含むことを特徴とする情報処理方法。

請求項6

データ対の類似度を判定するための類似度判定アルゴリズムを生成する情報処理装置の制御用プログラムであって、複数の演算子から成る特徴量抽出式を複数含む第1世代の特徴量抽出式リストをランダムに生成し、前記特徴量抽出式リストに含まれる各特徴量抽出式に、教師データとして与えられた第1および第2のデータを入力して、前記第1および第2のデータのそれぞれに対応する特徴量を計算し、計算された前記特徴量を用いて、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を計算するための類似度計算式を推定し、前記特徴量抽出式リストに含まれる各特徴量抽出式の前記評価値を、計算された前記特徴量と、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を用いて計算し、第2世代以降の前記特徴量抽出式リストを、前世代の前記特徴量抽出式の評価値に基づいて前世代の前記特徴量抽出式リストを更新することにより生成するステップを含む処理を情報処理装置のコンピュータに実行させることを特徴とするプログラム。

技術分野

0001

本発明は、情報処理装置情報処理方法、およびプログラムに関し、特に、データ対類似度を判定するアルゴリズムを自動的に構築できるようにした情報処理装置、情報処理方法、およびプログラムに関する。

背景技術

0002

従来、画像データや音楽データなどの類似度を判定する手法が数多く提案されている(例えば、特許文献1および2参照)。

0003

例えば、複数の音楽データの類似度を判定する場合には、特徴量として複数の音楽データそれぞれからリズムテンポなどを抽出し、抽出したリズムどうし、あるいはテンポどうしを比較する方法が用いられたりする。

0004

また例えば、複数の画像データの類似度を判定する場合には、特徴量として画素ヒストグラムなどを抽出し、抽出したヒストグラムどうしを比較する方法が用いられたりする。

0005

すなわち、複数のデータの類似度を判定する従来の手法では、類似度の判定対象とする複数のデータそれぞれから特徴量を抽出し、抽出した特徴量どうしを比較することが一般的である。

0006

特開2006−285615号公報
特開2005−77865号公報

発明が解決しようとする課題

0007

ただし、類似度の判定対象とするデータから抽出する特徴量については、人が設計しなければならない。このため、ユーザの手元類似度判定アルゴリズムを動的に構築することはできなかった。また、類似度判定アルゴリズムの構築には多くの時間と労力を必要としていた

0008

また、多くの場合類似度判定のために特定の特徴量が有効に働くデータの種類は限られているため、抽出する特徴量を予め決定した場合、類似度の判定対象とするデータの種類が音楽データなら音楽データに、画像データなら画像データに制限されてしまう。また、類似度の判定は設計時に人が決定した特徴量で表現できる範囲に限られ、将来にわたる新しいタイプのデータの出現や、新たな視点での類似度判定に対応できない可能性がある。

0009

上述したように、データ対の類似度を、人が設計した特徴量に基づいて判定する手法は従来から存在する。しかしながら、音楽データ、画像データなどあらゆる種類のデータからどのような情報を特徴量として抽出するかについて自動的に決定し、データ対の類似度を判定するための類似度判定アルゴリズムを自動的に構築する手法は提案されていない。

0010

本発明はこのような状況に鑑みてなされたものであり、類似度の判定対象とするデータから、どのような情報を特徴量として抽出するかについても自動的に決定することを含め、任意の種類のデータ対の類似度を、その特徴量に基づいて判定できるアルゴリズムを自動構築できるようにするものである。

課題を解決するための手段

0011

本発明の一側面である情報処理装置は、データ対の類似度を判定するための類似度判定アルゴリズムを生成する情報処理装置において、複数の演算子から成る特徴量抽出式を複数含む特徴量抽出式リストを、前世代の前記特徴量抽出式の評価値に基づいて前世代の前記特徴量抽出式リストを更新することにより生成する特徴量抽出式リスト生成手段と、前記特徴量抽出式リストに含まれる各特徴量抽出式に、教師データとして与えられた第1および第2のデータを入力して、前記第1および第2のデータのそれぞれに対応する特徴量を計算する手段と、前記特徴量抽出式リストに含まれる各特徴量抽出式の前記評価値を、計算された前記特徴量と、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を用いて計算する評価値計算手段と、計算された前記特徴量を用いて、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を計算するための類似度計算式推定する類似度計算式推定手段とを含むことを特徴とする。

0012

前記特徴量抽出式リスト生成手段は、第1世代の前記特徴量抽出式リストに含まれる複数の前記特徴量抽出式をランダムに生成し、第2世代以降の前記特徴量抽出式リストを、前世代の前記特徴量抽出式リストに含まれる複数の特徴量抽出式を遺伝子とみなし、前記特徴量抽出式の評価値に基づく、選択処理交差処理、または突然変異処理の少なくとも1つを含む遺伝的アルゴリズムを用いて前世代の前記特徴量抽出式リストを更新することにより生成するようにすることができる。

0013

前記評価値計算手段は、前記特徴量抽出式リストに含まれる各特徴量抽出式の前記評価値として、計算された前記第1のデータに対応する特徴量と第2のデータに対応する特徴量との距離を用いて、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を推定した場合の精度を計算するようにすることができる。

0014

前記類似度計算式推定手段は、前記最終世代の特徴量抽出式リストに含まれる複数の特徴量抽出式を使用または不使用に分類した使用テーブルを複数含む使用テーブル群を生成し、各使用テーブルによって使用に分類された特徴量抽出式に、教師データとして与えられた第1および第2のデータを入力して得られた前記第1のデータに対応する特徴量と前記第2のデータに対応する特徴量との距離から、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を計算するための類似度計算式を回帰または判別によって推定するとともに、推定結果の情報量基準を前記使用テーブルの評価値として算出し、前記使用テーブルを遺伝子とみなした遺伝的アルゴリズムを用いて前記使用テーブル群を更新するようにすることができる。

0015

本発明の一側面である情報処理方法は、データ対の類似度を判定するための類似度判定アルゴリズムを生成する情報処理装置の情報処理方法において、複数の演算子から成る特徴量抽出式を複数含む第1世代の特徴量抽出式リストをランダムに生成し、前記特徴量抽出式リストに含まれる各特徴量抽出式に、教師データとして与えられた第1および第2のデータを入力して、前記第1および第2のデータのそれぞれに対応する特徴量を計算し、計算された前記特徴量を用いて、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を計算するための類似度計算式を推定し、前記特徴量抽出式リストに含まれる各特徴量抽出式の前記評価値を、計算された前記特徴量と、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を用いて計算し、第2世代以降の前記特徴量抽出式リストを、前世代の前記特徴量抽出式の評価値に基づいて前世代の前記特徴量抽出式リストを更新することにより生成するステップを含むことを特徴とする。

0016

本発明の一側面であるプログラムは、データ対の類似度を判定するための類似度判定アルゴリズムを生成する情報処理装置の制御用のプログラムであって、複数の演算子から成る特徴量抽出式を複数含む第1世代の特徴量抽出式リストをランダムに生成し、前記特徴量抽出式リストに含まれる各特徴量抽出式に、教師データとして与えられた第1および第2のデータを入力して、前記第1および第2のデータのそれぞれに対応する特徴量を計算し、計算された前記特徴量を用いて、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を計算するための類似度計算式を推定し、前記特徴量抽出式リストに含まれる各特徴量抽出式の前記評価値を、計算された前記特徴量と、教師データとして与えられた前記第1のデータと前記第2のデータとの類似度を用いて計算し、第2世代以降の前記特徴量抽出式リストを、前世代の前記特徴量抽出式の評価値に基づいて前世代の前記特徴量抽出式リストを更新することにより生成するステップを含む処理を情報処理装置のコンピュータに実行させることを特徴とする。

0017

本発明の一側面においては、複数の演算子から成る特徴量抽出式を複数含む第1世代の特徴量抽出式リストがランダムに生成され、特徴量抽出式リストに含まれる各特徴量抽出式に、教師データとして与えられた第1および第2のデータが入力されて、第1および第2のデータのそれぞれに対応する特徴量が計算される。また、計算された特徴量を用いて、教師データとして与えられた第1のデータと第2のデータとの類似度を計算するための類似度計算式が推定される。さらに、特徴量抽出式リストに含まれる各特徴量抽出式の評価値が、計算された特徴量と、教師データとして与えられた第1のデータと第2のデータとの類似度を用いて計算される。そして、第2世代以降の前記特徴量抽出式リストが、前世代の前記特徴量抽出式の評価値に基づいて前世代の特徴量抽出式リストを更新することにより生成される。

発明の効果

0018

本発明の一側面によれば、任意の種類のデータ対の類似度を判定するアルゴリズムを自動構築することができる。

0019

また、本発明の一側面によれば、類似度の判定対象とするデータから、どのような情報を特徴量として抽出するかについても自動的に決定することが可能となる。

発明を実施するための最良の形態

0020

以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。

0021

本発明を適用した類似度判定機構築システム10(図2)は、予め類似度が与えられている2つの実データから成る複数の教師データを用いた学習に基づいて類似度算出機を生成するものである。生成された類似度算出機は、図1に示すような、類似度の比較対象とする複数のデータ(図1の場合、比較データC1と比較データC2)を入力として当該複数のデータの類似度を出力する類似度判定装置1に適用される。

0022

比較データC1およびC2は、多次元のデータであればよく、その種類は任意である。ただし、教師データと比較データC1およびC2とは、同じ種類のデータである必要がある。例えば、時間の次元チャンネルの次元を有する音楽データ、X次元とY次元と画素の次元を有する画像データ、画像データに時間の次元を加えた動画像データなどを比較データC1およびC2とすることができる。

0023

類似度判定装置1から出力される類似度は、類似の程度に応じて0.0乃至1.0の範囲の値とされ、全く類似していない場合には0.0とされ、完全に同一である場合には1.0とされる。

0024

図2は、本発明を適用した類似度判定機構築システムの構成例を示している。この類似度判定機構築システム10は、複数の特徴量抽出式からなる特徴量抽出式リストを生成、更新する特徴量抽出式リスト生成部11、生成された特徴量抽出式に教師データを代入して特徴量を計算する特徴量計算部12、特徴量計算部12による計算結果を教師データに基づいて各特徴量抽出式の評価値を計算する評価値計算部13、および、最終的に更新された特徴量抽出式リストに基づいて類似度計算式を生成する類似度計算式生成部14から構成される。

0025

特徴量抽出式リスト生成部11は、入力データの特徴量を演算する特徴量抽出式を生成し、複数の特徴量抽出式から成る特徴量抽出式リストを特徴量計算部12に出力する。

0026

図3A乃至図3Dは、特徴量抽出式リスト生成部11によって生成される特徴量抽出式の例を示している。

0027

特徴量抽出式には、その左端の入力データには、比較データC1およびC2の種類が記述され、入力データの右側に1種類以上のオペレータ(演算子)が演算される順序に従って記述される。各オペレータには、適宜、処理対称軸パラメータが含まれる。

0028

オペレータの種類としては、平均値(Mean)、高速フーリエ変換FFT)、標準偏差(StDev)、出現率(Ratio)、ローパスフィルタ(LPF)、ハイパスフィルタ(HPF)、絶対値(ABS)、微分(Differential)、最大値(MaxIndex)、不偏分散(UVariance)、ダウンサンプリング(DownSampling)などを挙げることができる。なお、決定されたオペレータによっては処理対称軸が固定されていることがあるので、その場合、パラメータに固定されている処理対称軸を採用する。また、パラメータを必要とするオペレータが決定された場合、パラメータもランダムまたは予め設定されている値に決定する。

0029

例えば、図3Aに示された特徴量抽出式の場合、12TonesMが入力データであり、32#Differential,32#MaxIndex,16#LPF_1;O.861,16#UVarianceそれぞれがオペレータである。また、各オペレータ中の32#,16#などは処理対称軸を示している。

0030

ここで、12TonesMはモノラルPCM(pulse coded modulation sound source)波形データであり、32#は周波数軸音程軸、16#は時間軸を示している。オペレータ中の0.861はローパスフィルタ処理におけるパラメータであり、例えば透過させる周波数閾値を示している。

0031

なお、第1の世代の特徴量抽出式リストを構成する各特徴量抽出式のオペレータの数と種類はランダムに決定されるが、特徴量抽出式を生成する際の制約として、図4に示すように、複数のオペレータに対応する演算が順次実行されるにつれて、演算結果の保有次元数が順次減少し、特徴量抽出式の最終的な演算結果がスカラになるか、あるいはその次元数が所定の小さい値(例えば、1,2など)となるようになされている。また、特徴量抽出式リストを構成する各特徴量抽出式の入力データを比較データC1およびC2と一致させる必要がある。

0032

以下、特徴量抽出式リスト生成部11によって生成される特徴量抽出式リストは、図5に示すように、m本の特徴量抽出式f1乃至fmによって構成されているものとする。特徴量抽出式f1乃至fmの入力データであるWavMはPCM波形データであり、保有次元は時間軸のみである。

0033

図2に戻る。また、特徴量抽出式リスト生成部11は、作成した現世代の特徴量抽出式リストを遺伝的アルゴリズム(GA:genetic algorism)に従って更新することにより、次世代の特徴量抽出式リストを生成する。

0034

ここで、遺伝的アルゴリズムとは、現世代の遺伝子から、選択処理、交差処理、突然変異処理、およびランダム生成処理により、次世代の遺伝子を生成するアルゴリズムを指す。具体的には、特徴量抽出式リストを構成する複数の各特徴量抽出式を遺伝子とみなし、現世代の特徴量抽出式リストを構成する複数の特徴量抽出式の評価値に応じて選択処理、交差処理、突然変異処理、およびランダム生成処理を行い、次世代の特徴量抽出式リストを生成する。

0035

すなわち、図6に示すように、選択処理では、現世代の特徴量抽出式リストを構成する複数の特徴量抽出式のうち、評価値の高い特徴量抽出式を選択して次世代の特徴量抽出式リストに含める。交差処理では、現世代の特徴量抽出式リストを構成する複数の特徴量抽出式のうち、評価値の高い複数の特徴量抽出式を交差させて(組み合わせて)特徴量抽出式を生成し、次世代の特徴量抽出式リストに含める。

0036

突然変異処理では、現世代の特徴量抽出式リストを構成する複数の特徴量抽出式のうち、評価値の高い特徴量抽出式を部分的に突然変異させて(変更して)特徴量抽出式を生成し、次世代の特徴量抽出式リストに含める。ランダム生成処理では、新たな特徴量抽出式をランダムに生成して次世代の特徴量抽出式リストに含める。

0037

図2に戻る。特徴量計算部12は、特徴量抽出式リスト生成部11によって生成された特徴量抽出式リストを構成する特徴量抽出式に、外部から供給される教師データを代入して教師データの特徴量を算出する。

0038

ここで、特徴量計算部12に供給される教師データについて図7を参照して説明する。特徴量計算部12には、複数(図6の場合、L個)の教師データT1乃至TLが供給される。各教師データTi(i=1,2,・・・,L)には、比較データC1およびC2と同じ種類のデータ組ATiおよびBTi、並びにデータATiとデータBTiとの類似度が含まれている。

0039

なお、データATiとデータBTiとの類似度は、例えば、データ組ATiおよびBTiとを実際に比較して得られた値(例えば、複数の人に比較させて得られた値の平均値など)であり、類似の程度に応じて0.0乃至1.0の範囲の値とされ、全く類似していない場合には0.0とされ、完全に同一である場合には1.0とされている。

0040

したがって、特徴量計算部12では、L個の教師データTiに含まれるデータ組ATiおよびBTiそれぞれをm本の特徴量抽出式fj(j=1,2,・・・,m)に代入して演算することにより、(L×2×m)個の特徴量が算出される。以下、算出された(L×2×M)個の特徴量を、図8に示すとおりとする。

0041

すなわち、例えば、教師データT1に含まれるデータ組AT1およびBT1それぞれが特徴量抽出式f1に代入されて、特徴量f1[AT1]=0.563725と特徴量f1[BT1]=0.42116が算出されたとする。また、例えば、教師データT1に含まれるデータ組AT1およびBT1それぞれが特徴量抽出式f2に代入されて、特徴量f2[AT1]=0.431047と特徴量f2[BT1]=0.790596が算出されたとする。

0042

さらに、特徴量計算部12は、教師データTiに含まれるデータ組ATiおよびBTiを同じ特徴量抽出式fjに代入して得られた特徴量fj[ATi]と特徴量fj[BTi]とのユークリッド距離(以下、教師データTiの特徴量抽出式fjにおける距離と称する)を算出する。

0043

先に算出された(L×2×m)個の特徴量が図8に示されたとおりである場合、図9に示すように、(L×m)個のユークリッド距離が算出される。

0044

すなわち、例えば、教師データT1の特徴量抽出式f1における距離として0.142565が算出される。また例えば、教師データT1の特徴量抽出式f2における距離として0.359549が算出される。なお、教師データにT1に含まれるデータAT1とデータBT1の類似度0.170257は、予め教師データT1に含まれて供給されている値である。

0045

図2に戻る。評価値計算部13は、教師データTiの特徴量抽出式f1における距離から、教師データTiとして与えられている類似度をどの程度類推できるかを示す値として、Pearsonの相関係数を計算し、この相関係数を特徴量抽出式f1の評価値とする。

0046

例えば、図9に示されたように、教師データTiの特徴量抽出式f1における距離が0.142565、0.104266,0.868273,0.101298,・・・,0.322262であり、教師データTiとして与えられている類似度が0.170257,0.397595,0.632679,0.247863,・・・,0.6628である場合、教師データTiの特徴量抽出式f1における距離と類似度とのPearsonの相関係数は0.71と計算されるので、特徴量抽出式f1の評価値は0.71とされる。

0047

同様にして、特徴量抽出式f2乃至fmの評価値も算出される。

0048

図2に戻る。類似度計算式生成部14は、特徴量抽出式リスト生成部11によって最終的に更新された、すなわち、最終世代の特徴量抽出式リストに基づいて類似度計算式を推定する。

0049

具体的には、教師データTiのデータ組ATiおよびBTiをそれぞれ特徴量抽出式fjに代入して得られる特徴量fj[ATi]と特徴量fj[BTi]との距離と、教師データTiに含まれるデータATiとデータBTiの類似度Siを利用した線形回帰により、次式の示す類似度計算式の線形結合係数b1乃至bmを推定する。
Si=b1(f1[ATi]-f1[BTi])2+b2(f2[ATi]-f2[BTi])2+・・・+bm(fm[ATi]-fm[BTi])2

0050

なお、類似度計算式の推定に際しては、最終世代の特徴量抽出式リストを構成する全ての特徴量抽出式f1乃至fmを用いてもよいし、特徴量抽出式f1乃至fmのうちの一部を用いるようにしてもよい。

0051

類似度計算式の推定に特徴量抽出式f1乃至fmのうちの一部を用いる場合、図10に示すように、特徴量抽出式f1乃至fmのうち、どの特徴量抽出式を用いるかを示す使用テーブルTBk(k=1,2,・・・,p)(丸印○が使用、バツ印×不使用を示す)をランダムに生成する。以下、生成した複数の使用テーブルTBkを使用テーブル群と称する。

0052

そして、各テーブルTBkに対応し、特徴量抽出式f1乃至fmのうちの一部を用いて、上述した類似度計算式を推定し、推定結果をAICなどの情報量基準を評価値として各使用テーブルTBkを評価する。

0053

さらに、各使用テーブルTBkを遺伝子とみなし、使用テーブル群を遺伝的アルゴリズムにより、各使用テーブルTBkのうちの最も良い評価のものの評価が上昇しなくなるまで更新する。そして、最終的な使用テーブルTBkのうち、最も良い評価の(AICの値が最小となった)使用テーブルTBkに基づいて推定された類似度計算式を最終的な類似度計算式として後段に出力する。

0054

以上のように構成される類似度判定機構築システム10の動作について、図11フローチャートを参照して説明する。

0055

ステップS1において、特徴量抽出式リスト生成部11は、第1世代の特徴量抽出式リストを構成するm本の特徴量抽出式をランダムに生成し、m本の特徴量抽出式から成る特徴量抽出式リストを特徴量計算部12に供給する。

0056

ステップS2において、特徴量計算部12は、特徴量抽出式リスト生成部11から供給された特徴量抽出式リストを構成する各特徴量抽出式fjに、外部から供給される教師データTiに含まれるデータATiおよびBTiをそれぞれ代入して、図8に示されたように、(L×2×m)個の特徴量を算出する。

0057

ステップS3において、特徴量計算部12は、教師データTiの特徴量抽出式fjにおける距離を算出し、図9に示されたような(L×m)個のユークリッド距離を評価値計算部13に供給する。

0058

ステップS4において、評価値計算部13は、教師データTiの特徴量抽出式f1における距離から、教師データTiとして与えられている類似度をどの程度類推できるかを示す値として、Pearsonの相関係数を計算し、この相関係数を特徴量抽出式f1の評価値とする。同様にして、特徴量抽出式f2乃至fmの評価値も算出し、算出した特徴量抽出式f1乃至fmの評価値を特徴量抽出式リスト生成部11に出力する。

0059

ステップS5において、特徴量抽出式リスト生成部11は、特徴量抽出式リストを更新するか否かを判定する。ここでは、評価値計算部13によって算出された現世代の特徴量抽出式リストを構成する特徴量抽出式f1乃至fmの評価値が所定の条件を満たしていない場合には更新すると判定され、所定の条件を満たしていない場合には更新しないと判定される。

0060

ここで、所定の条件は、例えば、現世代の特徴量抽出式リストを構成する特徴量抽出式f1乃至fmのうち、評価値が所定の閾値を越えるものが存在するなどとすることができる。

0061

ステップS5において、現世代の特徴量抽出式リストを更新すると判定された場合、処理はステップS6に進められる。ステップS6において、特徴量抽出式リスト生成部11は、現世代の特徴量抽出式リストを遺伝的アルゴリズムに従って更新することにより、次世代の特徴量抽出式リストを生成して特徴量計算部12に供給する。

0062

具体的には、遺伝的アルゴリズムの選択処理として、現世代の特徴量抽出式リストを構成する複数の特徴量抽出式のうち、評価値の高いms本の特徴量抽出式を選択して次世代の特徴量抽出式リストに含める。また、遺伝的アルゴリズムの交差処理として、現世代の特徴量抽出式リストを構成する複数の特徴量抽出式のうち、評価値の高いものほど選択され易いように重み付けをして2本の特徴量抽出式を選択し、選択した2本の特徴量抽出式を交差させる(組み合わせる)ことにより、mx本の特徴量抽出式を生成し、次世代の特徴量抽出式リストに含める。

0063

さらに、遺伝的アルゴリズムの突然変異処理として、現世代の特徴量抽出式リストを構成する複数の特徴量抽出式のうち、評価値の高いものほど選択され易いように重み付けをして1本の特徴量抽出式を選択し、選択した1本の特徴量抽出式を部分的に突然変異させる(変更する)ことにより、mm本の特徴量抽出式を生成し、次世代の特徴量抽出式リストに含める。さらにまた、遺伝的アルゴリズムのランダム生成処理として、新たにmr(=m−ms−mx−mm)本の特徴量抽出式をランダムに生成して次世代の特徴量抽出式リストに含める。

0064

以上のようにして次世代の特徴量抽出式リストが生成され、特徴量計算部12に供給された後、処理はステップS2に戻り、ステップS2乃至S6の処理が繰り返される。そして、ステップS5において、現世代の特徴量抽出式リストを更新しないと判定された場合、処理はステップS7に進められる。

0065

ステップS7において、特徴量抽出式リスト生成部11は、現世代の特徴量抽出式リスト、すなわち、最終世代の特徴量抽出式リストを類似度計算式生成部14に供給する。

0066

ステップS8において、類似度計算式生成部14は、特徴量抽出式リスト生成部11から供給された最終世代の特徴量抽出式リストに基づいて類似度計算式を推定する。

0067

ステップS8の処理について、図12のフローチャートを参照して詳述する。

0068

ステップS21において、類似度計算式生成部14は、図10に示されたように、最終世代の特徴量抽出式を構成する特徴量抽出式f1乃至fmのうち、どの特徴量抽出式を用いるかを示す使用テーブルTBk(k=1,2,・・・,p)からなる使用テーブル群をランダムに生成する。

0069

ステップS22において、類似度計算式生成部14は、各テーブルTBkに対応し、特徴量抽出式f1乃至fmのうちの一部を用いて、上述した類似度計算式を推定する。そして、ステップS23において、類似度計算式生成部14は、推定結果をAICなどの情報量基準を評価値として各使用テーブルTBkを評価する。

0070

ステップS24において、類似度計算式生成部14は、使用テーブル群を更新するか否かを判定する。ここでは、例えば、現世代の使用テーブル群を構成する使用テーブルTBkのうち、最も良い評価のものの評価が過去数世代前から上昇しなった場合には更新しないと判定され、現世代の使用テーブル群を構成する使用テーブルTBkのうち、最も良い評価のものの評価が世代を重ねる度に上昇している場合には更新すると判定される。

0071

ステップS24において、現世代の使用テーブル群を更新すると判定された場合、処理はステップS25に進められる。ステップ256において、類似度計算式生成部14は、現世代の使用テーブル群を遺伝的アルゴリズムに従って更新することにより、次世代の仕様テーブル群を生成する。

0072

この後、処理はステップS22に戻り、ステップS22乃至S25の処理が繰り返される。そして、ステップS24において、現世代の使用テーブル群を更新しないと判定された場合、処理はステップS26に進められる。

0073

ステップS26において、類似度計算式生成部14は、最終世代の使用テーブル群のうち、最も良い評価の(AICの値が最小となった)使用テーブルTBkに基づいて推定された類似度計算式を最終的な類似度計算式として後段に出力する。

0074

以上で、類似度判定機構築システム10の動作の説明を終了する。

0075

以上説明したように、本発明を適用した類似度判定機構築システム10によれば、任意の種類の2つの比較データC1およびC2の類似度を判定できる類似度判定式を生成できる。

0076

このようにして生成された類似度計算式は、図1の示された類似度判定装置1に適用される。この類似度判定装置1は、例えば、多数の音楽データが蓄積されているデータベースの中から、入力される音楽データ(楽曲の断片でもよい)に類似した他の音楽データを検索するシステムの構築に利用したりすることができる。また、例えば、複数の画像を順次切り替えて表示させる、いわゆるスライドショーを実現するアプリケーションプログラムにおいて、複数の画像の中から類似した画像の組を検出し、類似した画像の組については、そのうちの1枚の画像だけをスライドショーに含めるような利用方法が考えられる。

0077

なお、本実施の形態においては、2つの入力データの類似度を判定する場合について説明したが、例えば類似度判定を複数データの全ての組み合わせについて行うことで、本発明は、より多くのデータの類似度を判定する場合にも応用することができる。

0078

ところで、上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウェアにより実行することもできる。一連の処理をソフトウェアにより実行する場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば汎用パーソナルコンピュータなどに、プログラム記録媒体からインストールされる。

0079

図13は、上述した一連の処理をプログラムにより実行するコンピュータのハードウェアの構成例を示すブロック図である。

0080

このコンピュータ100において、CPU(Central Processing Unit)101,ROM(Read Only Memory)102,RAM(Random Access Memory)103は、バス104により相互に接続されている。

0081

バス104には、さらに、入出力インタフェース105が接続されている。入出力インタフェース105には、キーボードマウスマイクロホンなどよりなる入力部106、ディスプレイスピーカなどよりなる出力部107、ハードディスク不揮発性メモリなどよりなる記憶部108、ネットワークインタフェースなどよりなる通信部109、磁気ディスク光ディスク光磁気ディスク、或いは半導体メモリなどの着脱可能な記録媒体111を駆動するドライブ110が接続されている。

0082

以上のように構成されるコンピュータでは、CPU101が、例えば、記憶部108に記憶されているプログラムを、入出力インタフェース105およびバス104を介して、RAM103にロードして実行することにより、上述した一連の処理が行われる。

0083

なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。

0084

また、プログラムは、1台のコンピュータにより処理されるものであってもよいし、複数のコンピュータによって分散処理されるものであってもよい。さらに、プログラムは、遠方のコンピュータに転送されて実行されるものであってもよい。

0085

また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。

0086

なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。

図面の簡単な説明

0087

本発明が適用された類似度判定機構築システムによって生成される類似度計算式が適用される類似度判定装置の一例を示すブロック図である。
本発明が適用された類似度判定機構築システムの構成例を示すブロック図である。
特徴量抽出式の例を示す図である。
特徴量抽出式の構成を説明する図である。
特徴量抽出式リストの例を示す図である。
遺伝的アルゴリズムを説明するための図である。
教師データのデータ構造を示す図である。
教師データに対応する特徴量を示す図である。
教師データの特徴量抽出式における距離を示す図である。
使用テーブル群の例を示す図である。
本発明が適用された類似度判定機構築システムの動作を説明するフローチャートである。
図11のステップS8の処理を説明するフローチャートである。
コンピュータの構成例を示すブロック図である。

符号の説明

0088

1類似度判定装置, 10類似度判定機構築システム, 11特徴量抽出式リスト生成部, 12 特徴量計算部, 13評価値計算部, 14類似度計算式生成部, 101 CPU, 111 記録媒体

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ