JP2009536412A - 対象を定めた広告に適したリアルタイム視聴者推定およびコマーシャル選択を実施する方法および装置 - Google Patents

Abstract

測定装置からの入力測定値は、連鎖の遷移が信号に依存するマルコフ連鎖として処理される。このとき、測定装置に関係する所望の情報は、対象時刻における信号の状態を推定することによって得られる。観測モデルに基づいて信号の推定を提示するために、非線形フィルタシステムが使用されうる。非線形フィルタシステムは、非線形フィルタモデルと最適非線形フィルタ解を近似する近似フィルタとを含む。近似フィルタは、粒子フィルタ、または観測モデルに基づいて信号を実質的にリアルタイムで推定することを可能にする離散状態フィルタであってもよい。一用途において、ケーブルテレビネットワークのデジタルセットトップボックス（２００）に対して入力されるクリックストリーム（２０８）が解析され、広告（２０４）がユーザ（２０５）を対象としうるようにデジタルセットトップボックス（２０６）のユーザ（２０５）に関する情報を決定する。

Description

本発明は、観測過程がマルコフ連鎖としてモデル化される非線形フィルタリングの革新と、通信ネットワークにおけるユーザ機器デバイスのユーザ構成、たとえば、デジタルセットトップボックス（ＤＳＴＢ）環境におけるテレビ視聴者の数および人口統計を推定するために本発明の実施形態を利用することとに関する。さらに、本発明は、現在のネットワーク利用（たとえば、視聴率）の最適な条件付き推定のサンプリングに基づいて使用できるネットワーク帯域幅に資源のどの集合、たとえば、コマーシャルを挿入すべきかを最適に決定する方法を提供する。

本出願は、米国特許法第１１９条の下で、２００６年５月２日に出願された「対象を定めた広告に適したリアルタイム推定およびコマーシャル選択を実施する方法および装置（ＭＥＴＨＯＤ ＡＮＤ ＡＰＰＡＲＡＴＵＳ ＴＯ ＰＥＲＦＯＲＭ ＲＥＡＬ−ＴＩＭＥ ＥＳＴＩＭＡＴＩＯＮ ＡＮＤ ＣＯＭＭＥＲＣＩＡＬ ＳＥＬＥＣＴＩＯＮ ＳＵＩＴＡＢＬＥ ＦＯＲ ＴＡＲＧＥＴＥＤ ＡＤＶＥＲＴＩＳＩＮＧ）」という名称の米国仮出願第６０／７４６，２４４号の優先権を主張するものである。また、本出願は、２００６年１月１２日に出願された「放送ネットワーク資源配信に関する対象を定めた印象モデル（ＴＡＲＧＥＴＥＤ ＩＭＰＲＥＳＳＩＯＮ ＭＯＤＥＬ ＦＯＲ ＢＲＯＡＤＣＡＳＴ ＮＥＴＷＯＲＫ ＡＳＳＥＴ ＤＥＬＩＶＥＲＹ）」という名称の米国特許出願第１１／３３１，８３５号の優先権を主張するものである。これら両出願の内容は、あたかもその全体が記載されているかのように本明細書に組み込まれる。

総じて、テレビ視聴者へのコマーシャルの配信はこの５０年にわたって変化が比較的少なかった。市場調査会社と広告主は、歴史的なＮｉｅｌｓｏｎ（商標）視聴率情報を使って対象視聴者が何を見ているかを判断しようとする。このデータは、特定時間にテレビ番組の特定放映分を見た世帯数の推定と同時に、人口統計分析（通常、年齢、性別、収入、および民族性に基づく）を提示する。このようなデータ（他の視聴率データ）は、現在のところ、ユーザがテレビを見ていることを知らせた時点でどんな番組が見られているかを自動的にモニタする「ピープルメータ」データを使って収集される。これらのサンプルは比較的小さく、現在、全米各地の全視聴率の推定に使用されているのはおよそ８０００世帯にすぎない。放送からケーブルテレビへの視聴者が移行し、一世帯内のテレビ受像機台数の増加に伴って利用可能なテレビチャネル数が増加するにつれて、このような小さいサンプルに基づいてテレビ番組の実際の視聴者を正確に推定することは次第に困難になる。結果として、シェアの比較的小さい有線テレビ局はその視聴率を正しく推定することができず、したがって、広告主は利益の上がるターゲット層を正しく把握することができない。

デジタルケーブル供給への需要が高まることによってＤＳＴＢの普及が続くと、各世帯に関するより正確な情報が理論上は得られうる。すなわち、セットトップボックスは、どんなチャネルが見られているか、何時間そのチャネルが見られているか、などについての情報にアクセスする。この豊富な情報は、正しく処理されると、世帯の行動の知見を提供しうる。しかし、この情報は、広告主が希望する情報の種類、すなわち、特定時間にどんなタイプの人々が見ているかの情報を直接提供することはできない。広告主は、マーケティングの費用を削減してその効果を高めるために、自分の広告を対象視聴者に最も的確に掲示したいと願う。さらに、広告主は、不適切な視聴者にコマーシャルを放映することに関する負の広告費を回避したいと願う。広告主にその投資を最大にする能力を提供する鍵は、視聴者数を数える方法を変えることであり、これによって、「ジャンル全体の比較価値および人口統計区分全体が『変わる』可能性がある」（Ｇｅｒｔｎｅｒ，Ｊ；Ｏｕｒ Ｒａｔｉｎｇｓ，Ｏｕｒｓｅｌｖｅｓ；Ｎｅｗ Ｙｏｒｋ Ｔｉｍｅｓ；Ａｐｒｉｌ １０，２００５）。

現在の視聴者または視聴者の人口統計を明確にするために、様々なシステムが提案または実施されている。これらのシステムの一部には、ユーザに識別情報や人口統計情報を明白に入力するよう求めるという煩わしいものがあった。他のシステムは、様々な情報源からの情報に基づいて視聴者の行動的特徴を明らかにしようとした。しかし、これらのシステムは一般に以下の１つまたは複数の欠点があった。すなわち、１）これらのシステムは、現在誰が見ているかよりも家庭に誰がいるかに注目されること、２）これらのシステムは、家族の一部に関する大まかな情報しか提供しない場合があること、３）これらのシステムはユーザの関与を必要とし、これは一部のユーザにとって望ましくなく、誤差を伴う場合があること、４）これらのシステムは、複数の視聴者がいるときそれを判断する、または複数の視聴者がいる場合における人口統計を正確に定めるための枠組みを備えていないこと、５）これらのシステムは、前提が全く静的であり、世帯構成および人口統計の変化を適正に処理しないこと、および／または６）これらのシステムは、準最適な技術を採用しており、広範囲の訓練を必要とし、過剰な資源を必要としさもなければ実用化が制限されることである。

本発明は、対象信号に関する情報を得るために測定装置から得られた観測値を解析することに関する。一用途において、本発明は、ユーザ機器デバイスのユーザに関する情報（たとえば、ユーザの視聴者分類パラメータ）を決定する通信ネットワークのユーザ機器デバイスに関するユーザ入力（ユーザのたとえば、ケーブルテレビネットワークのデジタルセットトップボックス（ＤＳＴＢ）に関して入力されるユーザ入力クリックストリーム）を解析することに関する。本発明の一部の態様は、信号に関する情報を推論するために測定装置から受信されている、損傷したデータ観測値、歪んだデータ観測値、および／または部分データ観測値を処理すること、ならびに対象時刻における信号の状態を実質的にリアルタイムで推定するフィルタシステムを提供することに関する。とりわけ、このようなフィルタシステムは、許容状態、あるいは、観測環境から推論される組合せに関する一定の拘束条件に基づく最適な非線形フィルタ解の実用的な近似を提供することができる。

本発明の一態様に従って、解析される装置から得られるデータまたは測定値に関する観測モデルを開発する方法および装置（「システム」）が提供される。とりわけ、システムは、入力測定値をその遷移が信号に依存するマルコフ連鎖としてモデル化する。観測モデルは、外因的情報、すなわち、入力測定値に対する外部情報（入力測定値とは必ずしも無関係でない）を考慮してもよい。一実施形態において、入力測定値はＤＳＴＢのクリックストリームを表す。クリックストリームは、チャネル選択事象、および／または、たとえば、音量調節に関する他の入力を表してもよい。この場合、観測モデルは、選択されたチャネルに関連するプログラミング情報（たとえば、ヘッドエンドなどのネットワークプラットフォームからダウンロードされた）を含んでもよい。したがって、クリックストリーム情報はマルコフ連鎖として処理される。

この後、デバイスに関係する所望の情報は、対象時刻における信号の状態を推定することによって得られうる。ＤＳＴＢのクリックストリームを解析する例において、信号は、ユーザ構成（１ユーザまたは複数ユーザおよび／または関連する人口統計を含む）、および以下でさらに詳しく説明されるようなチャネル変化形態などのクリックストリームに影響を与える付加的要因を表してもよい。信号が推定されると、たとえば、資源目標システムと関連して使用されるユーザ構成情報を提供するために、過去、現在、または未来時における信号の状態が決定されうる。

本発明のさらに別の態様に従って、システムは観測モデルに基づく信号状態の実質的にリアルタイムの推定値を生成する。この点において、観測モデルに基づく信号の推定値を提供するために非線形フィルタシステムが使用される。非線形フィルタシステムは、非線形フィルタモデルおよび最適な非線形フィルタ解を近似する近似フィルタを含んでもよい。たとえば、近似フィルタは、観測モデルに基づく信号の実質的なリアルタイム推定を可能にする粒子フィルタまたは離散状態フィルタを含んでもよい。ＤＳＴＢの例において、非線形フィルタシステムは、複数の視聴者を含むユーザ構成を識別し、潜在的視聴者の変化、たとえば、以前は未知であった人々の参入や潜在的視聴者に関する従前ユーザの離脱に適応しうる。

本発明のさらに別の態様に従って、システムは、観測モデルに対して対象情報を得るために観測モデルにフィルタを適用することによって得られる信号を使用する。具体的には、過去、現在、または未来時に関する情報は、対象時刻における信号の推定状態に基づいて得られる。ＤＳＴＢの使用を解析する場合、特定時間におけるＤＳＴＢのユーザの身元および／または人口統計が信号状態から判断される。この情報は、ＤＳＴＢにおいて配信する資源オプションの中から資源を選択し、かつ／または資源を受信したユーザに対して配信された資源の適合度を決定または報告し、あるいはその両方を行うために、たとえば、次回のコマーシャルまたはプログラミングスポットに適した資源の「投票」または識別に使用されてもよい。

本発明の上記態様は、任意の適切な組合せで提供される。さらに、上記態様のいずれかまたはすべては、対象を定めた資源配信システムに関連して実施される。
本発明の一実施形態において、通信ネットワーク、たとえば、ケーブルテレビネットワークにおいてユーザ機器デバイスのユーザの目標資源に使用するシステムが提供される。このシステムは、ユーザ機器デバイスに関する１ユーザまたは複数ユーザによる入力に基づく観測モデルの開発、時間に対する上記ユーザ機器デバイスの１ユーザまたは複数ユーザの少なくともユーザ構成を反映する信号としての観測モデルのモデル化、信号の状態として対象時刻におけるユーザ構成の決定、およびユーザ機器デバイスに関する資源を対象として決定されたユーザ構成の利用を含む。このように、フィルタリング理論は、ユーザ構成を示す信号を生成するために、クリックストリームなどの、ユーザ機器デバイスの入力に対して適用される。

入力はマルコフ連鎖としてモデル化される。さらに、信号のモデルは、複数のユーザを含むものとしてユーザ構成を表現することができる。したがって、資源を対象とし、および／または視聴者の規模と構成をより良く評価し（たとえば、資源配信のための評価と支払を改善するために）、あるいはその両方を行う際に使用する複数ユーザの状況が明らかになりうる。さらに、信号モデルは、ユーザ構成の変化、たとえば、ユーザ視聴者の増減を表現できることが好ましい。

観測モデルに基づく信号を得るために非線形フィルタが規定される。この点において、信号は時間に対する世帯のユーザ構成を表してもよく、視聴者分類パラメータ（たとえば、現在の１ユーザまたは複数ユーザの人口統計）は対象時刻における信号状態の関数として決定されうる。最適な非線形フィルタ解の実用的推定を行うために、非線形フィルタの動作を近似する近似フィルタが提供される。たとえば、近似フィルタは、粒子フィルタまたは離散状態フィルタを含んでもよい。さらに、近似フィルタは、１つまたは複数の信号成分に対して少なくとも１つの拘束条件を実現してもよい。この点において、拘束条件は、第２の成分の変動が許容される場合に信号の１成分を時間に対して不変であるものとして処理するように働作してもよい。さらに、拘束条件は、第１の成分の少なくとも１つの状態を異常であるものとして処理するか、または異なる複数の信号成分の状態の一部の組合せを異常であるものとして処理するよう働作してもよい。たとえば、ＤＳＴＢのクリックストリームの場合、クリック事象の発生は少なくとも１名の人が存在することを示す。したがって、少なくとも１名の人の存在に対応するユーザ構成のみがクリック事象の発生時に許容される。他の許容される組合せまたは許容されない組合せによって、収益を場所に関係づける場合がある。拘束条件は、有限空間近似フィルタに関連して実行してもよい。たとえば、異常なセルにありがちな値は別の場所に移されてもよく、たとえば、周辺の正当なセルに比例して移動されてもよい。このようにして、近似フィルタは過度の処理リソースを必要とせずに正当な解に迅速に収束する。拘束が少なくとも１つの計算された潜在状態を異常であると判定するように働く場合、近似フィルタはこれに関連する１つまたは複数のカウントを再分配してもよい。

また、近似フィルタは、異常な状態への収束を阻止するように機能してもよい。したがって、近似フィルタは、論理的に不可能であるか、または起こりそうもない（ユーザが存在しないときのクリック事象）か、または規定により異常と見なされる（所与の場所では許容されない収入範囲）ＤＳＴＢに関するユーザ構成への収束を回避するように設計される。一実施形態において、これは、離散空間フィルタの正当なセルにシードカウントを加えることによって達成されて異常なセルに関連した収束を阻止する。

好ましくは、ユーザ構成情報はデジタルセットトップボックスにおいて決定される。すなわち、ユーザ情報は、デジタルセットトップボックスにおいて計算され、投票、資源選択、および／または報告に使用される。あるいは、クリックストリームデータは、ヘッドエンドなど、たとえば、メッセージング帯域幅が十分であり、ＤＳＴＢ処理リソースが制限される、ユーザ構成情報が決定されうる別のプラットフォームに向けられてもよい。さらに別の方法として、ユーザ構成情報（たとえば、資源投票情報に対立するものとして）は、ヘッドエンド、または挿入するコンテンツを選択する際に使用される他のプラットフォームに送信されてもよい。

決定されたユーザ構成情報は、資源目標システムによって使用されてもよい。たとえば、この情報は、資源をネットワークのコンテンツストリームに挿入できるヘッドエンドなどのネットワークプラットフォームに提供されてもよい。この点において、プラットフォームは、複数のＤＳＴＢからの入力を利用して利用可能なネットワーク帯域幅に挿入する資源を選択してもよい。資源配信のユーザごとの値を表す情報などの追加情報はこれに関連して利用されてもよい。プラットフォームは、観測モデルとして複数のユーザ機器デバイスからの情報を処理し、観測モデルに対して適切に構成されたフィルタを適用して対象時刻におけるネットワーク視聴者の全体構成を推定してもよい。

本発明の他の態様に従って、確率制御理論が対象を定めた資源配信、たとえば、動的視聴者分類および／またはテレビ広告選択の問題に適用される。従来、確率制御理論は、信号または機能を直接的に計算することができずに、ノイズを含む可能性のある観測値や不完全である可能性のある観測値に基づいて推定するしかない状況において適用されてきた。このような状況において、測定装置からの測定値は、状態情報を判定できる信号を推定するために確率制御理論によって処理されうる。たとえば、遠隔制御からのクリックストリームなどの入力装置からの測定値は、ノイズを含む観測値と考えられ、入力へ入力項目に関する世帯または視聴者および行動形態を表す信号を推定するために確率制御を使って処理される。確率制御では、特定時刻における信号の状態がそのときの視聴者の構成と形態を表すように信号を追跡することができる。この情報は、たとえば、視聴者の分類パラメータを利用可能な広告の対象パラメータに合わせることによって、配信される対象を定めた広告の選択に使用されうる。

本発明および本発明の他の利点をさらに十分に理解するために、ここで、図面を併用して以下で詳しい説明を行う。
以下の説明において、本発明はケーブルテレビネットワークに関する対象を定めた資源配信（たとえば、対象を定めた広告）システムに即して記載され、本発明は本明細書に記載されるような背景において具体的な利点を提供する。ただし、本発明の様々な態様はこうした背景に限定されるものでないことは理解されよう。さらに正確に言えば、本発明の範囲は冒頭に記載された特許請求の範囲によって規定される。

ケーブルテレビネットワークに関して対象を定めた様々な広告システムが提案または実施されている。これらのシステムは、一般に、コマーシャルの価値を最大にするためにコマーシャルが視聴者に適合しうるよう現在の視聴者構成を理解することに基礎を置いている。様々なこのようなシステムには現在の視聴者の分類パラメータ（たとえば、人口統計）を特定する本発明の構造と機能性が有効でありうることは理解されよう。したがって、特定の対象を定めた資源配信システムが説明を目的として以下で参照されるが、本発明がより広範囲に適用可能であることは理解されよう。

本発明が採用されてもよいことに関連して１つの対象を定めた資源配信システムが、２００６年１月１２日に出願された上記米国特許出願第１１／３３１，８３５号に記載されている。簡略にするため、本明細書ではこのシステムの全詳細を割愛する。一般に、このシステムでは、複数の資源オプションが所与のプログラミングチャネルにおける所与の時点で提供される。この点についてはその説明に記載されるように、様々な種類の資源が対象とされうるが、対象を定めた広告（たとえば、コマーシャルを対象とする）は例示的な用途であり、本明細書において好都合で簡単な引例として使用される。したがって、所与のプログラミングチャネルは、コマーシャルの時間の１つまたは複数の広告スポットに対する広告オプションを提供する複数の資源（たとえば、広告）チャネルによってサポートされてもよい。ＤＳＴＢは、対象を定めた広告を現在の視聴者に提供するために、コマーシャルの時間中に適切な広告チャネルに目立たないように（視聴者からは）切り替える働きをする。

本発明の視聴者識別の構造および機能性は、上記の対象を定めた資源配信システムにおいて様々な方法で使用されうる。上記のシステムにおいて、対象パラメータを含む広告リストがコマーシャルの時間に先立ってＤＳＴＢに送信される。ＤＳＴＢは、現在の視聴者に関する分類パラメータを決定し、これらの分類パラメータをリストの各広告に関する対象パラメータに適合させ、１つまたは複数の広告に関する「投票」をヘッドエンドに送信する。ヘッドエンドは、複数のＤＳＴＢからの投票を集め、最適化された広告群を利用可能な帯域幅（これはプログラミングチャネルと複数の広告チャネルを含んでもよい）に組み入れる。コマーシャルの時間に、ＤＳＴＢは、広告群の「経路」を選択して適切な広告を配信する。この後、ＤＳＴＢは、実際の視聴者が対象パラメータとどの程度一致したかを示す適合度情報とともに、どんな広告が配信されたかを報告しうる。

本発明は、上記の対象を定めた資源配信システムにおいて直接的に実行されうる。すなわち、本明細書に記載された技術を用いると、現在の視聴者に関する視聴者分類パラメータがＤＳＴＢにおいて決定されうる。この情報は、上記の係属中の出願に記載されたような投票、広告選択、および／または適合度判定に使用されうる。あるいは、以下の説明には、上記投票過程の代替であるフィルタ理論に基づくヘッドエンド広告選択システムが記載される。さらに別の代替として、クリックストリーム情報をヘッドエンド、または別のネットワークプラットフォームに提供することができ、ここで視聴者分類パラメータが計算されてもよい。したがって、視聴者分類パラメータ、広告選択、および他の機能性を変更することができ、ＤＳＴＢ、ヘッドエンド、または他のプラットフォームの間で様々な方法で分配されてもよい。

次節はいくつかの部分に分割される。第１部では、関連性のある非線形フィルタ理論の背景が説明される。第２部では、構造およびモデルクラスが説明される。
１．１ 非線形フィルタリング
対象を定めた広告視聴率（潜在的および現在の）問題を適切に解決するために、フィルタリングの数学的最適な分野に関心を向けてもよい。

１．１．１ 従来の非線形フィルタリングの概要
非線形フィルタリングは、信号の損傷したデータ観測値、歪んだデータ観測値、または部分データ観測値に基づいてリアルタイムで一部の非線形ランダムダイナミック課程（通常、「信号」と呼ばれる）の過去、現在、および／または未来の状態の最適推定を扱う。一般に、Ｘ_ｉは、ある確率空間

で定義されるマルコフ過程と見なされ、あるマルチンゲール問題に対する解である。観測は、通常、離散時間ｔ_ｍで行われ、センサ関数

を用いた確率論的な信号に依存する。実際には、従来の理論および方法はこの種の観察の下で構築され、測定値は信号の歪んだ（非線形関数ｈによる）サンプル、損傷した（ノイズＶによる）サンプル、部分（信号の状態の一部分のみへの依存可能性ｈによる）サンプルである。最適フィルタは、現時点までに観察値が有効であることを前提として、信号の状態の条件付き配信を提供する。

フィルタは、信号の現在の状態のみでなく過去および未来の状態に対しても、信号の全経路と同様に、最適な推定を提示する。

ここで、０≦ｔ_ｒ≦ｔ_ｓ＜∞である。

ある種の線形環境において、有効な最適な再回帰式が利用可能である。信号が伊藤確率微分方程式

に従うものとし、Ａは線形でＢは定数である。さらに、観測関数は

の形をとり、ここで、

は独立したガウス確率変数である。この公式はカルマンフィルタとして知られる。カルマンフィルタはその推定を行う上で非常に有効であるが、観測過程における信号の記述が厳密であるためその適用は本質的に制限される。信号のダイナミックスが非線形である場合、または観測値が非加法的ノイズおよび／または相関ノイズを有する場合、カルマンフィルタは準最適な推定値を提示する。結果として、これらのより一般的なシナリオにおいて最適な推定値を提示する他の方法が模索される。

最適非線形推定に関する方程式が数十年間利用可能であったが、最近までこれらがほとんど役に立たないことが分かっていた。最適方程式は、無限のメモリと計算資源を使用する必要があるため、コンピュータ上では実行不可能であった。しかし、過去１０年間に、この問題を克服する最適フィルタリング方程式の近似式が生成された。これらの近似式は、通常、漸近的に最適である。すなわち、計算に使用される資源量が増加するにつれて近似式が最適解に収束する。この種の２つの最も一般的な方法は、粒子法と離散空間法である。

１．１．２ 粒子フィルタ
粒子フィルタリング法は、

で示される信号の独立したコピー（「粒子」と呼ばれる）の生成を伴い、ここで、Ｎ_ｔは時刻ｔにおいて使用される粒子数である。これらの粒子は、信号の確率法則に従って時間とともに発生される。この後、各粒子には重み値

が割り当てられ、情報を効果的に取り入れて一連の観測値（Ｙ_１，．．．，Ｙ_ｍ）を形成する。これは、ｍ個の観測値の後の重みがｍ−１の後の重みにｍ番目の観測値Ｙ_ｍに依存する係数を掛けた値となるように行われうる。ただし、これらの重みは常にきわめて不均一であり、つまり、多くの粒子（比較的小さい重みを有する粒子）は、重要でなくなり、コンピュータサイクルを浪費すること以外はほとんど何もしない。むしろ、これらの粒子を排除し計算を減らして粒子数が減り続けるようにして、粒子を再サンプリングすると、粒子の位置と重みは、いずれも、すべての粒子が条件付き配信の計算に有意義な形で寄与するように調整され、一方でこの調整には統計的偏りが導入されなくなる。初期の粒子法では、過剰な再サンプリングノイズを粒子のシステムに導入して推定値を悪化させるという、あまりにも多くの再サンプリングを行う傾向があった。再サンプリングの後、ｍ個の観測値の後の粒子の重みが

で示されるものと仮定する。このとき、最適フィルタの条件付配信に対する粒子フィルタの近似式は下記のようになる。

Ｎ_ｔ→∞では、粒子フィルタリング推定は最適非線形フィルタ推定である。

本明細書において参考として組み込まれる「Ｆｌｅｘｉｂｌｅ Ｅｆｆｉｃｉｅｎｔ Ｂｒａｎｃｈｉｎｇ Ｐａｒｔｉｃｌｅ Ｔｒａｃｋｉｎｇ Ａｌｇｏｒｉｔｈｍｓ」という名称の米国特許出願第２００２／０１９８６８１号明細書において、粒子は、各時間ステップにおいて、確率的に複製され、破壊され、または不変に保たれる。現在の時間ステップのみ（Ｗ_ｍ（ξ^ｊ））に対して計算される重みに基づいて、粒子は以下のルーチンに従って修正される。

１．

であれば、粒子ξ^ｊの

コピーを作成し、確率

を有するもう１つのコピーを作成する。

２．

であれば、確率

を有する粒子を排除する。

３．不偏の制御アルゴリズムを実行して、粒子数を再サンプリング前に存在した総量に戻す。
この「注意深い」アプローチは以前に周知であった粒子フィルタの改良であって、本出願はアルゴリズムを効果的に実行するシステムとともに歴史的な改良型を含んでおり、ここでは、単なる現在の状態ではなく、時刻ｔまでのＸの経路を推定しようとするものである。性能低下を抑制し計算効率の改善によるさらなる改良が本明細書に参考として組み込まれられる「Ｓｅｌｅｃｔｉｖｅｌｙ Ｒｅｓａｍｐｌｉｎｇ Ｐａｒｔｉｃｌｅ Ｆｉｌｔｅｒ」という名称の米国特許番号７，０５８，５５０号明細書で導入されている。この方法は、ペアワイズの再サンプリングを以下のように実行している。

１．最大重み付きの粒子ｊと最小重み付きの粒子ｉに対して

を満たしている間に、
２．粒子ｉの状態を確率

を有するｊに設定し、粒子ｊの状態を確率

を有するｉに設定する。

３．粒子ｉとｊの重みを

にリセットする。

この方法では、実行される再サンプリングの総量を適切に抑制するために制御パラメータｐが導入される。出願第２００５／００４９８３０号明細書に記載されるように、フィルタの現在値および特定用途に適合するためにこの値は長期にわたって動的である。また、この出願は、このアルゴリズムに必要な量をコンピュータに格納して計算する効率的なシステムを含む。

１．１．３ 離散空間フィルタ
信号の状態空間が一部の有界な有限次元空間上にあるとき、離散空間および振幅近似が使用される。離散空間フィルタは、本明細書に参照して組み込まれる「Ｒｅｆｉｎｉｎｇ Ｓｔｏｃｈａｓｔｉｃ Ｇｒｉｄ Ｆｉｌｔｅｒ」（ＲＥＳＴフィルタ）という名称の米国特許第７，１８８，０４８号明細書に詳しく記載されている。この形態では、状態空間Ｄが離散セルη_Ｃに分割される。たとえば、この空間はｄ次元のユークリッド空間またはある計数測度空間でありうる。各セルは、「粒子数」（

で示される）として知られる離散化振幅を生じ、これは離散空間フィルタの条件付配信の形成に使用される。

各状態セルの粒子数は、信号のオペレータおよび処理される観測データに従って変更される。セル数が無限大になると、ＲＥＳＴフィルタの推定値は最適フィルタに収束する。分かりやすくするために、この出願では、信号を離散化して離散化信号に対する実行可能なフィルタリング方程式を案出するのではなくフィルタリング方程式を直接的に離散化することを検討している。

出願第２００５／００７１１２３号明細書において、本発明は観測値のリアルタイム処理に基づくフィルタの条件付き推定を効率良く再帰的に計算するためのデータ構造を有するセルを編成する動的インタリーブによる２進インデックスツリーを利用している。この構造は、状態空間の次元の複雑性が低い場合では一定の用途に適しているが、データ構造のオーバヘッドはこの方法の有用性を減じる可能性がある。

１．２ 確率制御
対象を定めたコマーシャル選択問題を適切に解くために、確率制御の数学的に最適な分野に関心を向けるべきである。

概念的には、コンピュータ上で確率制御問題を近似的に解くために直接離散化法の粒子法が考案される。しかし、これらはまだ行われていないか、または少なくとも広く認知されていない。代って、実施法は一般に問題全体を離散化した後で離散化問題を解くものである。

２．１ 対象を定めた広告システム構成
図１は対象を定めた広告システム全体を描いている。このシステムは、１台または複数台のデジタルセットトップボックス２００を制御するヘッドエンド１００からなる。ＤＳＴＢ２００は、テレビを見ている世帯の現在の構成員を含む、世帯２０５における潜在的視聴者の状態の条件付き確率を、ＤＳＴＢフィルタ２０２を使って推定しようとしている。ＤＳＴＢフィルタ２０２は、信号（世帯）と観測値（クリックストリームデータ２０６）を記載する１対のモデル２０１を使用する。ＤＳＴＢフィルタ２０２は、ヘッドエンド１００からダウンロードされた設定値３０２によって初期化される。また、世帯の状態を推定するために、ＤＳＴＢフィルタ２０２は、蓄積されたプログラム情報２０８から得られるプログラム情報２０７（これは、現在、または近接過去、または未来のものであってもよい）を使用する。

ＤＳＴＢフィルタ２０２は、その条件付き配信、または条件付き配信から得られた推定値をコマーシャル選択アルゴリズム２０３に渡し、この後、コマーシャル選択アルゴリズム２０３はフィルタの出力、ダウンロードされたコマーシャル３０１、および視聴者推定値が所与の許容されるコマーシャルを規定する何らかのルール３０２に基づいて現在の視聴者に見せるコマーシャル２０４を決定する。視聴者に見せられるコマーシャルは記録されて保存される。

ＤＳＴＢフィルタ２０２の推定値およびコマーシャル配信統計ならびにその他の情報は、ヘッドエンド１００に情報を提供するために、無作為にサンプリングされて３０３収集される３０４。この情報はヘッドエンドフィルタ１０２によって使用され、ヘッドエンドフィルタ１０２は、集合体能力に関する条件付き配信とこれが関連するＤＳＴＢの集合に関する実際の視聴率とを計算する（資源が利用可能であるものとして）。ヘッドエンドフィルタ１０１は、収集された世帯とＤＳＴＢフィードバックモデル１０１を使ってその推定値を提示する。これらの推定値は、ヘッドエンド１００によって制御されるＤＳＴＢの集合に渡されるべきコマーシャルを決定するためにヘッドエンドコマーシャル選択システム１０３によって使用される。また、コマーシャル選択システム１０３は、現在のコマーシャル契約およびこれらの契約の経済性に関する有効な市場情報１０５を考慮に入れる。選択の結果として得られるコマーシャル３０１は後でＤＳＴＢ１００にダウンロードされる。ダウンロードするために選択されるコマーシャルはレベル設定１０４に影響を与え、レベル設定１０４はある種の個人に示される一部のコマーシャルに拘束を課する。

以下の２つの節では、このシステムの一定の詳細要素を説明する。
２．２ 世帯信号および観測モデルの説明
この節では、一般的な信号および観測モデルが、このモデルの可能な実施形態の実例とともに説明される。

２．２．１ 信号モデルの説明
一般に、世帯の信号は、様々な個人および世帯の形態としてモデル化される。好ましい一実施形態において、この世帯は、ＤＳＴＢを使用する特定のテレビを見る可能性のある人々を表す。所与の時点ｔにおける各個人は（Ｘ^ｉで示される）は状態空間ｓ∈Ｓの状態を有し、ここで、Ｓは世帯内の各人に関して測定したい特性の集合を表す。たとえば、一実施形態において、個人の年齢、性別、収入、および視聴状況を分類したいと願うとする。年齢と収入は、実際の値または離散的な範囲と見なされてもよい。この例において、状態空間は以下のように定められることになる。
Ｓ＝｛０−１２，１２−１８，１８−２４，２４−３８，３８＋｝×｛男性、女性｝×｛０−＄５０，０００，＄５０，０００＋｝×｛はい、いいえ｝
世帯構成員の状態空間は、このとき、

であり、ここで、ｋは個人の数を示し、Ｓ^０は個人のいない単一状態を示す。世帯構成員

は、時間的に変化するランダム数の構成員を有し、ここで、ｎ_ｔは時刻ｔにおける構成員の数である。この集合内の構成員の順番は問題にとって重要でないため、筆者らは構成員

の経験測度を使って世帯を表す。

世帯形態は、クリックストリームデータの生成に実質的に影響しうる世帯の現在の視聴「思考」を描く。世帯の現在の形態ｒ_ｔは、状態空間Ｒの値である。本発明の一実施形態において、これらの形態は「ノーマル」、「チャネルフリッピング」、「ステータスチェッキング」、および「お気に入りサーフィング」などの値からなりうる。

したがって、完全な信号は、次式のように世帯の構成員および形態からなる。

信号の状態は、信号状態の変化を確率的に規定する変化率関数λによって時間とともに進化する。ある時間ｔの後に状態ｉからｊに状態が変化する確率は、このとき、次式のようになる。

各個人、世帯構成員そのもの、および世帯の形態の進化に関して個々の変化率関数がある。本発明の一実施形態において、個人ｉに関する変化率関数は、所与の個人、信号の経験測度、現在の時刻、および一部の外部環境変数

にのみ依存してもよい。

世帯内の個人の数ｎ_ｔは、出生率と死亡率によって時間とともに変化する。出生率と死亡率は、新たな生命の誕生や生存する生命の死亡を示すだけでなく、一個人または複数個人の世帯への転入および転出を生じる事象を表しうる。出生率と死亡率は、世帯内のすべての個人の現在の状態に基づいて計算される。たとえば、本発明の一実施形態において、独身者が同居人や配偶者を世帯に転入させる可能性を記述する変化率関数が計算されてもよい。

本発明の一実施形態において、これらの変化率関数は、推定確率と、有効な人口統計、マクロ経済、および視聴行動データからの状態変化の期待値とを一致させることによって経験的に決定されるパラメータを用いた数学的方程式として定式化される。別の実施形態において、年齢は連続状態空間［０，１２０］において確定的に進化される。

２．２．２ 観測モデルの説明
一般に、観測モデルは、ＤＳＴＢと１個人または複数個人との相互作用によって生成されるクリックストリーム情報からなる。本発明の好ましい一実施形態において、現在および過去のチャネル変更情報のみが観測モデルにおいて表される。Ｍチャネルの領域が所与とすると、過去Ｂの離散時間ステップで視聴されたＹ_ｋ＝（ｙ_ｋ，．．．，ｙ_{ｋ−Ｂ＋１}）チャネルの時刻ｔ_ｋにおけるチャネル変更待ち行列が得られる。本発明の好ましい一実施形態において、オーバヘッドを減らすためにチャネル変更が行われる時刻と変更されたチャネルのみが記録される。

さらに一般的な場合、視聴待ち行列はこの現在および過去のチャネルとともにボリューム履歴などを含む。上記の場合、視聴待ち行列はチャネル変更待ち行列に縮退する。
この後、信号の状態と一部のダウンロード可能なコンテンツＤ_ｔ（ｐ_ｉ→ｊ（Ｄ_ｔ，Ｘ_ｔ）で示される）とに基づいて時刻ｔにおいて状態ｉから状態ｊに視聴待ち行列が変化する確率が決定される。好ましい一実施形態において、このダウンロード可能なコンテンツは、とりわけ、たとえば、番組が「アクション映画」、または「ホームコメディ」のいずれであるか、および番組の時間帯、番組の開始時刻、番組が放映されているチャネルなど、各番組に対して現在利用できる番組の質的カテゴリの説明を詳述した一部のプログラム情報を含む。

特別な形態がないときは、マルコフ連鎖の遷移確率を計算するために経験的な方法が創生されている。これらの確率は、世帯の全構成員および利用可能な番組の現在の状態に依存する。この方法は、観測された視聴行動およびバラダラジャンの大数の法則を使って正当性が確認される。Ｐは確率をΩ＝（ω_１，．．．，ω_Ｋ）に割り当てる離散確率測度であると仮定すると、要素を選択する実験のＮ個の独立したコピーが得られる。このとき、大数の法則は次式にようになる。

ここで、ω^ｉはΩから要素を無作為に取り出す場合のｉ番目の結果である。

本発明の一実施形態において、この方法は、サイズ１のチャネル待ち行列（すなわち、Ｙ_ｋ＝ｙ_ｋ）に関する確率の計算に重点を置いている。観測確率、すなわち、次の離散ステップにおいて２つの視聴待ち行列が切り替わる確率は、番組の切替えカテゴリの確率を決定した後、このカテゴリ内の特定のチャネルに切り替わる確率を見つけることによってまず計算されうる。第１のステップは、チャネル変更および／または同一チャネルの番組変更によって生じるカテゴリ変更の相対的割合を多くの場合オフラインで計算することである。この計算を実行するために、可能なすべてのＸ_ｔに対して一部のπ_ｔ∈Πの場合にｆ（Ｘ_ｔ）＝π_ｔとなるように可能なすべての構成員状態Ｘ_ｉが離散状態空間Πに写像される。一定数のカテゴリＣ∈｛Ｃ_１，Ｃ_２，．．．，Ｃ_Ｋ｝があるものと仮定する。さらに、各視聴者記録は一定期間Δｔを表わし、各３組の視聴記録Ｖ（ｋ）＝（π，Ｃ^１，Ｃ^２）、ｋ＝１，２，．．．，Ｎｖは各世帯の離散化状態（π）と期間の開始（Ｃ^１）および終了（Ｃ^２）に関するカテゴリについての情報を含む、Ｎｖの視聴者記録があるものとする。このとき、各π∈Πおよび∀Ｃ_Ｉ，Ｃ_Ｊ∈Ｃに対して、次式を計算する。

最適推定システムがリアルタイムで動作しているとき、所与の時間ステップで起きるＣ_ＩからＣ_Ｊへのカテゴリ遷移に関する確率は、現在利用可能な番組を所与としてカテゴリ変更の確率をまず求めることによって次式から計算される。

ここで、Ａは利用可能な現在の番組に基づいて可能なすべての有効なカテゴリ切替えによって動作する。この後、この確率は次式によって必要なチャネル遷移確率に変換される。

ここで、ｎ_ｔ（Ｊ）は、現在の時間ステップの終了時にカテゴリＪに入る番組を有するチャネルの数である。

使用するもう１つの確率測度は、各離散時間ステップにおいてチャネル間の遷移の代わりにチャネルの「人気」を計算するものである。この方法は、所与のカテゴリに関する遷移確率を単に合計することによってこの形態を提供するために使用される。

さらに、この確率は、次式のように乗法則のインスタンスを使うことによって必要なチャネル遷移確率に変換される。

ここで、ｎ_ｔ（Ｊ）は、現在の時間ステップの終了時にカテゴリＪに入る番組を有するチャネルの数である。

本発明の一実施形態において、カテゴリのいくつかまたはすべては、最高の粒度レベルを所与として、これら自体が番組となる。他の例では、保存される必要のある確率の数を維持するために広範なカテゴリを有することが好ましい。

２．３ マルコフ連鎖観測を用いた最適推定
先に要約された従来のフィルタリング理論では、下記のような式によって、観測値は歪み、損傷し、部分的な信号の測定値である。

ここで、ｔｋはｋ番目の観測に対する観測時刻であって、

は駆動ノイズ過程、すなわち、連続時変性である。ただし、筆者らが直前の小節に記載したＤＳＴＢモデルの場合、Ｙは遷移確率が信号に依存する離散時間マルコフ連鎖である。この場合、新たな状態Ｙ_ｋは直前の状態に依存しうるので上記の標準理論は無効とする。この節では、観測値がマルコフ連鎖の場合の問題を解決する新たな類似の理論およびシステムが提示される。システムの注目に値する１つの普遍性は、マルコフ連鎖観測値が現在置かれている状態に依存するすべての状態の部分集合のみに遷移することが許容されてもよいことである。これは対象を定めた広告用途において有用な特徴であり、視聴待ち行列の直前データの多くは、観測後および一部の新たなデータの挿入後に視聴待ち行列に残っているかもしれないからである。これは明らかに一般性があるけれども、同一化を容易にするために、対象を定めた広告を再検討する中でこのことを記載しておく。

ジェネレータＬと初期配信νを有するマルコフ信号Ｘ_ｔがあるものと仮定する。正確には、信号は以下の（Ｌ，ν）マルチンゲール問題を満たす固有のＤ_Ｅ［０，∞）過程であると規定される。

および

は、すべてのφ∈Ｄ（Ｌ）のマルチンゲールである。

Ｘ_ｔおよび一部の外因的情報Ｄ_ｔに依存する｛１，２，．．．，Ｍ｝値の離散時間マルコフ連鎖観測に基づくＸ_ｔの条件付き配信を推定する。分かりやすくするために、

は、Ｐ（ｖ_ｋ＝ｉ）＝１／Ｍ、ただし、ｉ＝１，２，．．．，Ｍおよびｋ∈Ｚであるような信号および観測とは無関係な一連の独立確率変数であり、観測

は利用可能な事象の有限状態空間｛１，．．．，Ｍ｝とＹ_ｋ＝（ｙ_ｋ，ｙ_ｋ−１，．．．，ｙ_{ｋ−Ｂ＋１}）を用いて時刻ｔ_ｋで行われ、ここで、

は時刻ｔにおいて状態ｉから状態ｊに移行する同次遷移確率ｐ_ｉ→ｊ（Ｄ_ｔ，Ｘ_ｔ）を有する｛１，．．．，Ｍ｝^Ｂの値の間で遷移すると仮定する。ここで、Ｄ_ｔとＸ_ｔは、適当な外因的情報の現在の状態と、可能な状態変化の時点における信号状態である。

分かりやすくするために、

を定義し、次式を設定する。

ここで、

である。

表記の都合上、Ｚ_０＝１と定義する。このとき、いくつかの数学計算により次式が示される。

ここで、

として、それぞれｇ＝１およびｇ＝ｆの場合に（６）の分母と分子がともに

から計算されることに注目する。ここで、

である。ここで、次式が必要である。

ただし、関数の集合が十分に豊富な場合、

さらなる計算によって

が次式を満たすようになる。

ただし、すべてのｔ∈［０，∞）およびφ∈Ｄ（Ｌ）であり、ここで、

および

である。

２．４ フィルタリングの近似
リアルタイムコンピュータシステムにおいて上記の微分を使用するためには、得られる方程式がコンピュータアーキテクチャに実装されうるよう近似が行われなければならない。粒子フィルタまたは離散空間フィルタを使用するためには、異なる近似が行われなければならない。これらの近似は以下の節で明らかにされる。

２．４．１ 粒子フィルタの近似
方程式（６）によって次式を近似するだけでよい。

ここで、各々が過去の信号と同じ基準（ｌａｗ）を有する独立した信号粒子

を導入し、下記の重みを規定するものと仮定する。

すると、この式はｄｅＦｉｎｎｅｔｔｉの定理および大数の法則に従って次式のようになる。

２．４．２離散空間の近似
Ｘ_ｔの状態空間がＥとなるように設定する場合は、各

に対してｌ_ＮおよびＭ_Ｎが、

のときに

および

を満たすようにする。

の場合、

は

となるようなＥの分割であり、しかも、すべての離散状態は異なるセルにあり、言い換えれば、これはα＝αＮ→０として達する年齢で拡大および縮小しているだけである。ここで、

であるものとして

を定義し、これを以下で直感的に正当化する。

は、

をすべてのｉ∈Ｄ_Ｎおよび

に対して指すものと見なして、検定関数

を（１０）に代入すると、次式が得られる。

ここで、

である。

このとき、上式は次式のようになる。

２．５ 離散有限状態空間による確率グリッドフィルタの改良
米国特許第７，１８８，０４８号明細書には、ＲＥＳＴフィルタの一般形態が詳細に記載されている。この方法とシステムは、いくつかの用途、特にユークリッド空間追跡問題および離散計数測度問題に役立つことが証明されている。しかし、この方法にはいくつかの改善点が見つかっており、これは本発明の実施形態にとってメモリおよび計算要件の劇的な削減をもたらすものである。ＲＥＳＴフィルタに関する新しい方法とシステムは本明細書に記載されており、信号は離散および有限状態空間によってモデル化されうる。明確さを期して対象を定めた広告モデルを使った事例が提供されるが、この方法は以下で説明される環境を特徴とする任意の問題に使用される。

２．５ 環境の説明
一部の問題において、信号はゼロまたは複数の対象

およびゼロまたは複数の形態

からなる。たとえば、対象を定めた広告において、信号モデルの一実施形態はＸ_ｔ＝（Ｘ_ｔ，Ｒ_ｔ）の形式であり、ここで、Ｘ_ｔは目標の経験測度（すなわち、具体的に言うと世帯構成員）であり、形態は１つだけである。さらに、各目標と形態は離散的で有限数の状態のみを有し、目標と形態は有限数である（したがって、目標と形態の可能な組合せは有限数である）。有限数の組合せはすべての可能な組合せである必要がなく、有限数の正当な組合せのみが必要とされる。たとえば、世帯の有限の可能ななタイプ（内部に特定の人口統計を有する世帯を意味する）は、比較的粒度の細かいレベルでの地域に依存する国勢調査情報から導かれうる。個人のあらゆる可能な組合せ（ある最大世帯構成員^ｎＭＡＸまでの）を有するのではなく、所与の地理的地域内に見られる可能性のある組合せのみを正当であると考えて状態空間内に含める必要がある。

これらの制限された問題において、目標および／または形態の状態の一部は、最適推定が行われている短期間の間に不変であってもよい。これらの場合、こうした状態情報は一定に保たれるが、状態情報の他の部分は変動し続ける。世帯信号モデルの一実施形態において、世帯内の各個人の年齢、性別、収入、および教育レベルは、これらの値が長期間にわたって変化するがＤＳＴＢ推定は数週間の間に行われるので、一定であると考えられてもよい。ただし、世帯形態情報の現在の視聴状態は比較的短い期間枠で変化し、結果として、推定問題にはこれらの状態の変動したままである。信号の不変部分を

で表わし、信号の変動部分を

で表わすことにする。Ｎ個の可能な不変状態（ｉ番目のこのような状態を

で表す）とｉ番目の不変状態に対するＭ_ｉ個の可能な変動状態（ｊ番目の状態を

で表す）がある。

２．５．２ ＲＥＳＴ有限状態空間システムの概要
図２は、有限状態空間環境におけるＲＥＳＴフィルタの好ましい一実施形態を描いている。ＲＥＳＴは不変状態セルの集合からなり、不変状態セルの各々はそれらの不変状態特性とともに信号に関する対象と形態の１つの可能な集合を表す。各不変セルは変動状態セルの集合を含み、各変動状態セルは所与の不変セルの可能な時変状態を表す。黙示的に、変動セルはそれらの親不変セルの不変状態情報を含み、各変動セルは信号の特定の潜在的な状態を表すことを意味する。不変セル自体は、集合コンテナオブジェクトのみを表し、便宜目的で使用される。変動セルと不変セルの集合は、アレイ、ベクトル、リスト、または待ち行列の形式でコンピュータ媒体に保存されてもよい。所与の時刻ｔにおいて粒子数を持たないセルは、空間および計算の要件を削減するためにこのようなコンテナから除去されるが、このようなセルを後になって再挿入するメカニズムが必要である。

図３に示されるように、各変数状態セルは粒子数

を含む。この粒子数はそのセルの離散化振幅を表す。既に述べたように、この振幅は所与の状態の条件付き確率の計算に使用される。また、各変動状態セルも１組の仮想クロック

を含む。これらの仮想クロックは、所与の状態セルからの可能な状態変化を表す。各変動状態セルに関しては、Ｑ_ｉ，ｊの可能な状態遷移がある。この環境において、すべての有効な状態トランザクションが同じ不変状態セル内で起きる。ＲＥＳＴフィルタの条件付き配信における同時変化を説明するために、粒子数デルタ

と題する一時カウンタが、すべてのセルの順次処理が終了した時点で所与の変動状態セルに対して追加または削除される粒子の数を保存するために使用される。状態

を有する変動状態セルからからの有効状態遷移を有するセルは、そのセルのネイバーと言われる。

先に述べたように、不変状態セルは、情報の処理を簡素化するために使用されるコンテナである。各不変状態セルの粒子数

は、その子変動状態セル粒子数の集合である。同様に、不変状態セルの仮想タイムクロックは、変動セルからの全クロックの集合体である。現在の粒子数を持たない不変状態は処理の様々な段階でスキップされうるので、この集合体はフィルタの進化を促進する。

２．５．３ ＲＥＳＴフィルタの進化
図４はＲＥＳＴフィルタの典型的な進化を描いている。この進化方法は、仮想クロック値を使って隣接するセル間の粒子を移動することによって、ある期間ｄｔにわたってフィルタの条件付き配信を更新する。隣接するセル間の粒子の移動は事象として知られる。（ところで、筆者らは、粒子の移動を頻繁に新たな出生および死亡で置き換えて、より多くの出生率と死亡率の取り消しが行われうるようにしている。）このような事象は、進化の計算オーバヘッドを抑制するためにまとめてシミュレーションされる。シミュレーションする事象の数は、すべてのセルに対する全仮想クロックの合計λ_ｔに基づく。図５は、各ネイバーに移動する粒子数の決定方法を示す。事象のシミュレーションが完了すると、粒子数は更新されうるようになり、仮想クロックは封印されてフィルタの状態が変化したことを表す。

米国特許第７，１８８，０４８号明細書に記載された以前の方法に比べると、フィルタの有効性を改善するために新たなステップが追加されている。具体的に言うと、セル粒子数の調整がここではプッシュダウン観測法に先立って行われ、ドラフトバックルーチンが粒子制御に先立って追加されている。ある問題において、一部の状態は観測情報に基づく現在の信号状態である可能性がない場合がある。たとえば、世帯には、チャネル変更が記録されているかどうかを現在見守っている少なくとも１人の構成員がいなければならない。このような状況において、すべての無効な状態にある粒子は有効な状態に比例して再分配されなければならない。したがって、再分配すべき

の粒子がある場合、すべての有効変動状態セルは

の粒子を受け取ることになり、確率

を有する粒子をさらに受け取ることになる。この種の観測ベースの調整を用いる場合、信号の進化を規定する変化率はこのような方法の観測データの用途と一致するように適切に変更されなければならないと考えられる。

ＲＥＳＴフィルタのロバスト性を改善するために、ドリフトバック法が追加されている。この方法では、信号の初期配信νに基づいて変動状態セルにある関数

の粒子を使用する。各セルに加える粒子の数は、時刻、所与のセル、およびフィルタの状態全体に依存する。この方法は、不正な位置から復帰することができなければフィルタは１つまたは複数の不変状態に収束しないようにする。

２．６ ヘッドエンドの推定
複数のサービスオペレータの広告事業の収益を最大にするために、どのコマーシャルを集合体のＤＳＴＢに配信すべきかを決定することがきわめて重要である。ＤＳＴＢベースの漸近的最適非線形フィルタの条件付き配信（または、この配信から導かれる条件付き推定値）に基づいてコマーシャルの実際の視聴率に関するより多くの情報が得られるので、特定コマーシャルスロットの価格設定は動的であるため、総収益が改善される。

この潜在力を生かすために、各人口統計内にいる人々の数などを含む総世帯の推定が、条件付きＤＳＴＢ推定のランダムサンプリングに基づいてヘッドエンドにおいて行われる。以下のモデルは本発明の好ましい実施形態を含む。

２．６．１ ヘッドエンド信号モデル
ヘッドエンド信号モデルは、特定のヘッドエンドに接続されたＤＳＴＢボックスを有する潜在的なテレビ視聴者と現在のテレビ視聴者に関連する特性情報からなる。単一個人に関するこうした特性の集合を表す状態空間Ｓが定義される。本発明の一実施形態において、この空間は、個人に関する年齢層、性別、および最近の視聴歴から構成されうる。個人を追跡するために、Ｃ^０＝φを個人のいない世帯タイプとし、Ｃｎをｎ人の個人がいる世帯タイプの集合とする。

このとき、世帯の集合は、ｎ人の人々がいる世帯の和集合

となる。現実的には、筆者らが処理しうる最大世帯Ｎがあることになり、かつ筆者らは世帯状態空間が

になるように設定する。ここで、Ｎはある大数である。

ランダムサンプルメカニズムによってＤＳＴＢから戻される推定値を処理するために、筆者らはさらに各ＤＳＴＢに対する現在のチャネルを追跡したい。すなわち、潜在的な世帯視聴率、視聴状況、および現在のチャネルを含む各ＤＳＴＢ状態が次式から選ばれる。

ここで、ＤＳＴＢで変えられうるチャネルはＭ個ある。
筆者らは、単一のＤＳＴＢやどのＤＳＴＢが特定状態にあるかではなく、いくつのＤＳＴＢが状態ｄ∈Ｄにあるかに関心がある。それゆえ、信号Ｘが有限の計数測度に従って追跡されるようにして、各カテゴリｄ∈ＤにおけるＤＳＴＢの数を計数する。

本発明の実施形態において、計算要件を最小にするために各カテゴリにおけるＤＳＴＢの可能な数の集合を追跡することが可能である。このような場合、総数がやはりＤＳＴＢの最大数まで合計することになるようにサイズ０の原子が使用される。たとえば、１００万台のＤＳＴＢがあるものと仮定する。そのとき、１００，０００個の原子（各々ａ＝１０台のＤＳＴＢからなる）をＤに対して配信することになる。Ｍ（Ｄ）はＤに関する計数測度を示し、

はちょうど１００，０００個の原子を有するＭ（Ｄ）の部分集合を示すものと仮定する。信号は、マルチンゲール問題に従って数学的に進化することになる。

ここで、ｔ→Ｍ_ｔ（ｆ）は

に関する各々連続、有界汎関数ｆに対するマルチンゲールであり、Ｌは、ＤＳＴＢのレートと、世帯が独立に行動するという自然な前提とから主として決定されるはずのある演算子である。

公開モードで人口統計を提供する世帯は、信号の一部であると見なされない。
２．６．２ ヘッドエンドの観測モデル
本明細書では、２つの観測モデルを説明するが、１つはＤＳＴＢのランダムサンプリングに関するモデルで、もう１つは配信統計に関するモデルである。

ランダムサンプル観測モデルでは、Ｘを前節におけるように筆者らの信号であるものとしてチャネルと視聴率を考察し、Ｖ_ｋをサンプリング過程の時刻ｔ_ｋにおけるランダムサンプリングを示すものとする。正確には、特定のヘッドエンドに対してＭ台のＤＳＴＢがあるものと仮定し、少なくとも１人が現在視聴していると考えられるＤＳＴＢは５％の一定の確率でサンプルを供給することになるものとする。このとき、Ｖ_ｋは乱数の行を有する行列となり、各行はサンプルを提供している特定ＤＳＴＢのインデックスに対応するまさに１つの非ゼロ入力を有するＭ個の入力からなる。数字行は、サンプルを提供するＤＳＴＢの台数となる。非ゼロ入力の位置は行において当然明らかであり、行われる実際のサンプリングを反映する可能な順列に対して一様に選定されることになる。

ここで、

は、いずれも時刻ｔ_ｋにおけるＭ台のＤＳＴＢの条件付き配信視聴率推定値と対応するチャネルとの（列）ベクトルであるものとする。このとき、この観測過程は次式のようになる。

ここで、Ｖ_ｋはランダムサンプリングを行うことになり、ｈはフィードバックのために選定される情報を提供する関数となる。

集合広告配信統計モデルの場合、筆者らは時刻ｔ_ｋ〜ｔｊにおいて過去に配信された様々な広告の数を提供する時系列関数Ｈ_ｋｊを有している。少量のノイズＷ_ｋｊが存在することはよくあるが、これは一部のＤＳＴＢは一時的な誤動作（すなわち、「観測の停止」）によって情報を全く返さない場合があるという事実と、配信が正常であると判定するために使用される推定視聴率の正しいことが保証されないという事実とに基づくものである。

集合配信統計からの第２の観測情報は次式のようになる。

ここで、ｊは報告期間にスポットセグメントにおいて変動し、ｔ_ｋは報告期間である。

２．６．３ ヘッドエンドフィルタ
ヘッドエンドに関する信号はＤＳＴＢの確率分布となる。
２．７ ヘッドエンドのコマーシャル選択
本発明の一定の実施形態において、総視聴者率の推定にも使用される他の情報があってもよい。たとえば、集合（および遅れる可能性のある）広告配信統計は、ＤＳＴＢの推定視聴率の推論とともにある補償と引き換えに世帯がその状態情報（人口統計、心理的側面など）の提供を選ぶ「露出モード」の情報も提供する。

この設定において、コマーシャル契約は、契約内容、利用可能資源、および未来の信号状態の点における増分利益のグラフとしてモデル化される。筆者らは、これらのグラフを、契約内容、信号状態、および経済環境に依存する比率で到着する「契約グラフ」と呼んでいる。契約内容の一部は以下の項目を含む。

おそらく数千回単位の、コマーシャルを放映できる回数（最大限度および最小限度を含む可能性がある）、
コマーシャルを放映できる日／週の時間範囲、
コマーシャルに関する目標人口統計、
コマーシャルを放映できる特定のチャネルまたは番組、
契約書を作成した顧客、
上記項目の一部は任意である。

契約グラフのランダムな到着は、「契約グラフ過程」で示される。さらに、契約グラフ過程への資源の配分（契約に配分可能な最大値である必要はない）は、状態（現在および未来）と環境が所与として、配分された資源が利用可能資源、すなわち、様々なカテゴリにわたる利用可能なコマーシャルスポットを超えない場合に「実現可能な選択」と呼ばれる。ところで、人が契約を受諾するとこれらの限られた資源が減少するという事実に基づいて、現在対未来の潜在的利益は「効用」関数によってモデル化される。この効用関数は、利用可能な契約グラフの動向を示し（現在も未来もランダム到着）、金銭やその他の形の点から見た利益を示す数を納得のいくように返す。契約グラフでの将来の動きは不規則であるので、最大化による薄利の大きなリスクが生じないようにするための期待利益からのずれを考慮しなければ、効用関数が最大利益を単純にもたらすことはありえない。

最適なコマーシャル選択を行うために、ヘッドエンド信号モデル、ヘッドエンド観測モデル、契約発生モデル、および効用（利益）モデルと記載される以下のモデルを定義する必要がある。

２．７．１ 契約モデル
発生するコマーシャル契約は、契約グラフ上のマーク付き点過程としてモデル化される。契約の到着率は、締結された過去の契約と経済状況などの外部要因とに依存する。

ｌはルベーグ測度を示すものと仮定する。このとき、Ｃはあるトポロジーを有する可能な契約グラフの空間を示すものとし、｛η_ｔ，ｔ≧０｝は時刻ｔまでの契約グラフの到着に関する計数測度確率過程を示すものとし、ξはある平均測度ν×ｌ×ｌを有するＣ×［０，∞）×［０，∞）上のポアソン測度を示すものとする。さらに、λ（ｃ，η_{［０，ｔ）}，ｔ）は、η_{［０，ｔ）}が契約グラフの到着を時刻０からｔ（ただし、時刻ｔを含まない）まで記録するとき新たな契約が時刻ｔにおける契約グラフｃ∈Ｃを備えることになる比率（νに対する）であるものとする。このとき、下記の確率微分方程式によってモデル化を行う。

上記の契約内容は契約の承諾時に変更されてもよい場合がある。結果として、契約内容は外部環境に依存して時間とともに進化しうるようにモデル化される。

２．７．２ 効用関数の説明
分かりやすくするために、Ｒ（Ｄ_Ｓ）を時刻ｓにおいてダウンロード可能な番組情報Ｄ_Ｓに基づいて、現在および将来、利用可能な資源であるものとする。

筆者らは生じるすべての契約を承諾することはできず、将来を考えずに契約を承諾するか否かの決定を行わなければならない。筆者らは、各資源配分の決定に将来の契約や将来の観測情報を使用しないように受入れ可能な選択を実現可能な選択として表す。前節の表記法に照らして、ｎｔは時刻ｔ（時刻ｔを含む）までに到着した様々の種類の契約の数を表すものと仮定し、次式を得る。

ここで、Ｑはすべての潜在的な顧客の集合を表し、｛ｌ_Ｓ，ｓ≧０｝は選定過程である、すなわち、資源を各契約ｃに配分する。このとき、各ｓ≧０に対してｌ_ｓ≦Ｒ（Ｄ_ｓ）であれば｛ｌ_Ｓ，ｓ≧０｝は受入れ可能な選択であり、ｌ_ｓは将来契約も観測情報も使用することはなく、すなわち、各ｓ≧０の場合に

に関する測定が可能である。ここで、γ_ｔ ^（ｌ）は、受入れ可能な選択ｌによって時刻ｔまでに得られた利益を表す。分かりやすくするために、Λをすべてのこうした受入れ可能な選択の集合とする。

効用関数Ｊは、現在の利益と将来の利益のバランスを取って無理益または低利益のリスクのある特定契約で超高利益を得るように変更する。無理なく着手するために、将来の収益の重みを指数関数的に減らすことになる。さらに、筆者らは過度に積極的にならないように分散的状態を含めることになる。結果として得られる効用関数の一実施形態は、次式となる。

ただし、小さい定数λ、ａ＞０である。このとき、コマーシャル選択過程の目的は、ｌ∈Λに対してＥ［Ｊ（Ｘ，ｌ）］を最大にすることである。このような目的は１つまたは複数の漸近的最適フィルタを使って解決されうる。

本発明の先の記述は例証と説明を目的として提示されている。さらに、この記述は、本発明を本明細書で開示された形態に限定するものではない。したがって、上記教示に相応の変形形態および修正形態と関連技術の技量および知識とは本発明の範囲内にある。さらに、前述の実施形態は、本発明の実施について知られた最良の形態を説明するとともに、他の当業者が本発明をこのような実施形態および他の実施形態において、本発明の特定の用途または使用法に要求される様々な修正形態で利用できるようにするものである。冒頭の特許請求の範囲は先行技術が許す範囲で他の実施形態を含むものと解釈されたい。

本発明に従って対象を定めた広告システムの概略図である。 本発明に従ったＲＥＳＴ構造を示す。 本発明に従ったフィルタのセルに関するセル構造を示す。 本発明に従ってフィルタ進化過程を示すフローチャートである。 本発明に従って事象をシミュレーションする過程を示すブロック図である。

Claims (32)

1. 通信ネットワークにおいてユーザ機器デバイスのユーザが対象資源を使用する方法であって、
   ユーザ機器デバイスに関する１ユーザまたは複数ユーザによる入力に基づいて観測モデルを展開するステップと、
   時間に関する前記ユーザ機器デバイスの１ユーザまたは複数ユーザの少なくともユーザ構成を表す信号を前記観測モデルに組み込むステップと、
   前記信号による所与の前記測定データの条件付き分布の近似によって対象時刻に前記ユーザ構成を推定するステップと、
   前記ユーザ機器デバイスに関する資源を対象として前記推定されたユーザ構成を使用するステップと
   を備える方法。
2. 前記入力は時間的なユーザ入力のクリックストリームであって、前記観測モデルは前記クリックストリームをマルコフ連鎖としてモデル化する、請求項１に記載の方法。
3. 前記観測モデルは前記入力の少なくとも一部によって示されるネットワークコンテンツのプログラミング関連情報を考慮する、請求項２に記載の方法。
4. 前記マルコフ連鎖の観測は、状態の全集合の部分集合だけに遷移することができる数学モデルを使って前記マルコフ連鎖を処理するステップをさらに備え、前記部分集合は前記マルコフ連鎖の現在の状態に依存する、請求項３に記載の方法。
5. 前記モデル化するステップは、前記観測モデルをｋステップのマルコフ連鎖でマルコフ連鎖としてモデル化するステップを備える、請求項１に記載の方法。
6. 前記観測マルコフ連鎖の遷移関数は、推定する信号の位置に依存する、請求項５に記載の方法。
7. 前記信号は、前記ユーザ構成と前記ユーザ入力をもたらす別の要因とを表すものとして確定される、請求項１に記載の方法。
8. 前記信号のモデルは、複数ユーザを含むものとして前記ユーザ構成を表現することができる、請求項１に記載の方法。
9. 前記信号のモデルは、前記ユーザ構成の変化を表現することができる、請求項１に記載の方法。
10. 前記変化は、前記ユーザ機器デバイスに関連する多数のユーザの変化である、請求項９に記載の方法。
11. 前記モデル化するステップは、前記観測モデルおよび前記測定データに基づいて前記信号の確率的推定値を得るためにフィルタを規定するステップを含む、請求項１に記載の方法。
12. 前記モデル化するステップは、前記観測モデルに基づいて前記信号の確率的推定値を得るために非線形フィルタを定義するステップを備える、請求項１１に記載の方法。
13. 前記モデル化するステップは、前記非線形フィルタの動作を近似する近似フィルタを構築するステップをさらに備える、請求項１２に記載の方法。
14. 前記近似フィルタは、粒子フィルタである、請求項１３に記載の方法。
15. 前記近似フィルタは、離散空間フィルタである、請求項１３に記載の方法。
16. 前記使用するステップは、資源を前記ネットワークのコンテンツストリームに挿入するように機能するネットワークプラットフォームに前記ユーザ構成に基づく情報を提供するステップを備える、請求項１に記載の方法。
17. 前記情報は、前記ユーザ機器デバイスの１ユーザまたは複数ユーザの人口統計を特定する、請求項１６に記載の方法。
18. 前記プラットフォームは、複数のユーザ機器デバイスに関連するユーザ構成情報を集約し、前記集約された情報に基づいて挿入する１つまたは複数の資源を選択するように機能する、請求項１７に記載の方法。
19. 前記プラットフォームは、複数のユーザ機器デバイスからの情報を観測モデルとして処理し、前記対象時刻においてネットワーク視聴者の複合的な構成を推定するために前記観測モデルに関するフィルタを適用するように機能する、請求項１６に記載の方法。
20. 前記プラットフォームは、前記複合的な構成と特定資源の配信価値に影響を与える追加情報とに基づいて挿入する資源を選択するように機能する、請求項１７に記載の方法。
21. 前記情報は、前記ユーザ構成に基づいて前記ユーザ機器デバイスに配信する１つまたは複数の適切な資源を特定する、請求項１６に記載の方法。
22. 前記使用するステップは、前記１ユーザまたは複数ユーザに配信する資源を前記ユーザ機器デバイスにおいて選択するステップを備える、請求項１に記載の方法。
23. 前記使用するステップは、前記１ユーザまたは複数ユーザに関する前記ユーザ機器デバイスにおいて配信される資源の適合度を報告するステップを備える、請求項１に記載の方法。
24. 通信ネットワークにおけるユーザ機器デバイスのユーザの対象資源に使用する装置であって、
    ユーザ機器デバイスに関する１ユーザまたは複数ユーザによる入力に関する入力情報を受信するように動作するポートと、
    前記入力に基づいて観測モデルを提供し、前記観測モデルを時間に関する前記ユーザ機器デバイスの１ユーザまたは複数ユーザの少なくともユーザ構成を表す信号に依存するものとしてモデル化し、対象時刻におけるユーザ構成を信号の状態として決定し、前記ユーザ機器デバイスに関する資源を対象として前記決定されたユーザ構成を使用するように動作するプロセッサと、
    を備える装置。
25. 前記プロセッサは、前記観測モデルおよび前記測定データに基づいて前記信号の推定値を得るために非線形フィルタを定義するように動作する、請求項２４に記載の装置。
26. 前記プロセッサは、前記非線形フィルタの動作を近似する近似フィルタを構築するように動作する、請求項２５に記載の装置。
27. 前記非線形フィルタは、粒子フィルタおよび離散空間フィルタの一方である、請求項２６に記載の装置。
28. 別のネットワークプラットフォームの目標資源に使用する情報を伝送するポートをさらに備え、前記情報は前記決定されたユーザ構成に基づく、請求項２４に記載の装置。
29. 放送ネットワークにおける対象資源に使用する方法であって、
    一連のユーザ入力に対応するデータの流れを総合的に解析するステップと、
    この流れによって記述されるパターンをユーザの視聴者分類に関連する特性に一致させるロジックを適用するステップと、
    を備える方法。
30. 前記総合的に解析するステップは、観測モデルを構築するステップを含み、前記一連のユーザ入力はマルコフ連鎖としてモデル化される、請求項２９に記載の方法。
31. 前記ロジックを適用するステップは、前記一連のユーザ入力から信号推定値および配信を抽出するために非線形フィルタモデルを使うステップと、前記特性を得るために前記信号を使用するステップとを備える、請求項２９に記載の方法。
32. 前記ロジックを適用するステップは、前記非線形フィルタの動作を近似するために近似フィルタを実行するステップを備える、請求項２９に記載の方法。