(57)【要約】  実験に関する一定の予算及び一群の潜在的な対象者の下で、データ市場実験を計画する装置及び方法が説明される。実験者は、例えば対象の人に関する検査であるオンライン調査や、データを収集する他の何らかの種類の実験を行い、実験対象者のうちの参加者を、金銭的な対価により駆り立てることが可能である。実験者は、対象者に関する一般的に知られる何らかの情報だけでなく、実験に参加するために各々の潜在的な対象者が求める金銭をも監視する。この情報に基づいて、本方法は、何れのユーザが実験に参加して何れのユーザにどの程度の額を支払うかを判断する。本方法は、彼らのデータについて正直な値を報告するようにユーザを駆り立てるように、メカニズムデザイン問題を学習することにより、実験計画を戦略的状況とみなす。本方法は、予算内での利用可能性、演算の取り扱いやすさ、ほぼ最適であること等の特徴を有し、及び、対象者は偽りの要求対価を申請するインセンティブを有しない正直性の特徴を有する。
2016509307.tif 000002
【特許請求の範囲】
【請求項１】
実験のために集合から対象者を選択する方法であって、
少なくとも1人の対象者の特徴ベクトルにアクセスするステップであって、前記特徴ベクトルは前記実験に参加するための前記少なくとも1人の対象者のコストを含む、ステップと、
前記実験に使用するコストを記述する予算を受信するステップと、
前記実験に対する対象者集合のメンバ各々について値を算出し、前記集合のうち最高値のメンバを判定し、当該メンバを前記実験に加えるステップと、
前記集合のうち前記最高値のメンバ以外の前記集合中の対象者について凸最適化を実行して閾値を判定するステップと、
前記閾値と算出された値とを比較し、当該算出された値が前記閾値を超えるか否かを判断するステップと、
超える場合には、前記少なくとも1人の対象者に予算全額で対価を割り当てるステップと、
当該算出された値が前記閾値を超えない場合には、前記予算が尽きるまで、前記実験の値に対する各自のマージン寄与度の昇順に、前記実験に加えられる対象者に、前記予算の一部分を比例して割り当てるステップと、
を有する方法。
【請求項２】
前記特徴ベクトルは年齢及び性別を含む、請求項1に記載の方法。
【請求項３】
前記の値はD最適化基準である、請求項1に記載の方法。
【請求項４】
後者の割り当てるステップが、前記実験に対して1度に1人の対象者を反復的に追加することを含む、請求項1に記載の方法。
【請求項５】
各々の反復で追加される前記対象者は、実験に参加するためのコストに対する値の最大比率を有する者である、請求項4に記載の方法。
【請求項６】
実験のために集合から対象者を選択する1つ以上のプロセッサを有する装置であって、前記1つ以上のプロセッサは、協同して、
少なくとも1人の対象者の特徴ベクトルにアクセスするステップであって、前記特徴ベクトルは前記実験に参加するための前記少なくとも1人の対象者のコストを含む、ステップと、
前記実験に使用するコストを記述する予算を受信するステップと、
前記実験に対する対象者集合のメンバ各々について値を算出し、前記集合のうち最高値のメンバを判定し、当該メンバを前記実験に加えるステップと、
前記集合のうち前記最高値のメンバ以外の前記集合中の対象者について凸最適化を実行して閾値を判定するステップと、
前記閾値と算出された値とを比較し、当該算出された値が前記閾値を超えるか否かを判断するステップと、
超える場合には、前記少なくとも1人の対象者に予算全額で対価を割り当てるステップと、
当該算出された値が前記閾値を超えない場合には、前記予算が尽きるまで、前記実験の値に対する各自のマージン寄与度の昇順に、前記実験に加えられる対象者に、前記予算の一部分を比例して割り当てるステップと、
を実行するように構成される、装置。
【請求項７】
前記特徴ベクトルは年齢及び性別を含む、請求項6に記載の装置。
【請求項８】
前記の値はD最適化基準である、請求項6に記載の装置。
【請求項９】
後者の割り当てるステップが、実験に対して1度に1人の対象者を反復的に追加することを含む、請求項6に記載の装置。
【請求項１０】
各々の反復で追加される前記対象者は、前記実験に参加するためのコストに対する値の最大比率を有する者である、請求項9に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本原理はデータ市場実験(data  market  experiment)を計画する装置及び方法に関連する。
【背景技術】
【０００２】
実験計画の分野では、実験者はn個の潜在的な実験対象の母集団にアクセスする。各々の対象又は対象者(subject)は、例えば、性別、年齢、体重、職業などのような実験者に既知の一群の属性に関連付けられる。実験者は対象者の或る固有の特性を測定する実験を実行することを希望し、対象者に固有の特性は、例えば、広告をクリックする可能性、病気にかかる可能性又は高血圧の可能性などである。実験が実行される前に、対象者に関する結果は実験者にとって未知であるが、しばしば実験者はユーザ属性と結果との間の関係についての仮説(又は仮定又は前提)を有し、実験者は実験を通じてその仮説を検証することを望む。実験を行って測定値を取得することは、実験者がその仮説の有効性を判断することを可能にする。
【０００３】
上記の実験計画のシナリオは、例えば、医学的検査、マーケティングリサーチ(又は市場調査)、オンライン調査などを含む多くの用途を有する。本説明では、実験は(意図的に)操作することはできず、従って信頼できるものと考えられることが仮定される。しかしながら、各々の対象者について実験を行うことに関連するコストが存在し、コストは対象者毎に異なる。これは、検査される場合に対象者が支払うコスト及び対象者が払い戻しを受ける必要があるコストと考えられてもよいし；或いは、実験に参加する対象者のインセンティブ(又は奨励金)と考えられてもよいし；或いはデータについて本来備わっている値(inherent  value)と考えられてもよい。
【発明の概要】
【０００４】
多数の既存の推定手順が存在するだけでなく、得られた推定の質を定量化する方法論も存在する。実験者が限られた数の実験しか実行できず、実験プロセスが前提の母集団の真のパラメータの近似を返す場合に、対象者を選択する仕方について広範囲に及ぶ理論が存在する。戦略的な状況で実験計画を考察し、メカニズムデザイン問題(mechanism  design  issues)を学習することにより、例えば、ユーザのデータに対する真の値を報告するようにユーザに駆り立てることにより、本願で説明される原理はその古典的な仕組みから離脱する。
【０００５】
実験はしばしば厳しい予算(又はバジェット)とともになされるが、しばしば対象者は戦略的(strategic)であり、これは、彼らの金銭的利益を多くするために彼らの求める補償(又は対価)を偽って報告するインセンティブを彼らが有するかもしれないことを意味する。戦略的な観点からのこの問題についての原理的研究は十分には判明していない。
【０００６】
バジェットフィージブルメカニズムデザイン(Budget  feasible  mechanism  design)は元々は最初の従来アプローチとして提案されている。このアプローチは、バリュークエリモデルにおける予算制約の下で、すなわち、任意の所与の集合を対象とするサブモジュラーの値をオラクル(oracle)が提供することを仮定して、任意のサブモジュラー関数を最大化する問題を考察する。第1の従来アプローチは、サブモジュラ最大化に対する普遍的に真であるランダムな112近似メカニズム(112-approximation)が存在することを示す(すなわち、真のメカニズムにわたる分布からランダムにサンプリングされるメカニズムである)。第2の従来アプローチは、7.91近似メカニズムを提供することにより上記の結果を改善し、サブモジュラ最大化に対する普遍的に真のメカニズムの中で2である対応する下位境界を示す。上記の結果とは異なり、モジュラ最大化に関し、多項式時間で動作する真でない一定の近似メカニズムが現時点で知られている。本原理は、一群の対象者と実験に対する対価とを決定する一方、潜在的な対象者が彼らの求める対価を正しく報告することを動機付ける問題に対処する。
【課題を解決するための手段】
【０００７】
従来技術に関するこれら及び他の欠点ないし不利益は、データマーケットを計画する方法及び装置に関連する本原理により対処される。本原理は或る方法を提供し、当該方法では、実験に対する各自の値及び各自のコストに基づいて、対象者が実験に追加されるように、ある予算を有する実権計画者が、各自コストを有する対象者とともに実験を計画することが可能である。
【０００８】
本原理の一形態により提供される方法は、少なくとも1人の対象者の特徴ベクトルにアクセスするステップであって、前記特徴ベクトルは前記実験に参加するための前記少なくとも1人の対象者のコストを含む、ステップと、前記実験に使用するコストを記述するバジェットを受信するステップと、前記実験に対する対象者集合のメンバ各々の値を算出し、前記集合のうち最高値のメンバを判定し、当該メンバを前記実験に加えるステップと、前記集合のうち前記最高値のメンバ以外の前記集合中の対象者について凸最適化を実行して閾値を判定するステップと、前記閾値と算出された値とを比較し、当該算出された値が前記閾値を超えるか否かを判断するステップと、超える場合には、前記少なくとも1人の対象者に予算全額の対価を割り当てるステップと、当該算出された値が前記閾値を超えない場合には、前記予算が尽きるまで、前記実験の値に対する各自のマージン寄与度の昇順に、前記実験に加えられる対象者に、前記予算の一部分を比例して割り当てるステップとを有する方法である。
【０００９】
本原理の別の形態により提供される装置は、実験のために集合から対象者を選択する1つ以上のプロセッサを有する装置であって、前記1つ以上のプロセッサは、協同して、少なくとも1人の対象者の特徴ベクトルにアクセスするステップであって、前記特徴ベクトルは前記実験に参加するための前記少なくとも1人の対象者のコストを含む、ステップと、前記実験に使用するコストを記述するバジェットを受信するステップと、前記実験に対する対象者集合のメンバ各々の値を算出し、前記集合のうち最高値のメンバを判定し、当該メンバを前記実験に加えるステップと、前記集合のうち前記最高値のメンバ以外の前記集合中の対象者について凸最適化を実行して閾値を判定するステップと、前記閾値と算出された値とを比較し、当該算出された値が前記閾値を超えるか否かを判断するステップと、超える場合には、前記少なくとも1人の対象者に予算全額の対価を割り当てるステップと、当該算出された値が前記閾値を超えない場合には、前記予算が尽きるまで、前記実験の値に対する各自のマージン寄与度の昇順に、前記実験に加えられる対象者に、前記予算の一部分を比例して割り当てるステップとを実行するように構成される、装置である。
【００１０】
本原理のこれら及び他の形態、特徴並びに利点は、添付図面に関連して理解されるべき実施例に関する以下の詳細な説明から明らかになるであろう。
【図面の簡単な説明】
【００１１】
【図１】本原理を利用するデータマーケットを計画する方法の一形態を示す図。
【図２】本原理を利用するデータマーケットを計画する装置の一形態を示す図。
【発明を実施するための形態】
【００１２】
本願で説明される原理はデータ市場実験を計画する装置及び方法に関連する。一実施形態では、実験計画問題(Experimental  Design  Problem：EDP)のための多項式時間真性メカニズム(polynomial  time  truthful  mechanism)が提供される。
【００１３】
本発明は或る方法を提案し、その方法により、実験者は、例えば対象者の人に関する検査であるオンライン調査や、データを収集する他の何らかの種類の実験を行い、本方法は、実験対象者のうちの参加者を、金銭的な対価により駆り立てることが可能である。本発明は対象者に関する一般的に知られる情報(例えば、彼らの年齢、性別など)を監視するだけでなく、実験に参加するために各々の潜在的な対象者が求める金銭をも監視する。この情報に基づいて、本発明は、何れのユーザが実験に参加して何れのユーザにどの程度の額を支払うかを判断する。以下の説明において、本原理は、実験に含められる対象者が金銭の支払いを受けるという実験の文脈で説明されるが、本願で説明される原理は本原理の範囲内で他のデータマーケットにも適用可能であることを、当業者は理解するであろう。
【００１４】
開示される実施形態は、関連するユーザが或るコストを担う実験を実行できるようにする。説明される一実施形態において、実験者はユーザの集合(一群のユーザ又はユーザ群)とやり取りを行い、実験者はそのユーザのデータを取得及び処理することを望んでいる。ユーザは、一群の、実験者により閲覧可能な公の公開属性と、実験が完了した後にしか明らかにされない秘匿属性とを有する。例えば、公開属性は年齢や性別などのような人口統計データとすることが可能である。実験は、オンライン調査、映画に対する格付け(評価又はランキング)、血液サンプリング、医療検査又はそのような任意の実験の結果とすることが可能であり、隠れ変数又は秘匿変数(hidden  variable)は、フォームに記入された入力、サンプリングで測定された値あるいはその他の同様な結果であってもよい。
【００１５】
実験者の目的は、線形回帰(linear  regression)として知られる統計的処理を実行し、実験測定値(例えば、映画の格付け、血圧)とパブリック変数(年齢、性別など)とを関連付ける数学的関係を学習することである。これは、例えば、病気を治療すること等のような、他の一群の人々に対する隠れ変数を予測することに有用である。しかしながら、実験の対象者は、金銭的な対価の形式により彼らが参加するように駆り立てられない限り、実験に進んで参加しようとはしない。実験者はバジェット(又は予算)を有し、その使い方、すなわち実験を行うためにどの対象者に支払うかを決めるようとする。
【００１６】
本原理の一実施形態は或る方法であり、その方法は、
(a)  実験者の予算
(b)  対象者の公の属性(彼らの望む対価(compensation))
という入力を受け、
(a)  実験が行われる一群の対象者
(b)  実験者がその実験に参加する各々の対象者に支払う金額(これは対象者が望む対価より多い必要がある)
を出力する。
【００１７】
開示される方法は以下の特性を有する
(a)  予算的に実現可能である：実験に参加する対象者に支払われる額は、実験に充てられる予算の範囲内である。
【００１８】
(b)  演算が扱いやすい：包含される全ての処理は多項式時間(polynomial  time)で計算されることが可能である。
【００１９】
(c)  ほぼ最適である：実験者がデータについて線形回帰を行った後に、結果が、利用可能な所与の予算に近付くように、一群の対象者を選択する。
【００２０】
(d)  真実みがある：対象者は、システムを「ゲーム化」して彼らが真に要求するものとは異なる対価を申告するインセンティブを有しない。これは、彼らが高い対価を申告し、より多額の合計額を彼らに支払うことを実験者に強制しようとすることを防止する。
【００２１】
本願で説明される方法は、D最適化基準(D-optimality  criterion)のように文献で言及される値を、可能性のある一群の対象者の各々に割り当てることによって処理を進める。この値は、線形回帰処理が、その一群の対象者に適用される場合にどの程度正確であるかをとらえる。一群の対象者を選択するアルゴリズムは後にアルゴリズム1で説明される。このプロセスは、先ず、データセットの中で実験者に対して最高値を有するユーザを選択する。そして、残りの対象者について凸最適化(convex  optimization)と呼ばれる数学的処理を実行し、(アルゴリズム1においてギリシア文字ξ(xi)により示される)閾値を算出する。最も高いユーザ(the  most  valuable  user)の値がこの閾値を超える場合、本方法はこの対象者に予算の全部を支払う。そうでない場合、アルゴリズムは、1度に1人の対象者を追加することにより、貪欲法により(greedily)補償する一群の対象者を構成し：毎回追加される対象者は、(D最適化基準に基づいて)今までに選択された一群の対象者に貢献した程度とその対象者の望む対価との間で最高の比率を有する者である。最終的に、「閾値支払法(threshold  payments)」のように当業者に知られる既知のルールに従って対象者に支払がなされ：対象者は、希望する対価として設定可能な最高額の支払いを受け、更に貪欲アルゴリズムにより選択される。
【００２２】
実験計画の従来の状況では、実験者はn個の潜在的な実験対象者の母集団にアクセスする。各々の対象者は、実験者に既知の一群のパラメータ(又は属性)(例えば、性別、年齢、体重、職業など)に関連付けられる。実験者は、(例えば、広告をクリックする可能性、病気にかかる可能性、高血圧を有する可能性などのような)対象者の或る固有の特性を測定する実験を行うことを望むが、対象者についての結果は、事件が実行される前では、実験者にとって未知である。典型的には、実験者は、ユーザの属性と成果との間の関連性(例えば、高血圧は体重に関連すること)についての或る仮説を有し、実験者は実験を通じてその仮説を検証することを望んでいる。実験を行って測定値を得ることにより、その仮説の有効性は実験者により判断される。
【００２３】
上記の実験計画のシナリオは、例えば、医学的検査、マーケティングリサーチ、オンライン調査などを含む多くの用途を有する。本願で説明される状況では、実験は(意図的に)操作することはできず、従って信頼できるものと考えられる。しかしながら、各々の対象者について実験を行うことに関連するコストが存在し、コストは対象者毎に異なる。これは、検査される場合に対象者が支払うコスト及び対象者が払い戻しを受ける必要があるコストと考えられてもよいし；或いは、実験に参加する対象者のインセンティブと考えられてもよいし；或いはデータについて本来備わっている値と考えられてもよい。
【００２４】
経済的側面は実験計画に常に付いて回るものであり：実験者はしばしば厳しい予算の中で実施し、創造的な(又は工夫して編み出された)インセンティブを計画する。しかしながら、戦略的観点からのこの状況に対する原理的な研究は十分に判明していない。対象者が戦略的である場合、彼らは各自のコスト及び実験の選択を偽って報告するインセンティブを有するかもしれないし、支払は更に高度化される必要がある。
【００２５】
所与の予算の下で委ねられる実験計画についての問題は、自身のコストを欺く「戦略的エージェント」(ずる賢い対象者)が存在する点にある。特に、本原理は線形回帰に着目する。これは、当然に、予算的に実現可能なメカニズムデザイン問題と考えられ、目的関数は、xiの共分散(covariance)に関連する。特に、実験計画問題(EDP)は次のように定式化される：実験者Eは予算の制約のもとで(Σi∈Sci  ≦B)、次の量を最大化するように、対象者の集合Sを見出すことを望んでいる：
【００２６】
【数１】
2016509307.tif 000003
ここで、BはEの予算である。要となる目的関数は、線形回帰法により学習され所謂D最適化基準に関連する場合に、βに関して情報ゲインを最適化することにより得られる。上記の目的はサブモジュラー(submodular)である。
【００２７】
本願で提案される方法は次のように動作する：
・  各々の対象者iに関し、入力としてベクトルxiが受信され、これは、対象者の公の属性(例えば、年齢又は性別など)だけでなくコストciも記述し、実験に参加する場合に要求する対価(又は補償又は報酬)を記述する。
【００２８】
・  実験者から、実験に使うことが可能な金額を示す予算Bが受信される。
【００２９】
・  一群の対象者Sの各々について、次式による関数値V(S)が算出され、
V(S)=log  det(1+ΣiinS  xixiT)
これは、特定の実験の結果がどの程度有用であるかを示し、各々の集合のうちの個々の対象者の値が算出される。
【００３０】
・  アルゴリズム1で記述されるアルゴリズムを利用して何れのユーザからデータを購入するかについての判断がなされる。要約すると次のようになる：
。  入力のこれらの値の下で、最適化問題に対する解として閾値ξを算出する。
【００３１】
。  ある定数Cに関し、最も高い対象者のV(i*)の値がCξより高い場合、実験者はその最も高いユーザについて実験を単に実行し、全ての予算Bをその者に与える。
【００３２】
。  そうでない場合、アルゴリズム1に示されるように、関数値Vに対するマージナル寄与度(marginal  contribution)の昇順に、実験に対する一群の対象者を構成し、いわゆる閾値支払法(threshold  payment)を用いて彼らに対価を支払う。
【００３３】
【数２】
2016509307.tif 000004
図1のフローチャートには、本原理によるデータマーケットを計画する方法100の一形態が示されている。本方法は開始ブロック101から始まり、制御は進み、ブロック105において、可能性のある一群の対象者のメンバについての特徴ベクトルにアクセスする。特徴ベクトルは、集合メンバの公の属性により形成されてもよい。これらの特徴は例えば年齢や性別とすることが可能である。特徴ベクトルは、特定のメンバの所望の対価の情報を含んでもよい。これは、実験に参加するメンバに与える必要がある対価の額である。ブロック105に続いて、制御はブロック110に進み、実験についての予算を受信する。これは実験又は調査を行うために消費される総額であり、すなわち、実験で選択される参加者全員を補償するために費やされる総額である。ブロック110に続いて、制御はブロック115に進み、事件に対する潜在的な一群の対象者のうちの各々のメンバについての値と関数値V(S)とを算出する。個々の対象者の値は、集合の各メンバの所望の対価に基づき、これは各メンバの特徴ベクトルに含まれていてもよい。この値はD最適化基準を用いて算出されてもよい。制御は次にブロック120に進み、最も高い値のメンバを、実験のための一群の対象者に含める。ブロック120に続いて、制御はブロック125に進み、実験に対する潜在的な一群の対象者のうち残りのメンバについて凸最適化を実行して閾値を決定し、閾値は追加の対象者が実験に使用されるか否かを評価するために使用される。ブロック125に続いて、制御者はブロック130に進み、潜在的な対象者のうち最高値を有していた上記のメンバであって実験に既に含まれているメンバについての値と、閾値とを比較する。ブロック130に続いて、制御はブロック135に進み、この値と閾値とを比較する。実験に含まれる最初のメンバの値(潜在的な対象者全員のうちの最高値)が閾値より大きい場合、制御はブロック140に進み、最初のメンバは、実験に充てられる予算全額の対価の割り当てを受ける。しかしながら、実験に含まれる最初のメンバの値が閾値より大きくない場合、ブロック144において、最初のメンバは、そのメンバを実験に含めるのに必要な額の対価の割り当てを受け、そして制御者ブロック145に進み、潜在的な対象者のうち次に最高の値のメンバが、実験に加えられ、実験に含めるのに必要な額の対価の割り当てを受ける。ブロック145に続いて、制御はブロック150に進み、予算は使い尽くされたか否かを判定する。予算が使い尽くされていない場合、ブロック145及び150が反復され、予算が使い果たされたことがブロック150において確認されるまで、追加の対象者を実験に1人ずつ追加する。ブロック140及び150に続いて、制御はブロック155に進み、実験に対する対象者及び彼らに関連する対価の額が決定される。
【００３４】
図2には、本原理の下でデータマーケットを計画するための装置200の一形態が示される。本装置は図1の方法を実行する。装置200は、スタンドアローン又は統合されるユニットのような1つ以上のプロセッサにより構成され、上記の機能を実行するように構成される。本装置は、図2では、説明の便宜上3つの個別的なプロセッサを有するように示されているが、本機能は単独のプロセッサ或いは多数の個別的なプロセッサで実行されることが可能な点も理解されるべきである。図2では、装置200は、プロセッサA、プロセッサB及びプロセッサCにより構成されるように示されている。
【００３５】
装置200は、第1入力において実験に対する予算を入力として受信し、第2入力において実験に対する一群の対象者の潜在的なメンバ各々についての特徴ベクトルを入力として受信する。装置200内のプロセッサAは、これら2つの組の入力を受信するように示されており、これらのデータを求めるリクエストに応答して或いは措置200により又は外的な制御により、プロセッサAに送られてもよい。
【００３６】
プロセッサAは、この例では、集合に対する値と、実験に対する一群の集合の潜在的なメンバ各々に対する値とを算出し、集合のうち最高値のメンバを判定する機能を実行する。最高値のメンバは、その実験に対する一群の対象者に含められる。
【００３７】
プロセッサBは、次に、閾値を決定するために、集合の残りの潜在的なメンバについて凸最適化を実行する。プロセッサCは、次に、この閾値と、一群の対象者のうち既に含まれている最も高い値のメンバの値とを比較する。最も高い値の対象者の値がこの閾値より大きい場合、実験のための全ての予算が、最も高い値の対象者に充てられ、その対象者とともに実験が行われ、全ての予算が彼/彼女に割り当てられる。最も高い値の対象者の値が閾値より大きくない場合、最も高い値のメンバは、所望の対価に応じて対価の割り当てを受け、潜在的な対象者のうち次に高い値のメンバが実験に含められ、実験に含めるのに必要な閾値支払(threshold  payment)の割り当てを受ける。プロセッサは予算が使い果たされたか否かを検査する。使い尽くしていない場合、プロセッサは対象者を実験に1人ずつ追加し続け、彼らを実験に参加させるのに必要な額で各自に対価を割り当て、各自を含めた後に予算が尽きたか否かを確認する。予算が尽きる場合には、潜在的な一群の対象者及び各自の対応する支払が完了する。
【００３８】
より一般的な議論は情報ゲインの観点に従う。バジェットフィージブルリザーブオークション(budget  feasible  reserve  auction)は一群のアイテムN={1,...,n)だけでなく単独のバイヤー(又は買い手)も含む。各々のアイテムはコストを有する。更に、バイヤーは正値関数だけでなく予算Bも有する。完全情報(full  information)のケースにおいて、コストciは共通の情報であり；この状況におけるバイヤーの目的は、コストciの合計が予算B以下であるという制約の下で、値V(S)を最大化する集合Sを選択することである。完全情報の場合に達成可能な最適値は、次のようになる：
【００３９】
【数３】
2016509307.tif 000005
戦略的なケースでは、Nのうちの各々のアイテムは異なる戦略的なエージェントにより保持され、彼らのコストは事前の個人情報(a  priori  private)である。メカニズムM=(f;p)は、(a)割り当て関数f及び(b)支払関数pを有する。コストのベクトルc=[ci]の下で、割り当て関数fは、購入されるべきアイテムであるNのうちの集合を決定し、支払関数は支払のベクトル[pi]を返す。si(c)をiのバイナリインジケータとする。上記のアプローチと同様に、本説明は、(pi(c)=0であるように)正規化され、個別的にレーショナル(rational)であり(pi(c)≧ci_si(c))かつ正の転移(positive  transfer)を有しない(pi(c)≧0)メカニズムを記述する。上記に加えて、バジェットフィージブルリザーブオークションにおけるメカニズム設計は、以下の性質を有するメカニズムを求める：
1.  真実性又は正直さ(truthfulness)：エージェントは、エージェントの真のコストを偽って報告するインセンティブを有しない。
【００４０】
2.  予算的な実現可能性：支払総額は予算の制約を超えるべきでない。
【００４１】
3.  近似的比率：割り当てられる集合の値は、完全情報のケースの最適値から過剰に逸脱すべきでない。正式言えば、OPT≦αV(S)であるような何らかのα≧1が存在しなければならない。近似的比率は真実性による価格、すなわち、真実性の制約を追加することにより被る相対的な値の損失を捕らえる。
【００４２】
4.  演算効率性：割り当て及び支払関数は、エージェント数nにおける多項式時間で算出されるべきである。
【００４３】
バジェットフィージブルリザーブオークションは単一パラメータオークションであり：各々のエージェントが唯1つのプライベート値を有する。多くの場合、マイヤーソンの定理(Myerson’s  Theorem)は、正直さのメカニズムの特徴をもたらす。マイヤーソンの定理は、フォーカスが単調な割り当て関数を設計することにあることを許容する。従って、メカニズムは、支払は合計をB未満の値にする必要がある制約の下で、メカニズムが各々の対象者に各自の閾値支払を与える限り、「正直」である。
【００４４】
上記により、最適な実験計画の問題を、バジェットフィージブルリザーブオークションの観点から考察する。特に、実験者Eは、予算Bを有し、バイヤーの役割を演じることを仮定する。各々の実験
【００４５】
【数４】
2016509307.tif 000006
は戦略的なエージェントに対応し、各自のコストciはプライベートである。測定値yiを取得するために、実験者は、エージェントiに、その者のコストを超える価格を支払う必要がある。
【００４６】
例えば、各々のiは対象者の人に対応し；特徴ベクトルxiは、年齢、体重、性別、収入などについての正規化されたベクトルに対応し；測定値yiは何らかのバイオメトリック情報  (例えば、その人の赤血球数、遺伝子マーカー(generic  marker)等)を捕らえる。コストciは、研究に対象者の参加を駆り立てるのに十分であると対象者が思う量(又は額)である。この設定において、特徴ベクトルxiは、実験者が実験計画に先立って調べることが可能なパブリック情報である、ということに留意を要する。更に、対象者は自身のコストciについて偽るかもしれないが、対象者はxiについて偽ることはできず(すなわち、全ての属性は収集の際に確認可能である)、yiについて偽ることもできない(すなわち、対象者は自身の測定値を改ざんすることはできない)。対象者が自身の真のコストを偽る場合、対象者は実験に参加するようには選択されないかもしれない(なぜなら、実験に対するその対象者の値は、より高いコストにおいて、小さくなるからである)。
【００４７】
理想的には、D最適化判断により動機付けられる場合に、本原理の目的の1つは、適切な近似比率の範囲内において、
【００４８】
【数５】
2016509307.tif 000007
を最大化するメカニズムである。以下では、更に若干一般的な目的が考察される：
実験計画問題(EDP)
【００４９】
【数６】
2016509307.tif 000008
EDPに関する結果のメカニズムは、アルゴリズム1に登場した割り当て関数と、マイヤーソン定理で言及したような各々の割り当てエージェントIに各自の閾値支払を行う支払関数とにより構成される。{i*}が割り当てられる集合である場合、その人の閾値支払はBである(その人に最高コストを報告させるアルゴリズム1のライン1でその人は落とされる)。SGが割り当て集合である場合、閾値支払の特徴は、これらの支払を算出する数式を与える。アルゴリズム1は実験計画問題に対する主要な結果を与える。
【００５０】
上記の結果は更に一般的なベイジアン(Bayesian)のケースに拡張可能であり、実験者はβに関する先験的な分布を有することが仮定される。リッジ回帰(ridge  regression)を用いる場合の最適化は次式のように導出される：
【００５１】
【数７】
2016509307.tif 000009
H(β)がこの分布におけるβのエントロピであり、H(β|ys)が測定結果についての条件付きのβのエントロピであり、測定値の集合は情報ゲインを最大化するように選択されることが可能であり：
【００５２】
【数８】
2016509307.tif 000010
これは次式と等価であり、
【００５３】
【数９】
2016509307.tif 000011
一般的なベイジアンのケースの場合、次式が得られる：
【００５４】
【数１０】
2016509307.tif 000012
この原理を実現するための方法の一実施形態は、対象者の属性と、この対象者を実験に含めるためのコストとを含むデータを受信する。本方法は、更に、実験に使うことが可能な予算を割り振る。
【００５５】
特定の対象者に対する特定の実験結果の有用性を表現する関数値(value  function)が各々の対象者に関連付けられる。
【００５６】
次に、本方法は、アルゴリズム1に基づいて、最適化問題の解として閾値を決定する。この閾値は各々の対象者に対する関数値と比較される。
【００５７】
最も高い対象者(most  valuable  subject)の値が、Cξより高い場合(Cは定数)、その最も有用な値のユーザのみを利用して実験が行われ、予算全額をその対象者に与える。
【００５８】
しかしながら、最も高い対象者の値がCξより高くない場合、関数値Vに対するマージナル寄与度の昇順に、一群の対象者を用いて実験が行われ、閾値支払法を用いて彼らに予算の額を支払う。
【００５９】
何れのユーザを利用するかに関する処理及び彼らに割り振る予算は、本原理に基づいて、対象者及び割り振られる予算を表すデータの変換に応じてなされる。実験に利用される対象者及び1人以上の対象者に割り振る予算額を表すデータは、追加的なデータを変換するため又は追加的な処理を行わせるために使用される。
【００６０】
以上、本発明の好適実施形態による特定の特徴及び側面を有する1つ以上の実現手段が提供されてきた。しかしながら、説明される実現手段の特徴及び側面は他の実現手段にも適用可能である。例えば、これらの実現手段及び特徴は、他のビデオ装置又はシステムとの関連で使用されることが可能である。実現手段及び特徴が標準規格で使用されることは必須でない。
【００６１】
本原理の「一形態」、「一実施形態」、「一実施例」又は「実現手段」という明細書中での参照及びそれらの派生語は、実施形態に関連して説明される特定の属性、構造、特徴などが、本原理の少なくとも1つの実施形態に含まれることを意味する。従って、明細書を通じて様々な箇所で登場する「一形態」、「一実施形態」、「一実施例」又は「実現手段」及びそれらの何らかの派生語は、必ずしも全て同じ実施形態を指しているとは限らない。
【００６２】
本願で説明される実現手段は、例えば、方法、プロセス、装置、ソフトウェアプログラム、データストリーム又は信号で実現されることが可能である。1つの実現手段の文脈でしか説明されていない場合でさえ(例えば、方法としてしか説明されていない場合でさえ)、説明される特徴の実現は他の形態(例えば、装置、コンピュータソフトウェアプログラム等)で行われることも可能である。装置は、例えば、適切なハードウェア、ソフトウェア及びファームウェアで実現されることが可能である。方法は、例えば、一般的には処理装置を指すプロセッサのような装置で実現されることが可能であり、処理装置は、例えば、コンピュータ、マイクロプロセッサ、集積回路又はプログラム可能な論理装置などを含む。プロセッサは、例えば、コンピュータ、セルラ電話、ポータブル/パーソナルディジタルアシスタント(PDA)のような通信装置や、エンドユーザ間での情報通信を促す他の装置も含む。
【００６３】
本願で説明される様々なプロセス及び特徴による手段は、多種多様な装置又はアプリケーションで実現されることが可能である。そのような装置の具体例は、ウェブサーバ、ラップトップ、パーソナルコンピュータ、セルラ電話、PDA及び他の通信装置を含む。明らかに、装置は、移動体とすることが可能であり、移動する乗り物に導入されることさえ可能である。
【００６４】
更に、方法はプロセッサにより実行される命令により実現されることが可能であり、そのような命令(及び/又は実現手段により生成されるデータ値)は、例えば、集積回路、ソフトウェアキャリア又は他のストレージ装置のようなプロセッサ読み取り可能な媒体に保存されることが可能であり、ストレージ装置は、例えば、ハードディスク、コンパクトディスク、ランダムアクセスメモリ(RAM)又はリードオンリメモリ(ROM)等である。命令は、プロセッサ読み取り可能な媒体に実際に(又は有形に)実現されるアプリケーションプログラムを形成することが可能である。命令は、例えば、ハードウェア、ファームウェア、ソフトウェア又はそれらの組み合わせとして実現可能である。命令は、例えば、オペレーディングシステム、分離されたアプリケーション又はそれらの組み合わせにおいて使用されることが可能である。従って、プロセッサは、例えば、プロセスを実行するように構成される装置、及び、プロセスを実行する命令を有するプロセッサ読み取り可能な媒体(例えば、ストレージ装置)を含む装置の双方として特徴付けられることが可能である。更に、プロセッサ読み取り可能な媒体は、命令に加えて又は命令に代えて、実現手段により生成されるデータ値を保存することが可能である。
【００６５】
当業者に明らかであるとように、実現手段は本願で説明されるアプローチの全部又は一部を利用することが可能である。実現手段は、例えば、方法を実行するための命令、或いは、何れかの説明される実施形態により生成されるデータを含むことが可能である。
【００６６】
以上、多くの実現手段が説明されてきた。しかしながら、様々な変形が可能であることも理解されるであろう。例えば、異なる実施形態の要素は、他の実施形態を形成するように、組み合わされること、置換されること、修正されること又は削除されることが可能である。更に、説明されたものの代わりに他の構造及びプロセスが置換されてもよいこと、及び、その結果の実現手段は、少なくとも実質的に同じ機能を少なくとも実質的に同じ方法で実行し、説明された実現手段と少なくとも実質的に同じ結果を達成することを、当業者は理解するであろう。従って、これら及び他の実現手段は、本開示により想定されており、本原理の範囲内にある。
【００６７】
＜関連出願のクロスリファレンス＞
本願は2013年1月31日付けで出願された米国仮出願第61/759203号による利益を享受し、その内容全体は本願のリファレンスに組み入れられる。
【図１】
2016509307.tif 000013
【図２】
2016509307.tif 000014
【手続補正書】
【提出日】平成27年8月4日(2015.8.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
潜在的な対象者の集合の中から、データを収集するための対象者を選択する方法であって、
少なくとも1人の対象者の特徴ベクトルにアクセスするステップであって、前記特徴ベクトルは前記少なくとも1人の対象者の参加のためのコストを含む、ステップと、
前記対象者のために使用するコストを記述する予算を受信するステップと、
前記潜在的な対象者の集合のメンバ各々について値を算出し、前記集合のうち最高値のメンバを判定し、当該メンバを参加する対象者のリストに加えるステップと、
前記集合のうち前記最高値のメンバ以外の前記集合中の対象者について凸最適化を実行して閾値を判定するステップと、
前記閾値と算出された値とを比較し、当該算出された値が前記閾値を超えるか否かを判断するステップと、
超える場合には、前記少なくとも1人の対象者に予算全額で対価を割り当てるステップと、
当該算出された値が前記閾値を超えない場合には、前記予算が尽きるまで、参加のための値に対する各自のマージン寄与度の昇順に、前記参加する対象者のリストに加えられる対象者に、前記予算の一部分を比例して割り当てるステップと、
を有する方法。
【請求項２】
前記特徴ベクトルは年齢及び性別を含む、請求項1に記載の方法。
【請求項３】
前記の値はD最適化基準である、請求項1に記載の方法。
【請求項４】
後者の割り当てるステップが、前記参加する対象者のリストに1度に1人の対象者を反復的に追加することを含む、請求項1に記載の方法。
【請求項５】
各々の反復で追加される前記対象者は、実験に参加するためのコストに対する値の最大比率を有する、請求項4に記載の方法。
【請求項６】
潜在的な対象者の集合の中から、データを収集するための対象者を選択する1つ以上のプロセッサを有する装置であって、前記1つ以上のプロセッサは、協同して、
少なくとも1人の対象者の特徴ベクトルにアクセスするステップであって、前記特徴ベクトルは前記少なくとも1人の対象者の参加のためのコストを含む、ステップと、
前記対象者のために使用するコストを記述する予算を受信するステップと、
前記潜在的な対象者の集合のメンバ各々について値を算出し、前記集合のうち最高値のメンバを判定し、当該メンバを参加する対象者のリストに加えるステップと、
前記集合のうち前記最高値のメンバ以外の前記集合中の対象者について凸最適化を実行して閾値を判定するステップと、
前記閾値と算出された値とを比較し、当該算出された値が前記閾値を超えるか否かを判断するステップと、
超える場合には、前記少なくとも1人の対象者に予算全額で対価を割り当てるステップと、
当該算出された値が前記閾値を超えない場合には、前記予算が尽きるまで、参加のための値に対する各自のマージン寄与度の昇順に、前記参加する対象者のリストに加えられる対象者に、前記予算の一部分を比例して割り当てるステップと、
を実行するように構成される、装置。
【請求項７】
前記特徴ベクトルは年齢及び性別を含む、請求項6に記載の装置。
【請求項８】
前記の値はD最適化基準である、請求項6に記載の装置。
【請求項９】
後者の割り当てるステップが、前記参加する対象者のリストに1度に1人の対象者を反復的に追加することを含む、請求項6に記載の装置。
【請求項１０】
各々の反復で追加される前記対象者は、実験に参加するためのコストに対する値の最大比率を有する、請求項9に記載の装置。
【請求項１１】
前記対象者は実験に参加するように選択される、請求項1に記載の方法。
【請求項１２】
前記対象者は市場調査に参加するように選択される、請求項1に記載の方法。
【請求項１３】
前記対象者は医療リサーチ研究に参加するように選択される、請求項1に記載の方法。
【請求項１４】
前記対象者は実験に参加するように選択される、請求項6に記載の装置。
【請求項１５】
前記対象者は市場調査に参加するように選択される、請求項6に記載の装置。
【請求項１６】
前記対象者は医療リサーチ研究に参加するように選択される、請求項6に記載の装置。
【国際調査報告】
2016509307.tif 000015