(57)【特許請求の範囲】
【請求項１】
１組のユーザ装置のセットの中で、タイムスロット中に複数の候補広告のうちのターゲット広告を示しているユーザ装置の数を推定するコンピュータ実施方法であって、
（ａ）コンピュータが、ユーザ装置のセット中の各ユーザ装置に対して、タイムスロット中にユーザ装置によって示すことができる複数の候補広告のＩＤを送信するステップと、
（ｂ）コンピュータが複数のユーザ装置から、タイムスロット中にターゲット広告を示すユーザ装置の識別情報を隠す攪乱データを受信するステップと、
（ｃ）コンピュータが、複数のユーザ装置から受信した攪乱データから計算したターゲット広告の分布データと、分布データに対する重みとに基づいて、タイムスロット中にターゲット広告を示すユーザ装置の数を推定するステップとを含む、方法。
【請求項２】
ステップ（ａ）が、コンピュータが、ユーザ装置のセット中の複数のユーザ装置のそれぞれに対して、候補広告の内容を送信することをさらに含む、請求項１に記載の発明。
【請求項３】
ステップ（ａ）が、コンピュータが、複数の候補広告のＩＤをユーザ装置に送信する前に、収益を最大にするように候補広告を順序付けすることをさらに含む、請求項１に記載の発明。
【請求項４】
各ユーザ装置から受信するデータがブールベクトルである、請求項１に記載の発明。
【請求項５】
各ユーザ装置から受信するデータが、ユーザ装置に対応するユーザについての、候補広告のうちの１つまたは複数の妥当性に基づいて生成される、請求項１に記載の発明。
【請求項６】
各ユーザ装置から受信するデータが、１つまたは複数の無作為に生成された値に基づいて攪乱された情報を用いて生成される、請求項１に記載の発明。
【請求項７】
各ユーザ装置から受信するデータが、ユーザプロフィルの１つまたは複数のキーワードに基づいて生成される、請求項１に記載の発明。
【請求項８】
１組のユーザ装置のセットの中で、タイムスロット中に複数の候補広告のうちのターゲット広告を示しているユーザ装置の数を推定するためのデータを生成するユーザ装置実施方法であって、
（ａ）ユーザ装置が、タイムスロット中にユーザ装置によって示すことができる複数の候補広告のＩＤを受信するステップと、
（ｂ）ユーザ装置が、タイムスロット中にターゲット広告を示すユーザ装置の識別情報を隠す攪乱データを生成するステップと、
（ｃ）ユーザ装置が、複数のユーザ装置からの攪乱データから計算されるターゲット広告の分布データと、分布データに対する重みとに基づいてタイムスロット中にターゲット広告を示すユーザ装置の数を推定するように構成されたコンピュータに攪乱データを提供するステップとを含む、方法。
【請求項９】
請求項１から８のいずれか一項に記載の方法を実施するように構成された装置。
【請求項１０】
コンピュータと、
コンピュータと通信する１組のユーザ装置のセットとを含むシステムであって、
コンピュータが、
（ｉ）ユーザ装置のセット中の各ユーザ装置に対して、タイムスロット中にユーザ装置によって示すことができる複数の候補広告のＩＤを送信し、
（ｉｉ）複数のユーザ装置から、タイムスロット中にターゲット広告を示すユーザ装置の識別情報を隠す攪乱データを受信し、
（ｉｉｉ）複数のユーザ装置から受信した攪乱データから計算したターゲット広告の分布データと、分布データに対する重みとに基づいて、タイムスロット中にターゲット広告を示すユーザ装置の数を推定するように構成された、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、テレビジョン、ウェブ閲覧およびその他のメディアのターゲット広告（またはａｄ）の分野に関し、さらに詳細には、ユーザのプロフィル情報を非公開に保ちながらユーザに対して広告をターゲティングする配信およびスケジューリングシステムに関する。
【背景技術】
【０００２】
本項では、本発明のより深い理解を助ける可能性がある特徴を紹介する。したがって、本項の記述は、この点に照らして読むべきものであり、何が従来技術であり何が従来技術でないかについての自認として理解すべきものではない。
【０００３】
ユーザに対する効果的な広告のターゲティングは、ますます重要性が高まっている収益創出サービスである。適切かつ正確にターゲティングするためには、サービスプロバイダは、ユーザの関心プロフィルにアクセスできなければならない。Ｇｏｏｇｌｅ社のＡｄＷｏｒｄｓが先鞭を付けた広告ターゲティングは、当初は、ユーザの検索キーワードのみに基づいて広告をターゲティングするサービスであった。しかし、今日では、検索キーワードが全くない状況でもさらに良好にユーザにターゲティングするために、ユーザのプロフィルを使用する方向に傾いているサービスプロバイダが増加している。例えば、Ｇｏｏｇｌｅ社のＡｄＳｅｎｓｅは、ウェブサイトのページを要求したユーザのＩＤに基づいてそのページに様々な広告を供給して配置することができる。通常は、ユーザが様々なウェブサイトを閲覧していく間に、サービスプロバイダはユーザプロフィルを作成して保持し、そのプロフィルをそのインフラストラクチャ内に格納する。このシナリオでは、サービスプロバイダは、各ユーザの活動および関心を完全に把握しており、それらに対する完全なアクセス権を有している。この構成では、広告ターゲティングおよびユーザプロファイリングは、ユーザのプライバシと相容れない。
【０００４】
１つの従来の広告ターゲティング方式では、広告主は、所与の広告のターゲットとして広告主が関心を持っているユーザの種類を、その広告のユーザプロフィルごとの入札金額を指定することにより、表明する。サービスプロバイダは、その広告をユーザのプロフィルとマッチングして、ユーザに対して示すのに最良の広告を選択し、その後、選択された広告がユーザに対して示される。その後、サービスプロバイダは、広告主に対し、その広告を表示するたびにその入札金額を課金する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許出願公開第２０１１／００１６１９９号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
前述の方式では、サービスプロバイダは、どの広告がどのユーザに配信されたかも含めてユーザのプロフィルを把握しており、その情報に基づいて広告主に課金する。しかし、広告主の広告が示される頻度に応じて広告主に課金することを可能にしながら、ユーザのプライバシを保護するように広告をターゲティングすることが必要とされている。
【課題を解決するための手段】
【０００７】
本発明の特定の実施形態では、ユーザのプライバシを保護するように広告をターゲティングする方法体系を利用する。
【０００８】
プライバシを保護するように広告をターゲティングするために、本発明の特定の実施形態は、以下の２つのプライバシに関連する必要に対処することによって、従来のターゲット広告配信モデルから大きく離れている：第１に、サービスプロバイダがユーザプロフィルにアクセスできないように、ユーザプロフィルを作成して保持する必要がある。第２に、サービスプロバイダが、どの広告がどのユーザに対して表示されたかを知らなくても適切に広告主に課金できるように、特定の広告をどれだけの数のユーザが見たかに関する情報を蓄積できることが必要である。
【０００９】
本発明の特定の実施形態では、ユーザのプライバシを保護するために、ユーザプロフィルはサービスプロバイダのインフラストラクチャ内に常駐せず、ユーザの制御下にある装置内、望ましくは最終的に広告を表示する装置に収容される。このような装置としては、例えば、ユーザのパーソナルコンピュータ（ＰＣ）、携帯電話、宅内ゲートウェイ、セットトップボックス（ＳＴＢ）などが挙げられる。ホームネットワークでは、ユーザの装置が宅内ゲートウェイである場合には、広告がユーザのネットワーク化されたＴＶまたはＰＣ上に表示されるものと仮定する。プロフィル作成プロセスは、計算量が多くなる可能性があり、また追加のネットワークトラフィックを生じる可能性もある。現在の世代のユーザ装置は、十分な処理能力およびメモリを有しているが、技術的な理由またはビジネス上の理由から、これらの装置のネットワークスループットが制限される可能性がある。例えば、無線ネットワークの帯域幅利用は、月単位で制約を受ける可能性があり、ＤＳＬ接続のアップリンク帯域幅は、ダウンリンク帯域幅よりはるかに小さい。したがって、１つの難問は、ユーザ装置にとって適切であり、かつユーザ装置が利用できる資源に見合った方法で、プロフィルを作成することである。
【００１０】
ユーザ自身の装置においてプライバシを保護するような方法でユーザのプロフィルが作成され保持されるものと仮定すると、次のステップは、プロフィル情報を活用して、広告をユーザに対してターゲティングすることである。プライバシを保護するような方法でプロフィルが準備された後でも、ユーザの装置が適切な広告選択を行うためにそのプロフィルを外部のサービスプロバイダ、または信頼できるか否かに関わらずその他の任意の第３者に送信してしまえば、ユーザのプライバシが危険にさらされることになる。したがって、プロフィル情報は、常に、どのような形態であれ、また行き先がどのような装置であっても、ユーザの装置から出ることを許すことはできない。
【００１１】
プロフィル情報を秘密にしておく１つの方法は、以下のように役割交代を利用するものである。プロフィルをサービスプロバイダに送信して、特定のユーザがどの広告のセットに関心を持っているかをサービスプロバイダに判定させるのではなく、広告主が関心を持っているプロフィルパラメータをサービスプロバイダがユーザ装置に送信し、その後ユーザが関心を持っている広告のセットをユーザ装置が決定させることができる。その後、特定のユーザが関心を持っている広告のセットに関する情報がサービスプロバイダに供給され、サービスプロバイダが、適当な時点でこれらの広告を表示するためにユーザ装置に配信する。サービスプロバイダが関心を持っている広告のセットをユーザ装置が特定する場合には、ユーザの好みに関する情報に関するユーザプライバシが、少なくとも部分的には危険にさらされることを認識すべきである。例えば、ユーザがＡｕｄｉ社の車およびＢｕｄｗｅｉｓｅｒ社のビールの広告を見ることに関心を持っているとユーザ装置がサービスプロバイダに告知すれば、そのユーザが車とアルコール飲料に関心を持っていると推測することができる。
【００１２】
本発明の特定の実施形態の１つの目的は、最終的にサービスプロバイダがプロフィルを構築することを可能にするいかなるユーザ動作に関する情報も、サービスプロバイダに送信することを回避することである。この目的を達成するために、広告をターゲティングするプロセス（例えばユーザ）を、広告の入札（例えばサービスプロバイダ）から切り離す。従来の方法では、ユーザに対して示された広告に基づいてサービスプロバイダが広告主に課金するので、広告のターゲティングと広告の入札は、必然的に絡み合っている。広告主に適切に課金するために、サービスプロバイダが把握しておく必要があるのは、特定の広告を見るユーザの数だけであり、個々のユーザのＩＤは必要ないことに留意されたい。
【００１３】
本発明の特定の実施形態では、関連する期間を複数のエポック（例えば１日、６時間間隔、または１週間など）に分割する。ユーザのプロフィルはエポック内でも変化する可能性があるが、エポックの開始時にしか更新しないものと仮定する。サービスプロバイダは、そのエポックの間に示すことができる１組の広告のセットをユーザ装置にロードする。その広告のセットがサービスプロバイダが保持する全ての広告であることも考えられるが、実際には、ユーザの装置にロードされる広告のセットは、サービスプロバイダが保持する全ての広告のセットのうちの一部である。所与の瞬間に、ユーザ装置は、このセットの中から自分のプロフィルを満足する広告を選択し、この広告がユーザに対して表示される。しかし、ユーザ装置は、ユーザがどの広告を見たかはサービスプロバイダに通知しない。その代わりに、サービスプロバイダは、何らかの別の情報を用いて、特定の広告を見たユーザの数を推定する。この推定値を得るために、サービスプロバイダは、広告主が関心を持っているプロフィルをユーザ装置に送信する。各ユーザ装置は、これらの広告それぞれの妥当性を評価し、これによりブールベクトルが構築される。このブールベクトルを通常の形態で送信するのではなく、ユーザ装置は、このベクトルの各エントリを確率論的に攪乱し（例えば所与の第１の確率に基づいてエントリ０をエントリ１に変換し、所与の第２の確率に基づいてエントリ１をエントリ０に変換するなどによって（実施形態によって、第１の確率と第２の確率は同じでもよいし異なっていてもよい））、その後攪乱したベクトルをサービスプロバイダに送信する。その後、サービスプロバイダが、各広告の真の１の数を推定し、課金の際には、その広告を見たユーザの数としてこの推定値を使用する。このようにして、サービスプロバイダは、ユーザのプロフィルを知らないまま、その広告を示すたびに広告主に課金することができ、ユーザは、自分の好みを開示することなく、ターゲティングされた広告を見ることができる。したがって、サービスプロバイダが、ユーザ装置が送信する攪乱プロフィルベクトルから正確にユーザの数を推定できることを保証することが重要である。
【００１４】
本発明の特定の実施形態は、ユーザ自身の装置においてプライバシを保護する方法で（ユーザのウェブ閲覧習慣およびＴＶ視聴習慣に基づいて）ユーザプロフィルを作成するアーキテクチャおよび方法体系を提供する。本発明の特定の実施形態では、サービスプロバイダの収益を最大にしながら、ユーザプロフィル情報の完全な知識無しで広告をターゲティングすることができる広告スケジューリング機構を利用する。特定の実施形態では、プライバシ保護広告スケジューラは、ターゲットインターネット広告を表示する従来のオンライン手法を改良した保証付き近似オンラインアルゴリズムを利用する。このアルゴリズムは、サービスプロバイダをユーザから分離することによってプライバシを保護するのによく適している。システム中のユーザ装置は、ランダム化応答技術を使用して、攪乱プロフィル情報をスケジューラに提供する。本発明の特定の実施形態では、従来の手法より改善されたプライバシ保護を実現するだけでなく、広告を見るユーザの数を推定する標準的な手法より１桁から２桁性能が高い新たなランダム化による攪乱方式を利用する。本発明の特定の実施形態によるシステムは、信頼できる第３者を必要とすることなくプライバシを保護する方法で広告をターゲティングするために有効に使用することができる。したがって、本発明の特定の実施形態による方式は、「トリプルプレイ」サービスプロバイダ（例えば複合電話、ＴＶおよびインターネット）、セルラ電話サービスプロバイダおよび「オーバーザトップ」サービスプロバイダ（すなわちそのサービスが１つまたは複数の第３者ネットワークの上に配置されるプロバイダ）にも適している。これらの方式は、サービスプロバイダがユーザの活動に関する具体的な情報を取得できないように、またはユーザのプロフィルにアクセスできないようにすることにより、ユーザのプライバシを向上させる。
【００１５】
一実施形態では、本発明は、１組のユーザ装置のセットの中で、あるタイムスロット中に複数の候補広告のうちのターゲット広告を示しているユーザ装置の数を推定するコンピュータ実施方法を提供する。この方法は、（ａ）コンピュータが、セット中の各ユーザ装置に対して、タイムスロット中にユーザ装置によって示すことができる複数の候補広告のＩＤを送信するステップと、（ｂ）コンピュータが複数のユーザ装置からデータを受信するステップであり、（ｉ）タイムスロット中に複数の候補広告の中からターゲット広告を示すユーザ装置の数を、複数のユーザ装置から受信したデータに基づいて推定することができ、（ｉｉ）タイムスロット中にターゲット広告を示すユーザのＩＤを、複数のユーザ装置から受信したデータに基づいて決定することができない、受信するステップと、（ｃ）コンピュータが、複数のユーザ装置から受信したデータに基づいて、タイムスロット中にターゲット広告を示すユーザ装置の数を推定するステップとを含む。
【００１６】
別の実施形態では、本発明は、１組のユーザ装置のセットの中で、あるタイムスロット中に複数の候補広告のうちのターゲット広告を示しているユーザ装置の数を推定するためのデータを生成するユーザ装置実施方法を提供する。この方法は、（ａ）ユーザ装置が、タイムスロット中にユーザ装置によって示すことができる複数の候補広告のＩＤを受信するステップと、（ｂ）ユーザ装置がデータを生成するステップであり、（ｉ）ユーザ装置のセットの中で、タイムスロット中に複数の候補広告の中からターゲット広告を示すユーザ装置の数を、複数のユーザ装置からのデータに基づいて推定することができ、（ｉｉ）タイムスロット中にターゲット広告を示すユーザ装置の識別情報を、複数のユーザ装置からのデータに基づいて決定することができない、生成するステップと、（ｃ）ユーザ装置が、複数のユーザ装置からのデータに基づいてタイムスロット中にターゲット広告を示すユーザ装置の数を推定するように構成されたコンピュータにデータを提供するステップとを含む。
【００１７】
さらに別の実施形態では、本発明は、コンピュータと、コンピュータと通信する１組のユーザ装置のセットとを含むシステムを提供する。コンピュータは、（ｉ）セット中の各ユーザ装置に対して、タイムスロット中にユーザ装置によって示すことができる複数の候補広告のＩＤを送信し、（ｉｉ）複数のユーザ装置からデータを受信するように構成される。ユーザ装置のセットの中で、タイムスロット中に複数の候補広告の中からターゲット広告を示すユーザ装置の数は、複数のユーザ装置からのデータに基づいて推定することができる。タイムスロット中にターゲット広告を示すユーザ装置の識別情報は、複数のユーザ装置からのデータに基づいて決定することはできない。コンピュータは、複数のユーザ装置からのデータに基づいて、タイムスロット中にターゲット広告を示すユーザ装置の数を推定するように構成される。
【図面の簡単な説明】
【００１８】
【図１】ユーザのウェブ閲覧活動に基づいてユーザをプロファイリングする方法の２つの例示的なカテゴリを示すシステム図である。
【図２】各ユーザ装置が各タイムスロット中に攪乱プロフィルをスケジューラに提供する、本発明の一実施形態による例示的なプライバシ保護スケジューラを示すシステム図である。
【図３】本発明の一実施形態による例示的なプライバシ保護スケジューリング方式を示す流れ図である。
【発明を実施するための形態】
【００１９】
プライバシ保護プロフィル作成
図１は、ユーザのウェブ閲覧（またはＴＶ視聴）活動に基づいてユーザをプロファイリングする方法の２つの例示的なカテゴリを示す図である：すなわちクッキー型トラッキング（実線で示す）およびセッション検査（破線で示す）である。クッキー型トラッキングでは、ユーザの閲覧活動は、サービスプロバイが、ユーザ装置１０１上で動作しているブラウザがネットワーク１０４を介して現在ユーザが閲覧している１つまたは複数のウェブサーバ１０２に送信する１つまたは複数のファイル（「クッキー」と呼ぶ）を使用してトラッキングする。セッション検査型手法では、ユーザ装置１０１（例えばＰＣ、宅内ゲートウェイ、ＴＶまたは携帯電話）から発生するトラフィックを遠隔サーバ１０３（例えばディープパケットインスペクション装置またはウェブプロキシ）で検査して、どのウェブサイトを現在ユーザが訪問しているかを判定する。次いで、例えば訪問したウェブサイトの種類、訪問頻度、クリックスルー率などの情報に基づいて、ユーザプロフィルが作成される。
【００２０】
いずれの方法を用いてユーザのウェブ閲覧活動に関する情報を収集しても、従来は、それらの情報から作成されたプロフィルは、サービスプロバイダがそのインフラストラクチャ内に保持する。プロバイダがユーザに対して、プロファイリング方式に「オプトイン」すること、あるいはプロフィル情報を見、かつ／または修正することをユーザに許すこともあるが、肝心な点は、ユーザがプロフィルに関するいかなる明示的な制御権も有していないこと、およびプロフィルがユーザから離れることである。当然、このことは、ユーザプロフィル情報の利用について、またはその悪用の可能性について、ユーザの信頼低下をもたらすことがある。本発明の特定の実施形態は、ユーザのプロフィルをユーザの装置内で作成して保持し、プロフィルが装置から出ることを許さないようにすることにより、このような懸念を払拭する。サービスプロバイダがユーザプロフィルにアクセスすることを防止しなければならないだけでなく、サービスプロバイダがユーザプロフィルに含まれる情報を「推測」できるようになる推論を行うことも防止しなければならない。さらに、本明細書では、サービスプロバイダがいかなるユーザ関連情報もネットワークから収集しない、または収集することを（例えば法律によって）禁止されるものと仮定する。
【００２１】
次に、本発明の特定の実施形態におけるユーザの関心を反映したプロフィルの作成に関するさらなる詳細について述べる。ユーザは、１回の閲覧セッション中にいくつかのウェブサイトを訪問するのが普通である。ユーザプロフィルを構築するために、これらの各サイトを、いくつかの代表語によって分類することができる。この代表語を、以下「分類子」と呼ぶ。例えば、ｗｗｗ．ｃｎｎ．ｃｏｍおよびｗｗｗ．ｅｄｍｕｎｄｓ．ｃｏｍの分類子は、それぞれ｛ニュース、ワールドニュース｝および｛車、ユーザカー｝とすることができる。ユーザの関心は、そのユーザが訪問したウェブサイトを表す１組の分類子のセットとして表現することができる。例えばユーザが同じウェブサイトを複数回訪問したり、性質の類似したウェブサイトを訪問したりすることなどにより、いくつかの分類子は複数回出現する可能性があるので、各分類子に０から１の間の重みの形態でスコアを割り当てて、その分類子の相対的な重要度を所与のユーザに対して示す。例えば、車とフットボールに関心があるユーザのプロフィルを、｛（車、０．４）、（スポーツ、０．７）｝とすることもでき、これは、そのユーザが車よりもスポーツに関心を抱いていることを示している。
【００２２】
本発明の特定の実施形態では、ユーザプロフィルの作成は、以下の３つのステップを含む：第１に、ウェブサイト訪問およびクリックスルー率を反映するデータを収集する。第２に、ウェブサイトを、そのサイトの性質を反映する１つまたは複数の分類子にマッピングする。第３に、分類子と、対応するウェブサイト訪問の頻度とを使用して、１組の（分類子、スコア）対のセットを含むユーザのプロフィルを作成する。この第３のステップ中に、最近の関心の方が過去の関心より重みが大きくなるように（すなわちスコアが高くなるように）ユーザの関心を「エージング」することもできる。
【００２３】
プロフィル計算の勘所は、複数のウェブサイトのそれぞれに割り当てる適当な分類子のセットを小さくすることである。プロフィルは、ユーザ装置内で最小限の資源を使用して実時間で作成して保持することが望ましい。したがって、ウェブサイトを分類する手続きは、簡単かつ効果的でなければならない。そうでなければ、大きな処理およびメモリ資源と良好なネットワーク接続性を有するサーバなど、ユーザ装置以外の装置によって実行しなければならないからである。
【００２４】
本発明の特定の実施形態では、ユーザプロフィルは、例えばＰＣや携帯電話、セットトップボックス、宅内ゲートウェイ、テレビジョンなど、ユーザの装置内で作成される。上記の装置の現在のバージョンは、いずれであっても、プロフィル作成プロセスの第１のステップおよび第３のステップを容易に実行することができる。しかし、第２のステップは、場合によってはこれらの装置の能力を超える可能性があるので、ウェブサイトの１組の適当な分類子のセットを要求に応じて戻すように構成されたオフサイトサーバによって、これらの装置を補助することがある。しかし、このような外部補助を用いると、第２のステップでプロフィル関連情報がサービスプロバイダに漏れる危険性がある。その結果として生じるプライバシに対する懸念には、例えば、装置中心方法およびプロバイダ援用方法と呼ぶ、以下の２つの例示的な方法のうちの１つを用いて対処できることが望ましい。
【００２５】
装置中心方法では、ユーザ装置が、キーワードをウェブサイトに割り当てることを担当する。ウェブサーバは、ユーザ装置からのページ受信要求に応答して、閲覧しているユーザの装置にｈｔｍｌページを送信する。このページがユーザ装置を通過するときに、ユーザ装置は、分類子を調べてページに割り当てるソフトウェアルーチンを実行する。分類子を割り当てる軽量な方法では、ウェブページに含まれるメタデータ（例えばタイトル、キーワード、記述など）を使用する。この方法は、ユーザ装置に追加の作業負荷をほとんど生じず、現行世代の装置のほとんどが容易に扱うことができ、携帯電話でも容易に扱うことができる。この方法は、いかなる新たなネットワークトラフィックも生じさせず、またいかなるユーザ固有情報もサービスプロバイダに漏洩しない。唯一の欠点は、この分類子割当て方法は、ページ作成者の思いつきで選ばれた情報のみに依存するので、分類子が必ずしも正しくウェブページの実際のコンテンツに対応しているとは限らない可能性があることである。一方、ユーザ装置が十分な処理能力および無制限の高速なネットワークアクセスを有する（例えばブロードバンド接続を有するＰＣなど）場合には、ユーザ装置は、より多くの資源を使用する分類子割当て方法を実施するように構成することもできる。
【００２６】
プロバイダ援用方法では、ユーザ装置は、分類子データベースサーバ（ＣＤＳ）または場合によってはキーワードデータベースサーバ（ＫＤＳ）と呼ばれるネットワーク常駐サーバを調べて、分類子をウェブサイトに割り当てる。ＣＤＳの機能は、アルゴリズムに基づいて、ユーザ装置からの要求を満たしてウェブサイトに１組の分類子のセットを提供することである。ＣＤＳの機能は、ネットワークサービスプロバイダまたはオーバーザトップ（ＯＴＴ）サービスプロバイダが提供してもよいし、あるいは公開サーバで実施してもよい。異なる所有者に属するいくつかのＣＤＳサーバがネットワーク上に分散している可能性もある。このシナリオでは、ユーザ装置は、ユーザから要求されたウェブページの統一資源ロケータ（ＵＲＬ）を、無作為に選択したＣＤＳに安全に送信し、このＣＤＳが、これに応答して、そのＵＲＬによって特定されるウェブページに割り当てられた分類子を戻す。プロバイダ援用方法では、ユーザ装置の計算負荷が低下し、ユーザ装置とＣＤＳの間の通信中に比較的小さな負荷しかネットワークにかからない。この負荷の影響をさらに低減するためには、問合せのトラフィックに対して低い優先順位を割り当てて、問合せのトラフィックがその他のネットワークトラフィックを妨害しないようにしてもよいし、あるいはオフピーク時間中に問合せを行うようにしてもよい。ただし、問合せの内容が、どのウェブサイトをユーザが訪問したかをＣＤＳに知らせることにより、何らかのユーザ関連情報をサービスプロバイダに漏らす可能性は依然としてある。このような情報の漏洩を防止するために、以下の３つの例示的な仕組みのうちの１つを用いることができる：すなわちランダム化、プロバイダのアノニマイザおよびパブリックドメインアノニマイザのうちの１つを用いることができる。
【００２７】
ランダム化：この方法では、ＣＤＳは、ユーザ装置からの２種類の要求に応答する：すなわち（ｉ）分類子のデフォルトセットを求める要求、および（ｉｉ）特定の１組のウェブサイトの分類子を求める要求に応答する。ユーザ装置が分類子のデフォルトセットを要求するときには、ＣＤＳは、ユーザ母集団全体からのアクセス頻度が高い何らかのウェブページのセットに対応する分類子を送って応答する。このウェブページのセットは、例えば、要求される頻度が最も高いページ、要求される頻度が最も低いページ、最近数時間の間に要求されたウェブページの上位１００、およびこれらのウェブページのセットの組合せなどを含むことができる。ユーザ装置は、この情報をキャッシュする。ユーザがこのセットに含まれるいずれかのウェブサイトを訪問した場合には、ユーザ装置は、ＣＤＳに対して明示的な要求を送信する必要はなく、ユーザ固有情報がサービスプロバイダに漏れることはない。ユーザが訪問したウェブサイトがこのセットに含まれない場合には、装置は、このサイトの要求をＣＤＳに送信するか否かを無作為に判断する。装置は、要求を送信すると判断した場合には、ユーザが実際には訪問していない追加のウェブサイトもいくつか慎重に選んで、それらで要求を増補する。このようにすると、プロバイダには、それらのウェブサイトのうちのどれをユーザが訪問したのかが正確に分からない。ユーザ装置が複数のＣＤＳにアクセスできる場合には、装置は、問合せを複数の異なるＣＤＳに分散させて、１つのＣＤＳがプロフィルを再現できるだけの十分なユーザに関する情報を取得しないようにすることを選ぶこともできる。なお、この方法は、追加のネットワークトラフィックを多少生じることもあり（例えば１要求あたり数百バイトなど）、またサービスプロバイダがユーザのウェブサーフィン挙動を曖昧ではあるがある程度把握できる可能性があることに留意されたい。
【００２８】
プロバイダのアノニマイザ：この方法では、プロバイダは、ＣＤＳをネットワークアドレス変換（ＮＡＴ）装置の背後に配置する。ユーザ装置は、ウェブサイトから分類子へのマッピングが必要になったときには、ＣＤＳに対して（例えばセキュアソケットレイヤ（ＳＳＬ）を介して）セキュア要求を行う。ＳＳＬセッションは、ＮＡＴ装置を通過するが、この過程では、いずれのユーザ装置とも関係のない１つまたは複数のインターネットプロトコル（ＩＰ）アドレスがＣＤＳに対して示される。ＣＤＳは、その応答を、ＳＳＬセッションを介して安全にユーザ装置に返送する。ＣＤＳは、ユーザ装置の元のＩＰアドレスに触れることがないので、どのユーザ装置がその要求を行ったのかが分からない。要求と応答がＳＳＬを介して伝送されるので、ＮＡＴ装置には、ユーザ装置がどのウェブページを要求したのかが分からない。このように、ユーザ関連情報は、サービスプロバイダにさらされない。この方法では、ユーザが実際に訪問するウェブサイトを求める要求に関連する帯域幅以外には、ネットワークへのいかなる追加のトラフィック負荷も生じない。ただし、ＮＡＴ装置およびＣＤＳが同じパーティの制御下にある場合には、ユーザが訪問したウェブサイトを決定することが可能であることもあることに留意されたい。
【００２９】
パブリックドメインアノニマイザ：この方法では、ユーザ装置は、任意のパブリックドメインアノニマイザまたは第３者「信頼される」アノニマイザを使用して、ＣＤＳにコンタクトを取る。この方法は、例えばユーザが他の方法を利用しているプロバイダによって提供されるプライバシに満足できない、またはこれを信頼できない場合に使用することができる。プロバイダがパブリックドメインアノニマイザまたは第３者アノニマイザと共謀する可能性は比較的低いので、この構成では、ユーザ装置によって行われる要求をＣＤＳが知ることが防止される。この方法ではプライバシが改善されるが、全ての要求および応答が、インターネットを介してアノニマイザに送られ、またアノニマイザから送られるときに追加の帯域幅を生じる。
【００３０】
ウェブサイトを１組の分類子のセットにマッピングした後で、ユーザ装置は、対応するウェブサイトへの訪問の頻度に基づいて分類子のスコアを計算する。なお、特定のウェブサイトへの訪問の頻度に関する情報がサービスプロバイダに示されることはなく、したがって、サービスプロバイダがユーザのプロフィルを正確に再現することは不可能である。さらに、ユーザ装置は、新しい関心の方が古い関心よりスコアが高くなるようにプロフィルのエージングも行い、サービスプロバイダは、この「エージング」後のユーザのプロフィルを計算することはできない。
【００３１】
前述の方法体系は、ユーザのＴＶチャンネルサーフィン活動、ビデオオンデマンド（ＶｏＤ）要求、およびそれに類するＳＴＢを通過する情報に基づいてユーザプロフィルを作成するために使用することもできる。現在のＳＴＢは、電子番組ガイド（ＥＰＧ）のダウンロードやＶｏＤ注文などのためのＩＰ接続性を有する。したがって、ＳＴＢは、上述のステップと同様のステップを実行して、プロフィル作成および分類子割当てを行うことができる。この構成では、ＳＴＢは、ＥＰＧ情報をキャッシュし、チャンネルサーフィン情報をＥＰＧにマッピングして、ユーザがどのＴＶ番組を見ているかを特定する。ＴＶ番組には、上述のＣＤＳと同様のデータベースサーバによって分類子が割り当てられる。ＳＴＢは、ＣＤＳから分類子を取り出し、所与の番組を見る頻度およびその番組を見ている時間（例えばユーザが３０分の番組を視聴するのに実際に費やす総分数）によって分類子を重み付けすることによって、ユーザのＴＶ視聴プロフィルを作成する。同様に、ビデオオンデマンド（例えばペイパービュー）の要求はＳＴＢを通過するので、ＳＴＢは、どのサービス／映画がいつ注文されたか分かる。ＣＤＳに関連して上述したように、ＳＴＢは、この情報を使用して、ユーザから注文されたサービス／映画に関する（分類子、スコア）対を作成する。ＥＰＧ情報および関連する分類子が装置内に残っている場合には、ユーザのチャンネルサーフィン活動をサービスプロバイダに送信する必要がないので、ユーザ関連情報の漏れは生じない。オンデマンドサービスでは、ユーザが通常は多数の項目の選択肢の中から注文することができるので、装置がその項目に関連する分類子をキャッシュすることができないこともあり、その場合には、前項で述べた３つの技術（ランダム化、プロバイダのアノニマイザ、およびパブリックドメインアノニマイザ）のうちのいずれかなどを使用して分類子を集めることができる。
【００３２】
前述の方法に加えて、キーワード生成およびプロフィル作成を行うその他の可能な方法が、米国特許出願公開第２０１１／００１６１９９号に記載されており、その開示は、引用によりその全体が本明細書に組み込まれている。
【００３３】
例示的な広告ターゲティングシステムの概要
ターゲティングした広告を一群のユーザに対して表示することに関心がある１組の広告主を含むシステムでは、例えば人口統計学的情報、位置情報ならびにテレビジョンおよびオンライン視聴挙動を含むユーザプロフィルによって各ユーザを記述することができる。人口統計学的情報など、一部のプロフィル情報は比較的静的である可能性があるが、オンラインサーフィン挙動やユーザ位置など、他のプロフィル情報は動的である可能性がある。各広告主は、特定の情報を含むプロフィルを有するユーザにターゲティングすることに関心がある。各広告主は、（ｉ）１つまたは複数のターゲットプロフィルを、（ｉｉ）ターゲットプロフィルを有するユーザに広告が示された場合に広告主が支払うつもりの入札金額および（ｉｉｉ）サービスプロバイダが広告主に課金することができる最高金額（すなわち予算）とともに指定する。本明細書の方法体系の説明では、広告主は１つのターゲットプロフィルを指定しているが、この方法体系は、広告主が、プロフィルごとに入札金額を変えて複数のターゲットプロフィルを指定するように拡張することができる。本発明の特定の実施形態による広告スケジューリングシステムの目的は、サービスプロバイダの収益を最大にすることである。本発明の特定の実施形態によるスケジューラは、収益を最大にしようと努めるのと同時に、さらにいくつかの目的を考慮しなければならない。第１に、スケジューラは、ユーザプロフィル、ユーザ利用情報または広告主の入札金額および予算に関するいかなるアプリオリな知識も前提としてはならない。このことは、広告スケジューリングの判断をオンラインで行わなければならないことを意味する。第２に、各ユーザは、自分のプロフィル情報を知っており、それを非公開に保ちたいと思うものと仮定する。このことは、プライバシの観点から、本発明の特定の実施形態によるスケジューリングアルゴリズムが、ユーザプロフィル情報についてのいかなる知識も用いずに実行されなければならないことを意味する。
【００３４】
上記の２つの制約に照らしてスケジューラがサービスプロバイダの収益を最大にすることは困難または不可能に思われるかもしれないが、広告主に関するアプリオリな情報を用いずに、ユーザに関する確率論的情報のみを用いてスケジューラが収益を最適化することは実際に可能である。この目的を達成するために、ターゲティングした広告を分配する３つの異なるスケジューラ（すなわちスケジューリング方式）について述べる。第１のスケジューラは、将来に関する完全な知識およびユーザプロフィル情報に関する全ての知識を有する「完全情報スケジューラ」である。第２のスケジューラは、将来についての知識は持たないがユーザプロフィル情報に関する完全な知識は有している「オンラインスケジューラ」である。第３のスケジューラは、ユーザプロフィルに関する攪乱（すなわちプライバシ保護）情報のみを有する「オンラインプライバシ保護スケジューラ」である。次に、これら３つのスケジューラについて、さらに詳細に述べる。
【００３５】
完全情報スケジューラ：このスケジューラでは、全ての将来のユーザ利用（すなわちどのユーザがいつアクティブになるか）、ユーザプロフィル情報、および広告主の好みがアプリオリに分かっているものと仮定する。この情報が全て与えられたものとすると、スケジューラは、収益を最大にする最適化問題を定式化し、その後この解を実施することができる。この手法で立てる仮定は非現実的であるが、完全情報スケジューラは、達成可能な収益に上限を設け、第２のタイプのスケジューラ、すなわちオンラインスケジューラのための基準を形成する。
【００３６】
オンラインスケジューラ：オンラインスケジューラは、各タイムスロット中に広告割当てを行う。このスケジューラは、各タイムスロット中のアクティブなユーザのセットおよびそれらのユーザのプロフィルと、各広告主の残りの予算とを知っている。適当な判断を下すことによって、オンラインスケジューラの性能は、完全情報スケジューラの性能の数分の１（一定値）以内となる。この手法は、アプリオリな情報を用いずに収益を最大にするという第１の目的は満たす。しかし、この手法では、全てのユーザプロフィル情報がスケジューラにさらされることを前提としている。第３のタイプのスケジューラは、ユーザプロフィル情報をマスクするようにこのオンラインアルゴリズムを修正したものである。
【００３７】
上記のオンラインスケジューラは、２つの主要な特徴を有する：すなわち、（ｉ）オンラインスケジューラは、そのスケジューラが計算する入札金額およびその他のパラメータに基づいて広告を順序付けすること、および（ｉｉ）各ユーザ装置が、対応するユーザのプロフィルと一致する順序付けされたリスト中の最初の広告を表示することを特徴とする。オンラインスケジューラが各タイムスロット中に必要とするユーザ装置からの重要な情報には、各広告を見たユーザの総数が含まれるが、ユーザのＩＤを知る必要はない。（ｉ）全ての広告が各ユーザ装置に予めロードされており、（ｉｉ）ユーザプロフィルを把握しているのがユーザ装置だけであるシステムを考えると、各ユーザ装置は、各タイムスロット中にどの広告を表示すべきかを容易に決定することができる。しかし、オンラインスケジューラを実施することの欠点は、このスケジューラが、広告主にいくら課金すべきかを決定するのに、どれだけの数のユーザが各広告を見たか分からないことである。
【００３８】
プライバシ保護スケジューラ：図２は、１人または複数人のユーザが（例えば携帯装置２０１あるいはＰＣ２１１またはＴＶ２１２に接続された宅内ゲートウェイ２１０を用いるなどして）各タイムスロット中に攪乱プロフィルをスケジューラ２０２に提供する、例示的なプライバシ保護スケジューラ２０２を示す図である。（実施形態によっては、プライバシ保護スケジューラは、プロフィルに変更があったときにしか攪乱プロフィルを提供しない。）スケジューラ２０２は、ネットワーク２０４を介してＣＤＳ２０３と通信している。以下でさらに詳細に述べるように、このスケジューラは、所与のユーザがどの広告を見たかを知ることなく、各タイムスロット中にどれくらいの数のユーザが各広告を見たかを推定して、ユーザのプライバシを保護しながら適切に広告主に課金できるようにすることができる。
【００３９】
ユーザプロフィルおよび広告の妥当性
上述のように、本発明の特定の実施形態では、ユーザのプロフィルは、ユーザに関する静的な情報および動的な情報の両方を含み、各広告主は、プロフィルが所与のプロフィル要素の組合せを含んでいるユーザに入札する。例えば、広告主は、この１週間の間にインターネット上で車を検索した特定の地域に住んでいる一群のユーザをターゲティングしたいと考えることがある。したがって、広告主にとって関心のあるプロフィルは、ユーザの挙動のいくつかの要素の組合せを含む可能性がある。ユーザ装置がそのユーザ自身のプロフィルをトラッキングする場合には、ユーザ装置がそのユーザが所与の広告のターゲットであるかどうかを知ることは比較的容易である。したがって、ユーザｊが広告ｉによって指定されたターゲットプロフィルに一致する場合には、ユーザｊは広告ｉに「妥当」であると言うことができる。所与の時点ｔにおけるユーザｊにとっての広告ｉの「妥当性」は、２値変数Ａｉｊ（ｔ）で表される：
【００４０】
【数１】
0006047161.tif 000002
【００４１】
ユーザのプロフィルおよび広告主のターゲットは時間経過とともに変化する可能性があるので、妥当性ベクトルＡｉｊ（ｔ）の定義は、時間インデックスを陽に含む。妥当性ベクトルＡｉｊ（ｔ）の値をスケジューラが知っている場合には、スケジューラは、そのユーザが広告ｉと関連する広告主が指定した全てのプロフィル要素を満たすことも分かる。したがって、ユーザの目的は、妥当性ベクトルＡｉｊ（ｔ）の値を非公開に保つことである。以下の項で述べる最初の２つのスケジューラ（すなわち完全情報スケジューラおよびオンラインスケジューラ）では、妥当性ベクトルＡｉｊ（ｔ）の値をスケジューラが知っていることを前提とする。ただし、この前提は、プライバシ保護スケジューラでは緩和される。
【００４２】
完全情報スケジューラ
次に、広告のスケジューリングおよび広告収益の最適化の問題の定式化について述べる。ｎ個の異なる広告を含むシステム（簡単のために、各広告主が所与の広告ｉと関連付けられるものと仮定する）では、広告は、ｔ＝１、２、…、Ｔのインデックスで示すＴ個のタイムスロットにわたってスケジューリングされる。変数Ｓ（ｔ）は、タイムスロットｔ中の「アクティブ」なユーザの集合を示す。あるタイムスロット中に広告を表示することができる装置をユーザが見ている場合に、そのタイムスロットにおいてそのユーザがアクティブであると言う。広告ｉと関連する広告主が、タイムスロットｔ中に任意のユーザｊに対して広告を表示することに対してｂｔ（ｉ）を支払うつもりであり、その妥当性ベクトルはＡｉｊ（ｔ）＝１であり、かつｊ∈Ｓ（ｔ）である、すなわちユーザがアクティブであり、かつ広告ｉのプロフィルに適合するものと仮定する。さらに、広告ｉと関連する広告主は、Ｔ個のタイムスロットにわたって広告主が支払うつもりである最高金額を表す予算Ｂ（ｉ）を指定する。完全情報スケジューラでは、Ｓ（ｔ）、Ａｉｊ（ｔ）およびｂｔ（ｉ）の値は、全てのタイムスロットｔ、全てのユーザｊ、および全ての広告ｉについてアプリオリに分かっているものと仮定する。完全情報スケジューラの目的は、各広告主の予算を考慮しながら総収益を最大にする、各タイムスロットにおけるユーザに対する広告主の割当てを決定することである。このスケジューラの決定変数は、２値変数Ｘｉｊ（ｔ）である：
【００４３】
【数２】
0006047161.tif 000003
【００４４】
収益を最大にする問題は、以下の整数計画プログラムとして書くことができる。
【００４５】
【数３】
0006047161.tif 000004
ここで、ＴＲＣＩは、完全情報スケジューラによって達成される総収益を表す。数式（１）は、各ユーザに対して各スロット中に最大で１つの広告が示されるようにする。数式（２）は、各広告主の予算が守られるようにする。数式（３）は、決定変数が各タイムスロットｔ中にユーザｊごとに各広告ｉに割り当てられるようにする。数式（１）−（３）は、整数計画問題を構成するので、この問題は、これをそのまま解くのではなく、次の項で展開するオンラインアルゴリズムの基準となる。
【００４６】
オンラインスケジューラ
オンラインスケジューラは、完全情報スケジューリング問題の近似解を与えるプライマルデュアルアルゴリズムである。しかし、所与の瞬間に１人のユーザが現れる通常のインターネット広告ターゲティングとは異なり、オンラインスケジューラを利用するシステムでは、任意のタイムスロット中に複数のユーザがアクティブである可能性がある。したがって、同時に存在するユーザのグループに対してプライマル更新およびデュアル更新を実行し、これにより、次項で概説するプライバシ保護オンラインスケジューラを可能にする。オンラインアルゴリズムを展開するために、上限Ｘｉｊ（ｔ）を０≦Ｘｉｊ（ｔ）≦１に設定して、完全情報スケジューラの線形計画緩和を最初に考慮する。上限Ｘｉｊ（ｔ）≦１は、上記の数式（１）によって示されるので、この定式化では削除することができる。次に、上記の線形計画緩和に対する双対問題は、以下のように書くことができる：
【００４７】
【数４】
0006047161.tif 000005
ここで、双対変数δ（ｉ）の符号に制限はない。（なお、双対変数π（ｊ、ｔ）およびδ（ｉ）は、近似保証を導出する際に使用される中間変数に過ぎず、それ自体ではいかなる特定の重要性も有していないことに留意されたい。）数式（４）から、双対変数π（ｊ、ｔ）は、以下のように設定することができる：
【００４８】
【数５】
0006047161.tif 000006
【００４９】
上述のようなオンラインスケジューリングアルゴリズムは、完全情報広告スケジューラの線形計画緩和を解く。
【００５０】
オンラインスケジューラは、各タイムスロットの開始時にユーザと広告をマッチングする。タイムスロットｔの開始時に、この広告選択アルゴリズムは、以下の情報を有しているものと仮定する：（ｉ）時点ｔにおけるアクティブなユーザの集合Ｓ（ｔ）、（ｉｉ）広告ｉに対応する広告主がＡｉｊ（ｔ）＝１であるユーザｊに対して示す入札金額ｂｔ（ｉ）、および（ｉｉｉ）各広告ｉに対応する広告主の予算Ｂ（ｉ）および現在の残りの予算。オンライン広告選択アルゴリズムは、Ｓ（ｔ）中の各ユーザの厳密に１つの広告ｉに対する割当てを出力する。
【００５１】
次に、本発明の一実施形態によるオンラインスケジューリングアルゴリズムの概要を述べる。以下に述べるオンラインスケジューラは、プライマルデュアル方式を使用して、各タイムスロット中に広告を選択する。
【００５２】
双対変数δ（ｉ）は、ゼロに初期化され（δ（ｉ）←０  ∀ｉ、ｔ＝１）、各タイムスロットｔの終了時に更新される。変数Ｎｉ（ｔ）＝ΣｊＸｉｊ（ｔ）は、時点ｔに広告ｉを見るユーザの数を表し、予算制約条件Ｂ（ｉ）は、以下のように書き直すことができる：
【００５３】
【数６】
0006047161.tif 000007
【００５４】
各タイムスロットで、このオンラインスケジューリングアルゴリズムは、３つのステップを実行する：
ステップ１。広告の順序付け：各タイムスロットにおいて、スケジューラは、ｋ＝１、２、３、…、ｎ−１について、ｂｔ（σ（ｋ））［１−δ（σ（ｋ））］≧ｂｔ（σ（ｋ＋１））［１−δ（σ（ｋ＋１））］となるように、広告の順列σを計算する。表現を簡略にするために、タイムスロットｔ中で広告の番号を付け直して、ｂｔ（１）［１−δ（１）］≧ｂｔ（２）［１−δ（２）］≧…≧ｂｔ（ｎ）［１−δ（ｎ）］となるようにするものと仮定する。したがって、各タイムスロットにおいて、スケジューラは、Ｂ（ｉ）＞０である広告をｂｉ（ｉ）［１−δ（ｉ）］の降順に並べることによって計算した、順序付けされた広告のリストを選択して、ユーザに通信する。
【００５５】
ステップ２。広告の選択：ユーザｊは、Ａｉｊ（ｔ）＝１となるように順序付けされた広告のリストの最初の広告ｉを選択し、その広告を見る。これは、ユーザｊが以下の式を用いて中間変数Ｐ（ｊ）を計算し、他の全てのｉについてＸＰ（ｊ）ｊ（ｔ）＝１およびＸｉｊ（ｔ）＝０と設定することによって行われる：
【００５６】
【数７】
0006047161.tif 000008
【００５７】
ステップ３。予算およびデュアルの更新：次いで、オンラインスケジューラは、各広告を見たユーザの数を決定し、双対変数を更新する。なお、このアルゴリズムのこのステップでは、以下の定理（１）に従って選択される定数ｃがあることに留意されたい：
定理（１）：ＴＲＣＩは、完全情報スケジューラによって生成される収益を示し、ＴＲＯＮは、オンラインスケジューラによって生成される収益を示し、Ｒは、任意のタイムスロットで使用することができる任意の広告主の予算の最大割合を示す。ステップ３では、ｃ←（１＋Ｒ）１／Ｒである場合には、ＲＯＮ≧βＲＣＩである。ここでベータは以下の通りである：
【００５８】
【数８】
0006047161.tif 000009
Ｒ→０である場合には、全ての可能な入力について、ＲＯＮ≧［（ｅ−１）／ｅ］ＲＣＩである。
【００５９】
双対変数π（ｊ、ｔ）は、近似保証を導出する際には使用されるが、広告をユーザに割り当てる際には使用されない。オンラインスケジューラは、期間ｔ中に広告ｉを見たユーザの数を表すＮｉ（ｔ）＝ΣｊＸｉｊ（ｔ）を計算し、以下のように予算制約条件Ｂ（ｉ）ならびに双対変数δ（ｉ）およびπ（ｊ、ｔ）の値を更新する：
【００６０】
【数９】
0006047161.tif 000010
【００６１】
オンラインスケジューラは、各タイムスロット中に各ユーザがどの広告を見たかを把握しているものと仮定する。この情報は、ユーザのプロフィルをスケジューラにさらす。ユーザは、自分のプロフィルを秘密に保ちたいと思う場合には、自分がどの広告を見たかを明らかにすることはできない。
【００６２】
オンラインスケジューラは、ユーザが実行する動作とスケジューラが実行する動作の、２つの基本動作を有することに留意されたい：すなわち、（ｉ）スケジューラは、最初にｂｔ（ｉ）［１−δ（ｉ）］の値の降順に広告を順序付け、また双対変数δ（ｉ）の値を更新することも担い、（ｉｉ）ユーザは、この順序付けされたリストから、ユーザのプロフィルに一致する最初の広告を選択する。ユーザ装置はユーザのプロフィルを把握しているので、可能な全ての広告が装置に予めロードされている場合には、ユーザ装置は、ユーザに対して表示するのに適切な広告を選択することができる。オンラインスケジューラは、双対変数の値を更新することができるように、また広告主に適切に課金することができるように、各広告をどれほどの数のユーザが見たかを把握している。ただし、オンラインスケジューラは、スケジューラがＮｉ（ｔ）の値、すなわち期間ｔ中に広告ｉを見たユーザの数を把握している限り、それぞれのユーザがどの広告を見たかを厳密に知る必要はないことを理解されたい。
【００６３】
次項では、スケジューラがオンライン型アルゴリズムを実行できるようにしながら、スケジューラにさらされるユーザ情報の量を最小限に抑えるプライバシ保護スケジューラについて述べる。
【００６４】
プライバシ保護スケジューラ
次に、各広告を見たユーザの数をスケジューラが決定するのに十分な情報を開示しながら、ユーザが自分の真のプロフィルを隠すことができるようにするプライバシ保護スケジューリング方式について述べる。最初に、このプライバシ保護機構について概説し、その後、各タイムスロット中に各広告を見るユーザの数をスケジューラがどのようにして計算することができるのかを分析する。以下の説明では、全ての広告がユーザ装置に予めロードされていることを前提としている。
【００６５】
プライバシ保護機構は、次のように働く。ｎ次元ベクトルＡ・ｊ（ｔ）を使用して、タイムスロットｔの開始時のユーザｊの「妥当性」ベクトルを表す。Ａｉｊ（ｔ）は、広告ｉが時点ｔにおいてユーザｊにとって妥当であることを示していることに留意されたい。ユーザｊの装置は、その妥当性ベクトルをスケジューラに対して開示しない。その代わりに、ユーザｊの装置は、以降「開示分布ベクトル」と呼ぶ、２値ベクトルＤ・ｊ（ｔ）で表される攪乱したバージョンの妥当性ベクトルを開示する。開示分布ベクトルの各成分は、例えば以下のランダム化を実現する２パラメータ攪乱手続きを用いて、妥当性ベクトルの対応する成分から決定される。
【００６６】
本発明の特定の実施形態の（ｐ、γ）攪乱手続きは、以下のようになるように２値変数Ｂを別の２値変数Ｂ’にマッピングする方式である。
【００６７】
【数１０】
0006047161.tif 000011
【００６８】
この（ｐ、γ）ランダム化手続きの実施態様では、それぞれ「トス」されたときに無作為に（または疑似ランダムに）「表」または「裏」のいずれかが出る、２つのバイアス仮想「コイン」を使用する。第１のコインは、トスされたときに確率ｐで表が出、第２のコインは、トスされたときに確率γで表が出る。
【００６９】
第１のコインが表であれば、Ｂ’＝Ｂとなる。第１のコインが裏であれば、第２のコインをトスする。
【００７０】
そして第２のコインが表であれば、Ｂ’＝１となる。第２のコインが裏であれば、Ｂ’＝０となる。
【００７１】
最も一般的なケースでは、妥当性ベクトルの各成分を、異なるランダム化機構を用いて攪乱することができる。ただし、この場合には、スケジューラが解く推定問題が指数関数的な状態空間になる。したがって、妥当性ベクトルの攪乱は、一定攪乱法またはランダム攪乱法のいずれかを用いて実施されるものと仮定する。
【００７２】
固定攪乱法では、全てのユーザ装置が、一定の（ｐ、γ）確率対を利用して、妥当性ベクトルの各成分を攪乱し、全てのユーザ装置およびスケジューラがｐおよびγの値を把握している。
【００７３】
ランダム攪乱法では、全てのユーザ装置が分かっている共通の分布関数からそれぞれの（ｐ、γ）の値を選択する。ｐの値とγの値は独立して選択され、ｐおよびγの分布は異なっていてもよいものと仮定する。ユーザｊの装置は、その（ｐ、γ）の確率対を選択したら、この値の対を使用してＡ・ｊの各要素を攪乱する。
【００７４】
全てのユーザ装置がそのｐおよびγの値を選択する共通の確率密度関数は、それぞれ変数ρ（ｐ）およびω（γ）を用いて表される。スケジューラも、このｐおよびγの分布関数を把握している。ただし、ユーザ装置は、パラメータｐおよびγの値をスケジューラに対して開示しない。例示を目的として、ｐおよびγの値がそれぞれ［ｌ、１］および「ｌ’、１」の間の一様分布から選択されるシナリオを用いる。ここで、０≦ｌ、ｌ’≦１である。スケジューラは、ｌおよびｌ’の値、ならびにｐおよびγの値が一様分布から選択されることを把握している。ただし、スケジューラは、ｐおよびγの個々の値は把握していない。なお、ランダム攪乱では、いずれの攻撃も個々のユーザの攪乱パラメータを推定することを伴うので、追加のプライバシレイヤをユーザに提供することに留意されたい。
【００７５】
次に、プライバシ保護広告スケジューラの重要なステップの１つである、所与の広告を見るユーザの数を計算する方式について述べる。各広告を見るユーザの数の決定を主に妨げるのは、スケジューラがＡｉｊ（ｔ）の値を把握していないという事実である。変数Ｎｉ（ｔ）は、期間ｔ中に広告ｉを見たユーザの数を表す。スケジューラは、Ｓ（ｔ）、すなわちタイムスロットｔ中のアクティブなユーザの集合を把握しているものと仮定する。数式
【００７６】
【数１１】
0006047161.tif 000012
を使用して、タイムスロットｔ中のアクティブなユーザの総数を表す。ユーザの数は、タイムスロットごとに計算されるので、この説明の残りの部分では、表記を簡略化するために変数ｔを省略する。変数Ｎを使用して、タイムスロットｔ中のアクティブなユーザの総数を表し、変数
【００７７】
【数１２】
0006047161.tif 000013
を使用して、スロットｔ中に広告ｉを見たユーザの数Ｎｉの推定量を表す。各タイムスロットで、広告はスケジューラによって順序付けされ、順序付けされた広告のリストが、各ユーザ装置に送信される。これらの広告は、順序付けされたリストが｛１、２、…、ｎ｝となるように番号を付け直されるものと仮定する。
【００７８】
ユーザｊの装置は、Ａｉｊ＝１となるようにｉの最小値を決定することによって、見る広告を選択し、選択した広告を見る。したがって、ユーザｊが所与の広告ｍを見るのは、以下の場合のみとなる：
Ａｉｊ＝０、ｉ＝１、２、…、ｍ−１、および
Ａｍｊ＝１  （７）
なお、数式（７）を使用して広告ｍをユーザｊが見たかどうかを判定した場合には、１≦ｉ≦ｍ−１で変数Ａｉｊの取り得る値は２ｍ−１個存在する可能性があることに留意されたい。以下でさらに詳細に述べるように、計算負荷は、広告数とともに指数関数的に増大する。このシステムは多数の広告を有する可能性があるので、前述の手法は、実用的ではなく、実施できない可能性さえある。
【００７９】
この問題に対処するために、さらに集約度の高い等価な条件を使用して、ユーザが広告ｍを見るかどうかを判定する。数式（７）は、ユーザが広告ｍを見る条件が以下のようになるように書き直すことができる：
【００８０】
【数１３】
0006047161.tif 000014
広告ｍが見られていない場合に、数式（７）は、（ｉ）何故広告ｍが見られなかったのか、および（ｉｉ）順序付けされたリスト中で広告ｍより前にあるどの広告が見られたかを正確に示す。この情報は、非公開に保たれることが望ましい。この潜在的なプライバシ問題に対処するために、数式（７）の代わりに数式（８）を使用して、
【００８１】
【数１４】
0006047161.tif 000015
であることから、広告ｍが見られなかったことしか推測できないようにして、見られた広告のＩＤは推測することができないようにする。広告の視聴者の数を決定するときには、全てのユーザ装置がそれぞれの（ｐ、γ）確率値を同じ分布から選択し、したがってｐの値とγの値を入れ替えることができるので、数式（８）を使用することができる。この結論は、以下の推定手続きの説明で明らかになるであろう。数式（８）を用いることにより、広告数とともに線形に大きくなる状態空間となる。
【００８２】
各広告を見るユーザの数の推定手続きは、通常はタイムスロットｔの順序付けされた広告のリスト中の最初の広告から始めて、一度に１つの広告について実行される。広告ｍを見るユーザの数の推定に使用される要素は、２つある：すなわち、「報告分布」または「報告データ分布」ベクトルＶ（ｍ）と、「重み」ベクトルＷ（ｍ）である。
【００８３】
広告ｍの報告分布ベクトルＶ（ｍ）は、ユーザによって与えられる開示された分布値Ｄｉｊから計算される２ｍ次元ベクトルである。
【００８４】
広告ｍの重みベクトルＷ（ｍ）も、最初の期間の前に予め計算される２ｍ次元ベクトルである。重みベクトルは、（ｐ、γ）確率値に基づいてプライバシ保護機構のみによって決まり、開示された分布のＤｉｊの値または広告の順序付けには依存しない。
【００８５】
次に、広告ｍの報告分布ベクトルの例示的な計算について述べる。ｌ＝０、１、…、ｍ−１について、以下の式が定義される：
【００８６】
【数１５】
0006047161.tif 000016
ここで、集合Ｔｌ０は、最初のｍ−１個の広告において値１をｌ個有し、広告ｍについては値０を有すると報告するユーザ装置の数を表し、Ｔｌ１は、最初のｍ−１個の広告において値１をｌ個有し、広告ｍについては値１を有すると報告するユーザ装置の数を表す。変数Ｚｌ（ｍ）は、無作為に選択したユーザが集合Ｔｌ０に属する確率を表し、変数Ｏｌ（ｍ）は、無作為に選択したユーザが集合Ｔｌ１に属する確率を表す。ここで、次のように定義する：
【００８７】
【数１６】
0006047161.tif 000017
また、Ｎは、現在のタイムスロットにおけるアクティブなユーザの総数を表す。
【００８８】
広告ｍの報告分布ベクトルＶ（ｍ）は、以下のように、値Ｚｌ（ｍ）およびＯｌ（ｍ）の連接として定義される２ｍ次元ベクトルである：
【００８９】
【数１７】
0006047161.tif 000018
【００９０】
ｍの全ての値について、視聴者の数の推定量は、報告分布ベクトルＶ（ｍ）の線形和として表すことができる。この重みの２ｍ次元ベクトルは、重みベクトルＷ（ｍ）である。ここで、以下の関係がある：
【００９１】
【数１８】
0006047161.tif 000019
【００９２】
重みベクトルＷ（ｍ）の成分は、必ずしも非負ではない。報告分布ベクトルに対応しているのは、Ａｉｊの値によって決まる０と１の実際の分布を表す「実際分布」または「実際データ分布」ベクトルＹ（ｍ）である。以下の数式が定義される：
【００９３】
【数１９】
0006047161.tif 000020
ここで、集合Ｓｌ０は、最初のｍ−１個の広告において値１をｌ個有し、広告ｍについては値０を有すると報告するユーザ装置の数を表し、Ｓｌ１は、最初のｍ−１個の広告において値１をｌ個有し、広告ｍについては値１を有すると報告するユーザ装置の数を表す。変数
【００９４】
【数２０】
0006047161.tif 000021
は、無作為に選択したユーザが集合Ｓｌ０に属する確率を表し、変数
【００９５】
【数２１】
0006047161.tif 000022
は、無作為に選択したユーザが集合Ｓｌ１に属する確率を表す。ここで、次のように定義する：
【００９６】
【数２２】
0006047161.tif 000023
また、Ｎは、現在のタイムスロットにおけるアクティブなユーザの総数を表す。実際分布ベクトルＹ（ｍ）は、
【００９７】
【数２３】
0006047161.tif 000024
および
【００９８】
【数２４】
0006047161.tif 000025
の値の連接として定義される２ｍ次元ベクトルであり、以下のように表される：
【００９９】
【数２５】
0006047161.tif 000026
次に、報告データ分布ベクトルＶ（ｍ）と実際データ分布ベクトルＹ（ｍ）の間の関係を決定しなければならない。一般的なケースでは、これを行う前に、第１の広告（ａｄ１）の特定のケースのＶ（１）とＹ（１）の間の関係を考慮すると説明に役立つ。
【０１００】
第１の広告では、
【０１０１】
【数２６】
0006047161.tif 000027
および
【０１０２】
【数２７】
0006047161.tif 000028
は両方とも、２次元ベクトルである。次のことが分かる：
【０１０３】
【数２８】
0006047161.tif 000029
ここで、Ｐｒ［］は、確率を示している。次に、数式（９）内の条件付き確率を、攪乱プロセスのパラメータで表現しなければならない。全てのユーザ装置が固定の（ｐ、γ）対の攪乱機構を使用するものと仮定すると、ａ、ｂ∈｛０、１｝について、以下の数式を書くことができる：
【０１０４】
【数２９】
0006047161.tif 000030
ここで、
【０１０５】
【数３０】
0006047161.tif 000031
である。上記の関係は、（ｐ、γ）対プライバシ保護機構の定義から直接得られる。例えば、φ０１は、そのＡベクトルの何らかの成分としてゼロを有するユーザ装置が、その値ゼロを値１として報告する確率である。これは、例えば最初のコイントス（確率１−ｐ）の結果が裏で、２回目のコイントス（確率γ）の結果が表である場合に起こる。これらのコイントスは独立しているので、これらの事象が両方とも発生する確率は（１−ｐ）γである。同様にして、φａｂの他の値も導出することができる。数式（９）は、以下のように書き直すことができる：
【０１０６】
【数３１】
0006047161.tif 000032
いずれの実際のデータとも無関係であり、したがって予め計算しておくことができる行列Ｍ（１）を次のように定義すると：
【０１０７】
【数３２】
0006047161.tif 000033
数式（１３）は、以下のように書き直すことができる：
Ｍ（１）Ｙ（１）−１＝Ｖ（１）Ｔ
これは、報告データ分布Ｖ（１）と真データ分布Ｙ（１）の間の関係を生じる。この式は、Ｖ（１）Ｔ＝Ｍ（１）−ＴＹ（１）Ｔと書き直すことができる。ここで、以下のように定義する：
【０１０８】
【数３３】
0006047161.tif 000034
【０１０９】
最初の広告の視聴者の集合は、Ａ１ｊ＝１であるユーザｊの集合である。ユーザがこの性質を有する確率（または頻度解釈を用いて、この性質を有するユーザの割合）は、Ｏ０（１）である。したがって、Ｏ０（１）について解くと、Ｏ０（１）＝Ｗ（１）Ｙ（１）Ｔとなり、ここで：
【０１１０】
【数３４】
0006047161.tif 000035
が、Ｍ−１（１）の最後の行である。数式（１２）の表現を代入すると、以下のようになる：
【０１１１】
【数３５】
0006047161.tif 000036
したがって、広告１を見るユーザの推定数は、以下のように表現される：
【０１１２】
【数３６】
0006047161.tif 000037
なお、Ｎ１の推定量は、報告データ分布ベクトルＹ（１）の要素の１次結合で表現されていることに留意されたい。したがって（因子Ｎを無視すると）、Ｗ（１）は重みベクトルであり、以下の特徴を有する：すなわち（ｉ）重みベクトルＷ（１）は、プライバシ保護機構のパラメータのみに依存し、（ｉｉ）重みベクトルＷ（１）は、報告値Ｄｉｊから独立しているだけでなく、広告１のＩＤからも独立しており、（ｉｉｉ）重みベクトルＷ（１）は、プライバシ保護機構が決定されれば、予め計算しておくことができ、（ｉｖ）重みベクトルＷ（１）の計算の複雑さは、実質的に２×２行列の逆行列を求めるのと同等である。
【０１１３】
この推定プロセスは、以下のように、ランダム化による攪乱の場合に適応させることができる。複数のユーザ装置が、共通の分布関数からｐの値を選択し、（場合によってはそれとは異なる）共通の分布関数から独立してγの値を選択するので、推定プロセスに加える唯一の変更は、行列Ｍの要素の期待値を考慮することである。ｐが密度関数ρ（ｐ）から選択され、γが密度関数ω（γ）から選択される場合には、以下の数式が得られる：
【０１１４】
【数３７】
0006047161.tif 000038
ここで、以下のように定義する：
【０１１５】
【数３８】
0006047161.tif 000039
ここで、Ｅ［］は、例えば以下のようにφの値を積分することによって計算することができる期待値を表現している：
【０１１６】
【数３９】
0006047161.tif 000040
ｐとγが独立であり、関数はｐおよびγについて線形であることから、以下が分かる：
【０１１７】
【数４０】
0006047161.tif 000041
【０１１８】
ｍ＞１の行列Ｍ（ｍ）の要素は、ｐおよびγについて非線形となる。したがって、この行列の要素の期待値を得るために、解析的または数値的に積分を行わなければならない。ただし、ｐおよびγが１つの分布から選択される場合でも、行列Ｍ（１）は、プライバシ保護機構のパラメータのみに依存する（実際のデータには依存しない）ので、予め計算しておくことができる。
【０１１９】
広告ｍを見るユーザの数を推定するさらに一般的なケースも、上述の最初の広告の手続きと同じステップをたどる。行列の表現はさらに複雑になるが、以下でさらに詳細に述べるように、原理は変わらない。
【０１２０】
広告ｍを見るユーザの数Ｎｍを推定する一般的なケースでは、実際分布ベクトル
【０１２１】
【数４１】
0006047161.tif 000042
は、報告分布ベクトル
【０１２２】
【数４２】
0006047161.tif 000043
から推定される。なお、Ｖ（ｍ）およびＹ（ｍ）は、両方とも２ｍ次元ベクトルであることに留意されたい。数式（９）に類似した数式を使用し、広告ｍを見るユーザの割合を表すＯ０（ｍ）の値を推定する。したがって、０≦ｌ≦ｍ−１およびａ、ｂ＝０、１について、以下が成り立つ：
【０１２３】
【数４３】
0006047161.tif 000044
２ｍ×２ｍ行列Ｍ（ｍ）は、以下のように定義される：
【０１２４】
【数４４】
0006047161.tif 000045
また、以下の定理（２）が適用される：
定理（２）：全てのユーザ装置が（ｐ、γ）プライバシ保護機構を利用する場合には、以下が成り立つ：
【０１２５】
【数４５】
0006047161.tif 000046
ここで、φａｂは、上記の数式（１２）における記載のように定義される。
【０１２６】
最初の広告のユーザ数を決定する場合と同様に、数式（１７）は、以下のように行列形態で書き直すことができる：
Ｍ（ｍ）Ｙ（ｍ）Ｔ＝Ｖ（ｍ）Ｔ
なお、行列Ｍ（ｍ）は、データから独立しているので、予め計算しておくことができる。その後、行列Ｍ（ｍ）の逆行列Ｍ−１（ｍ）を計算することができ、以下の数式に代入することができる。
【０１２７】
Ｙ（ｍ）Ｔ＝Ｍ−１（ｍ）Ｖ（ｍ）Ｔ
広告ｍの重みベクトルを表す変数Ｗ（ｍ）は、行列Ｍ−１（ｍ）のｍ＋１番目の行であり、２ｍ次元ベクトルである。行列Ｍ（ｍ）の場合と同様に、ベクトルＷ（ｍ）は、データから独立しており、予め計算しておくことができる。このデータから、次の式が得られる：
Ｏ０（ｍ）＝Ｗ（ｍ）Ｖ（ｍ）Ｔ
また、以下の定理（３）を使用して、所与の広告ｍのユーザ数の推定値の分散を計算することができる：
定理（３）：システム内の全てのユーザ装置が（ｐ、γ）プライバシ保護機構を使用し、Ｖ（ｍ）が２ｍ次元報告分散ベクトルであり、Ｗ（ｍ）が広告ｍの２ｍ次元重みベクトルである場合には、以下が成り立つ：
【０１２８】
【数４６】
0006047161.tif 000047
次の式も成り立つ：
【０１２９】
【数４７】
0006047161.tif 000048
【０１３０】
【数４８】
0006047161.tif 000049
がＮｍに等しいことは、重みベクトルＷ（ｍ）の導出から直接得られる。報告分布ベクトルＶ（ｍ）は、確率密度関数とみなすことができ、重みベクトルＷ（ｍ）の無作為な重み付けであり、これにより上記の分散を計算するための式が得られる。
【０１３１】
図３は、本発明の一実施形態による例示的なプライバシ保護スケジューリング方式を外接する流れ図である。図示のように、ステップ３０１で、ｔ＝１でｉの全ての値についてδ（ｉ）の値を０に初期化する。次に、ステップ３０２で、スケジューラが、上記で詳細に述べたように、１≦ｍ≦ｎについて重みベクトルＷ（ｍ）を計算する。次に、ステップ３０３で、各ユーザ装置が、分かっている分布からその（ｐｊ、ｙｊ）確率対を選択する。次に、各タイムスロットｔについて、以下のステップ３０４ａ−３０４ｅを実行する。ステップ３０４ａで、各ユーザ装置ｊ∈Ｓ（ｔ）が、変更された全ての妥当性ベクトル値Ａｉｊ（ｔ）の開示分布ベクトル値Ｄｉｊ（ｔ）を、スケジューラに送信する。ステップ３０４ｂで、スケジューラが、正の予算を有する広告をｂｉ（ｉ）［１−δ（ｉ）］の降順に配列する。ステップ３０４ｃで、ユーザｊの装置が、以下の式を用いて中間変数Ｐ（ｊ）を計算する：
【０１３２】
【数４９】
0006047161.tif 000050
また、他の全てのｉについてＸＰ（ｊ）ｊ（ｔ）＝１およびＸｉｊ（ｔ）＝０を設定する。ステップ３０４ｄで、スケジューラが、上記で詳細に述べたように１≦ｍ≦ｎについて報告分布ベクトルＶ（ｍ）を計算し、広告ｍを見ているユーザの数
【０１３３】
【数５０】
0006047161.tif 000051
を
【０１３４】
【数５１】
0006047161.tif 000052
として設定し、予算制約条件Ｂ（ｉ）を
【０１３５】
【数５２】
0006047161.tif 000053
として設定する。最後に、ステップ３０４ｅで、スケジューラが、双対変数δ（ｉ）およびπ（ｊ、ｔ）を、それぞれ
【０１３６】
【数５３】
0006047161.tif 000054
およびπ（ｊ、ｔ）←ｂｔ（Ｐ（ｊ））［１−δ（Ｐ（ｊ））］を用いて更新する。
【０１３７】
代替実施形態
本発明の様々な実施形態では、ユーザ装置の位置およびサービスプロバイダの位置（通常はユーザ装置の位置から離れているが、必ずしも離れていなければならないわけではない）の両方で、適当なハードウェア、ソフトウェアまたはハードウェアとソフトウェアの組合せを提供して、上述の処理が実施されることを理解されたい。さらに、本発明の個々の実施形態は、本明細書に記載する動作モードのうちの１つに対応していることもあれば、複数に対応していることもあり、必ずしもこれらの動作モードの全てに対応していなくてもよいものと認識されたい。
【０１３８】
本明細書では、「ユーザ」が所与の家庭内で１つの「ユーザ装置」を使用する１人の人間であるという文脈で本発明の実施形態について説明しているが、同一家庭内で複数の個人がその他の個人とインターネット接続およびまたはＴＶサービスを共用している（あるいは、同様に、例えばある仕事現場で複数の作業者が同僚とインターネット接続を共用している）可能性が高い。このシナリオに対処する１つの方法は、全ての個人を１人のユーザとして扱って、インターネット検索をしている個人に関わりなく、１つの家庭で１つのユーザプロフィルを作成するようにキーワードのセットを１組のみ収集するように、また、実際にそれらの広告を見る個人に関わりなく、全ての広告をそれらのキーワードに基づいてスケジューリングするようにする。あるいは、インターネット検索キーワードとともに、どの個人が検索を行っているかを特定するために使用することができる追加の基準（例えば検索エンジンにログインするために使用されるユーザ名や、ホームネットワーク上の特定のコンピュータのＩＰアドレスなど）を受け取り、１つの家庭またはその他の物理的なネットワーク位置について複数のユーザプロフィルを作成できるようにすることもできる。例えば、ホームネットワーク上の特定のテレビジョンのセットトップボックスのＩＰアドレス（またはその他のＩＤ）、あるいは現在見ているチャンネル、テレビジョンを見ている日時、視聴中の番組の種類または内容などに基づいてどの個人が最もＴＶを見ている可能性が高いかを判定するための過去の視聴習慣の調査など、同様の基準を使用して、どの個人がＴＶを見ているかを識別することもできる。したがって、「ユーザ」および「ユーザ装置」という用語は、単独ユーザ装置（例えば携帯電話、テレビジョン、またはＰＣなど）および複数ユーザ装置（例えばテレビジョン、セットトップボックス、ＰＣ、ネットワークサーバまたは宅内ゲートウェイなど）の両方を含むものと理解されたい。また、「ユーザ装置」という用語は、「ユーザ装置」が１つの物理的装置（例えばＰＣまたはセットトップボックス）である実施形態、および「ユーザ装置」が複数の物理的装置（例えばセットトップボックスおよびテレビジョンに接続された宅内ゲートウェイ、ＰＣに接続されたネットワークサーバ、または無線ハブに接続された携帯電話など）を含む実施形態を含むものと理解されたい。さらに、本発明の実施形態では、（ｉ）ユーザが１つのユーザ装置に関連して使用される１つのプロフィルしか有していなくてもよいし、（ｉｉ）ユーザが複数のユーザ装置に関連して使用される複数のプロフィルを有していてもよいし、あるいは（ｉｉｉ）ユーザが複数のユーザ装置とともに使用される１つのプロフィルを有していてもよい。
【０１３９】
本明細書で使用する「視聴者」または「ユーザ」という用語は入れ替え可能であり、例えばウェブ閲覧セッションや検索エンジンセッションなどのインターネットセッションを行う個人、および例えばＴＶまたはＩＰＴＶを見たりＩＰラジオを聞いたりするなどしてパケット型メディアを受信する個人を含むものとして定義される。また、本明細書において単数形で用いられる「視聴者」および「ユーザ」という用語は、１つの家庭で生活している家族など個人の集まりを集合的に指している場合もあり、その場合には、本発明の実施形態による方式は、それらの個人のうちの誰がＴＶを見ているのか、またはインターネットセッションを行っているのかを判定できないこともあるので、それらの動作を行っている可能性のある全ての個人を、そのうちの誰が、または何人が実際にそれらの動作を行っているのかを考慮せずに１人の視聴者として扱って、例えばキーワードの収集および／または広告の提示を行う。
【０１４０】
本明細書で述べる広告は、放送番組、オンデマンド番組および／または録画（例えばデジタルビデオレコーダ）番組を含むＴＶシステムまたはインターネットプロトコルＴＶ（ＩＰＴＶ）システムの映像広告であるが、本発明は、その他のメディアで広告を提示するのにも有用である可能性があり、例えば、ＩＰラジオシステムにおける音声広告、オンデマンドビデオシステムにおける映像広告、インターネット配信またはウェブ配信ビデオシステムにおける映像広告、あるいは携帯電話を用いたオンデマンドメディアシステムおよび／またはストリーミングメディアシステムにおける音声広告または映像広告などにも有用である可能性がある。「番組」という用語は、前述したものを全て含むものとして広範に解釈されたい。したがって、本明細書で用いる「メディア」という用語は、音声のみのコンテンツも、映像のみのコンテンツも、音声および映像の両方を含むコンテンツも含むものと理解されたい。
【０１４１】
本明細書では、広告が、セットトップボックス、宅内ゲートウェイ、ネットワークサーバまたは携帯電話などのユーザ装置に「予めロードされている」ものとして述べる本発明の実施形態を記載した。本発明は、広告自体は異なる装置（例えば安全な遠隔サーバなど）に予めロードしておいて、ユーザ装置には広告のリストのみを予めロードしておくようにする実施形態も含むことを理解されたい。このシナリオでは、広告は、あるタイムスロット中に、要求に応じてＴＶやセットトップボックス、携帯電話などのユーザ装置にダウンロードまたはストリーミングして、視聴者に示すことができる。
【０１４２】
本明細書で、あるタイムスロット中の広告に関する入札を行うための、広告の入札で得られるキーワードと視聴者のインターネットセッションで得られるキーワードとの比較に関連して使用する「一致」という言葉は、キーワードの１文字１文字が厳密に一致している場合だけでなく、曖昧な論理で一致している場合、すなわち１文字１文字は一致していなくても単語または語句の最確一致に基づいて一致しているとされる場合も指すものとして広範に理解されたい。また、本発明の文脈では、突合せは、厳密でないキーワードの突合せ、および例えば同義語に基づくキーワード突合せ、関連語に基づくキーワード突合せまたは概念に基づくキーワード突合せを用いるなど、任意のその他の基準およびアルゴリズムに基づく突合せを含むものとして解釈されたい。
【０１４３】
本明細書で使用する「無作為」という用語は、純粋な無作為選択または純粋に無作為な数生成に限定されるものとして解釈すべきではなく、シードに基づく選択や数生成を含む疑似ランダム、および純粋に無作為ではないが偶発性をシミュレートすることができるその他の選択または数生成方法を含むものとして理解されたい。したがって、本発明の実施形態で使用した攪乱ベクトルを生成するために使用される関数は、乱数に基づいていても、非乱数に基づいていても、あるいは乱数と非乱数を組み合わせたものに基づいていてもよい。さらに、攪乱ベクトルは、本明細書で述べたように１つまたは複数の乱数を用いて生成してもよいし、本明細書では具体的に述べていないその他のアルゴリズムと関連して１つまたは複数の乱数を用いて生成してもよい。
【０１４４】
本明細書に記載する本発明の実施形態は、所与の広告について、その広告が示されたタイムスロットの後で視聴者の数を推定するものとして述べているが、本発明のいくつかの実施形態では、この推定を、広告が示されているタイムスロット中に行うこともできるし、あるいは推定を行うのに利用する攪乱ベクトルを生成できるだけの十分なデータが存在していれば、広告が実際に示されるタイムスロットより前に行うこともできることを理解されたい。
【０１４５】
当業者なら、本発明の範囲を逸脱することなく、本発明の性質を説明するために記載および図示した各部の詳細、材料および構成に様々な変更を加えることができることを理解されたい。例えば、本発明の実施形態の発明性のある概念は、上述したような家計資産をマッピングするシステムだけでなく、企業資産およびその他の財務データのマッピングを行うその他のシステムにも適用することができることを理解されたい。
【０１４６】
本発明は、方法としての形態、およびそれらの方法を実施する装置としての形態で実施することができる。また、本発明は、磁気記録媒体、光記録媒体、固体状態メモリ、フロッピー（登録商標）ディスケット、ＣＤ−ＲＯＭ、ハードドライブまたはその他の任意の非一時的な機械可読記憶媒体などの有形メディアに実装されるプログラムコードとしての形態で実施することもでき、その場合には、プログラムコードがコンピュータなどの機械にロードされて実行されたときに、その機械が本発明の実施形態を実施する装置となる。また、本発明は、例えば機械にロードされ、かつ／または実行されるなど、非一時的な機械可読記憶媒体に記憶されるプログラムコードとしての形態で実施することもでき、その場合には、プログラムコードがコンピュータなどの機械にロードされて実行されたときに、その機械が本発明の実施形態を実施する装置となる。汎用プロセッサ上に実装されたときには、プログラムコードの各セグメントがプロセッサと結合して、特定の論理回路と似た動作をする固有の装置となる。
【０１４７】
当業者なら、本明細書に記載した本発明のシステムの例示的な実施形態の機能構成要素は、従来のネットワークハードウェアおよびネットワークソフトウェア（例えばＬＡＮ／ＷＡＮネットワークバックボーンシステムおよび／またはインターネットなど）によってネットワーク化された、１つまたは複数の従来の汎用コンピュータ（例えばＩＢＭ互換機、Ａｐｐｌｅ社のＭａｃｉｎｔｏｓｈおよび／またはＲＩＳＣマイクロプロセッサコンピュータなど）、メインフレーム、ミニコンピュータ、従来の電気通信（例えばモデム通信、Ｔ１通信、光ファイバ回線通信、ＤＳＬ通信、衛星通信および／またはＩＳＤＮ通信など）、メモリ記憶手段（例えばＲＡＭ、ＲＯＭなど）、ならびに記憶装置（例えばコンピュータ可読メモリ、ディスクアレイ、直接アクセス記憶装置など）上の、１つまたは複数の分散したコンピュータプログラムプロセス、データ構造、辞書および／あるいはその他の記憶データとして実施することができるが、その他のタイプのコンピュータおよびネットワーク資源も、本発明を逸脱することなく使用することができることを理解するであろう。本明細書で述べる１つまたは複数のネットワークは、ローカルエリアネットワーク、広域ネットワーク、インターネット、イントラネット、エキストラネット、固有ネットワーク、仮想私設ネットワーク、ＴＣＰ／ＩＰネットワーク、無線ネットワーク（例えばＩＥＥＥ８０２．１１またはＢｌｕｅｔｏｏｔｈ（登録商標）など）、電子メールの送信側と受信側の電子メールによるネットワーク、モデムによる、セルラまたは携帯電話網、電話によってユーザがアクセスできる対話型電話網、あるいはこれらのうちの１つまた複数の組合せとすることができる。
【０１４８】
本明細書に記載する本発明の実施形態は、ネットワークトランザクションサーバシステムに常駐する１つまたは複数のコンピュータに実装することができ、本発明の実施形態への入出力のアクセスは、実時間トランザクションおよび／またはバッチ型トランザクションで人間のユーザがデータを送受信できるようにする、または本発明の実施形態の様々な動作の無人実行を許可できるようにする適当なハードウェアおよびソフトウェア（例えばインターネット広域ネットワーク通信のハードウェアおよびソフトウェア（例えばＣＱＩベース、ＦＴＰ、Ｎｅｔｓｃａｐｅ  ＮａｖｉｇａｔｏｒＴＭ、Ｍｏｚｉｌｌａ  ＦｉｒｅＦｏｘＴＭ、Ｍｉｃｒｏｓｏｆｔ  Ｉｎｔｅｒｎｅｔ  ＥｘｐｌｏｒｅｒＴＭ、Ｇｏｏｇｌｅ  ＣｈｒｏｍｅＴＭ、またはＡｐｐｌｅ  ＳａｆａｒｉＴＭのＨＴＭＬインターネットブラウザソフトウェア、および／あるいはＴＣＰ／ＩＰソケットに実時間でアクセスする直接実時間または準実時間ＴＣＰ／ＩＰインタフェース）を備えるパーソナルコンピュータおよび／またはメインフレームコンピュータなど）を含むことができる。同様に、本発明のシステムは、従来のブラウザソフトウェア（例えばＮｅｔｓｃａｐｅ  ＮａｖｉｇａｔｏｒＴＭ、Ｍｏｚｉｌｌａ  ＦｉｒｅｆｏｘＴＭ、Ｍｉｃｒｏｓｏｆｔ  Ｉｎｔｅｒｎｅｔ  ＥｘｐｌｏｒｅｒＴＭ、Ｇｏｏｇｌｅ  ＣｈｒｏｍｅＴＭ、またはＡｐｐｌｅ  ＳａｆａｒｉＴＭ）を用いて従来の通信チャネル（例えば従来の電気通信、ブロードバンド通信、無線通信など）を介してアクセス可能な１つまた複数の遠隔のインターネットサーバを含むことができる。したがって、本発明は、このような通信機能およびインターネット閲覧能力を有するように適宜構成することができる。さらに、当業者なら、本発明のサーバシステムの様々な構成要素は互いに離れていてもよく、また本明細書に記載する機能を実現するために適当な通信ハードウェア／ソフトウェアならびに／あるいはＬＡＮ／ＷＡＮハードウェアおよび／またはソフトウェアをさらに含むことができることを理解するであろう。
【０１４９】
本発明の各機能構成要素は、従来のネットワーク化ハードウェアおよびソフトウェアによってネットワーク化された１つまたは複数の従来の汎用コンピュータ上で実行される１つまたは複数の分散したコンピュータプログラムプロセスとして実装することができる。これらの各機能構成要素は、分散したコンピュータプログラムプロセス（例えばＩＢＭ  ＤＢ２ＴＭ、Ｍｉｃｒｏｓｏｆｔ  ＳＱＬ  ＳｅｒｖｅｒＴＭ、Ｓｙｂａｓｅ  ＳＱＬ  ＳｅｒｖｅｒＴＭまたはＯｒａｃｌｅ  １０ｇＴＭのデータベースマネージャおよび／あるいはこれらのデータベースにリンクするＪＤＢＣインタフェースなどの「フルスケール」リレーショナルデータベースエンジンを用いて生成されるものなど）を、適当な大容量記憶装置、ネットワーキング、ならびにこれらの機能構成要素が記載の機能を実現できるようにするその他のハードウェアおよびソフトウェアを含むネットワーク化されたコンピュータシステム（例えばメインフレーム、および／あるいはＩＢＭ  ＳＢ２ＴＭまたはＨＰ  ９０００ＴＭのコンピュータシステムなどの対称または超並列計算システムなどを含む）上で実行することによって実装することもできる。これらのコンピュータシステムは、地理的に分散させ、適当な広域ネットワークおよびローカルエリアネットワークのハードウェアおよびソフトウェアを介して互いに接続することができる。一実施形態では、データベースに記憶されるデータまたはその他のプログラムデータは、解析および報告を目的として、標準的なＳＱＬ問合せを介してユーザがアクセスできるようにすることができる。
【０１５０】
本発明の実施形態の主要な要素は、サーバベースにすることができ、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）  ＮＴ／２０００ＴＭまたはＵＮＩＸ（登録商標）などのオペレーティングシステムをサポートするハードウェアに常駐することができる。
【０１５１】
本発明の実施形態によるシステムの構成要素は、移動装置および非移動装置を含むことができる。本発明で利用することができる移動装置としては、例えば米国カリフォルニア州ＣｕｐｅｒｔｉｎｏのＡｐｐｌｅ  Ｃｏｍｐｕｔｅｒ社製のものや米国カリフォルニア州Ｓａｎｔａ  ＣｌａｒａのＰａｌｍ社製のものなどの携帯情報端末（ＰＤＡ）型のコンピュータ、およびＡｎｄｒｏｉｄ、Ｓｙｍｂｉａｎ、ＲＩＭ  Ｂｌａｃｋｂｅｒｒｙ、Ｐａｌｍ  ｗｅｂＯＳ、またはｉＰｈｏｎｅオペレーティングシステムを実行するその他のコンピュータ、Ｗｉｎｄｏｗｓ  ＣＥＴＭ手持ち型コンピュータまたはその他の手持ち型コンピュータ（場合によっては無線モデムを含む）、ならびに無線電話、セルラ電話または携帯電話（ＧＳＭ（登録商標）電話、Ｊ２ＭＥおよびＷＡＰ方式電話、インターネット電話およびデータ処理スマートフォンなど）、１方向および２方向のページングおよびメッセージング装置、ラップトップコンピュータなどが挙げられる。本発明の実施形態によるシステムで潜在的なサービスチャネルとして使用することができるその他の電話網技術としては、ＧＰＲＳおよびＥＤＧＥなどの２．５Ｇセルラネットワーク技術、ならびにＣＤＭＡ１ｘＲＴＴやＷＣＤＭＡ（登録商標）２０００などの３Ｇ技術および４Ｇ技術が挙げられる。本発明の実施形態では携帯装置を使用することができるが、本発明の実施形態では、パーソナルコンピュータ、インターネット機器、セットトップボックス、陸線電話など、非携帯通信装置も企図されている。クライアントは、Ａｐｐｌｅ  Ｍａｃｉｎｔｏｓｈ  ＴＭ、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ  ９５／９８／ＮＴ／ＭＥ／ＣＥ／２０００／ＸＰ／Ｖｉｓｔａ／７ＴＭ、ＵＮＩＸ  ＭｏｔｉｆのワークステーションプラットフォームをサポートするＰＣ、またはＴＣＰ／ＩＰまたはその他のネットワーク型対話を行うことができるその他のコンピュータも含むことができる。一実施形態では、クライアントプラットフォーム上で、ウェブブラウザ以外のソフトウェアが不要であることもある。
【０１５２】
あるいは、前述の機能構成要素は、従来のネットワーク化ハードウェアおよびソフトウェアを介してネットワーク化された、それらのその他の従来のハードウェアおよびソフトウェアをさらに含むＩＢＭタイプ、Ｉｎｔｅｌ  Ｐｅｎｔｉｕｍ（登録商標）ＴＭまたはＲＩＳＣのマイクロプロセッサ型パーソナルコンピュータ上で実行される、複数の別個のコンピュータプロセス（例えばｄＢａｓｅＴＭ、ＸｂａｓｅＴＭ、ＭＳ  ＡｃｃｅｓｓＴＭあるいはその他の「フラットファイル」型のデータベース管理システムまたは製品を介して生成されるものなど）によって実装することもできる。これは、それらの機能構成要素が記載の機能を実現できるようにするために必要になることがある。この代替構成では、これらのパーソナルコンピュータは、通常は上述のタイプのフルスケールリレーショナルデータベースエンジンを実行することができない可能性があるので、ノンリレーショナルのフラットファイル「テーブル」（図示せず）を、ネットワーク化されたパーソナルコンピュータの少なくとも１つに含めて、本発明によるシステムによって記憶されるデータの少なくとも一部分を表すことができる。これらのパーソナルコンピュータは、Ｕｎｉｘ（登録商標）、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ  ＮＴ／２０００ＴＭまたはＷｉｎｄｏｗｓ  ９５／９８／ＮＴ／ＭＥ／ＣＥ／２０００／ＸＰ／Ｖｉｓｔａ／７ＴＭのオペレーティングシステムを実行することができる。また、本発明によるシステムの前述の機能構成要素は、上記の２つの構成を組み合わせて含むこともできる（例えば適当な広域ネットワークおよびローカルエリアネットワークのハードウェアおよびソフトウェアを介してネットワーク化されたパーソナルコンピュータ、ＲＩＳＣシステム、メインフレーム、対称または並列コンピュータシステム、ならびに／またはその他の適当なハードウェアおよびソフトウェアの組み合わせの上で実行されるコンピュータプログラムプロセスによる）。
【０１５３】
本発明によるシステムは、その他のデータタイプ、処理システム（例えばトランザクション、財務、管理、統計、データの抽出および監査、データ伝送／受信、ならびに／または会計サポート／サービスシステムなど）、ならびに／または記憶の方法体系を本発明の方法体系と併用して、追加の機能を（例えば家庭の光ファイバネットワークのサービスプロバイダによって動作する多機能電話、インターネットおよびテレビジョンシステムの一部として）実現する、マルチデータベースあるいはマルチコンピュータシステムまたは「ウェアハウス」など、さらに大きなシステムの一部であってもよい。
【０１５４】
一実施形態では、ソースコードは、リレーショナルデータベースを用いて、オブジェクト指向プログラミング言語で書くことができる。このような実施形態は、Ｃ＋＋などのプログラミング言語およびＭｉｃｒｏｓｏｆｔ社の．ＮｅｔＴＭフレームワークなどのツールセットを使用することを含むことがある。本発明によるシステムを構築する際に使用することができるその他のプログラミング言語としては、Ｊａｖａ（登録商標）、ＨＴＭＬ、Ｐｅｒｌ、ＵＮＩＸシェルスクリプト、アセンブリ言語、Ｆｏｒｔｒａｎ、Ｐａｓｃａｌ、Ｖｉｓｕａｌ  ＢａｓｉｃおよびＱｕｉｃｋＢａｓｉｃなどが挙げられる。当業者なら、本発明が、ハードウェア、ソフトウェアまたはハードウェアとソフトウェアの組合せとして実施することができることを理解するであろう。
【０１５５】
したがって、本明細書で使用する「コンピュータ」または「システム」という用語は、プロセッサを制御するための適当な命令を有するプロセッサを有する少なくとも１つの機械を含む、ハードウェア構成要素とソフトウェア構成要素の組合せを意味するものとして理解されたい。単数形の「コンピュータ」または「システム」という用語は、例えばネットワーク中の複数のパーソナルコンピュータ、ルータ、ハブ、パケット検査機器またはファイヤウォールなどの１つまたは複数のその他の装置と関連する１つまたは複数のパーソナルコンピュータなど、互いに協調して動作する複数のハードウェア装置、セットトップボックスおよびテレビジョンに接続された宅内ゲートウェイ、ＰＣに接続されたネットワークサーバ、および無線ハブに接続された携帯電話なども指しているものとして理解されたい。
【０１５６】
また、これらの機能構成要素は、本発明を逸脱することなく、別法として特注の専用電子ハードウェアおよび／またはソフトウェアから構成することもできることは、最初に理解されたい。したがって、本発明は、本発明の趣旨および広範な範囲に含まれることができる、このような代替形態、修正形態および均等形態の全てをカバーするように意図されている。
【０１５７】
本明細書で「一実施形態」または「実施形態」に言及している場合、それは、その実施形態に関連して述べる特定の特性、構造または特徴が、本発明の少なくとも１つの実施形態に含まれる可能性があるという意味である。本明細書の様々な箇所に見られる「一実施形態において」という表現は、必ずしもその全てが同じ実施形態のことを指しているわけではなく、また必然的に互いにその他の実施形態を除外する別個または代替の実施形態でもない。
【０１５８】
本明細書に記載する例示的な方法のステップは、必ずしも記載した順序で実行しなければならないものではなく、これらの方法のステップの順序は、単なる例示に過ぎないものと理解されたい。同様に、これらの方法に追加のステップが含まれていてもよく、また本発明の様々な実施形態による方法において、特定のステップを削除または結合することもできる。
【０１５９】
以下の方法クレームの要素は、対応するラベルを付けた特定の順序で記載されているが、クレームの記述がそれ以外の形でそれらの要素の一部または全てを実施する特定の順序を暗に示していない限り、それらの要素は、必ずしもその特定の順序での実施に限定されないものとする。
【０１６０】
さらに、当業者なら、以下の特許請求の範囲に示す本発明の範囲を逸脱することなく、本発明の性質を説明するために記載および図示した各部の詳細、材料および構成に様々な変更を加えることができることも理解されたい。
【０１６１】
本願の特許請求の範囲によってカバーされる実施形態は、（１）本明細書によって可能になる、（２）法定主題に対応する、実施形態に限定される。可能にならない実施形態および非法定主題に対応する実施形態は、それらが特許請求の範囲に含まれる場合であっても、明示的に権利が放棄される。
【図１】
0006047161.tif 000055
【図２】
0006047161.tif 000056
【図３】
0006047161.tif 000057