"意味解釈のために1つまたは複数のキーワードを取得するステップと、知識データベース内にある、前記1つまたは複数のキーワードに関する上位k個の概念を計算するステップと、前記上位k個の概念を用いて、前記1つまたは複数のキーワードを概念空間にマッピングするステップと、を含むキーワードの意味解釈を行う方法。上位k個の概念を計算する前記ステップは、入力行の数の限界を推定することと、完全に見えないオブジェクトまたは部分的に見えないオブジェクトの予測スコアを計算することを含む請求項1に記載の方法。意味解釈のために1つまたは複数のキーワードを取得する前記ステップは、コンテンツと共に含まれたクローズドキャプションデータからキーワードを抽出することを含む請求項1に記載の方法。前記1つまたは複数のキーワードを概念空間にマッピングするステップによって得られる概念をさらに処理することを含む請求項1に記載の方法。前記処理は、概念の順位付けを含む請求項4に記載の方法。前記処理は、前記得られる概念に基づいてユーザプロファイルを作成することを含む請求項4に記載の方法。前記処理は、前記得られる概念に基づいて分割されたコンテンツを作成することを含む請求項4に記載の方法。前記処理は、前記得られる概念に基づいてフィルタリングすることを含む請求項4に記載の方法。前記処理は、前記得られる概念に基づいて検索することを含む請求項4に記載の方法。キーワード収集と、概念収集と、概念処理と、を含むキーワードの意味解釈を行うシステム。キーワード収集は、クローズドキャプション抽出部と、文分割部とを含む請求項10に記載のシステム。概念収集は、意味解釈部と、概念蓄積部と、を含む請求項10に記載のシステム。概念処理は、順位付けと、ユーザプロファイルと、を含む請求項10に記載のシステム。コンピュータ可読プログラムを有するコンピュータが使える媒体を含むコンピュータプログラム製品であって、前記コンピュータ可読プログラムは、コンピュータで実行されて、前記コンピュータに、意味解釈のための1つまたは複数のキーワードを取得するステップと、知識データベース内にある、前記1つまたは複数のキーワードに関する上位k個の概念を計算するステップと、前記上位k個の概念を用いて、前記1つまたは複数のキーワードを概念空間にマッピングするステップと、を含む方法を行わせるコンピュータプログラム製品。本原理は、コンテンツ検索に関し、より詳細には、Top-k技術を用いた検索に使用するキーワードの意味解釈に関する。本明細書に明示されていないが、本発明の精神および範囲内で本発明を実現する様々な形態を当業者が考案することは当然である。本明細書に記載の全ての例および条件を示す文言は、本発明と、本発明者が技術を進めるために提供した概念とを読者が理解することを助けるためのものであり、具体的に記載された例および条件には限定されないと解釈されたい。さらに、本発明の原理、態様、実施形態に関する本明細書中の記載の全て、および、具体的な例は、その構造的等価物および機能的等価物を包含する。また、このような等価物は、現在知られている等価物と、将来、開発される等価物、すなわち、構造にかかわらず、同じ機能を果たす、任意の開発される要素を含む。従って、例えば、本明細書に示すブロック図は、本発明を実現する例証的な回路を概念的に表したものであることを、当業者は理解されよう。同様に、フローチャート、フロー図、状態遷移図、疑似コードなどは、実質的にコンピュータ可読媒体に表され、コンピュータまたはプロセッサコンピュータ、プロセッサが明示的に示されていてもいなくてもによって実行される様々なプロセスを表すことは、理解されたい。図に示される様々な要素の機能は、専用ハードウェア、および適切なソフトウェアと共同してソフトウェアを実行することができるハードウェアの使用によって、提供してよい。機能がプロセッサによって提供される場合、単一の専用プロセッサ、単一の共用プロセッサ、または、複数の個々のプロセッサで提供してよく、個々のプロセッサの一部は共用されてよい。さらに、プロセッサまたは制御装置という用語の明示的使用は、ソフトウェアを実行することができるハードウェアのみを指すのではなく、デジタル信号プロセッサDSPハードウェア、ソフトウェアを記憶するためのリードオンリメモリROM、ランダムアクセスメモリRAM、不揮発性記憶装置を暗に含むが、それらに限定されない。他のハードウェア、つまり、従来のハードウェアおよび/またはカスタムメイドのハードウェアも含まれてよい。同様に、図に示されているスイッチは、概念的なものにすぎない。その機能は、プログラム論理演算を通して、専用論理で、プログラム制御と専用論理の対話を通して、または、手動で、実行されてよく、文脈からより詳細に理解できるように、実施者が特定の技術を選択することができる。本出願の請求項においては、特定の機能を行う手段として表されている要素は全て、例えば、aその機能を行う回路素子の組み合わせ、または、bファームウェア、マイクロコードなどの任意の形態のソフトウェアと、そのソフトウェアを実行して機能を提供するための適切な回路構成との組み合わせなど、その機能を行う任意の方法を含むものとする。このような請求項で定義される本発明は、記載した様々な手段が提供する機能を、請求項が要求する方法で、組み合わせ、まとめるということにある。従って、これらの機能を提供することができるいかなる手段も、本明細書に記載のものと等価であるとみなされる。本明細書において、本発明の一実施形態または実施形態、およびそれらの変更形態に言及することは、その実施形態に関連して記載された特定の機能、構造、特徴などは、本発明の少なくとも1つの実施形態に含まれることを意味する。従って、本明細書の様々な箇所に書かれた、一実施形態においてまたは実施形態においてというフレーズ、および、任意の他の変更形態は、必ずしも、全て、同一の実施形態を指しているわけではない。図1を参照すると、ホームユーザまたはエンドユーザにコンテンツを配信するシステム100の実施形態のブロック図が示されている。コンテンツは、映画スタジオや製作会社などのコンテンツソース102から来ている。コンテンツは、2つの形態の少なくとも1つの形式で、供給されてよい。1つは、コンテンツを放送する形態であってよい。放送コンテンツは放送管理者104に提供される。放送管理者104は、典型的にはABC放送AmericanBroadcastingCompany、NBCNationalBroadcastingCompany、コロンビア放送CBSなどの、全国的な放送サービスである。放送管理者は、コンテンツを集めて、記憶し、配信ネットワーク1106として示す配信ネットワークを介して、コンテンツの配信をスケジュールしてよい。配信ネットワーク1106は、全国的なセンターから1つまたは複数の地域センターまたはローカルセンターへの衛星通信を含んでよい。配信ネットワーク1106は、地上波放送、衛星放送、またはケーブル放送などのローカル配信システムを用いて、ローカルのコンテンツ配信を含んでよい。ローカルに配信されたコンテンツは、ユーザの家庭にある受信装置108に提供され、次に、ユーザはそのコンテンツを検索する。受信装置108は、多くの形態をとってよく、セットトップボックス/デジタルビデオレコーダDVR、ゲートウェイ、モデムなどとして実現してよいことを理解されたい。また、受信装置108は、ホームネットワーク内でクライアント装置またはピアデバイスとして構成された追加の装置を含むホームネットワークシステムのエントリポイントまたはゲートウェイの機能を果たしてもよい。コンテンツの第2の形態は、スペシャルコンテンツと呼ばれる。スペシャルコンテンツは、映画、テレビゲームまたは他の映像要素などの、プレミアムビュー、ペイパービュー、または、放送管理者に提供されない他のコンテンツとして配信されるコンテンツを含んでよい。多くの場合、スペシャルコンテンツは、ユーザのリクエストによって配信されるコンテンツであってよい。スペシャルコンテンツは、コンテンツマネージャ110に配信されてよい。コンテンツマネージャ110は、例えば、コンテンツプロバイダ、放送サービス、または、配信ネットワークサービスと提携している、インターネットウェブサイトなどのサービスプロバイダであってよい。コンテンツマネージャ110は、インターネットのコンテンツを配信システムに組み込んでもよい。コンテンツマネージャ110は、別個の配信ネットワーク、すなわち、配信ネットワーク2112を介して、コンテンツをユーザの受信装置108に配信してよい。配信ネットワーク2112は、高速ブロードバンドインターネット型の通信システムを含んでよい。放送管理者104からのコンテンツも、配信ネットワーク2112の全てまたは一部を用いて配信してもよく、コンテンツマネージャ110からのコンテンツも、配信ネットワーク1106の全てまたは一部を用いて配信してよいことに注目することは重要である。さらに、ユーザは、コンテンツマネージャ110に必ずしもコンテンツを管理させずに、配信ネットワーク2112を介してインターネットから直接コンテンツを得てもよい。別個に配信されたコンテンツを利用するための適合方法が幾つか考えられる。可能な方法の1つは、放送コンテンツを拡張させるものとして、スペシャルコンテンツを提供し、代替の表示を行ったり、購入や販売促進の選択肢を提供したり、拡張材料などを提供することである。別の実施形態においては、スペシャルコンテンツが、放送コンテンツとして提供された番組内容に完全に置き換わってよい。最後に、スペシャルコンテンツは、放送コンテンツから完全に切り離し、単に、ユーザが選択して利用可能な代替媒体としもよい。例えば、スペシャルコンテンツは、放送コンテンツとしてはまだ視聴できない映画のライブラリであってよい。受信装置108は、配信ネットワーク1および配信ネットワーク2の片方または両方から、異なった種類のコンテンツを受信してよい。受信装置108は、ユーザ選択やユーザ命令に基づいて、コンテンツを処理し、コンテンツの分離を行う。受信装置108は、音声コンテンツおよび映像コンテンツを記録、再生するための、ハードドライブまたは光ディスクドライブなどの記憶装置も含んでよい。受信装置108の操作と記憶されたコンテンツの再生に関する機能は、図2を参照しながら、さらに詳細に後述する。処理されたコンテンツは、主表示装置114に供給される。主表示装置114は、従来の2-Dディスプレイであっても、進化した3-Dディスプレイであってもよい。受信装置108は、第2の画面制御装置などの第2の画面、例えば、タッチスクリーン制御装置116にインタフェースをとってよい。第2の画面制御装置116は、受信装置108および/または表示装置114をユーザが制御できるように適合されてよい。第2の画面装置116は、映像コンテンツを表示できるようにしてもよい。映像コンテンツは、ユーザインタフェース入力などのグラフィックス入力でもよく、表示装置114に配信される映像コンテンツの一部でもよい。第2の画面制御装置116は、赤外線IR通信または無線周波数RF通信などの任意の周知の信号伝送システムを用いて、受信装置108にインタフェースを取ってよく、赤外線通信協会IRDA規格、Wi-Fi、ブルートゥースなどの標準プロトコル、または任意の他の独自のプロトコルを含んでよい。タッチスクリーン制御装置116の操作については、下記にさらに詳しく述べる。図1の例においては、システム100は、バックエンドサーバ118と利用データベース120も含む。バックエンドサーバ118は、ユーザの使用習慣を分析して、その使用習慣に基づいて推薦を行うパーソナライズエンジンを含む。利用データベース120は、ユーザの使用習慣を記憶する場所である。一部の例では、利用データベース120は、バックエンドサーバ118の一部であってよい。本例においては、バックエンドサーバ118及び利用データベース120は、システム100に接続され、配信ネットワーク2112を介してアクセスされる。図2を参照すると、受信装置200の実施形態のブロック図が示されている。受信装置200は、図1に示す受信装置と同様に動作してよく、ゲートウェイ装置、モデム、セットトップボックス、または他の類似の通信装置の一部として含まれてよい。図示の受信装置200は、音声装置または表示装置を含む他のシステムに組み込んでもよい。どちらの場合においても、システムが完全に動作するために必要な数個のコンポーネントは、当業者には周知であるため、簡潔さを優先して図示していない。図2に示す受信装置200においては、コンテンツは、入力信号受信機202によって受信される。入力信号受信機202は、地上波、ケーブル、衛星、イーサネット登録商標、ファイバー線、および、電話回線のネットワークを含む可能な数種類のネットワークの1つを介して供給される信号を、受信し、復調し、復号するために用いられる幾つかの既知の受信機回路の1つであってよい。制御インタフェース222を介して供給されたユーザ入力に基づいて、入力信号受信機202が、望ましい入力信号を選択し、回収してよい。制御インタフェース222は、タッチスクリーン装置のインタフェースを含んでよい。タッチパネルインタフェース222は、携帯電話、タブレット、マウス、ハイエンドリモコンなどへのインタフェースに適合されてもよい。復号された出力信号は、入力ストリームプロセッサ204に供給される。入力ストリームプロセッサ204は、最終的な信号選択と処理を行い、コンテンツストリームのために声コンテンツから映像コンテンツを分離することを含む。音声コンテンツは、圧縮デジタル信号などの受信フォーマットからアナログ波形信号に変換するために、音声プロセッサ206に供給される。アナログ波形信号は、音声インタフェース208に供給され、さらに、表示装置または音声増幅器に供給される。あるいは、音声インタフェース208は、高精細度マルチメディアインタフェースHDMIケーブルまたはソニー/フィリップスデジタルインターコネクトフォーマットSPDIFなどの他の音声インタフェースを用いて、デジタル信号を音声出力装置または表示装置に供給してよい。音声インタフェースは、さらに一組のスピーカを駆動する増幅器を含んでもよい。音声プロセッサ206は、音声信号を記憶するために必要な変換も行ってよい。入力ストリームプロセッサ204からの映像出力は、映像プロセッサ210に供給される。映像信号は、数種のフォーマットのうちの1つであってよい。映像プロセッサ210は、必要があれば、入力信号フォーマットに基づいて、映像コンテンツを変換する。映像プロセッサ210は、映像信号を記憶するために必要な変換も行う。記憶装置212は、入力で受信した音声コンテンツ、映像コンテンツを記憶する。記憶装置212によって、制御装置214の制御の下で、ユーザインタフェース216および/または制御インタフェース222から受信した命令、例えば、早送りFFや巻き戻しRewなどの操作指示に基づいて、記憶したコンテンツを後に検索したり、再生したりすることが可能になる。記憶装置212は、ハードディスクドライブや、スタティックRAMSRAMまたはダイナミックRAMDRAMなどの1つまたは複数の大容量の集積電子メモリであってよく、コンパクトディスクCDドライブまたはデジタル多用途ディスクDVDドライブなどの交換可能な光ディスク記憶装置であってよい。変換された映像信号は、入力によるものでも、記憶装置212からのものでも、映像プロセッサ210からディスプレイインタフェース218に供給される。ディスプレイインタフェース218は、さらに、上述の表示装置に表示信号を供給する。ディスプレイインタフェース218は、RGB赤、緑、青インタフェース等のアナログ信号インタフェースであってもよく、HDMI等のデジタルインタフェースであってもよい。ディスプレイインタフェース218は、より詳しく後述するように、3次元グリッドで検索結果を示す様々な画面を生成することを理解されたい。制御装置214は、入力ストリームプロセッサ202、音声プロセッサ206、映像プロセッサ210、記憶装置212、およびユーザインタフェース216を含む、受信装置200のコンポーネントの幾つかにバスを介して相互接続される。制御装置214は、入力ストリーム信号を、記憶装置に記憶するための、または、表示するための信号に変換する変換プロセスを管理する。制御装置214は、記憶されたコンテンツの検索および再生も管理する。さらに、後述するように、制御装置214は、コンテンツを検索し、記憶、または、上述の配信ネットワークを介して配信するために、そのコンテンツを表すグリッド表示を、作成、調整する。制御装置214は、制御装置214に関する情報および命令コードを記憶するために、さらに、制御メモリ220例えば、RAM、SRAM、DRAM、ROM、プログラマブルROMPROM、フラッシュメモリ、電気的プログラマブルROMEPROM、電気的消去可能プログラマブルROMEEPROMなどの揮発性または不揮発性メモリに接続される。制御メモリ220は、制御装置214に関する指示を記憶してよい。制御メモリは、コンテンツを含むグラフィック要素などの要素のデータベースも記憶してよい。データベースは、グラフィック要素のパターンとして記憶されてよい。あるいは、メモリは、識別されたまたはグループ化されたメモリ位置にグラフィック要素を記憶し、アクセステーブルまたは位置テーブルを用いてグラフィック要素に関する情報の様々な部分のメモリ位置を識別してよい。グラフィック要素の記憶装置に関しては、さらに詳しく後述する。また、制御メモリ220の実装は、単一のメモリ装置、あるいは、共有のまたは共通のメモリを形成するように通信可能に接続または互いに連結された複数のメモリ回路など、幾つかの可能な実施形態を含んでよい。さらに、メモリは、バス通信回路の部分などの他の回路と共に、より大きい回路に含まれてよい。本開示のユーザインタフェースプロセスは、早送り、巻き戻しなどの機能を表すのに使用可能な入力装置を採用する。これを可能にするために、タッチパネル装置などの第2の画面制御装置が、受信装置200のユーザインタフェース216および/または制御インタフェース222を介して、インタフェースを取られてよい。図3は、図1および図2に関して上述した受信装置106、200などのセットトップボックスSTB310において意味解釈の実行に関するプロセス300の可能な1つの実施形態を示す。ここで、STB310は、コンテンツソース102からコンテンツ305を受信する。次に、コンテンツ305は、1キーワード収集320、2概念収集340、3概念処理360の3つの部分で処理される。キーワード収集320においては、クローズドキャプション抽出部325を用いて、コンテンツ305の一部として供給されたクローズドキャプションデータを受信、取得、抽出する。次に、文分割部330を用いて、クローズドキャプションデータ内の文の構造を識別して、文の主語または目的語、及び、フレーズ全体など、候補となるフレーズやキーワードを探す。クローズドキャプション中の多くの文に関して、主語の入ったフレーズは、とても重要である。そのため、文頭を見つけるのに係り受け解析部を用いることができ、文頭が候補フレーズでもあれば、文頭により高いプライオリティを与えることができる。次に、候補キーワードを用いて、概念収集340において、関連のある概念を見つける。ここは、意味解釈部350を用いて、候補キーワードを概念にマッピングする所でもある。次に、概念蓄積部340によって、概念をグループ化することができる。結果として得られる蓄積された概念を、次に処理360する。この処理は、順位付け365、やユーザプロファイル370の作成などの他の機能を含むことができる。例えば、ユーザのTV視聴プロファイルの作成にセグメントのクローズドキャプションを用いることができ、その結果、コンテンツをユーザに合わせてカスタマイズすることができ、ユーザに提供する推薦の質を向上させることができる。広告を一致させることができる、または、同じような関心を持つ友人に勧めることができるなど、正確かつ有益なユーザプロファイルを作成する他の多くのアプリケーションがある。ユーザのテレビ視聴習慣からプロファイルを作成する現在のシステムが直面する主な課題は、正確なデータが疎らで不足していることである。この問題を軽減するために、視聴されたテレビ番組のセグメントに対応するクローズキャプションのセグメントを、視聴時間や番組のEPG情報などの他のメタデータと共に、取得することができる。クローズドキャプションを取得することによって、ユーザが興味を持つものを理解し、コンテンツベースの推薦をするための基準を提供することが可能になる。さらに、取得したクローズドキャプションを、意味解釈部を用いて概念空間にマッピングすると、得られるプロファイルは、より直観的に理解、活用できるものとなる。さらなる長所として、クローズドキャプションのセグメントの全てを記憶しないので、記憶が必要なデータ量が減る。クローズドキャプションのセグメントが表す上位k個の概念のみが記憶される。別の例において、意味解釈部によってマッピングされた概念を用いて、オンライン例えば、ライブ/放送およびオフライン例えば、デジタルビデオに記録の両方で、クローズドキャプションデータに基づいて映像を分割することができる。各セグメントは、1つのコヒーレントな単位例えば、イブニングニュースのタイガーウッズに関するセグメントである概念セットを含まなければならない。映像が分割されると、対応するクローズドキャプションのセグメントは、概念空間と、得られた上位k個の概念の注釈が付いた映像とにマッピングすることができる。このアプリケーションによって、これらのミニクリップを友人と共有したり、DVRに保存したり、興味があるとして単にタグをつけたりが可能になる。これは、ユーザが映像全体に興味があるわけではない場合、または、映像全体だと大きすぎて共有できない場合、著作権の問題がある場合などに、有用である。現代のDVRは、ライブポーズ/巻き戻し機能を提供するために既に、視聴中の番組を記録する。これを、さらに、分割化と概念マッピングアルゴリズムをトリガするように拡張することができる。その結果、得られるセグメントにタグを付けることができる、および/または保存することができ、および/または検出したセグメントの前後短い時間間隔/-t秒で共有することができる。別の例においては、この技術を用いて検索を向上させることができる。現在、ユーザは、興味のある番組を見つけるために完全に一致するキーワードを用いて情報を検索する必要がある。この方法は、ユーザが自分の探しているものがはっきり分かっている場合は役立つが、完全に一致するキーワードによる検索は、ユーザが興味を持つかもしれない、新しい、心躍るようなコンテンツの発見を妨げる。意味解釈部を用いて、この問題を解決することができる。人間の知識の全てを表すという実用的な目的のためにあるとみなされているウィキペディアから概念空間を引き出すことができる。従って、この空間内で表されるドキュメントは同じ概念を用いてクエリを行うことができる。例えば、ユーザは、ねずみ講PonziSchemeまたはサプライチェーンSupplyChainなどの高度な知識を用いて、その概念に最も関連のある媒体を発見することができるはずである。対応する媒体にねずみ講またはサプライチェーンに完全に一致するキーワードがなくても、この発見は可能である。さらに、常設のフィルタを設定することによって、あらゆる受信する媒体を概念空間にマッピングすることができ、その概念が常設のフィルタに一致すれば、システムが、その媒体にさらなるアクションのためのタグを付けることができる。ユーザのフィルタルールに一致する番組が放送されると、ユーザに通知され、ユーザはその番組を保存、関連性を閲覧、共有または視聴する。図3の例においては、STB310でそのプロセスが行われているが、同じプロセスを、コンテンツソース102またはサービスプロバイダ104、110で行うこともできることは理解されたい。一部の例では、そのプロセスは、必要に応じて、異なる装置または場所に分割することもできる。実際、多くの例において、意味解釈はリモートサーバで行われ、得られた概念は、さらなる処理のため、STB310、コンテンツソース102、またはサービスプロバイダ104、110に戻される。コンテンツソース102で処理が行われる場合は、コンテンツが作成されると、該当するクローズドキャプションまたはサブタイトルデータが、概念空間にマッピングされる。次に、推定された概念が、別個のストリーム例えば、MPEG-7規格を用いてとしてメディア多重部に埋め込まれる。長所は、メディアファイルごとに、複数回ではなく、一度処理を行えばよいことである。短所は、埋め込み、さらには、メタデータの処理および消費のために規格の開発が必要なことである。サービスプロバイダ104または110の場合は、サービスプロバイダのネットワークまたはクラウドを介してコンテンツが送信されるとき、処理が行われる。例えば、サービスプロバイダは、意味解釈部を用いて全ての受信チャネルを処理し、適切な方法MPEG-7、独自の、または、ウェブベースの技術を用いてで、メタデータを埋め込むことができる。サービスプロバイダは、STBがこのメタデータを解釈でき、さらに処理できれば、標準スキームを用いる必要がない。この手法の大きな長所は、精巧な規格を開発する必要がなく、また、これらのスキームを用いて、異なるサービスプロバイダを区別することができることである。図4を参照すると、フロー図400は、上位k個の概念を用いた意味解釈の実行に関するプロセスの一実施形態を示している。最初に、1つまたは複数のキーワードを意味解釈ステップ410のために取得する。次に、その1つまたは複数のキーワードを用いて、知識データベース内の上位k個の概念を計算するステップ420。次に、上位k個の概念を用いてキーワードを概念空間にマッピングすることができるステップ430。1つまたは複数のキーワードは、任意の数の方法で取得することができる。キーワードは、図3を参照して上述したクローズドキャプションデータに関するキーワード抽出を用いて取得してよい。他の実施形態においては、キーワードは、概要、番組の説明、要約、粗筋などの各コンテンツに関するデータから抽出することができる。さらに別の実施形態においては、ユーザは、検索語を供給することができる。下記のプロセスの記載においては、キーワードは、ドキュメントの一部として供給される。上位k個の概念を計算するステップステップ420および概念空間へのマッピングのステップステップ430は、SparseTopkアルゴリズムの記載と共に、図5から図8を参照して後述する。問題の定義このセクションでは、問題を正式に定義し、アルゴリズムの開発、記述に使用する表記法を紹介する。可能な全てのウィキペディアの概念を用いて意味を再解釈Uをu個の異なるワードを有する辞書とする。ウィキペディアの概念は、例えばu×mのc概念行列C530の形で表される。ここで、mは、ウィキペディアの項目に該当する概念の数で、uは、辞書中の異なるキーワードの数である。Cirは、r番目の概念cr中のi番目のキーワードtiの重みを表す。Cr=[w1r,w2r....wur]Tをr番目の概念ベクトルとする。一般性をなくさないように、各概念ベクトルCrは単位長さに正規化すると仮定する。辞書Uの場合、ドキュメントdは、l次元のベクトル=[w1,w2....wu]515として表される。キーワード概念行列をC530、ドキュメントベクトルをとすると、あらゆる可能なウィキペディア概念で意味を再解釈した充実したドキュメントベクトル’=[w’1,w’2....w’m]525は、=Cと定義される。行列乗算の定義によると、ベクトル’中の概念crの寄与は、次のように計算される。上位k個のウィキペディア概念を用いた意味の再解釈導入部で述べたように、’全ての可能なウィキペディア概念を計算すると、膨大な費用がかかる可能性がある。従って、目標は、そのドキュメントに関連するウィキペディア内の最適なk個の概念でドキュメントを再解釈することである。再解釈されたドキュメント’=[w’1,w’2...w’m]の場合、Skをk個の概念のセットとすると、下記のようになる。言い換えれば、Skは、’への寄与が他の概念より大きいまたは他の概念と同等のk個の概念を含む。次に、ウィキペディア内で’に一致する上位k個の概念に基づいたの意味の再解釈は、’=[w’1,w’2...w’m]として定義され、式中、の場合、それ以外の場合は、w’r=0となる。問題の定義:上位k個のウィキペディアの近似的概念を用いた意味再解釈所与のドキュメントに関連する最適のk個の概念を正確に計算するためには、キーワード概念行列の全てをスキャンすることが必要となることが多く、非常に費用がかかる。従って、さらに効率を向上させるために、Skを次のように緩和する。すなわち、ドキュメントにおいて、Skαを、Skα中の少なくともαk個の答えがSkに属するようなk個の概念のセットとし、ここで、とする。そうすると、目的は、次のように定義される。問題1Skαを用いて意味再解釈キーワード概念行列をC、ドキュメントベクトルを、対応するk個の近似的な最適の概念をSkαとすると、ウィキペディア内でに一致する上位k個の近似的概念に基づいたの意味再解釈は、次のように定義される。の場合、それ以外の場合は、w’r=0となる。言い換えると、元のドキュメントdは、ワード空間510から、ウィキペディア内でドキュメントdに最も一致するk個の近似的概念からなる概念空間520にほとんどマッピングされる。従って、この問題に関する主な課題は、このようなk個の近似的概念Skαを効率的に識別する方法である。この問題に対処するために、所与のドキュメントに関して効率的にSkαを計算する新規の順位付け処理アルゴリズムを提示する。Skへの単純な解決法このセクションにおいて、所与のドキュメントの上位k個の概念Skを正確に計算するための単純なスキームすなわち、非実用的な解決法を最初に記載する。全てのデータをスキャンこの問題の明らかな解決法は、u×m個のキーワード概念行列C530の全てをスキャンし、ドキュメントベクトルに各概念ベクトルCrを掛け、得られたスコアを降順にソートし、k個の最適な解のみを選択する方法である。この問題のより有望な解決法は、IRシステムでよく使われる逆索引を活用することである。そうすると、キーワード概念行列内の該当する値が0より大きいエントリのみをスキャンすることができる。どちらのスキームを用いても、最適のk個の結果に属さないであろう見込みのないデータの処理に資源のほとんどを使うので、非常に費用がかかる。閾値ベースの順位付け処理スキーム順位付けまたはtop-k処理に関しては多くの提案がされてきた。上述のように、閾値アルゴリズムTA、FaginのアルゴリズムFA、非反復アルゴリズムNRAなどの閾値ベースのアルゴリズムが、最もよく知られている方法である。これらのアルゴリズムは、所与のソートリストにおいて、各オブジェクトが各リスト内に1つだけスコアを有し、各リスト内の個々のオブジェクトのスコアを合算する集合関数aggregationfunctionが、最低min、最大max、重みの合計weightsumおよび積productのように単調であると、仮定する。これらの単調なスコア関数によって、サブスコア内で他の候補に優越する候補は、当該他の候補よりも合算したスコアが良くなることが確実になり、top-k計算の途中で、早めに計算を停止して、全てのリストをスキャンすることを避けることができる。一般的に、TAおよびFAアルゴリズムは、ランダムアクセスとソートアクセスという2つのアクセス方法を必要とする。しかしながら、ドキュメント用語行列などの高次元データへのランダムアクセスを支援すると、膨大な費用がかかることになる。従って、NRAは、ソートアクセス方法しか必要とせず、概念行列Cなどの高次元データに適しているので、基本の枠組みとしてNRAを採用する。概念行列に関するソートされた逆リストu×m個のキーワード概念行列C530へのソートアクセスを支援するために、u個のリストを含む逆索引610を作成する図6。各キーワードtiに関して、該当するリストLiは、<cr,Cir>のセットを含む。ここで、Cirは、ウィキペディアの概念cr中のキーワードtiの重みである。図6に示すように、各逆リストは、重みが0を超える概念のみを保持している。この逆リストは、ソートアクセスを支持するように、重みの降順に作成されている。Skを計算するNRAベースのスキーム上記w’rの定義から、スコア関数は重みの合計として定義されるので、u個の独立したリスト内では単調であることが明らかである。ドキュメント=[w1,w2....wu]の場合、NRAは、ラウンドロビン方式で入力リストにあたり、閾値ベクトル=[T1,T2,...,Tu]を更新する。ここで、Tiは、リストLiで読み取られた最後の重みである。言い換えれば、閾値ベクトルは、入力リストの見えないインスタンスの重みの上限からなる。リストLi内のインスタンス<cr,Cir>を読み取った後、thepossibleworstscoreofther-thpositionin意味を再解釈したドキュメントベクトル=[w’1,w’2,...,w’r...,w’m]のr番目の位置が取り得るワーストスコアは次のように計算される。式中、KNrは、該当する重みがアルゴリズムによって以前読まれたことのある概念ベクトルCr,中の位置のセットである。他方、r番目の位置が取り得るベストスコアは次のように計算される。まとめると、取り得るワーストスコアは、概念ベクトルの見えないエントリが0であるという仮定に基づいて計算され、取り得るベストスコアは、概念ベクトルの見えないエントリが全て各リストの最後のスキャン位置の後に出会うものであると仮定されている。NRAは、現在の上位k個の候補のうち最低のスコアに値するカットオフスコアmink,を保持する。カットオフスコアminkが、現在の上位k個の候補に属さない概念の最高のベストスコアより大きくまたは等しくなると、NRAは計算を停止する。この停止条件によって、正確な上位k個の結果すなわち、ここでは、Skが必ず生成されるが、各概念ベクトルの未知の値は全て、各リストの現在のスキャン位置の後に読み取られると仮定すると、このような停止条件はあまりにも悲観的である。しかしながら、各概念ベクトルの未知の値がかなり高い確率で0になる疎らなキーワード概念行列に関しては特に、これは当てはまらない。よって、NRAは、結局全てのリストをスキャンすることになる可能性があり、膨大な費用がかかる。ウィキペディアの概念を用いたドキュメントの効率的な解釈このセクションにおいては、ウィキペディアを用いた効率的な意味解釈部のためのアルゴリズムについて述べる。提案のアルゴリズムは2段階からなる。すなわち、1所与のドキュメントの上位k個の近似的概念Sk、αを計算する段階と、2Sk、αを用いて元のドキュメントを概念空間にマッピングする段階である。段階1:上位k個の近似的概念Sk、αを識別上述のように、閾値ベースのアルゴリズムは、所与のソートされたリストにおいて、各オブジェクトは、各リスト内に1つだけスコアを有するという仮定に基づいている。NRAアルゴリズムにおける見えないオブジェクトの取り得るスコアは、この仮定に基づいて計算される。しかしながら、この仮定は、エントリのほとんどが0である疎らなキーワード概念行列には適用できない。従って、このサブセクションにおいては、最初に、疎らなキーワード概念行列を用いて見えないオブジェクトのスコアを推定する方法を記載し、次に、推定したスコアを活用して、所与のドキュメントの上位k個の近似的概念を取得する方法を示す。入力リストの数の限界を推定各オブジェクトは各入力リスト内に1つだけスコアを有するという仮定は、疎らなキーワード概念行列に関しては有効でないので、このサブセクションにおいては、目的は、各オブジェクトが計算中に発見されると予測される入力リストの数の限界を正確に推測することである。ヒストグラムは、通常、データ分布すなわち、確率密度関数を近似するために用いられる。多くの既存の近似的top-k処理アルゴリズムは、入力リストのヒストグラムを保持し、ヒストグラムを用いることで、未知のオブジェクトのスコアを推定する。一般的に、近似法は、完全一致のスキームよりも効率がよい。しかし、キーワード概念行列の膨大な数のリストがあることを考えると、このようなヒストグラムを保持し、取り得る合計スコアを計算するためにランタイム中にそのヒストグラムを活用することは、実行可能な解決法ではない。従って、さらに効率よくするためには、各逆リストのデータ分布を、逆リストが所与の概念を含む場合、または、含まない場合という、二項分布によって単純化する。このように単純化されたデータ分布でも、概念行列が極度に疎らなので、上位k個の結果の質が大きく減じられることはない。キーワードをti、キーワード概念行列をCとすると、該当するソートリストLiの長さは、次のように定義される。u×m個のキーワード概念行列をCとすると、インスタンス<cr,Cir>がLi内にある確率は、次のようになる。一般に、閾値ベースのアルゴリズムは、各ソートリストを順次スキャンする。アルゴリズムは、ソートリストLiから最初のfiインスタンスを順次スキャンし、インスタンス<cr,Cir>は、スキャン中に見つからなかったと仮定する。次に、インスタンス<cr,Cir>がリストLiのスキャンしていない部分すなわち、残りの|Li|-fiインスタンス中に見つかる確率P<cir,fi>は、次のように計算することができる。各オブジェクトは各入力リストに1つだけスコアを有するすなわち、|Li|=mという仮定の下では、P<cir,fi>は1となることに注意。しかしながら、キーワード概念行列が極めて疎らである、従って、大抵の場合、P<cir,fi>は0に近い。ドキュメントをdとし、対応するu次元のベクトルを=[w1,w2,...,wu]とする。さらに、において、Lをソートリストのセットとすると次のようになる。言い換えれば、Lは、該当するワードが所与のドキュメントdに現れるソートリストのセットである。Lに含まれない他のリストは、元のベクトルの該当する重みが0に等しいので、意味を再解釈したベクトル’の計算には寄与しない図2。さらに、ドキュメント内のワードの出現は、互いに独立していると仮定できる。ワードの独立という仮定は、簡単なので、多くのアプリケーションで長く用いられてきた。Pfoundexactを、今までどのリストでも見られていない概念crがその後、L中の正確にn個のリストで発見される確率とすると、その確率は次のように計算される。式中、さらに、全く見えない概念crが、計算中、L中、n個以下のリストで発見される確率Pfounduptoは、次のように計算できる。Pfounduptoは、常に1であることに注意。上述のように、目的は、Skα中の少なくともαk個の答えが完全一致の上位k個の結果に属するような上位k個の近似的概念Skαを求めることである。アプリケーションまたはユーザが提供した容認できる精度をαとし、全く利用できない概念crが見つかるであろうリストの数の限界brを計算するために、選択された値は、下式を満足する最小値brである。まとめると、brは、br個の入力リストより小さい見えない概念crの確率は容認できる精度αよりも高いという条件を満足する最も小さい値である。全くまたは部分的に見えないオブジェクトの予測スコアを計算全く見えないオブジェクトを発見するであろうリストの数を推定すると、全くまたは部分的に見えないオブジェクトの予測スコアを計算することができる。現在の閾値ベクトルを=[T1,T2,...,Tu]および元のドキュメントのベクトルを=[w1,w2,...,wu]とすると、Wは次のように定義される。次に、全く見えない概念crの予測したスコアは、下記のように制限される。式中、WhはW内でh番目に大きい値である。逆索引の各リストは、概念IDよりも重みでソートされ、結果として、top-k計算中、所与の概念crの部分的に利用可能な見える概念ベクトルとなる。従って、部分的に見えるオブジェクトの予測スコアも推定する必要がある。crを部分的に見える概念とする。さらに、KNrをアルゴリズムによって既に重みが見られた概念ベクトルCr内の位置のセットとする。そうすると、部分的に見える概念crの予測スコアは次のように定義される。の場合、それ以外の場合、crが見つかるであろう入力リストの数の限界brがLと同じになるとき、完全に見えるまたは部分的に見える任意の概念crの予測スコアが、上述の可能なベストスコアbrに等しくなることに注意。しかしながら、キーワード概念行列が疎らであると、確実に、予測スコアは可能なベストスコアより常に小さくなる。アルゴリズム図7は、所与のドキュメントの上位k個の近似的概念Skαのセットを効率的に計算するために提案されたアルゴリズム用の疑似コードを記載している。最初に、アルゴリズムは、上位k個の近似的概念Skαのセット、カットオフスコアmink、および候補セットCndを初期値にする。閾値ベクトルthは、最初は[1,1,1]にセットする。まず、上述のように、任意の完全に見えない概念の予測スコアを計算する1~5行目。一般的に、閾値アルゴリズムは、ラウンドロビン方式で入力リストにアクセスする。しかしながら、入力リストの長さが異なる場合は、該当するスコアが比較的低いにもかかわらず、短いリストに属しているので早く読まれる、見込みのないオブジェクトを処理するのにリソースを消費するので、このスキームは非効率である。この問題を解決するために、入力リストは、全く利用できない概念の予測スコアを最小化する方法でアクセスされる。直観的に、こうすることによって、アルゴリズムは、より高いカットオフスコアminkを供給して、早い段階で計算を停止することができる。元のドキュメントベクトルを=[w1,w2,...,wu]とし、現在の閾値ベクトルを=[T1,T2,...,Tu]とすると、アルゴリズムが次回に読み取る入力リスト、リストLi8行目は、次のようになる。上の条件を満足するリストによって、任意の利用できない概念の予測スコアを確実に最小にして、早期に停止する条件をアルゴリズムに与える。リストLi中の新規の見えるインスタンス<cr,Cir>に関して、該当するワーストスコアW‘rwstを計算し、候補リストを<cr,W‘rwst>で更新する9~11行。カットオフスコアminkは、現在の候補セットCndのワーストスコアのうちk番目に高い値と等しくなるように選択される12行目。そして、閾値ベクトルを更新する13行目。15行目から20行目で、高い確率を有する上位k個の結果には含まれないであろう見込みのない概念が候補セットから削除される。現在の候補セット中の各概念Cpに関して、該当する予測スコアW’pexpが上述のように計算される。現在の候補セット中の各概念は、部分的に見える概念に該当することに注意されたい。部分的に見える概念Cpの予測スコアWpexpがカットオフスコアより小さい場合、この概念は、高い確率で最終的な上位k個の結果に入るとは予測されないので、<cp,W’pwst>のペアは、現在の候補セットから削除される18行目。21行目で、任意の完全に見えない概念の予測スコアを計算する。現在の候補セットがk個の要素を含み、完全に見えない概念の予測スコアが、カットオフスコアより小さくなる見込みのときのみ、top-k計算は終了する7行目。段階2:キーワード空間から概念空間へのドキュメントのマッピング所与のドキュメントの上位k個の近似的概念を識別すると、次のステップは、元のドキュメントをキーワード空間から概念空間にマッピングすることである。図8は、Skαを用いて、元のドキュメントをキーワード空間から概念空間にマッピングするための疑似コードを記載している。最初に、意味を再解釈したベクトル’を[0,0,]と設定する1行目。図4のアルゴリズムは、全ての入力リストをスキャンする前に停止しているので、Skα中の概念の概念ベクトルは、部分的に利用可能である。よって、Skα中の各概念に関して、上記のように、部分的に見える概念ベクトルを用いて予測スコアを推定することが必要である3行目。そして、意味を再解釈したベクトル’中の該当するエントリを、推定したスコアで更新する4行目。最後に、アルゴリズムは、意味を再解釈したドキュメントベクトル’に戻る6行目。新しい意味解釈部は、ウィキペディアの概念に基づいて元のドキュメントを効率的に充実させるために記述される。提案した手法によって、所与のドキュメントにとってウィキペディア内の最も重要なk個の概念を効率的に識別することができ、これらの概念を活用して、元のドキュメントをキーワード空間から概念空間にマッピングすることにより、元のドキュメントを意味的に充実させることができる。提案した技術は、正確さを大きく減じることなしに、意味の再解釈の効率性を大いに向上させることが、実験結果より分かる。本原理のこれらの特徴および長所、また他の特徴および長所は、本明細書に記載の教示に基づいて、関連技術分野の当業者には容易に理解されるであろう。本原理の教示は、ハードウェア、ソフトウェア、ファームウェア、専用プロセッサ、またはそれらの組み合わせなどの様々な形態で実践してよいことは理解されよう。本原理の教示は、ハードウェアおよびソフトウェアの組み合わせとして実践されるのが、より好ましい。さらに、ソフトウェアは、プログラム記憶装置上で具体的に実現されるアプリケーションプログラムとして実践してよい。アプリケーションプログラムは、任意の適切なアーキテクチャを備える機械にアップロードし、その機械によって実行されてよい。機械は、1つまたは複数の中央処理装置CPU、ランダムアクセスメモリRAMおよび入出力I/Oインタフェースなどのハードウェアを有するコンピュータプラットフォーム上で実践されるのが好ましい。コンピュータプラットフォームは、オペレーティングシステムやマイクロ命令コードも含んでよい。本明細書に記載の様々なプロセスや機能は、マイクロ命令コードの一部、アプリケーションプログラムの一部、または、その任意の組み合わせであってよく、それらはCPUによって実行してよい。さらに、追加のデータ記憶装置や印刷装置などの様々な他の周辺機器をコンピュータプラットフォームに接続してよい。添付図面に記載された、構成要素となっているシステムコンポーネントの一部、および、方法の一部は、ソフトウェアで実践されるのが好ましいので、システムコンポーネント間、または、プロセスの機能ブロック間の実際の接続は、本原理をプログラムする方法に応じて異なって良いことも理解されたい。本明細書の教示を前提として、関連技術分野の当業者は、本原理の記載した実装または構成、および類似の実装または構成を考案することができるであろう。添付の図面を参照して本明細書に実施形態を例示したが、本原理は、これらの具体的な実施形態に限定されず、本原理の範囲、精神から逸脱することなく、関連技術分野の当業者は、様々な変更や修正を行ってよいことは理解されたい。このような変更および修正は全て、請求項に記載する本原理の範囲に含まれるものとする。"