(57)【要約】コマーシャルを推奨するシステム及び方法が開示される。ビデオ信号からのコマーシャルが識別され抽出される。識別されるコマーシャルに関するトランスクリプト情報が学習され抽出される。各コマーシャルは、それらのトランスクリプト情報に従って異なったカテゴリへ分類される。コマーシャルに対するユーザの好みが決定される。コマーシャルはユーザの好みと共に、ユーザへ推奨すべきコマーシャルを選択するために決定木を構築又は学習するのに使用される。選択されたコマーシャルは、個人的なチャンネルを用いて推奨される。【特許請求の範囲】
【請求項１】
視聴者にコマーシャルを推奨する方法であって、
ビデオ信号から１つ以上のコマーシャルセグメントを検出する段階と、
前記１つ以上のコマーシャルセグメントから記述情報を抽出する段階と、
推奨のため前記記述情報に基づいて１つ以上のコマーシャルを選択する段階とを含む、方法。
【請求項２】
前記選択されたコマーシャルを表示するための個人用チャンネルを与える段階を更に含む、請求項１記載の方法。
【請求項３】
前記検出する段階は、
ビデオ信号を受信する段階と、
前記ビデオ信号中の１以上の識別特徴を抽出する段階と、
前記抽出された特徴に基づいてビデオ内容を識別する段階とを含む、請求項１記載の方法。
【請求項４】
前記抽出する段階は、
前記コマーシャルセグメントに関連するトランスクリプト情報を解析する段階と、
前記コマーシャルセグメントの種別を識別する段階とを含む、請求項１記載の方法。
【請求項５】
前記抽出する段階は、
前記識別された種別及び前記コマーシャルセグメントを格納する段階を更に含む、請求項４記載の方法。
【請求項６】
前記１以上のコマーシャルに対するユーザの好みを監視する段階を更に含む、請求項１記載の方法。
【請求項７】
前記選択する段階は、
ユーザの視聴の好みを監視する段階と、
１以上のコマーシャル属性を分類する段階と、
前記ユーザの視聴の好みに従って前記コマーシャル属性を有する決定木を構築する段階と、
前記決定木を１以上のコマーシャルに適用する段階とを含む、請求項１記載の方法。
【請求項８】
前記適用する段階は、
前記決定木を、放送される１以上のコマーシャルに適用する段階を含む、請求項７記載の方法。
【請求項９】
前記適用する段階は、
前記決定木を、格納された１以上のコマーシャルに適用する段階を含む、請求項７記載の方法。
【請求項１０】
前記与える段階は、
ユーザが個人用チャンネルを選択することを可能とする段階と、
前記個人用チャンネル上に推奨されたコマーシャルのリストを表示する段階と、
前記ユーザに前記リストからコマーシャルを選択させることを可能とする段階と、
前記ユーザに前記選択されたコマーシャルを視聴することを可能とする段階とを含む、請求項２記載の方法。
【請求項１１】
コマーシャルを推奨するシステムであって、
１以上のコマーシャルを検出するコマーシャル検出器モジュールを制御するプロセッサと、
ビデオ信号から１以上のコマーシャルを検出するモジュールと、
前記検出されたコマーシャルから記述情報を抽出するモジュールと、
前記記述情報に基づいてユーザへ推奨すべきコマーシャルを選択する推奨器モジュールと、
選択されたコマーシャルを提示するダイナミック・チャンネルを作成するダイナミック個人用チャンネル・モジュールとを有する、システム。
【請求項１２】
コマーシャルを推奨する方法の各段階を実行するよう機械によって実行可能な命令のプログラムを有形に具現化した、機械読み取り可能なプログラム記憶装置であって、
前記各段階は、
ビデオ信号から１以上のコマーシャルセグメントを検出する段階と、
前記コマーシャルセグメントから記述情報を抽出する段階と、
推奨のために前記記述情報に基づいて１以上のコマーシャルを選択する段階とを含む、プログラム記憶装置。
【請求項１３】
前記選択されたコマーシャルを表示する個人用チャンネルを与える段階を更に含む、請求項１２記載のプログラム記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、視聴者の好み及びコマーシャル内容に基づき視聴者へコマーシャルを推奨する方法に関連する。
【背景技術】
【０００２】
テレビジョンコマーシャルは、テレビジョン視聴者が、最新の製品、番組等に気づいているようにするための効果的な方法を提供する。このために、視聴者に対してコマーシャルを推奨するために多くの異なったシステムが開発されている。例えば、特許文献１は、電子番組ガイド（「ＥＰＧ」）をカスタマイズするためにプロファイルが使用されうるよう、視聴者プロファイルを作成することについて記述している。視聴者プロファイルは、ユーザがどのようにシステムと対話するかに関する統計を収集することによって学習される。構築されたプロファイルは、ＥＰＧ上の適当な場所に広告を配置するのに使用される。しかしながら、特許文献１は、プロファイルを構築するのにコマーシャルの内容を使用しない。特許文献２は、ユーザに対して、可能な関心となるコマーシャルを推奨するよう、人工統計的及び幾何学的な情報を用いる。
【特許文献１】米国特許第６，１７７，９３１号明細書
【特許文献２】国際公開第００／４９８０１号パンフレット
【発明の開示】
【発明が解決しようとする課題】
【０００３】
特許文献１及び２はいずれもコマーシャルの推奨について開示するが、これらは、ユーザに関する情報又はユーザがどのようにテレビジョンと対話するかに関する情報を収集することによって行なう。これを行うことの主な不利点は、かかるシステムは、ユーザの関心となるコマーシャルを正確に提案することが可能でないことである。従って、コマーシャルの内容に基づいて視聴者の関心となるコマーシャルをより正確に自動的に推奨しうるシステムが必要とされる。
【課題を解決するための手段】
【０００４】
本発明によれば、内容に基づいてユーザにコマーシャルを推奨するコマーシャル推奨器が提供される。１つの面によれば、コマーシャルを推奨する方法は、ビデオ信号からコマーシャルセグメントを識別する段階を有する。次に、これらのコマーシャルセグメントからの記述情報が抽出される。記述情報、及び、例えばユーザの視聴履歴からのユーザの好みに基づいて、ユーザへ推奨するために例えば決定木を用いて関心となるコマーシャルが選択される。次に、推奨されたコマーシャルは、例えばダイナミック・チャンネル作成を用いてユーザへ提示される。
【０００５】
他の面によれば、コマーシャルを推奨するシステムは、コマーシャルを検出するコマーシャル検出器モジュールと、検出されたコマーシャルから記述情報を抽出するモジュールとを含む。検出されたコマーシャル中の抽出された情報は、ユーザに対してどのコマーシャルが推奨されるべきかを決定する推奨器モジュールへ入力される。推奨のための選択されたコマーシャルは、ダイナミック・チャンネル作成モジュールを介してユーザに提示される。
【発明を実施するための最良の形態】
【０００６】
図１は、本発明の１つの面によるコマーシャル推奨方法を示すフローチャートである。ステップ１０２において、ビデオ信号からコマーシャルが検出される。一般的には、放送されたビデオ信号中のコマーシャルは、他の番組セグメントから識別され抽出されうる。例えば、ここに参照として全体として組み入れられる本発明と同じ譲受人に譲渡された１９９９年１０月１３日出願の（発明者ネヴェンカ・ディミトロヴァ（Nevenka  Dimitrova）外、出願人整理番号ＰＨＡ２３−８０３）「AUTOMATIC  SIGNATURE-BASED  SPOTTING,  LEARNING  AND  EXTRACTING  OF  COMMERCIALS  AND  OTHER  VIDEO  CONTENT」なる名称の米国特許出願第０９／４１７，２８８号明細書には、ビデ信号中のコマーシャル又は他の特定の種類のビデオ内容を発見し、学習し、抽出する改善された技術が記載されている。
【０００７】
ステップ１０４において、検出されたコマーシャルから記述情報が抽出される。本発明と同じ譲受人に譲渡された（発明者ラリサ・アグニホトリ（Lalitha  Agnihotri）外、出願人整理番号ＵＳ０１０３３８、２００１年９月４日出願）「A  METHOD  OF  USING  TRANSCRIPT  DATA  TO  IDENTIFY  AND  LEARN  COMMERCIAL  PORTIONS  OF  A  PROGRAM」なる名称の米国特許出願第０９／９４５，８７１号明細書には、ビデオ信号のコマーシャル部分から記述情報を抽出する例が開示されている。当該出願は、ここに全体として参照として組み入れられている。
【０００８】
当該出願に記載されているように、コマーシャルは、例えば自動車、家庭用品等の様々なカテゴリへとグループ分けされうる。ステップ１０６において、コマーシャルの記述内容に基づいて、ユーザの好みのコマーシャルがユーザへ推奨されうる。例えば、本発明と同じ譲受人に譲渡された（発明者スリニヴァス・ギュッタ（Srinivas  Gutta）外、出願人整理番号ＰＨＡ２３−９０２、１９９９年１２月１７日出願）「METHOD  AND  APPARATUS  FOR  RECOMMENDING  TELEVISION  PROGRAMMING  USING  DECISION  TREES」なる名称の米国特許出願第０９／４６６，４０６号明細書には、番組を推奨する方法の例が開示されている。当該出願に記載されたのと同じ方法は、コマーシャルの推奨にも適用されうる。当該出願は、ここに全体として参照として組み入れられる。
【０００９】
推奨されたコマーシャルは、ステップ１０８において、関心となるコマーシャルがユーザに対して表示されうるよう、個人用チャンネルを作成することによって表示されうる。例えば、本発明と同じ譲受人に譲渡された（発明者スリニヴァス・ギュッタ（Srinivas  Gutta）外、出願人整理番号ＵＳ０１００７４、２００１年３月２９日出願）「DYNAMIC  TELEVISION  CHANNEL  CREATION」なる名称の米国特許出願第０９／８２１，０５９号明細書は、推奨された番組を表示するチャンネルを提供することが開示されている。当該出願は、ここに全体として参照として組み入れられる。推奨されたコマーシャルは、当該出願に記載されたのと同様にユーザへ提示又は表示されうる。
【００１０】
コマーシャルは、テレビジョン受像機、ＶＣＲ又は他のビデオ記憶装置、又は、任意の他の種類のビデオ源等の１以上のビデオ源を介して受信されるビデオ信号から検出されうる。源は、或いは、例えばインターネット、広域ネットワーク、都市エリア・ネットワーク、ローカル・エリア・ネットワーク、地上波放送システム、ケーブル網、衛星網、無線網、又は電話網、並びに、これらの及び他の種類のネットワークの一部又は組合せ等のグローバル・コンピュータ通信網を通じた１つ又は複数のサーバからビデオを受信するための１以上のネットワーク接続を含みうる。コマーシャルは、テレビジョン、セットトップボックス、デスクトップ、ラップトップ又はパームトップコンピュータ、携帯情報端末（ＰＤＡ）、ビデオ・カセット・レコーダ（ＶＣＲ）、ディジタル・ビデオ・レコーダ（ＤＶＲ）、ＴｉＶＯ装置等のビデオ記憶装置、並びに、これらの及び他の装置の部分又は組合せといった装置を介して受信されうる。
【００１１】
図２は、本発明による放送ビデオ信号からコマーシャルを発見し、学習し、抽出する方法の例を示す図である。この例では、入力ビデオは、少なくとも１つの番組及び多数のチャンネルを含む放送ビデオ信号を有すると想定される。
【００１２】
ステップ２０２乃至２１０は、入力ビデオ信号が存在するかぎり繰り返される。ステップ２０２において、放送ビデオ信号中の通常でないアクティビティのセグメントが検出される。これは、例えば、放送ビデオ信号中の高いカット率領域の検出、又は高いテキストのアクティビティの領域の検出を含みうる。他の例は、色ヒストグラムを累積させること、オーディオレベルの上昇を検出すること、音楽から発話（speech）へ、１つのリズムから他のリズムへ速い変化を検出すること等によって、視覚領域中の速い変化を検出することを含む。
【００１３】
ステップ２０４において、ステップ２０２で通常でないアクティビティを含むものとして識別されたセグメントは、コマーシャルに関連する可能性が高いかどうかを判定するよう更に処理される。このように決定されたセグメントは、次にマーク付けされる。この検出を行うのに使用されうる特徴の例は、以下のものを含む。
（ａ）コマーシャルに関連する既知の会社名、製品又はサービス名、フリーダイヤル番号又は他の電話番号、Uniform  Resource  Locator（ＵＲＬ）等の記憶されたテキストファイル中のエントリに対応する表示されたテキスト。
（ｂ）発話。この場合、発話が抽出されえ、テキストへ変換され、結果として得られるテキストは、既知の会社名、製品又はサービス名、フリーダイヤル番号又は他の電話番号、ＵＲＬ等を検出するよう、上述の記憶されたテキストファイルに対して解析される。
（ｃ）高いカット率と組み合わされたクロースド・キャプション情報の欠如。
（ｄ）多数の空白行を含むクロースド・キャプション情報。
（ｅ）映画、ショー、又は他の番組についてのエンディング・クレジットの完了。
（ｆ）平均キーフレーム距離又は平均カットフレーム距離の趨勢、例えば増加する趨勢又は減少する趨勢。
（ｇ）ロゴの欠如。例えば、放送者を識別する重ね合わされたビデオ・ロゴ。
（ｈ）重ね合わされたテキストについての異なったフォントのタイプ、サイズ、及び色。
（ｉ）カラーパレット又は他の色特徴の急な変化。
【００１４】
署名は、マーク付けされたセグメント中のキーフレームから抽出され、特定の「起こりうる（probable）」署名リスト中に置かれる。本願で用いる「キーフレーム」の語は、一般的には、所定のショット又はビデオ信号の他の部分に関連する１以上のフレーム、例えば特定のショット中の最初のフレームを指すものである。起こりうる署名リストの例は、リストＬ１、Ｌｉ，Ｌｎ等と称される。ステップ２０２を通じた最初の回の間、起こりうるリストのうちの所定の１つは、一般的には、多数のコマーシャルに対する署名、並びに、番組に対する部分を含む。
【００１５】
所定の署名は、例えば、視覚フレーム署名又はオーディオ署名、又は、他の適当な識別特徴に基づくものでありうる。視覚フレーム署名は、例えば、ＤＣ及びＡＣ係数（ＤＣ＋ＡＣ）に基づく抽出方法、ＤＣ及び動き係数（ＤＣ＋Ｍ）に基づく抽出方法、又は、例えばウェーブレット又は他の変換に基づく他の適当な抽出方法を用いて抽出されうる。
【００１６】
上述のＤＣ＋ＡＣ方法は、当業者に周知であり、例えば１つのＤＣ係数と５つのＡＣ係数とを有する視覚フレーム署名を生成するのに使用されうる。
【００１７】
他の例として、上述のＤＣ＋Ｍ方法は、（キーフレーム１、署名１、キーフレーム２、署名２、等）の形の一組の署名を生成するのに使用されうる。このＤＣ＋Ｍ抽出方法は、例えば、「Video  Retrieval  of  MPEG  Compressed  Sequences  Using  DC  and  Motion  Signatures」なる名称の発明者エヌ・ディミトロヴァ（N.  Dimitrova）及びエム・アブデル−モッタレブ（M.  Abdel-Mottaleb）の１９９９年２月９日発行の米国特許第５，８７０，７５４号明細書、並びに、エヌ・ディミトロヴァ（N.  Dimitrova）及びエム・アブデル−モッタレブ（M.  Abdel-Mottaleb）著、「Content-Based  Video  Retrieval  By  Example  Video  Clip」、画像及び及びビデオデータベースの記憶及び検索に関する議事録Ｖ、ＳＰＩＥ、第３０２２巻、第５９乃至７０頁、米国カリフォルニア州サンノゼ、１９９７年、に詳細に記載されている。
【００１８】
他の視覚フレーム署名抽出技術は、エヌ・ディミトロヴァ（N.  Dimitrova）、ジェイ・マルティノ（J.  Martino）及びエイチ・エレンバース（H.  Elenbaas）著、「Color  Super-histograms  for  Video  Representation」、ＩＥＥＥ画像処理に関する国際会議、日本国神戸、１９９９年、に記載のように、少なくとも部分的にはカラー・ヒストグラムに基づくものでありうる。
【００１９】
オーディオ署名Ａｉは、ピッチ（例えば、最大、最小、メジアン、平均、ピーク数等）、平均振幅、平均エネルギー、帯域幅及びメル周波数ケプストラム係数（ＭＦＣＣ）ピークといった情報を含みうる。かかる署名は、例えば、コマーシャルの最初の５秒間から抽出された単一のオブジェクトＡ１の形でありうる。他の例として、オーディオ署名は、例えば、各識別されたカットに続く指定された時間期間から抽出された一組のオーディオ署名｛Ａ１，Ａ２，．．．，Ａｎ｝でありうる。
【００２０】
本発明はまた、多数の他の種類の署名を使用しうる。例えば、他の種類の署名は、広告されている製品又はサービスを記述するクロースド・キャプション・テキストの形であり得る。他の例として、署名は、フレーム番号に、フレームに関連する識別されたテキスト、例えばフリーダイヤル番号、会社名、製品又はサービス名、ＵＲＬ等のサブ画像からの情報を加えた形であり得る。更なる他の実施例として、署名は、フレーム番号に、適当な囲みボックスによって識別されるような、画像中の顔又は他のオブジェクトの位置及び寸法でありうる。これらの及び他の種類の署名の様々な組合せが使用されうる。
【００２１】
ステップ２０６において、新しい潜在的なコマーシャルセグメントが検出されるたびに、当該セグメントの署名は、起こりうるリスト内の他の署名と比較される。新しい署名が、起こりうるリストのうちの１つに既に存在する任意の署名と一致しない場合、起こりうるリストへ新しい署名が加えられる。新しい署名が起こりうるリストのうちの１つの１つ以上の署名と一致する場合、１つ以上の一致する署名は特定の「候補（candidate）」署名リスト内に入れられる。候補署名リストの例を、リストＣｌ，Ｃｊ，Ｃｍ等として示す。
【００２２】
新しい署名が、約３０秒間よりも以前又は約１０分よりも少ない以前のセグメントのいずれの署名とも類似していないが、約１０乃至１３分以前のセグメントの署名と類似する場合、これがコマーシャルの部分である可能性が高い。すなわち、類似する署名間のこの時間的な関係は、所定の確率リストが、指定されたおおよその時間間隔があけられた、例えば１０分間あけられたコマーシャルセグメントを含みうる。この時間的な間隔の関係は、他の種類の番組、放送時間スロット、国等に対して実験的に決定されうる。
【００２３】
他の種類の時間的又は文脈上の情報は、比較処理において考慮に入れられ得る。例えば、特定の署名が、ある日、前の日と同じ時間帯に現れれば、これはコマーシャルに関連付けられる可能性が高い。このリストはまた、比較処理を容易とするため、異なった日、時間、又はチャンネルスロットに対して異なったグループへ分割されうる。例えば、子供向け番組は、一般的には早朝の時間帯に放映され、例えば月曜の夜のフットボールといった夜の番組とは異なったコマーシャルがある可能性が高い。電子番組ガイド（ＥＰＧ）は、この情報及び他の情報を与えるために使用されうる。例えば、署名は、特定の番組名及びレーティングに関連付けられてもよく、例えば（番組名，レーティング，チャンネル，キーフレーム１，署名，キーフレーム５，署名等）の配置を生じさせる。ＥＰＧからの番組カテゴリ情報もまた、リスト中のコマーシャルを識別するのを助けるために使用されうる。
【００２４】
ステップ２０８において、新しい潜在的なコマーシャルセグメントが検出されると、当該セグメントのコマーシャルはまた、上述の候補リスト内のセグメントと比較される。新しい署名が候補リストのうちの１つの中の署名と一致すれば、新しい署名は、本願では永久リストとも称される特定の「発見したコマーシャル」リストへ移動される。発見したコマーシャルリストの例は、リストＰ１及びＰｋである。
【００２５】
ステップ２１０において、所与の発見したコマーシャルリスト上に少なくとも１つの署名がある場合、任意の新しい潜在的なコマーシャルセグメントの署名は、まず、当該リスト内の署名と比較される。一致が見つかれば、対応する署名に関連付けられるコマーシャル頻度カウンタは、１つインクリメントされる。発見したコマーシャルリスト内で署名の一致がなかった場合、新しい署名は１つ以上の候補リスト内の署名と比較される。所与の候補リスト内に新しい署名についての一致が見つからなければ、ステップ２０８のようにコマーシャル発見リストに新しい署名が入れられる。候補リスト内のいかなる署名とも一致がなければ、新しい署名は起こりうるリストのうちの１つに入れられる。
【００２６】
発見したコマーシャルリスト内の署名についての上述のカウンタは、どれだけ頻繁にインクリメントされるかを決定するために監視されえ、結果は、更なるコマーシャル識別情報を与えるのに使用される。例えば、カウンタが比較的短い時間期間内に、例えば約１乃至５分間の間にインクリメントされれば、これはおそらくはコマーシャルではない。他の例として、カウンタが非常に長い時間に亘って、例えば一週間又はそれ以上の間、インクリメントされなければ、コマーシャルがいずれはシステムによって「忘れられる」よう、カウンタはデクリメントされる。この種類の時間的な関係の手段は、上述の起こりうるリスト内の署名に対しても行われうる。有利には、本発明は、特定のビデオ内容の識別及び抽出を可能とする。本発明によれば、コマーシャルの内容及び種類は識別されうる。方法の詳細は、上述のような同時継続中の共有の米国特許出願第０９／４１７，２８８号明細書に詳述されている。
【００２７】
図３は、図２を参照して上述したように識別されたビデオ内容から記述情報を抽出する方法を示すフローチャートである。典型的には、広告主は、メッセージを比較的短い時間内に伝えることを望む。これにより、製品名、会社名、及び他の識別特徴は、コマーシャル放送中に頻繁に繰り返される。従って、１つの面では、例えば図２を参照して上述したように識別される放送番組のコマーシャル部分は、例えば各コマーシャル部分に関連するクローズド・キャプション等のトランスクリプト情報を解析することによって学習されうる。
【００２８】
従って、ステップ３０２において、コマーシャル部分に関連するトランスクリプト情報は、特定の単語及び特徴に対して解析される。例えば、トランスクリプト情報は、ステップ３０４において頻繁に生ずる語を検出することによって個々の種類のコマーシャルを識別するのに使用されうる。実際の放送されたコマーシャルの解析に基づいて、本願発明者は、所定の時間期間（１５秒間）内に非停止語が少なくとも３回生じた場合は、コマーシャルの終了を示すと決めた。非停止語は、「an」、「the」、「of」等以外の語である。本願発明者は、非停止語が、任意の１５秒の間隔中に３回以上、番組の非コマーシャル部分で生ずる可能性は低いことを見いだした。
【００２９】
以下のテキストは、２つのコマーシャルを含むLate-Night  Show  with  David  Lettermanから抽出されたクロースド・キャプション・テキストである。
【００３０】
【表１】
2006500859.tif 000002
クロースド・キャプション・テキストは、本発明の有効性を示し、単語「Nizoral」、「A-D」，「dandruff」及び「shampoo」は、タイムスタンプ１３７４８４７と１４４９０２３の間の第１のコマーシャル（１５秒）のセグメント中に少なくとも３回出願した。更に、「lauder」及び「pleasures」は、タイムスタンプ１４５１５９７と１５２８９４７の間の第２のコマーシャルの間に３回以上出現した。これは、広告主がメッセージを短い時間内に伝えようとし、従って、所望のメッセージ及び情報を短時間内に伝えるために製品名、会社名、及び製品の他の識別特徴を視聴者に対して頻繁に繰り返さなくてはならないことに基づく。所定の時間期間内のトランスクリプト情報内でのこれらの非停止語の発生を検出することにより、個々のコマーシャルが学習されえ、互いから分離されうる。
【００３１】
個々のコマーシャルの種類、例えばシャンプー又は香水等は、例えば、「Shift-Or  アルゴリズム」といった適切な文字列照合技術を用いることにより学習され、カテゴリへグループ化されうる。このアルゴリズムは、従来技術において当業者によって周知である。「Shift-Or  アルゴリズム」は、トランスクリプト・テキストが取得され発生された多数の源によりテキストへ導入されうる偽の文字（語、句、文章）を考慮に入れる。
【００３２】
個々のコマーシャルの種類が識別されると、ステップ３０６において、各コマーシャルに対応するトランスクリプト情報はコマーシャルと共に、例えばコマーシャルの種類によってインデックス付けされてデータベースに格納される。かかる情報の格納は、データベース内で特定のコマーシャルについて探索する探索機構を与え、例えば、それにより特定の広告が探索され、検索され、ユーザの要件に合うコマーシャルがユーザに提示される。例えば、データベースは、特定の種類のコマーシャル（自動車）又は特定の製品（ホンダ  アコード）に対するコマーシャルに関するコマーシャルを検索するよう探索されうる。データベースは、コマーシャルの種類、及び任意の追加的な識別特徴、並びにコマーシャル自体を含む。この方法の更なる詳細は、上述の同時継続中の米国特許出願第０９／９４５，８７１号明細書に完全に説明されている。
【００３３】
図４は、推奨のためにコマーシャルを選択する方法を示すフローチャートである。この方法は、決定木を用いてコマーシャルのプログラミングを推奨する。１つの面によれば、ユーザの過去の視聴履歴に基づいて、特定の視聴者の関心となりうる一組の推奨されたコマーシャルを識別するために帰納法原理が用いられる。
【００３４】
ステップ４０２において、ユーザの視聴履歴が監視され、ユーザによって実際に見られたコマーシャル（積極的な例）と見られていないコマーシャル（消極的な例）が解析される。例えば、図１及び図２を参照して上述した方法によって識別されたように、コマーシャルが放送されているときにユーザがそのチャンネルのままにしていれば、コマーシャルは見られたと判定される。ユーザがチャンネルを変えるかテレビジョンをミュートすれば、コマーシャルは見られていないと判定される。任意に、コマーシャルが見られているかを判定するために室内にユーザの中止又は存在を検出するカメラが設けられうる。個々のユーザの好みは、コマーシャルが検出され識別されるのと同時に監視され構築されうる。
【００３５】
一定のコマーシャルに対するユーザの好みは、例えば、図２及び図３を参照して上述したようにコマーシャルが識別され格納されるのと同時に決定されうる。例えば、ユーザプロファイルは、コマーシャルが識別され格納されている間、コマーシャルの放送中のユーザの行動に従って構築されうる。任意に、又は、追加的に、例えば以前に構築された、既存のユーザ視聴履歴は、ユーザの好みを決定するのに使用されうる。
【００３６】
積極的なコマーシャル例（即ち、見られたコマーシャル）及び消極的なコマーシャル例（即ち、見られていないコマーシャル）の夫々に対して、ステップ４０４において、ユーザプロファイル中に多数のコマーシャル属性、例えば、持続時間、広告の種類、所与のコマーシャルのジャンル、時刻、放送局コールサイン（例えば、ＣＮＢＣ，ＣＮＮ等）、及び特定の単語（dandruf,  shampoo,  nizoral-d等）が分類される。ステップ４０６において、各属性のエントロピーの順位に基づいて、階層的決定木において様々な属性の位置が決められる。決定木の各節点及び下位節点は、ユーザプロファイルからの所与の属性に対応する。決定木の各葉節点は、対応する葉節点に置かれたコマーシャルに対する積極的な推奨又は消極的な推奨のいずれかに対応する。決定木は、出来る限り多くの積極的な例を網羅するが消極的な例は１つも通らないように試みる。
【００３７】
例えば、訓練データ中の所与のコマーシャルが３０秒以上の持続時間を有し、家庭用品を広告する場合、コマーシャルは葉節点で積極的な例として分類される。その後、テストデータ中のコマーシャルがこれらの持続時間及び種別の属性についてのこの規準を満たす値を有する場合、コマーシャルが推奨される。
【００３８】
ステップ４０６において、決定木は「トップダウン分割統治法」アプローチを行う決定木を用いて構築又は学習される。本発明の決定木技術は、例えば、ロス・クインラン（Ross  Quinlan）著、「Programs  for  Machine  Learning」第４．５章、Morgan  Kaufmann出版社、米国カリフォルニア州パロアルト、１９９０年に記載の確立した理論に基づく。決定木は、容易に計算されえ、リアルタイムで使用されえ、任意の数のクラスへ拡張されうる。以下の段落では、決定木の原理について詳述する。
【００３９】
決定木は、ハント（Hunt）外により１９５０年代後半に開発された確立した概念学習の理論に基づく。例えば、ハント（Hunt）外著、「Experiments  in  Induction」、Academic  Press社、米国ニューヨーク（１９６６年）を参照。これは、ブライマン（Breiman）外著、「Classification  and  Regression  Trees」、米国カリフォルニア州ベルモント（Wadsworth社、１９８４年）；クインラン・ジェイ・アール（Quinlan  J.  R.）著、「Learning  Efficient  Classification  Procedures  and  their  Application  to  Chess  End  Games」、ミカルスキ・アール・エス（Michalski  R.  S.）、カーボネル・ジェイ・ジー（Carbonell  J.  G.）、及びミッチェル・ティー・エム（Mitchell  T.  M.）編、「Machine  Learning:  An  Artificial  Approach」第１巻、Morgan  Kaufmann出版社、米国カリフォルニア州パロアルト（１９８３年）；クインラン・ジェイ・アール（Quinlan  J.  R.）著、「Probablistic  Decision  Trees」、コドラトフ・ワイ（Kodratoff  Y.）及びミカルスキ・アール・エス（Michalski  R.  S.）編、「Machine  Learning:  An  Artificial  Approach」第３巻、Morgan  Kaufmann出版社、米国カリフォルニア州パロアルト（１９９０年）；並びに、クインラン・ジェイ・アール（Quinlan  J.  R.）著、「Programs  for  Machine  Learning」第４．５章、Morgan  Kaufmann出版社、米国カリフォルニア州サンマテオ、１９９３年によって拡張され普及された。
【００４０】
決定木を構築する基本的な方法は、次の通りである。即ち、Ｔを、例えば視聴者が好むコマーシャルと好まないコマーシャルといった学習ケースの集合とし、クラスを｛Ｃ1，Ｃ2，．．．，Ｃk｝と示すとする。以下の３つの可能性がある。
１．  Ｔは１つ以上のケースを含み、全てが単一のクラスＣjに属する：
Ｔに対する決定木は葉を識別するクラスＣjである。
２．  Ｔはケースを含まない：
即ち、決定木はやはり葉であるが、葉に関連付けられるべきクラスはＴ以外の情報から決定されねばならない。例えば、葉は、領域に関する背景知識の助けなしに選択されうる。
３．  Ｔは、クラスの混合に属するケースを含む：
このような場合、アプローチは、ケースの単一のクラスの集まりへ向かっているように見えるケースの下位集合へとＴを細分化することである。検定は、属性に基づいて、１以上の相互に排他的な結果｛Ｏ1，Ｏ2,...,Ｏn｝を有するよう選択される。Ｔは、下位集合Ｔ1，Ｔ2,..,Ｔnへ分割され、Ｔiは、選択された結果である結果Ｏiを有するＴ中の全てのケースを含む。Ｔに対する決定木は、検定を識別する決定節点と、各可能な結果に対する１つの枝とから構成される。同じ木構築アプローチは、ｉ番目の枝が、学習ケースの下位集合Ｔiから構築された決定木をもたらすよう、学習ケースの各下位集合に対して反復的に適用される。
【００４１】
木構築処理は、適切な検定の選択に依存する。Ｔを些細ではないように、少なくとも２つの下位集合｛Ｔi｝が空ではないように分割するいかなる検定も、いずれは単一のクラス下位集合へと分割されることとなり、これらの全て又は殆どが単一の学習ケースを含むようになっても分割される。しかしながら、本発明は、単に分割から木を構築するだけでなく、データ集合の構造を明らかとし、未知の場合について予測的な力を有する木を構築することを目的とする。検定は、通常は、以下説明する情報理論に基づき利得規準に基づいて選択される。
【００４２】
学習ケースの集合Ｔを下位集合Ｔ1，Ｔ2....,Ｔnへ分割するｎ個の可能な結果を有する仮説的な検定を考えると、この検定は、Ｔiの続く分割を探すことなく評価されるべきである場合は、利用可能な情報は、Ｔ及びその下位集合におけるクラスの分布である。Ｓはケースの任意の集合であるとし、freq（Ｃi，Ｓ）は、クラスＣiに属するＳ中のケースの数を示し、｜Ｓ｜は集合Ｓ中のケースの数を示すとする。検定を選択する基準を支える情報理論は、以下の通りである。メッセージによって伝達される情報は、その確率に依存し、その確率の基数２の対数の負として、ビットで測定されうる。例えば、８つの等しい確率のメッセージがあるとすると、これらのうちの任意のメッセージによって伝達される情報は、−log2(1/8)、即ち３ビットである。同じクラスＣjに属するケースの集合Ｓからランダムに１つのケースを選択すると、メッセージは以下の確率、
【００４３】
【数１】
2006500859.tif 000003
を有し、メッセージが伝達する情報は、
【００４４】
【数２】
2006500859.tif 000004
である。クラスのメンバシップに関するかかるメッセージから予想される情報を見つけるために、クラスに亘る和は、Ｓにおけるそれらの頻度に比例して取られ、
【００４５】
【数３】
2006500859.tif 000005
が与えられる。
【００４６】
訓練ケースの集合に適用するとき、info（Ｔ）は、Ｔ内のケースのクラスを識別するのに必要な情報の平均量を測定する。この量は、しばしば、集合Ｓのエントロピーとして知られる。Ｔが検定Ｘのｎ個の結果に従って分割されると、予想される情報は、下位集合に亘る加重和として見つけることができ、
【００４７】
【数４】
2006500859.tif 000006
によって与えられる。
【００４８】
以下の量、
【００４９】
【数５】
2006500859.tif 000007
は、検定Ｘに従ってＴを分割することによって得られる情報を測定し、しばしば利得規準と称される。この規準は、一般的に検定Ｘとクラスの間の相互情報と称される情報利得を最大化するよう検定を選択する。
【００５０】
利得規準は良い結果を与えるが、潜在的に重大な欠陥を有しうるものであり、即ち多くの結果を与える検定のために強いバイアスを有するという欠陥を有しうる。例として、属性のうちの１つが患者識別情報を含む仮定的な医療診断タスクを考える。各識別情報は一意であることが意図されるため、学習ケースの集合をこの属性の値で分割することは、夫々がただ１つのケースを含む多数の下位集合を生じさせる。これらの１つのケースの下位集合の全ては、単一のクラスのケースを含むため、infox（Ｔ）は０となる。従って、学習ケースの集合を分割するためにこの属性を用いることによる情報利得は最大である。しかしながら、予測の観点からは、かかる分割はあまり有用ではない。
【００５１】
利得規準に内在するバイアスは、多くの結果を伴う検定に帰因しうる見掛けの利得が調整される正規化によって調整される。ケースが属するクラスではなく、検定の結果を示すケースに関連するメッセージの情報内容について考慮すると、info（Ｓ）の定義に似たsplit  info（ｘ）は以下の通りである。
【００５２】
【数６】
2006500859.tif 000008
これは、Ｔをｎ個の下位集合へ分割することによって発生する潜在的な情報を表わし、一方で、情報利得は、同じ分割から生ずる分類に関連する情報を測定する。すると、式は、
【００５３】
【数７】
2006500859.tif 000009
となり、分割によって生ずる情報の比率を表わす。分割情報が小さい場合、この比率は不安定である。これを防止するために、利得比規準は、情報利得が少なくとも調べられる全ての検定に亘る平均利得と同じくらい大きくなくてはならないという制約を受ける比率を最大化するよう検定を選択する。
【００５４】
決定木の構築のための上述の説明は、任意の場合について検定の結果が決定されうるという想定に基づく。しかしながら、実際は、データはしばしば属性値が欠けている。これは、値が特定のケースに関連がないため、データが収集されたときに記録されなかったため、又はデータを入力する責任のある対象によって解読され得ないためでありうる。かかる不完全さは、実世界データでは一般的である。すると、残される選択肢は一般的に２つである。即ち、利用可能なデータのうちのかなりの比率が廃棄され、いくつかのテストケースが分類不可能として宣言されること、あるいは、アルゴリズムは欠如した属性値に対処するよう修正されねばならない。殆どの状況では、前者は、パターンを見つける可能性を低下させるため許容できない。欠落した属性値を扱うために規準を修正することは、以下のように実現されうる。
【００５５】
Ｔを学習集合とし、Ｘを、いくつかの属性Ａに基づく検定とし、Ａの値は、Ｔの中のケースの分数Ｆでのみ既知であるとする。Ａの既知の値を有するケースのみを考慮に入れること以外は、info（Ｔ）及びinfox（Ｔ）は以前と同様に計算される。利得の定義は、以下の式、
gain(X)＝Ａが既知である確率×（info（Ｔ）−infox（Ｔ））＋Ａが未知である確率×０＝Ｆ×（info（Ｔ）−infox（Ｔ））
へと修正されうる。
【００５６】
この利得の定義は、関連のある属性の既知の値を有するケースを、訓練集合中の当該ケースの分数で乗算したものから見た見掛けの利得である。同様に、split  info（Ｘ）の定義もまた、追加的なグループとしての未知の値を有するケースに関して変更されうる。検定がｎ個の結果を有する場合、その分割情報は、検定がケースをｎ＋１個の下位集合へ分割したかのように計算される。利得及び分割情報の修正された定義を用いると、訓練集合の分割は以下のように達成される。既知の結果Ｏiを有するＴからのケースが下位集合Ｔiに割り当てられると、当該のケースが下位集合Ｔiに属する確率は１であり、全ての他の下位集合に属する確率は０である。しかしながら、結果が未知であるとき、より弱い確率の宣言のみがなされうる。ケースが既知の結果を有する場合、この重みは１である。ケースが未知の結果を有する場合、重みは、その点における結果Ｏiの確率にすぎない。各下位集合Ｔiは、おそらくは分数のケースの集合であり、従って｜Ｔi｜は、集合中のケースの分数の重みの和として再び解釈されうる。Ｔ中の訓練ケースが最初に１でない重みを有することが可能であり、なぜならばＴは以前の分割の１つの下位集合であるかもしれないからである。一般的には、その結果が未知であり重みｗを有するＴからのケースは、重みと共に各下位集合Ｔiに割り当てられ、
ｗ×結果Ｏiの確率
である。
【００５７】
後者の確率は、結果がＯiであることが既知であるＴのケースの重みの和を、この検定に対する既知の結果を有するＴのケースの重みの和で割り算したものとして推定される。
【００５８】
クラスが「見られたコマーシャル」及び「見られていないコマーシャル」であると考えられると、決定木のフォーマットは、節点が行われるべき上述の検定に対応し、葉が２つのクラスに対応する、節点及び葉を有するようなものである。未知のケース（ショー）を検定することは、ここでは、未知のケースがどのクラスに属するかを決定するために木を分析（parse）することを含む。しかしながら、特定の決定節点において、当該の属性値が未知であるという状況に遭い、検定の結果が決定されえないと、システムは全ての可能な結果を探し、結果としての分類を結合する。ここで、木の根から、又は下位木から葉への多数の経路があるため、分類は、単一のクラスではなくクラスの分布である。未知のケースについてのクラス分布が得られると、最も高い確率を有するクラスは予測クラスとして割り当てられる。
【００５９】
データベース中の各コマーシャルに対して、また、ユーザの好みを適用して、決定木は、コマーシャルを葉節点のうちの１つへ分類するよう調べられる。割り当てられた葉節点に基づいて、所与のプログラムは、積極的な推奨又は消極的な推奨のいずれかである。例えば放送から識別されたいずれのコマーシャルの集合も、ステップ４０８における推奨のために決定木に適用されうる。例えば、視聴者が以下の属性、即ち、
時間：  ９：００ｐｍ
局  ：  ＣＮＢＣ
持続時間：  ３０秒
種類    ：  速い動き
ジャンル：  家庭用品
特定の語：  dandruff（フケ）,  shampoo（シャンプー）
を有するコマーシャルを好むことが決定されると、決定木の上の属性節点に続く葉節点は積極的な属性を有し、例えば８９％のランキングを含みうる。コマーシャルを視聴者へ推奨するかどうかを決定するためにコマーシャルを適用するとき、木はそのまま使用されてもよく、又は、木は、
ＩＦ(時間＞＝８：３０ＰＭ)ＡＮＤ（持続時間＞１５秒）ＡＮＤ（ジャンル＝家庭用品）
ＴＨＥＮ
ＰＯＳ［８９％］
のような一組の規則へ分解されてもよい。この規則によれば、全てのコマーシャルは記述情報を有し、上述の規準に一致するユーザ好み情報は８９％の確率を有する積極的な例として分類されうる。これらは積極的であるとして分類されるため、推奨される。従って、テストデータであるコマーシャルが、
時間：  １１：００ｐｍ
局  ：  ＡＢＣ
持続時間：  ６０秒
種類    ：  遅い動き
ジャンル：  家庭用品
特定の語：  electronics（電化製品）,  TV（テレビ受像機）
といった属性を有する場合、属性値は上述の規則を満たすため、このコマーシャルは推奨される。
【００６０】
この方法の更なる詳細は、上述のような同時継続の共有の米国特許出願第０９／４６６，４０６号明細書に記載されている。
【００６１】
特定のユーザに対する推奨のために決定されたコマーシャルは、次にユーザへ提示される。図５は、推奨されたコマーシャルをユーザへ提示するダイナミック・チャンネル作成を示す図である。ステップ５０２において、ユーザは、コマーシャルを見るために個人用チャンネルを選択することが可能とされる。例えば、遠隔制御器の星（＊）ボタンは、画面上に個人用チャンネルモードを呼び出すために使用されうる。例えば、決定木が作成され、ローカルに格納されると、星（＊）ボタンを押すことにより、コマーシャルサービスからコマーシャルの転送が開始しうる。これらは、決定木に適用され、推奨のために決定されたコマーシャルは再生のために格納される。
【００６２】
ステップ５０４において、視聴者に対する推奨のために選択されたコマーシャルのリストは、例えばテレビジョン画面等のディスプレイ上に表示される。視聴者は、視聴のために意図される特定のコマーシャルを選択する。ＶＣＲ上のレコーダは、ステップ５０６において、コマーシャルを画面上での使用のためにもたらすよう自動的にプログラムされる。この方法の更なる詳細は、上述の同時継続中の共有の米国特許出願第０９／８２１，０５９号に記載されている。
【００６３】
図６は、１つの面の本発明の構成要素を示すシステム図である。コマーシャルを推奨するシステムは、図２及び図３を参照して説明したように、コマーシャルを検出するコマーシャル検出器モジュール６０４と、検出されたコマーシャルから記述情報を抽出するモジュール６０６とを含むプロセッサ６０２を含む。検出されたコマーシャル中の抽出された情報は、上述のように構築される決定木に基づいて図４を参照して説明されるようにどのコマーシャルがユーザに推奨されるべきかを決定する推奨器モジュール６０８へ入力される。推奨のための選択されたコマーシャルは、次に、図５を参照して説明したようにダイナミック・チャンネル作成モジュール６１０を介してユーザへ提示される。
【００６４】
本願に記載した方法によれば、コマーシャル及びそれらの種類及び属性が識別され、視聴者の好みが決定される。識別されたコマーシャル及び視聴者の好みを用いて、決定木が構築又は学習される。決定木は、これらのコマーシャルのうちのどれが視聴者へ推奨されるべきかを決定するよう１以上のコマーシャルに適用される。推奨のために選択されたコマーシャルは、ダイナミックな個人用チャンネルを用いて視聴者へ提示される。推奨のために決定木に適用されるコマーシャルは、リアルタイムで放送されえ、即ちこれらは放送される。推奨のために決定木に適用されるコマーシャルはまた、視聴者に対して再生される既に記憶された又は録画されたものでありうる。同様に、決定木を構築するのに用いられるコマーシャルは、既に識別され種別が分けられ、或いは、これらのコマーシャルは放送から識別されるように決定木を構築するのに使用されうる。任意に、決定木の構築は、ユーザの好みが連続的に監視及び更新されるにつれて、ユーザの好みが変更されうる継続的な処理でありうる。
【００６５】
本発明は、いくつかの実施例を参照して説明されたが、当業者によれば、本発明は図示され説明された特別の形に限られるものではないことが理解されよう。例えば、コマーシャルを抽出し識別するために他の公知の方法が使用されうる。更に、このように識別されたコマーシャルを推奨するために他の公知の方法が使用されうる。即ち、形及び細部についての様々な変更は、添付の特許請求の範囲に定義されるように本発明の趣旨及び範囲を逸脱することなくなされうる。
【図面の簡単な説明】
【００６６】
【図１】本発明の１つの面のコマーシャル推奨方法を示すフローチャートである。
【図２】ビデオ信号中のコマーシャルを識別又は検出する方法を示すフローチャートである。
【図３】識別されたビデオ成分から記述情報を抽出する方法を示すフローチャートである。
【図４】推奨のためにコマーシャルを選択する方法を示すフローチャートである。
【図５】推奨されたコマーシャルをユーザに提示するためのダイナミックチャネル作成を示すフローチャートである。
【図６】１つの縁で本発明の構成要素を示すシステム図である。
【図１】
2006500859.tif 000010
【図２】
2006500859.tif 000011
【図３】
2006500859.tif 000012
【図４】
2006500859.tif 000013
【図５】
2006500859.tif 000014
【図６】
2006500859.tif 000015
【国際調査報告】
2006500859.tif 000016
2006500859.tif 000017
2006500859.tif 000018