(57)【特許請求の範囲】
【請求項１】
コンピュータ実施方法であって、
複数のコンテンツアイテムを取得するステップと、
前記複数のコンテンツアイテムの各々から複数の特徴を抽出するステップと、
探索空間を作成するために前記抽出した特徴の各々についての特徴ベクトルを生成するステップと、
前記生成した特徴ベクトルに基づいて一連の要素行列を生成するステップであって、前記一連の要素行列の各要素行列は、1つまたは複数の関係に関連付けられる、ステップと、
変換が前記一連の要素行列の各要素行列に関連付けられた前記1つまたは複数の関係を保つように、前記一連の要素行列を構造化行列に変換することを少なくとも一部的に行うことによって前記探索空間を拡張するステップと、
探索オブジェクトを受信するステップと、
前記受信した探索オブジェクトに基づいて前記拡張探索空間を探索するステップと、
前記探索オブジェクトに対応する1つまたは複数のコンテンツアイテムに1つまたは複数のリンクを提供するステップとを含む、方法。
【請求項２】
前記要素行列に関連付けられた前記1つまたは複数の関係は、直交性を含む、請求項1に記載の方法。
【請求項３】
前記要素行列に関連付けられた前記1つまたは複数の関係は、ユークリッド距離を含む、請求項1または2に記載の方法。
【請求項４】
前記一連の要素行列を前記構造化行列に変換するステップは、
一連の要素行列に対するクロネッカー積の適用に部分的に基づくクロネッカー射影を生成するステップをさらに含む、請求項1から3のいずれか一項に記載の方法。
【請求項５】
前記受信した探索オブジェクトに基づいて前記拡張探索空間を探索するステップは、
前記探索オブジェクトに関連付けられた1つまたは複数の特徴を抽出するステップと、
前記探索オブジェクトの前記特徴を代表する探索オブジェクトベクトルを生成するステップと、
前記探索オブジェクトベクトルを前記構造化行列を含む前記拡張探索空間と比較するステップと、
前記比較に基づいて所定の関係を満足する1つまたは複数のコンテンツアイテムを識別するステップとをさらに含む、請求項1から4のいずれか一項に記載の方法。
【請求項６】
前記一連の要素行列は、特徴ベクトル探索空間の特定のスナップショットの元のユークリッド距離に少なくとも部分的に基づいてランダムに生成される、請求項1から5のいずれか一項に記載の方法。
【請求項７】
前記変換が前記一連の要素行列の各要素行列に関連付けられた前記1つまたは複数の関係を保つように、前記一連の要素行列を構造化行列に変換するステップは、d次元のデータに対してO(log d)のストレージ空間複雑度で達成される、請求項1から6のいずれか一項に記載の方法。
【請求項８】
1つまたは複数のコンピュータと、1つまたは複数のストレージデバイスであって、前記1つまたは複数のコンピュータによって実行されると、前記1つまたは複数のコンピュータに、
複数のコンテンツアイテムを取得するステップと、
前記複数のコンテンツアイテムの各々から複数の特徴を抽出するステップと、
探索空間を作成するために前記抽出した特徴の各々についての特徴ベクトルを生成するステップと、
前記生成した特徴ベクトルに基づいて一連の要素行列を生成するステップであって、前記一連の要素行列の各要素行列は、1つまたは複数の関係に関連付けられる、ステップと、
変換が前記一連の要素行列の各要素行列に関連付けられた前記1つまたは複数の関係を保つように、前記一連の要素行列を構造化行列に変換することを少なくとも一部的に行うことによって前記探索空間を拡張するステップと、
探索オブジェクトを受信するステップと、
前記受信した探索オブジェクトに基づいて前記拡張探索空間を探索するステップと、
前記探索オブジェクトに対応する1つまたは複数のコンテンツアイテムに1つまたは複数のリンクを提供するステップとを含む演算をさせるように動作可能な命令を記憶する1つまたは複数のストレージデバイスとを含む、システム。
【請求項９】
前記要素行列に関連付けられた前記1つまたは複数の関係は、直交性を含む、請求項8に記載のシステム。
【請求項１０】
前記要素行列に関連付けられた前記1つまたは複数の関係は、ユークリッド距離を含む、請求項8または9に記載のシステム。
【請求項１１】
前記一連の要素行列を前記構造化行列に変換するステップは、
一連の要素行列に対するクロネッカー積の適用に部分的に基づくクロネッカー射影を生成するステップをさらに含む、請求項8から10のいずれか一項に記載のシステム。
【請求項１２】
前記受信した探索オブジェクトに基づいて前記拡張探索空間を探索するステップは、
前記探索オブジェクトに関連付けられた1つまたは複数の特徴を抽出するステップと、
前記探索オブジェクトの前記特徴を代表する探索オブジェクトベクトルを生成するステップと、
前記探索オブジェクトベクトルを前記構造化行列を含む前記拡張探索空間と比較するステップと、
前記比較に基づいて所定の関係を満足する1つまたは複数のコンテンツアイテムを識別するステップとをさらに含む、請求項8から11のいずれか一項に記載のシステム。
【請求項１３】
前記一連の要素行列は、特徴ベクトル探索空間の特定のスナップショットの元のユークリッド距離に少なくとも部分的に基づいてランダムに生成される、請求項8から12のいずれか一項に記載のシステム。
【請求項１４】
前記変換が前記一連の要素行列の各要素行列に関連付けられた前記1つまたは複数の関係を保つように、前記一連の要素行列を構造化行列に変換するステップは、d次元のデータに対してO(log d)のストレージ空間複雑度で達成される、請求項8から13のいずれか一項に記載のシステム。
【請求項１５】
実行されると1つまたは複数のコンピュータによって実行可能な命令を含むソフトウェアを記憶する非一時的コンピュータ可読媒体であって、前記1つまたは複数のコンピュータに請求項1から7のいずれか一項に記載の方法の演算を行わせる、非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
高速直交射影に関する。
【背景技術】
【０００２】
例えば、コンピュータビジョンアプリケーションなどといった様々な複雑なコンピュータプロセスにおける情報の大規模探索および検索では、線形射影が利用される場合がある。そのようなアプリケーションは、データ点間のユークリッド距離を保つために直交射影を利用し得る。そのような直交射影の生成は、非構造化行列の利用が通常は必要となっていた。しかしながら、非構造化直交行列の構築の計算複雑度がO(d3)である一方で、空間および時間複雑度はO(d2)である。このことは、入力された次元dが増大するに連れて、非構造化直交行列の生成が非常にコストのかかる演算となることを意味している。
【発明の概要】
【課題を解決するための手段】
【０００３】
本明細書に記載した発明特定事項のある実施形態によれば、線形射影が、計算時間およびストレージ領域に関するコストの節約を達成するために、比較的大きな構造化行列を使用して効率的に行われる。比較的大きな構造化行列は、一連の比較的小さな直交要素行列に基づいて生成され得る。例えば、比較的大きな構造化行列は、一連の比較的小さな直交要素行列のクロネッカー積をとることによって形成され得る。数学としては、
【数１】
0006469890.tif 000002
で表される、クロネッカー積またはテンソル積は、大きな行列を削減する任意のサイズの2つの行列に対する演算である。クロネッカー積とは、ベクトルから行列への外積の生成であり、基準の標準的な選択に関してテンソル積の行列を与える。
【０００４】
いくつかの態様においては、本明細書において具現化される発明特定事項は、複数のコンテンツアイテムを取得するアクションを含み得る方法で具現化され得る。追加のアクションは、複数のコンテンツアイテムの各々から複数の特徴を抽出するステップと、探索空間を作成するために抽出した特徴の各々についての特徴ベクトルを生成するステップと、生成した特徴ベクトルに基づいて一連の要素行列を生成するステップであって、一連の要素行列の各要素行列は、1つまたは複数の関係に関連付けら得る、ステップと、変換が一連の要素行列の各要素行列に関連付けられた1つまたは複数の関係を保つように、一連の要素行列を構造化行列に変換することを少なくとも一部的に行うことによって探索空間を拡張するステップとを含み得る。追加のアクションは、探索オブジェクトを受信するステップと、受信した探索オブジェクトに基づいて拡張探索空間を探索するステップと、探索オブジェクトに対応する1つまたは複数のコンテンツアイテムに1つまたは複数のリンクを提供するステップとを含み得る。複数のコンテンツアイテムは、高次元データを含み得る。高次元データは、テキスト、画像、ビデオ、コンテンツ広告、地図データからなるグループから選択され得る。
【０００５】
他のバージョンは、方法のアクションを行うように構成される、対応するシステム、装置、コンピュータストレージデバイス上に符号化されたコンピュータプログラムを含む。
【０００６】
これらおよび他のバージョンの各々は、1つまたは複数の以下の特徴を必要に応じて含み得る。例として、いくつかの実施形態においては、要素行列に関連付けられた関係は、直交性を含み得る。あるいは、または、加えて、要素行列に関連付けられた関係は、ユークリッド距離を含み得る。
【０００７】
いくつかの態様においては、一連の要素行列を構造化行列に変換するステップは、一連の要素行列に対するクロネッカー積の適用に部分的に基づくクロネッカー射影を生成するステップを含み得る。一連の要素行列は、特徴ベクトル探索空間の特定のスナップショットのユークリッド距離に少なくとも部分的に基づいてランダムに生成され得る。一連の要素行列の各要素行列に関連付けられた1つまたは複数の所定の関係を保つように一連の要素行列を構造化行列に変換することは、d次元のデータに対してO(log d)のストレージ複雑度で達成され得る。
【０００８】
ある実施形態においては、方法は、探索オブジェクトに関連付けられた1つまたは複数の特徴を抽出するステップと、探索オブジェクトの特徴を代表する探索オブジェクトベクトルを生成するステップと、探索オブジェクトベクトルを構造化行列を含む拡張探索空間と比較するステップと、比較に基づいて所定の関係を満足する1つまたは複数のコンテンツアイテムを識別するステップとに関するアクションを含み得る。
【０００９】
態様が任意の都合のよい形式で実施され得ることを諒解されたい。例えば、態様および実施形態は、有形キャリア媒体(例えばディスク)または無形キャリア媒体(例えば通信信号)であり得る適切なキャリア媒体上で実行され得る、適切なコンピュータプログラムによって実施され得る。態様はまた、発明を実施するように構成されたコンピュータプログラムを動作させるプログラマブルコンピュータの形式をとり得る適切な装置を使用して実施され得る。
【００１０】
1つまたは複数の実施形態の詳細を、以下の添付の図面および説明において記載している。他の特徴および利点は、説明および図面から、および特許請求の範囲から明らかとなるであろう。
【図面の簡単な説明】
【００１１】
【図１】本開示の少なくとも1つの態様による、線形射影を効率的に行うために使用され得る例示的なシステムのブロック図である。
【図２】本開示の少なくとも1つの態様による線形射影を効率的に行うために使用され得る例についてのフローチャートである。
【図３】本開示の少なくとも別の態様による、線形射影を効率的に行うために使用され得る別の例示的なシステムのブロック図である。
【図４】少なくとも本開示の態様による、拡張探索空間に対して探索クエリを実行するための例示的なプロセスのフローチャートである。
【発明を実施するための形態】
【００１２】
図面においては、類似の参照番号は、全般的に類似の要素を指す。
【００１３】
図1は、本開示の少なくとも1つの態様による、線形射影を効率的に行うために使用され得る例示的なシステム100のブロック図である。システム100は、例えば、クライアント110、サーバ120、リモートコンピュータ130、およびネットワーク140を含み得る。
【００１４】
一般に、例示的なシステム100を使用して、構造化行列の一群が、例えば、コンピュータビジョンアプリケーションなどといった、様々な複雑なコンピュータアプリケーションに関連して存在し得る、高次元データのための直交射影を効率的に行うために使用され得る。システム100は、一連の比較的小さな直交要素行列の作成のために提供され得る。一連の比較的小さな直交要素行列が取得されると、本開示の態様は、一連の小さな直交要素行列を構造化行列に変換し得る。本開示の少なくとも1つの態様によれば、構造化行列は、一連の小さな直交要素行列のクロネッカー積をとることによって形成され得る。そのような変換の結果として、本開示は、計算複雑度および空間複雑度の双方において既存のシステムを超えた利点を実現し得る。例として、本開示は、d次元のデータに対してO(dlog d)の計算複雑度およびO(log d)の空間複雑度を達成する。
【００１５】
システム、および非一時的コンピュータ可読媒体によって実現される、大きなデータベース内に保持されている高次元データを記憶、探索、および検索するために要する、メモリおよび処理能力の削減は、著しいものである。本開示によって提供したそのような利点は、高次元データの探索および検索がモバイルプラットフォームにおいて行われることを可能とし得るし、このことは、高次元データの効率的な記憶、探索、および検索を容易にするために必要とされるメモリ領域を低減し得る。それゆえ、これらに限定されないが、画像検索、ビデオ検索、関連コンテンツ広告の表示、および/または地図データを含む、複雑なコンピュータアプリケーションが、より小さなメモリフットプリントおよびより少ない処理能力で実施され得るし、それにより、例えば、スマートフォン、タブレット、および/または他のシンクライアントデバイスなどのモバイルプラットフォームを介した、そのようなアプリケーションに関連付けられた高次元データの記憶、探索、および検索を可能としている。本開示は、したがって、探索が高次元データに対して効率的に行うことを可能にするにはどのようにすべきであるかという課題を対処している。
【００１６】
システム100のクライアント110は、少なくともプロセッサ111、メモリ112、およびデータベース115を含み得る。メモリ112は、クライアント110上で1つまたは複数のアプリケーションを実行するために使用されるコンピュータプログラムコードのストレージを提供し得る。アプリケーションは、例えば、ブラウザ113を含み得る。クライアント110は、ブラウザ113を使用してネットワーク140を介して1つまたは複数のウェブベースのアプリケーションにアクセスすることが可能となり得る。そのようなウェブベースのアプリケーションは、例えば、地図アプリケーション、ビデオストリーミングアプリケーション、モバイル決済システム、広告サービスなどを含み得る。ブラウザ113は、クライアント110に関連付けられた1つまたは複数のユーザインターフェースを介してクライアント110のユーザから入力を受信するように構成され得る。受信した入力は、例えば、とりわけ、特に、例えば、物理キーボード、静電容量式タッチユーザインターフェースを介したグラフィカル表現キーボードなどといったキーパッドを介した探索クエリ入力、および、音声コマンド、1つまたは複数の実行可能なコマンドを表すジェスチャなどを介した探索クエリ入力を含み得る。
【００１７】
あるいは、または、加えて、クライアント110は、クライアント110上にローカルに記憶された1つまたは複数のモバイルアプリケーション114を記憶および実行するためにプロセッサ111およびメモリ112を使用し得る。例として、クライアント110は、例えば、テキストファイル、オーディオファイル、画像ファイル、ビデオファイル、またはその組合せを含む、ローカルコンテンツを記憶するように構成され得る、コンテンツデータベース115を含み得る。コンテンツデータベース115からそのような保存されているローカルコンテンツを読み出すために、1つまたは複数のモバイルアプリケーション114は、例えば、ローカル文書検索、ローカルオーディオファイル検索、ローカル画像ファイル検索、ローカルビデオ検索などを容易にするための機能性を提供し得る。あるいは、または、加えて、しかしながら、モバイルアプリケーション114は、任意のそのようなローカル検索がまた、ネットワーク140を介してアクセス可能な1つまたは複数のコンピュータ120および130によってホストされている1つまたは複数のコンテンツデータベース129および133に対してリモートで実行され、ローカルおよびリモートコンテンツデータベースの双方からの探索結果を含み得る探索結果のマージ済みリストを提供し得ることも保証し得る。同様に、モバイルアプリケーション114は、例えば、手書き認識プログラムを含む他のタイプのアプリケーションを含み得る。他のタイプのモバイルアプリケーション114も本明細書によって提供した開示の範囲に含まれ得る。
【００１８】
モバイルアプリケーション114は、ブラウザ113に関して上述したものと類似した方式で、クライアント110のユーザから入力を受信するように構成され得る。あるいは、または、加えて、1つまたは複数のモバイルアプリケーション114は、1つまたは複数のモバイルアプリケーション114によって提供される特定の機能性に基づいて、ブラウザ113とは異なる入力を受信するように構成され得る。例として、手書き認識プログラムは、クライアント110に統合されているかクライアント110に外的に接続されているかしている静電容量式タッチユーザインターフェースと組み合わせたスタイラスまたはユーザの指を使用して、ユーザによって行われたモーションを介して、手書きテキスト入力の形式で、入力を受信するように構成され得る。そのような入力が本開示の態様によってキャプチャされると、手書きテキスト入力に関連する特徴が、本開示の態様に従って、手書き入力に対応し得る1つまたは複数のテキスト文字、テキスト文字列などを読み出すために探索され得る。
【００１９】
クライアント110は、1つまたは複数のクライアントデバイスを表し得る。そのようなクライアントデバイスは、例えば、モバイルコンピューティングプラットフォームおよび非モバイルコンピューティングプラットフォームを含み得る。モバイルコンピューティングプラットフォームは、例えば、スマートフォン、タブレット、ラップトップコンピュータ、または他のシンクライアントデバイスを含み得る。非モバイルコンピューティングプラットフォームは、例えば、デスクトップコンピュータ、セットトップボックスエンターテインメントシステムなどを含み得る。クライアント110は、1つまたは複数の通信プロトコルを使用してネットワーク140を介してサーバ120と通信するように構成され得る。
【００２０】
サーバ120は、1つまたは複数のサーバコンピュータを表し得る。サーバ120は、少なくともプロセッサ121、メモリ122、およびコンテンツデータベース129を含み得る。メモリ122は、本明細書に開示した発明特定事項の特徴を実施するために使用され得るソフトウェアツール一式を含み得る。これらのソフトウェアツールは、例えば、コンテンツ識別ユニット123、特徴抽出ユニット124、特徴ベクトル生成ユニット125、要素行列生成ユニット126、および構造化行列生成ユニット127を含み得る。前述のソフトウェアツールの各々は、プロセッサ121によって実行されると、本明細書において説明した例示的な機能性を行って、高次元データに関わる記憶、探索、および検索演算を容易にするために必要となるメモリフットプリントを著しく削減する拡張探索空間を作成し得るプログラム命令を含み得る。高次元データは、例えば、数百の次元、数千の次元、数百万の次元、またはそれ以上の次元などといった多次元のデータを含み得る。
【００２１】
コンテンツ識別ユニット123は、複数の異なるソースのうちの1つ以上からコンテンツを取得するように構成され得る。例として、コンテンツ識別ユニット123は、ネットワーク140を巡回して1つまたは複数のリモートコンピュータ130のデータベース133に保持されているコンテンツアイテムをスキャンおよび識別し得る、ウェブクローラ、ウェブスパイダなどを利用してもよい。識別されると、コンテンツ識別ユニットは、データベース133からコンテンツアイテムまたはその一部分のコピーを取得し、サーバ120のコンテンツデータベース129にコンテンツアイテムのコピーを記憶し得る。コンテンツアイテムは、クライアント110、サーバ120、またはリモートコンピュータ130を使用して作成され得る、例えば、テキストデータ、オーディオデータ、画像データ、ビデオデータ、または任意のその組合せを含む、様々な異なるタイプのコンテンツを含み得る。
【００２２】
あるいは、または、加えて、コンテンツ識別ユニット123は、クライアントデバイス110の1つまたは複数のユーザインターフェースを介してユーザによって入力されたコンテンツの一部をキャプチャするように構成され得る。例として、コンテンツ識別ユニット123は、クライアント110に統合されているかクライアント110に外的に接続されているかしている静電容量式タッチユーザインターフェースと組み合わせたスタイラスまたはユーザの指を使用してユーザによって行われたモーションを介して入力された手書きテキストをキャプチャするように構成され得る。あるいは、または、加えて、コンテンツ識別ユニット123は、1つまたは複数のリモートコンピュータを介してアップロードされ得る1つまたは複数のコンテンツアイテムを受信するように構成され得る。例として、コンテンツ識別ユニット123は、リモートコンピュータ130の1人または複数のユーザがデータベース129によって保持されているコンテンツアイテムのライブラリに追加することを希望する1つまたは複数のコンテンツアイテムを受信し得る。あるいは、または、加えて、コンテンツ識別ユニットは、サーバ120のデータベース129に以憶されていたコンテンツアイテムを取得するように構成され得る。
【００２３】
1つまたは複数の前述のソースから取得したコンテンツアイテムは、クライアント110の1つまたは複数のユーザ、リモートコンピュータ130などによるアクセスに適するよう作成され得るデータベース129に記憶されるコンテンツアイテムのライブラリを生成するために使用され得る。例として、サーバ120は、ブラウザ112もしくはモバイルアプリケーション114を介してクライアント110のユーザがアクセス可能な、または、リモートコンピュータ130を介して類似のアプリケーションのユーザがアクセス可能な地図アプリケーションをサポートするために使用され得る、ある期間にわたる膨大な量のロケーション情報、地理的情報、画像情報などを集約し得る。あるいは、または、加えて、例えば、サーバ120は、ある期間にわたる膨大な量のビデオファイルを集約して、ブラウザ112もしくはモバイルアプリケーション114を介してクライアント110のユーザがアクセス可能な、または、リモートコンピュータ130を介して類似のアプリケーションのユーザがアクセス可能なビデオストリーミングサービスをサポートし得る。サーバ120によって取得されたコンテンツアイテムは、同様に、クライアント110のユーザまたはリモートコンピュータ130がアクセス可能な他のタイプのアプリケーションをサポートするために使用され得る。
【００２４】
コンテンツ識別ユニット123は、十分な数のコンテンツアイテムを拡張探索空間の生成の開始のために収集し終えたかを周期的に判定し得る。この周期的判定は、例えば、所定の期間の満了に基づいていてもよい。あるいは、または、加えて、周期的判定は、例えば、データの100GB、データの100TBなどを収集した後といった、所定の量のデータの収集に基づいてなされてもよい。あるいは、または、加えて、周期的判定は、例えば、サービスに申し込んでいる所定の数のユーザからキャプチャしたコンテンツ、サービスを実際に利用している所定の数のユーザからキャプチャしたコンテンツ、所定の数の既知となっているすべてのコンテンツソースからキャプチャしたコンテンツのなどといった、コンテンツを所定の量のコンテンツソースから収集し終えたかの判定に基づいてなされてもよい。あるいは、または、加えて、コンテンツ識別ユニット123は、1人または複数の人間のユーザからの拡張探索空間を生成するようにという命令の受信に応じて拡張探索空間の生成をトリガし得る。
【００２５】
特徴抽出ユニット124は、各特定のコンテンツアイテムに一意に関連付けられ得る従属的な特徴または特性を識別するために、コンテンツ識別ユニット123によって取得されたコンテンツを分析するように構成され得る。特徴データは、例えば、画像コンテンツに関連付けられ得る、例えば、色、カウンタ、カーブ、テクスチャ、ピクセルなどを含み得る。あるいは、または、加えて、特徴データは、例えば、テキストコンテンツに関連付けられる、例えば、文書キーワード、単語使用頻度などを含み得る。コンテンツリソースの複雑度が増大するにつれて、コンテンツに関連付けられた特徴の数も同様に増大し得る。例として、特定の高解像度画像は、画像内の各特定のピクセルに対応する少なくとも1つの特徴に関連付けられ得る。コンテンツアイテムから抽出された特徴に基づいて探索および検索プロセス中に特定のコンテンツアイテムを識別することができる尤度は、コンテンツアイテムから抽出された特徴の量とともに増大し得る。特徴抽出ユニット124によって抽出したコンテンツ特徴は、特徴ベクトル生成ユニット125によって後ほど使用するために、メモリユニット122またはデータベース129に記憶され得る。
【００２６】
特徴ベクトル生成ユニット125は、特徴抽出ユニット124によって抽出した高次元特徴データを取得、さもなければ、受信するように構成され得る。抽出された特徴データの受信時に、特徴ベクトル生成ユニット125は、取得したコンテンツから抽出された特徴の各々を数字として表すために使用され得る複数の特徴ベクトルを生成し得る。特定の特徴ベクトルの値は、単一の行の行列の形式で表され得る。抽出したデータベース129に記憶されている特徴から生成された特徴ベクトルの集合セットは、そのため、コンテンツ識別ユニット123によって取得された高次元データの探索可能なモデルを生成し得る。類似度の判定が、2つ以上の特徴ベクトル間のユークリッド距離の計算に基づいて、任意の2つ以上の特徴ベクトル間でなされ得る。ユークリッド距離が類似すればするほど、特徴ベクトル間に存在する類似度が大きくなる。
【００２７】
本願の明細書に開示した発明特定事項の少なくとも1つの態様においては、任意の特定の時点における特徴ベクトル探索空間の特定のスナップショットに関する特定の特徴ベクトル探索空間に存在する特徴ベクトルの各々の間にユークリッド距離が存在し得る。特徴ベクトル探索空間の特定のスナップショットを、例えば、所定の数の特徴ベクトルを特徴ベクトル生成ユニット125によって生成し終えた後の任意の特定の時点においてキャプチャしてもよい。ある例では、特徴ベクトル探索空間の学習または最適化の前に、各々が元のユークリッド距離で分離されている複数の特徴ベクトルを含む元の特徴ベクトル探索空間が存在し得る。あるいは、または、加えて、元のユークリッド距離は、例えば、特徴ベクトル探索空間のスナップショットがキャプチャされた時間における特徴ベクトルの各々の間に存在するユークリッド距離であり得る。
【００２８】
要素行列生成ユニット126は、特徴ベクトル生成ユニット125によって生成された複数の高次元特徴ベクトルを取得、さもなければ、受信するように構成され得る。要素行列生成ユニット126は、その後、取得した特徴ベクトルを一連のM個の要素行列に構築し得る。一連のM個の要素行列内の各要素行列は、下記で説明する構造化行列より比較的小さくなり得る。例えば、本願の明細書に開示した発明特定事項の少なくとも1つの態様においては、各要素行列は、2x2のサイズとなり得る。あるいは、または、加えて、一連のM個の要素行列内の各要素行列は直交し得る。要素行列生成ユニット126は、例えば、小さく、ランダムなガウシアン行列を作成し、QR分解を行うことによって、一連のM個の要素行列を生成し得る。一連のM個の要素行列のランダム生成は、例えば、特徴ベクトル探索空間の特定のスナップショットの元のユークリッド距離に少なくとも部分的に基づき得る。例えば、一連のM個の要素行列内の各要素行列は、元の特徴ベクトル探索空間の元のユークリッド距離を保つように、ランダムに生成され得る。あるいは、一連のM個の要素行列は、例えば、特定の画像が提示された際に特定の画像結果を返すように、機械学習システムを使用して要素行列を訓練するように構成され得る。
【００２９】
構造化行列生成ユニット127は、要素行列生成ユニット126によって生成された一連のM個の要素行列を取得、さもなければ、受信するように構成され得る。構造化行列生成ユニット127は、一連のM個の要素行列を構造化行列に変換するように構成され得る。構造化行列は、比較的小さい一連のM個の要素行列の各行列よりサイズが比較的大きくなり得る。一連のM個の要素行列の変換は、一連のM個の要素行列の各要素行列に関連付けられた関係を保つ方式で生じ得る。保たれる関係は、例えば、直交性またはユークリッド距離を含み得る。本開示の少なくとも1つの態様においては、変換は、一連のM個の要素行列のクロネッカー積をとることによって線形射影を生成することを含み得る。本願の明細書に開示した発明特定事項の少なくとも1つの態様に関して、一連のM個の要素行列のクロネッカー積は、例えば、高速フーリエ変換または高速フーリエ変換と類似した計算を含むプロセスを使用して実現され得る。一連のM個の小さな要素行列を比較的大きな構造化行列に変換するために構造化行列生成ユニット127を使用した線形射影の生成は、非構造化行列の射影と比較して、計算および空間コストにおいて著しい削減をもたらし得る。例として、構造化行列生成ユニット127を使用して生成された線形射影は、非構造化行列に対するO(d2)の計算速度およびO(d2)の空間複雑度とは対照的に、d次元データに対してO(dlog d)の計算速度およびO(log d)の空間複雑度を達成し得る。
【００３０】
構造化行列生成ユニット127の出力は、拡張探索空間をもたらし得る。拡張探索空間は、拡張探索空間ストレージエリア128に記憶され得る。非構造化行列に対する空間複雑度をO(d2)からO(log d)に低減するために探索空間が拡張されているが、比較的大きな構造行列は、コンテンツアイテムの特定のセットに関して生成した特徴ベクトルのすべてを実質的に含み得る特徴ベクトル空間の表現をさらに提供し得る。それゆえ、探索の精度も正確さも、本明細書に記載の本開示の態様を使用することで低下することはない。
【００３１】
リモートコンピュータ130は、1つまたは複数のリモートコンピュータのうちの1つ以上を表し得る。各リモートコンピュータ130は、少なくともプロセッサ131、メモリ132、およびコンテンツデータベース133を含み得る。リモートコンピュータ130は、例えば、コンテンツ識別ユニット123などといった、ウェブコンテンツを識別および取得することが可能なソフトウェアツールにとって探索に利用可能な1つまたは複数のコンテンツアイテムを作成するように構成され得る。あるリモートコンピュータ130の1つまたは複数のユーザは、コンテンツデータベース129に保持されているコンテンツアイテムを探索およびアクセスすることも可能にし得る。リモートコンピュータ130は、ネットワーク140を介してサーバ120と通信するように構成され得る。
【００３２】
ネットワーク140は、クライアント110、サーバ120、および/またはリモートコンピュータ130との間の接続を円滑にするように構成され得る。クライアント110、サーバ120、および/またはリモートコンピュータ130は、それぞれ、1つまたは複数の有線もしくは無線の通信リンク142a、142b、および/または142cを介して、ネットワーク140に接続され得る。ネットワーク140は、これらに限定されないが、ローカルエリアネットワーク(LAN)、ワイドエリアネットワーク(WAN)、インターネット、セルラデータネットワーク、または任意のその組合せを含む、1つまたは複数のタイプのパブリックおよび/またはプライベートネットワークの任意の組合せを含み得る。
【００３３】
図2は、本開示の少なくとも1つの態様による、線形射影を効率的に行うために使用され得る例示的なプロセス200のフローチャートである。
【００３４】
プロセス200は、コンテンツ識別ユニット123によって210において開始して、サーバ120のローカルまたはリモートに存在し得る1つまたは複数のコンテンツソースから1つまたは複数のコンテンツアイテムを介してコンテンツに関するスキャンを開始し得る。コンテンツスキャンは、例えば、ウェブクローラ、ウェブスパイダなどによって行われ得る。あるいは、または、加えて、コンテンツ識別ユニット123は、1つまたは複数のコンテンツアイテムを1つまたは複数のリモートコンピュータ130または1つまたは複数のクライアントコンピュータ110から受信し得る。コンテンツが識別されると、コンテンツ識別ユニットは、識別されたコンテンツをサンプリングし、コンテンツデータベース129に識別されたコンテンツの少なくとも一部を記憶し、メインメモリ122の別の部分に識別されたコンテンツの少なくとも一部を記憶し、または、識別されたコンテンツの少なくとも一部を特徴抽出ユニット124に送信し得る。
【００３５】
プロセス200は、220に進み、特徴抽出ユニット124がコンテンツ識別ユニット123によって識別されたコンテンツの1つまたは複数の一部にアクセスし得る。特徴抽出ユニット124は、取得したコンテンツに関連付けられた1つまたは複数の特徴および/または特性を抽出し得る。抽出した特徴は、コンテンツデータベース129に記憶され得るし、メインメモリ122の別の部分に記憶され得るし、または、特徴ベクトル生成ユニット125に送信され得る。
【００３６】
プロセス200は、230に進み、特徴ベクトル生成ユニット125が特徴抽出ユニット124によって抽出したコンテンツ特徴に基づいて1つまたは複数の特徴ベクトルを生成し得る。特徴ベクトルは、高次元データの探索可能なデータモデルを生成するために使用され得る。探索可能なモデルは、2つ以上の特徴ベクトルの比較に基づく類似度の判定を容易にし得る。そのような比較は、2つ以上の特徴ベクトル間に存在するユークリッド距離の評価に基づき得る。任意の所与のペアの特徴ベクトル間に存在する距離が小さくなればなるほど、特徴ベクトル間に存在し得る類似度は大きくなる。生成した特徴ベクトルは、コンテンツデータベース129に記憶され得るし、メインメモリ122の別の部分に記憶され得るし、または、要素行列生成ユニット126に送信され得る。
【００３７】
プロセス200は、240に進み、要素行列生成ユニット126が特徴ベクトル生成ユニット125によって生成された複数の高次元特徴ベクトルのセットに基づいて一連のM個の要素行列を生成し得る。一連のM個の要素行列の各行列は直交し得る。一連のM個の要素行列は、特徴ベクトル探索空間の特定のスナップショットの元のユークリッド距離に少なくとも部分的に基づいて、ランダムにまたは擬似ランダムに生成され得る。あるいは、または、加えて、一連のM個の要素行列は、本明細書で後述しているものなどような、1つまたは複数のマシン言語学習システムを使用して訓練され得る。生成した一連のM個の要素行列は、コンテンツデータベース129に記憶され得るし、メインメモリ122の別の部分に記憶され得るし、または、構造化行列生成ユニット117に送信され得る。
【００３８】
プロセス200は、250に進み、構造化行列生成ユニット127が比較的小さな一連のM個の要素行列に基づいて比較的大きな構造化行列を作成するように構成され得る。比較的大きな構造化行列は、一連のM個の要素行列を比較的大きな構造化行列に変換または回転することによって作成され得る。変換は、変換が一連のM個の要素行列の各要素行列に関連付けられた関係を保つように、行われ得る。本願の明細書に開示した発明特定事項の少なくとも1つの態様においては、変換は、一連のM個の要素行列のクロネッカー積をとることによって線形射影を生成することを含み得る。比較的大きな構造化行列は、拡張探索空間をもたらし得る。比較的大きな構造化行列の空間複雑度は、d次元のデータに対してO(log d)のオーダーとなり得る。260において、拡張探索空間は、拡張探索空間ストレージエリア128、コンテンツデータベース129などに記憶され得る。
【００３９】
クロネッカー積に関して本開示が本明細書において説明されているが、本開示を必ずしもそのように限定する必要がないことに留意されたい。そのため、他の方法の行列変換または回転が、本明細書において説明したような、一連の小さな直交要素行列を大きな構造化行列に変換すること容易にするために使用されてもよい。例えば、一連の要素行列に関連付けられた1つまたは複数の関係を保つ要素行列の任意の効率的な変換が、本開示に従って、一連の小さな直交要素行列から大きな構造化行列を生成するために使用されてもよい。生成した構造化行列において保たれているそのような関係の例としては、例えば、とりわけ、直交性、ユークリッド距離などが含まれる。
【００４０】
図3は、本開示の少なくとも別の態様により、線形射影を効率的に行うために使用され得る、例示的なシステム300のブロック図である。システム300は、例えば、クライアント310、サーバ320、リモートコンピュータ330、およびネットワーク340を含み得る。
【００４１】
クライアント310は、各々がクライアント110と実質的に同様であり得る1つまたは複数のクライアントデバイスを含み得る。クライアント310は、少なくともプロセッサ311、メインメモリ312、およびコンテンツデータベース319を含み得る。ただし、クライアント310は、コンテンツ識別ユニット313、特徴抽出ユニット314、特徴ベクトル生成ユニット315、要素行列生成ユニット316、構造化行列生成ユニット317、および拡張探索空間ストレージエリア318も含み得る。コンテンツ識別ユニット313、特徴抽出ユニット314、特徴ベクトル生成ユニット315、要素行列生成ユニット316、構造化行列生成ユニット317、および拡張探索空間ストレージエリア318の各々は、図1のシステム100のコンテンツ識別ユニット123、特徴抽出ユニット124、特徴ベクトル生成ユニット125、要素行列生成ユニット126、構造化行列生成ユニット127、および拡張探索空間ストレージエリア128と実質的に同一であってもよい。しかしながら、図3のシステム300においては、コンテンツ識別ユニット313、特徴抽出ユニット314、特徴ベクトル生成ユニット315、要素行列生成ユニット316、構造化行列生成ユニット317、および拡張探索空間ストレージエリア318が、サーバ320のかわりに、または、サーバ320に加えて、クライアント310上に実装されてもよい。結果として、本願の明細書の発明特定事項によって提供した効率が、例えば、クライアント310などのクライアントデバイス上での高次元データの探索および検索を容易にし得る。
【００４２】
それゆえ、本願の明細書に記載した発明特定事項の特徴は、テキストファイル、オーディオファイル、画像ファイルビデオファイル、またはその組合せについてのローカル記憶、探索、および検索をサポートするために、例えば、拡張探索空間の生成などといった、クライアント310上で動作され得る1つまたは複数のモバイルアプリケーション114の態様に適用され得る。本開示の特徴はまた、例えば、手書き認識アプリケーション、コンテンツ広告の検索および表示などといった、他のタイプのモバイルアプリケーションに関連付けられた記憶、探索、および検索演算を改善するために、拡張探索空間の生成に適用され得る。
【００４３】
上述した特徴の結果として、本開示は、例えば、とりわけ、バイナリ埋め込み(binary embedding)またはデカルトk-meansなどのアプローチを使用する際に、例えば、近似最近傍(ANN)探索方法を含む、探索および検索技法に対してかなりの利点を提供することになり得る。本開示は、そのため、著しく少ない時間およびメモリを要する一方で、より望ましい精度で複雑な探索問題を解決している。
【００４４】
図4は、少なくとも本開示の態様による、拡張探索空間に対して探索クエリを実行するための例示的なプロセス400のフローチャートである。
【００４５】
プロセス400は、例えば、サーバ120またはクライアント310などのコンピュータが探索オブジェクトを受信した際に、410において開始し得る。探索オブジェクトは、コンテンツデータベース129または319によって保持されているコンテンツアイテムに関連付けられ得る、1つまたは複数のキーワード、画像、ビデオクリップ、スタイラスまたはユーザの指を介して入力された手書きのストローク、アドレス、および/または他のデータを含むクエリを含み得る。探索オブジェクトを受信した後に、サーバ120またはクライアント310は、探索オブジェクトを分析して、420において受信した探索オブジェクトに関連付けられた1つまたは複数の特徴または特性を抽出し得る。
【００４６】
プロセス400は、430に進み、探索オブジェクトに関連付けられるとともに420において抽出した探索オブジェクト特徴に基づいて、1つまたは複数の探索オブジェクト特徴ベクトルを生成する。440において、サーバ120またはクライアント310は、拡張探索空間ストレージエリア128または318に保持されている以前生成した拡張探索空間に対する探索オブジェクト特徴ベクトルを処理し得る。このことは、例えば、探索オブジェクト特徴ベクトルに関する最近傍の一致を提供する高次元特徴ベクトルのサブセットを識別するために、構造化行列の線形射影のビュー内の探索オブジェクト特徴ベクトルを分析することを含み得る。あるいは、または、加えて、ステージ440は、探索オブジェクト特徴ベクトルの所定の閾値距離内にある特徴ベクトルのサブセットを表す複数の一致を識別することを含み得る。本開示の少なくとも1つの態様においては、探索オブジェクトベクトルと拡張探索空間において構造化行列を用いて線形射影された特徴ベクトルとの間の距離は、ユークリッド距離であり得る。最後に、460において、プロセスは、探索オブジェクト特徴ベクトルと十分に一致すると、拡張探索空間において識別された特徴ベクトルのサブセットに関連付けられた1つまたは複数のコンテンツアイテムを読み出し得る。あるいは、または、加えて、読み出したコンテンツアイテムを参照する1つまたは複数のリンクを、探索オブジェクトを送信したコンピュータに提供し得る。
【００４７】
上述したように、複雑なコンピュータアプリケーションに関連するデータの大規模探索および検索のための方法において、少なくとも部分的に、少なくとも1つの段階は、線形射影を利用することであり得る。例えば、x∈Rdおよび射影行列R∈Rk×dなどといった所与のベクトルについては、線形射影は、式(1)において以下のように示され得る。h(x)∈Rkであり、
h(x)=Rx        (1)
【００４８】
そのような線形射影は、例えば、とりわけ、量子化の後に、例えば、バイナリ埋め込みまたはプロダクトコードなどといった、少ないメモリを使用するコンパクトコードに高次元特徴を変換し得る。コンパクトコードは、バイナリコードまたは非バイナリコードであってもよい。そのようなコンパクトコードは、探索実行時間を効率的に行い、様々な複雑なコンピュータアプリケーション、例えば、画像検索、特徴マッチング、属性認識、およびオブジェクトカテゴリ分類などに関連付けられたストレージ要件を低減するために使用され得る。例えば、大規模近似最近傍探索に関するLocality Sensitive Hashing(LSH)技法が、入力データをコンパクトコードに変換する前に入力データを線形射影するために使用され得る。例として、kビットのバイナリコードは、以下の式(2)を満足し得る。
h(x)=sign(Rx)        (2)
【００４９】
しかしながら、そのような線形射影演算は、入力次元dが増大するにつれて計算的にコストのかかるものとなる。検索タスクにおける高い再現率を達成するために、一つには、k=O(d)となる大きなkを有するロングコードを使用し得る。この場合には、射影の空間および計算複雑度は、O(d2)であり、そのような高射影コストは、学習および予測時間の双方においてしばしばボトルネックとなる。例えば、k=d=50,000である場合には、射影行列のみで10GB(単精度)を要し得るし、1つのベクトルの射影に単一のコア当たり800msかかり得る。
【００５０】
本開示の少なくとも1つの態様においては、射影行列は直交し得る。直交変換は、例えば、とりわけ、点間のユークリッド距離を保ち、分散を次元にわたってより均等に分布させることも知られているため、有益であり得る。これらのプロパティは、いくつかの既知の技法を実世界データに対してうまく行わせるために重要である。
【００５１】
直交射影を使用することは、特定のアプリケーションに対して追加の利益を提供し得る。例として、直交性は、データ依存のバイナリコードを学習する際に最大限に無相関なビットを学習するという目的を満足するための1つのアプローチであり得る。この前述した目的を達成する1つの方法は、直交または近似的に直交という制約を射影に課すことである。同様に、バイナリ埋め込みにおいては、射影に直交制約を課すことは、近似最近傍探索を実行する際に改善された結果を実現することになり得る。
【００５２】
高次元データに関する線形射影を効率的に行うために、本開示は、元の要素行列に関連付けられた関係を行列の変換の前に存在していた関係として保つ方式で、一連の小さな要素行列を構造化行列に変換するための方法、システム、および非一時的コンピュータ可読媒体を提供している。変換に殻生じる構造化行列は、例えば、大きな単一の行列であり得る。あるいは、しかしながら、構造化行列は、直交構造化行列のフレキシブルな一群を概念的には表し得る。本開示の少なくとも1つの態様においては、保たれる関係は、一連の要素行列の各行列に関連付けられた直交性であり得る。あるいは、または、加えて、保たれる関係は、行列に関連付けられた対応する特徴ベクトル間の距離であり得る。距離は、例えば、行列に関連付けられた対応する特徴ベクトル間のユークリッド距離であり得る。要素行列の変換は、小さな要素行列のクロネッカー積を使用することによって実現され得るし、このことは、実質的に削減された空間および計算複雑度をもたらすことになる。本変換に関連付けられたフレキシビリティは、所与のアプリケーションのニーズに適応するために行列内のフリーパラメータの数の変化を容易にし得る。
【００５３】
それゆえ、本開示の少なくとも1つの態様は、一連の小さな直交行列を変換して大きな構造化行列を形成することによって直交構造化行列の一群を構築し得る。本開示の少なくとも1つの態様は、一連の小さな直交要素行列のクロネッカー積を使用して前述の変換を容易にし得る。クロネッカー射影行列は、式(3)を満足し得る。
【００５４】
【数２】
0006469890.tif 000003
【００５５】
式(3)において、Aj、j=1,...,Mは、小さな直交行列である。小さな直交行列Aj、j=1,...,Mを要素行列と称してもよい。前述の変換に従って生成された大きな行列は、少なくとも4つの主な利点に関連し得る。第1には、大きな行列は直交制約を満足する、そのため、大きな行列は元の空間内のユークリッド距離を保ち得る。第2には、O(dlog d)の時間複雑度で射影を計算するために高速フーリエ変換と類似した計算を使用することができる。第3には、要素行列のサイズを変更することによって、その結果として生じる大きな行列は、パラメータの数(自由度)を変更することに関連し得る、そのため、パフォーマンスと速度のトレードオフを制御することが容易になる。第4には、大きな行列の空間複雑度は、大抵の他の構造化行列ではO(d)なるのにと比較してO(log d)となる。加えて、提案するクロネッカー射影は、例えば、バイナリ埋め込みおよびベクトル量子化を含む、様々な異なる設定の下での近似最近傍探索問題において利点を提供する。
【００５６】
バイナリ埋め込みの方法は、h(x)∈{+1、-1}kとなるように元のベクトルをkビットのバイナリベクトルにマッピングし得る。そのようなマッピングは、バイナリコードとしてデータ点の表現を利用し得る、それによって、k=O(d)である場合でさえストレージコストを著しく低減している。近似最近傍は、例えば、テーブルルックアップの使用、または最新のコンピュータ機構におけるPOPCNT命令などといった様々な方法で極めて効率的に計算され得るバイナリコード空間におけるハミング距離を使用して、検索され得る。
【００５７】
LSHは、コサイン距離を保ち、ランダム射影を通常は使用してバイナリコードを生成する方式で、バイナリコードを生成するために使用され得る。しかしながら、そのようなランダム射影を使用することは、射影行列Rを最適化することによってデータ依存のバイナリコードを学習する長所を捨てることになり得る。例として、Iterative Quantization(ITQ)を利用する方法は、学習した直交射影の後にPCA射影を使用することによって、その結果生じるバイナリ埋め込みが非直交またはランダム直交射影を上回り得ることを示す。射影は、データ点を射影することとSVDを用いた射影について解くこととの間で相互に入れ替えることによって学習され得る。しかしながら、高次元特徴については、そのようなアプローチは、次元が根本的に削減されない限り実行不可能となり得るし、このことは、パフォーマンスを損なうことになる。クロネッカー積で学習した射影を容易にする本開示の態様を利用することは、ITQと同様のパフォーマンス性能をもたらす一方で、実質的により効率的なものとなっている。
【００５８】
量子化方法は、例えば、k-meanアルゴリズムなどのベクトル量子化アルゴリズムによって通常は取得され得る、量子化器のセットを用いて、データ点を表し得る。所与のクエリベクトルqの最近傍を探索するために、qとデータベース内のすべてのデータ点との間のユークリッド距離が計算され得る。ユークリッド距離は、ベクトル-量子化器(vector-to-quantizer)距離によって近似され得る。あるいは、または、加えて、データが高次元である場合には、量子化が、独立してサブ空間において実行され得る。一般的に使用されるサブ空間は、直積量子化(PQ)をもたらし得るベクトルをチャンキングすることによって、識別され得る。
【００５９】
クエリベクトルqとデータベースの点xとの間の距離を、式(4)に関して示し得る。
【００６０】
【数３】
0006469890.tif 000004
【００６１】
式(4)において、mは、サブ空間の総数であり、x(i)およびq(i)は、サブベクトルであり、μi(x(i))は、サブ空間iにおける量子化関数である。その非対称性の特質により、データベースの点のみが量子化され、クエリベクトルは量子化されない。パフォーマンスを増大するために、異なるサブ空間は、所与のデータについて類似した分散を有する。このことを実現する1つの方法は、式(5)に記載しているように、直交変換Rをデータに適用することである。
【００６２】
【数４】
0006469890.tif 000005
【００６３】
射影行列Rは直交性があるため、射影行列Rはユークリッド距離を保ち得る。ランダム射影行列を使用する代わりに、射影行列は、改善された検索結果をもたらす所与のデータから学習され得る。しかしながら、本開示以前に存在する射影演算を容易にするための方法は、高次元空間においては、例えば、プロセッサ使用量、メモリ使用量、実行時間などといった、高いリソースコストに関連し得る。
【００６４】
それゆえ、少なくとも上述した理由により、バイナリ埋め込みおよび量子化の双方については、直交的および効率的の双方で学習可能な高速射影が必要となる。後述しているように、本目的は、各要素行列の各々に関連付けられた関係を保つ変換アルゴリズムを使用して、一連の要素行列を大きな構造化行列に変換することによって実現され得る。変換アルゴリズムは、射影を生成するために、例えば、とりわけ、クロネッカー積の利用を含み得る。
【００６５】
クロネッカー積は、前述の変換を容易にするプロパティの数に関連し得る。例として、
【数５】
0006469890.tif 000006
、および
【数６】
0006469890.tif 000007
であるとする。A1およびA2のクロネッカー積は、式(6)を満足する
【数７】
0006469890.tif 000008
である。
【００６６】
【数８】
0006469890.tif 000009
【００６７】
式(6)において、a1(i,j)は、A1のi番目の行かつj番目の列の要素である。クロネッカー積は、テンソル積または直積とも称され得る。演算行列(x,a,b)は、d次元ベクトルをa×bの行列(ab=d)に変形し得るし、vec(・)は、行列をベクトルに「ストレッチする」ことによってベクトルを形成し得るし、vec(mat(x,a,b))=xである。
【００６８】
クロネッカー積は、本明細書に記載の利点を容易にする複数の特性と関連し得る。例として、少なくともこれらの特性のサブセットは、高速直交射影の生成に役立つし、元の要素行列に関連付けられた関係を保つのにも役立つ。前述の利点を容易にするクロネッカー積の2つの特定の特性は、
【数９】
0006469890.tif 000010
と、クロネッカー積が要素行列の直交性を保つという事実とを含む。すなわち、A1およびA2の双方が直交である場合には、
【数１０】
0006469890.tif 000011
も直交である。
【００６９】
本開示の少なくとも1つの態様に従って、クロネッカー射影行列R∈Rk×dは、式(7)に記載しているように、いくつかの要素行列のクロネッカー積を含み得る。
【００７０】
【数１１】
0006469890.tif 000012
【００７１】
式(7)において、
【数１２】
0006469890.tif 000013
であり、
【数１３】
0006469890.tif 000014
および
【数１４】
0006469890.tif 000015
を満たす。
【００７２】
このように大きな行列を形成する1つの利点は、クロネッカー射影の計算が低減された計算複雑度を巧みに利用できることにある。説明を簡潔にするために、行列Rが、正方、すなわち、k=dであり、すべての要素行列も、同一の次数deを有する正方であると仮定する。浮動小数点演算(FLOPs)は、異なる方法の計算コストを正確に評価する。次数deの要素行列を用いた、d次元ベクトル上へのクロネッカー射影を計算するためのFLOPsをf(d,de)とする。クロネッカー積の1つのプロパティを以下の式(8)に示す。
【００７３】
【数１５】
0006469890.tif 000016
【００７４】
mat(x,d/de,de)A1Tを行うには、d(2de-1)FLOPs(dde回の乗算およびdde-d回の加算)が必要になる。その後、
【数１６】
0006469890.tif 000017
の計算は、式(9)に反映されるような、各々が特徴次元d/deおよび次数deの要素行列を有するクロネッカー射影を計算する、de個のより小さなスケールの問題となる。
f(d,de)=d(2de-1)+def(d/de,de)    (9)
【００７５】
式(9)に基づけば、d次元ベクトルのクロネッカー射影を行う際のFLOPsは、
【数１７】
0006469890.tif 000018
となる。
【００７６】
本明細書に記載の利点を容易にすることに役立つクロネッカー射影のもう一つの魅力的な特性は、その構造のフレキシビリティにある。例として、Aj、j=1,...,Mのサイズを制御することによって、モデルのパラメータの数(すなわち、容量)と計算コストとのバランスを容易に取れることになり得る。各がde2個のパラメータを有する、
【数１８】
0006469890.tif 000019
個の要素行列が存在する。クロネッカー射影におけるパラメータの数は、
【数１９】
0006469890.tif 000020
であり、その範囲は、d2(de=dのとき)から4log2d(de=2のとき)までである。
【００７７】
以上のように、本開示は、クロネッカー射影Rとすべての要素行列とが正方である例を参照して説明してきた。しかしながら、本開示はそのことに限定される必要はない。その代わりに、例えば、本開示はまた、非正方クロネッカー射影および/または非正方要素行列に拡張し得る。例として、要素行列のサイズを、dおよびkを因数分解することによって選択してもよい。あるいは、または、加えて、dまたはkを小数の積として因数分解することができない事例が生じる場合がある。例えば、入力特徴に対して、ゼロをサブサンプリングまたはサンプリングすることによって次元を変更してもよい。独立して、例えば、出力に対して、より長いコードを使用してサブサンプリングしてもよい。クロネッカー射影の生成を、正方射影行列Rおよび非正方射影行列の双方の状況について以下にさらに説明する。
【００７８】
非構造化射影、巡回射影(circulant projection)、および/または双線形射影(bilinear projection)などと類似した方式においては、クロネッカー射影はまた、ランダムに生成され得る。しかしながら、ランダムに生成したクロネッカー射影は、高次元データに適しているため、射影の上述したリスト化を改善する。
【００７９】
ランダムクロネッカー射影は、バイナリ埋め込みおよび量子化に適用され得る。クロネッカー射影のそのような適用は、非構造化射影行列(式(1)および式(5)におけるR)をランダムクロネッカー射影行列と置換することによって実現され得る。
【００８０】
例として、クロネッカー射影に関して、本明細書に記載の方法、システム、およびコンピュータプログラムは、M個の(小さい)直交要素行列を生成し得る。本開示の少なくとも1つの態様においては、要素行列は、小さなランダムガウシアン行列を作成し、その後QR分解を行うことによって生成され得る。サイズが2×2の要素行列については、例えば、次数dのランダムクロネッカー射影を生成する時間複雑度は、O(log d)のみである。このことは、例えば、時間複雑度O(d3)を有する次数dの直交行列の非構造化射影の生成のために、著しい利点となる。それゆえ、ランダムクロネッカー射影は、高次元データのためのランダム射影を生成するための実用的なソリューションを提供している。
【００８１】
本開示の別の態様による、クロネッカー射影パラメータを最適化するシステムおよび方法を開示している。以下により詳細に説明しているように、最適化アルゴリズムを、バイナリ埋め込みおよび量子化に関して記載しており、双方を、各要素行列に関する直交プロクラステス問題を解決するように定式化し得ることを示している。この説明を目的として、X=[x1,x2,...,xN]∈Rd×Nのデータを訓練すると仮定する。まずk=dであると仮定して個別に以下に説明をしており、k≠dの場合についてのソリューションはその後その説明を拡張する。
【００８２】
まず、バイナリ埋め込みに関する二値化ロスを最小化する問題を取り上げる。最適化問題は、式(10)に示したように表され得る。
【００８３】
【数２０】
0006469890.tif 000021
【００８４】
式(10)において、バイナリ行列B=[b1,b2,...,bN]∈{-1,1}d×Nであり、biは、xiのバイナリコードである、すなわち、bi=sign(Rxi)である。加えて、クロネッカー構造は、Rとする。式(3)の局所解は、最小化を代替することによって求まり得る。Rが固定されている場合には、Bは、定義に基づいた直接的な二値化によって計算される。あるいは、Bが固定されており、k=d(k<dのケースは後述する)である場合については、Rは、式(11)
【数２１】
0006469890.tif 000022
に記載した直交プロクラステス問題によって求まる。
【００８５】
次に、量子化に関して、デカルトK-Mean(ck-mean)法を考慮する。ck-meanについては、入力サンプルxは、m個のサブ空間、x=[x(1);x(2);...;x(m)]に分割され、各サブ空間は、h個のサブセンターに量子化され得る。後述した例によれば、すべてのサブセンターセットが同一の一定の濃度を有しているとシナリオを考慮する。しかしながら、本開示はそのことに限定される必要はない。例として、本開示を、様々な濃度を有するサブセンターセットについても同様の方式で適用してもよい。
【００８６】
p=[p(1);p(2);...;p(m)]、ここで、
【数２２】
0006469890.tif 000023
であるとする。換言すれば、p(j)は、どのサブセンターx(j)が最も近いかを示している。式(12)に記載しているように、C(j)∈Rd×hが、第jのサブセンター行列であり、C∈Rd×mhが、すべてのサブセンターの(対角方向の)連結によって形成される、センター行列であるとする。
【００８７】
【数２３】
0006469890.tif 000024
【００８８】
ck-meanにおいて、センター行列Cは、直交行列R∈Rd×dおよびブロック対角行列D∈Rd×mhによってパラメータ化される。ck-meanの最適化問題を、式(13)のように記載してもよい。
【００８９】
【数２４】
0006469890.tif 000025
【００９０】
クロネッカー構造を類似の代替の手順を用いる直交行列Rする。Rが固定されている場合には、DおよびPの更新は、k-meanを用いた各サブ空間におけるベクトル量子化と等しくなり得る。前述したアプローチは、各サブ空間についてのクラスタの数が常に小さな数(例えば、h=256)に設定されることによりセンターの数が通常は小さくなるため、効率的である。固定されたDおよびPを用いてRの更新は、式(1)に反映されるような、直交プロクラステス問題としてアプローチされてもよい。
【００９１】
【数２５】
0006469890.tif 000026
【００９２】
それゆえ、上述した双方のアプローチについて、直交プロクラステス問題が生じ得る。クロネッカー積および/または射影を用いる開示の態様については、前記問題は、クロネッカープロクラステスとも称され得る。クロネッカープロクラステスを、式(15)に関して以下のように示してもよい。
【００９３】
【数２６】
0006469890.tif 000027
【００９４】
上記最適化を解決するために、各要素行列を更新して局所解を順次求めるためにイテレーティブな方法を使用してもよい。前記方法は、式(16)のように
【数２７】
0006469890.tif 000028
を書き換えることによって開始してもよい。
【００９５】
【数２８】
0006469890.tif 000029
【００９６】
クロネッカー積が直交性を保ち得るため、第2の等式が成り立つ。そのため、次のステップは、
【数２９】
0006469890.tif 000030
を最大化することになり得る。トレースのプロパティを使用して、式(17)のように表され得る。
【００９７】
【数３０】
0006469890.tif 000031
【００９８】
式(17)において、biおよびxiは、それぞれ行列Bおよび行列Xのi番目の列である。本問題は、他のすべてを固定したままで、同時に1つの要素行列を更新することによって解決され得る。一般性を失うことなく、式(18)に示したようにAを更新することを考慮している。
【００９９】
【数３１】
0006469890.tif 000032
【０１００】
式(18)において、
【数３２】
0006469890.tif 000033
であり、
【数３３】
0006469890.tif 000034
である。Apre、Anext、およびAjの次元が、それぞれ、kpre×dpre、knext×dnext、およびkj×djであるとする。また、dpredjdnext=dおよびkprekjknext=kであるとする。
【０１０１】
クロネッカー積に関連付けられた特性に従って、式(18)内の目的関数Ajは、以下を満足する。
【０１０２】
【数３４】
0006469890.tif 000035
【０１０３】
Gi=mat(xi,djdnext,dpre)ApreTであり、Fi=mat(bi,kjknext,kpre)ApreTであるとする。その結果、式(19)を以下のように表すことができる。
【０１０４】
【数３５】
0006469890.tif 000036
【０１０５】
1つの要素行列を更新する際に、計算コストは、3つの異なる要因に由来し得る。第1の要因、ここではS1と称する、は、固定された要素行列を用いてデータのクロネッカー射影を計算することに起因する。第2の要因、ここではS2と称する、は、射影したデータおよびコードの積を計算することに起因する。第3の要因、ここではS3と称する、は、直交要素行列を得るためにSVDを行うことに起因する。要素行列が大きくなり得る場合については、最適化ボトルネックは、SVDであり得る。あるいは、要素行列が、例えば、2×2などのように、小さくなり得る場合については、SVDの実行を、ほぼ一定の時間内に実現することができる。したがって、主な計算コストは、S1(O(Ndlog d))およびS2(O(Nd))に由来する。合計
【数３６】
0006469890.tif 000037
個の要素行列が存在するため、最適化全体の計算複雑度は、O(Ndlog2d)である。
【０１０６】
前述の最適化において、ランダムクロネッカー射影は、初期化として使用されていた。バイナリ埋め込みおよび量子化については、対象は、提案した手順に基づいて高速に減少され得る。満足のいく解が、10回のイテレーションのうちに求まり得る。
【０１０７】
上述したアプローチは、k=dであるシナリオに基づいて説明した。しかしながら、本開示の態様を、k≠dであるシナリオについても利用してもよい。k≠dである場合については、射影行列Rは、非正方行/列直交要素行列のクロネッカー積によって形成され得る。そのような場合には、クロネッカー積は、行/列の直交性を保ち得る。例えば、k>dである場合には、直交プロクラステス最適化問題を、k=dである場合と同様に解き得る。あるいは、例えば、k<dである場合には、RTR≠Iである。したがって、式(16)における第2の等式は成り立たない。それゆえ、
【数３７】
0006469890.tif 000038
は、以下のようになる。
【０１０８】
【数３８】
0006469890.tif 000039
【０１０９】
問題は、k≧dのケースと同様に、tr(XTRTRX)がRと独立していると仮定することによって、緩和され得る。
【０１１０】
本明細書で説明したシステムおよび技法の様々な実施形態を、デジタル電子回路、集積回路、専用ASIC(特定用途向け集積回路)、コンピュータハードウェア、ファームウェア、ソフトウェア、および/またはその組合せで実現してもよい。これらの様々な実施形態は、ストレージシステム、少なくとも1つの入力デバイス、および少なくとも1つの出力デバイスからデータおよび命令を受信するとともに、ストレージシステム、少なくとも1つの入力デバイス、および少なくとも1つの出力デバイスにデータおよび命令を送信するように接続されている、専用または汎用であり得る、少なくとも1つのプログラマブルプロセッサを備えるプログラマブルシステム上で実行可能および/またはインタープリタ処理可能な1つまたは複数のコンピュータプログラムにおける実施形態を含み得る。
【０１１１】
これらのコンピュータプログラム(プログラム、ソフトウェア、ソフトウェアアプリケーションまたはコードとしても知られる)は、プログラマブルプロセッサのためのマシン命令を含み、ハイレベル手続き型および/またはオブジェクト指向型プログラミング言語、および/またはアセンブリ/マシン言語で実装され得る。本明細書で使用されており、「機械可読媒体」および「コンピュータ可読媒体」という用語は、機械可読信号としてマシン命令を受信する機械可読媒体を含む、プログラマブルプロセッサにマシン命令および/またはデータを提供するために使用される、任意のコンピュータプログラム製品、装置、および/またはデバイス(例えば、磁気ディスク、光ディスク、メモリ、プログラマブルロジックデバイス(PLD))を指す。「機械可読信号」という用語は、プログラマブルプロセッサにマシン命令および/またはデータを提供するために使用される、任意の信号を指す。
【０１１２】
ユーザとのインタラクションを提供するために、本明細書で説明したシステムおよび技法を、ユーザに情報を表示するための表示デバイス(例えば、CRT(陰極線管)またはLCD(液晶ディスプレイ)モニタ)と、ユーザがそれによって入力をコンピュータに提供し得るキーボードならびにポインティングデバイス(例えば、マウスまたはトラックボール)とを有するコンピュータ上で実施してもよい。他の種類のデバイスを、ユーザとのインタラクションを提供するために同様に使用してもよい。例えば、ユーザに提供されるフィードバックが、任意の形式の感覚フィードバック(例えば、視覚フィードバック、聴覚フィードバック、または触覚フィードバック)であってもよいし、ユーザからの入力を、音響、音声、または触覚入力を含む、任意の形式で受信してもよい。
【０１１３】
本明細書で説明したシステムおよび技法を、(例えば、データサーバといった)バックエンドコンポーネントを含む、または、ミドルウェアコンポーネント(例えば、アプリケーションサーバ)を含む、または、フロントエンドコンポーネント(例えば、ユーザがそれを介して本明細書で説明したシステムおよび技法の実施形態とやりとりする、グラフィックユーザインターフェースもしくはウェブブラウザを有するクライアントコンピュータ)、または、そのようなバックエンド、ミドルウェア、またはフロントエンドコンポーネントの任意の組合せを含む、コンピューティングシステム内で実施してもよい。システムのコンポーネントは、デジタルデータ通信の任意の形式または媒体(例えば、通信ネットワーク)で相互接続され得る。通信ネットワークの例としては、ローカルエリアネットワーク(「LAN」)、ワイドエリアネットワーク(「WAN」)、およびインターネットを含む。
【０１１４】
コンピューティングシステムは、クライアントおよびサーバを含み得る。クライアントおよびサーバは、一般的に互いにリモートに存在しており、通信ネットワークを介して通常はやりとりする。クライアントとサーバとの関係は、それぞれのコンピュータ上で動作するとともに互いにクライアントサーバ関係を有するコンピュータプログラムによって生じる。
【０１１５】
本開示はいくつかの具体例を含んでいるが、これらを、開示の例示的な実施形態の特徴の説明としてではなく、開示の範囲または特許請求の範囲の限定として、解釈すべきではない。別個の実施形態に関連する本開示において説明したある特徴を、単一の実施形態における組合せで提供することもできる。反対に、単一の実施形態に関連して説明した様々な特徴を、複数の実施形態で別々に、または、任意の適切なサブコンビネーションで提供することもできる。さらに、特徴をある組合せで動作するように上述しているとしても、たとえそのようにはじめは主張していたとしても、いくつかのケースでは、主張した組合せのうちの1つまたは複数の特徴を組合せから削除し得るし、主張した組合せをサブコンビネーションまたはサブコンビネーションのバリエーションを対象とし得る。
【０１１６】
同様に、処理を特定の順序で図面に図示しているが、このことを、望ましい結果を実現するためには、図示した特定の順序でもしくはシーケンシャルな順序でそのような処理を行う必要がある、または、図示した処理をすべて行う必要がある、と理解すべきではない。ある状況においては、マルチタスク処理およびパラレル処理が有利となり得る。さらに、上述した実施形態における様々なシステムコンポーネントの分離がすべての実施形態におけるそのような分離が必要であると理解すべきではないし、説明したプログラムコンポーネントおよびシステムを単一のソフトウェア製品に一緒に統合することまたは複数のソフトウェア製品にパッケージすることが一般的にできることを理解されたい。
【０１１７】
発明特定事項の特定の実施形態を説明してきた。他の実施形態も特許請求の範囲の範囲内にある。例えば、特許請求の範囲に記載したアクションは、異なる順序で実施され得るし、さらに望ましい結果を実現し得る。記載したフローから、他のステップを提供してもよいし、ステップを削除してもよく、他のコンポーネントを記載したシステムに加えても除去してもよい。いくつかのケースでは、マルチタスク処理およびパラレル処理が有利となり得る。
【符号の説明】
【０１１８】
100  システム
110  クライアント
111  プロセッサ
112  メインメモリ
113  ブラウザ
114  モバイルアプリケーション
115  DB
120  サーバ
121  プロセッサ
122  メインメモリ
123  コンテンツ識別ユニット
124  特徴抽出ユニット
125  特徴ベクトル生成ユニット
126  要素行列生成ユニット
127  構造化行列生成ユニット
128  最適化された探索空間ストレージエリア
129  DB
130  リモートコンピュータ
131  プロセッサ
132  メモリ
133  DB
300  システム
310  クライアント
311  プロセッサ
312  メインメモリ
313  コンテンツ識別ユニット
314  特徴抽出ユニット
315  特徴ベクトル生成ユニット
316  要素行列生成ユニット
317  構造化行列生成ユニット
318  最適化された探索空間ストレージエリア
319  DB
320  サーバ
321  プロセッサ
322  メインメモリ
330  リモートコンピュータ
331  プロセッサ
332  メモリ
333  DB
340  ネットワーク
【図１】
0006469890.tif 000040
【図２】
0006469890.tif 000041
【図３】
0006469890.tif 000042
【図４】
0006469890.tif 000043