JP7754592B2 - オブジェクトを順位付けするためのシステム及び方法 - Google Patents

Description

［関連出願の相互参照］
本出願（対応米国出願）は、２０２１年５月６日に出願された仏国特許出願第ＦＲ２１０４８０１号に基づき３５ ＵＳＣ １１９に従う優先権を主張し、その内容が参照により本明細書に組み込まれる。

本出願（対応米国出願）は、２０２１年１１月８日に出願された欧州特許出願第ＥＰ２１３０６５６５号に基づき３５ ＵＳＣ １１９に従う優先権をさらに主張し、その内容が参照により本明細書に組み込まれる。

本発明の分野は情報検索及び推薦（recommendation）である。より具体的には、本発明の実施例は、検索されるオブジェクト（object）の公正な順位付けのためのコンピュータ具現化方法及びシステムに関する。

一般に、情報検索及び推薦は２つのステップから構成される。第１のステップは、複数の結果の候補セットを検索するのに焦点を当て、第２のステップは、複数の結果の候補セットを順位付けするのに焦点を当てる。

複数の結果の候補セットは、検索結果（例えば、クエリ（query）に応じた検索結果からの文書に対するリンクのリスト）及び、推薦（例えば、識別された位置に応じた関心地点の推薦リスト、或いは、ジャンル選択に応じた歌の推薦リストなど）を含むことができる。

例えば、情報検索のために第１のステップの検索器にクエリを入力でき、これはクエリを（例えば、関連性に基づいて）プロセスすることにより、複数の文書のセットを検索する。次いで、第２のステップ又はランカー（ranker）（或いは、リランカー（reranker））は、検索された複数の文書のセットを順位付けし、順位付けした文書のセットを出力するが、ここで、その数が第１のセットと同一又はさらに少ないことができる。

ユーザ（例えば、コンテンツ消費者）は、最も関連性の高い結果が最も多く露出されることを期待するが、提供者（例えば、コンテンツ生産者）は、自分のコンテンツに対して公正（または公平）に露出されることを追求する。したがって、第２のステップにおいて、複数の結果の候補セットを順位付けする際に、順位付け方法は、効用性（複数の結果のセットにアクセスするユーザを示す）及び公正性（複数の結果のセットを構成する提供者を示す）間のバランスを維持することが望ましい。

効用性（utility）及び公正性（fairness）のバランスを維持する一部の順位付け方法は存在するが、一般にその方法の複雑性により現実的なシナリオにおける使用が禁止される。したがって、例えば、ウェブ規模の公正性－効用性の順位付けを可能にするために、既存の方法に比べて複雑性が減少された（例えば、正確な最適のソリューションを計算できる）最適の方法に対するニーズが続いている。

韓国登録特許第１０－１７１０４６５号公報

本発明の例示的な方法は、第１の様態による複数のオブジェクトのセットを順位付けするためのコンピュータ具現化方法を提供し、方法は、複数のオブジェクトのセット及び複数の目標関数のセットを受信するステップ；ペルムトヘドロン（permutohedron）を用いて、ｎ個の決定変数を有する決定空間を定義するステップ、ここで、ｎは順位付けするオブジェクトの数であり、ペルムトヘドロンの頂点は、対応する順位によりセット内のオブジェクトに提供される露出の順列を示す；複数の目標関数のセットに対するパレート（Pareto）セットを決定するステップ；パレート最適地点をパレートセット内とし、決定空間を用いて、セット内のオブジェクトに関する順位に対する分布を決定するステップ、ここで、前記分布内の各々の順位及び比率が関連付けられる；比率により順位に対する分布からセット内のオブジェクトに関する順位のシーケンスを選択するステップ；及び、選択された順位のシーケンスを出力するステップ；を含む。

第１の様態による方法の好ましいが非制限的な様態は、次の通りである。

複数の目標関数のセットは、２次関数及び線形関数を含むことができ、
２次関数は公正性関数であり得、線形関数は効用性関数であり得、
公正性関数は、決定変数から構成されるベクトルとターゲットベクトルとの間の差の自乗Ｌ２－ｎｏｒｍのような正規化した差であり得、
方法は、セット内の各々のオブジェクトに対する関連性点数及び順位と各々関連付けられた、セット内のオブジェクトに提供される露出のリスト、順位付け公正性目標関数及び順位付け効用性目標関数を受信するステップをさらに含むことができ、
複数の目標関数のセットに対するパレートセットを決定するステップは、順位付け公正性目標関数及び順位付け効用性目標関数を考慮して、決定空間内でパレートセットを計算するステップを含むことができ、決定空間を用いて、セット内のオブジェクトに関する順位に対する分布を決定するステップは、決定空間内でセット内のオブジェクトにわたってターゲット露出に変換されるパレートセット内の特定地点を受信するステップ、及び、ターゲット露出を用いて、セット内のオブジェクトに対するターゲット露出を平均的に達成する順位に対する分布を決定するステップを含むことができ、順位に対する分布の各々の順位は決定空間内の頂点に対応し、
決定空間を用いて、セット内のオブジェクトに関する順位に対する分布を決定するステップは、セット内のオブジェクトの数に対し、
（ｉ）決定空間の任意の頂点を決定するステップ；
（ｉｉ）線が決定空間の面と交差するまで、ターゲット露出により任意の頂点から始まる線を描くステップ；及び、
（ｉｉｉ）新しく交差された面が頂点となるまで、ターゲット露出の代わりに、新しい交差地点を用いて決定空間の交差された面上において、（ｉ）及び（ｉｉ）を繰り返すステップ；をさらに含むことができ、
公正性関数は、能力主義（Meritocratic）公正性又は人口統計学的公正性に基づくことができ、
決定空間を用いて、セット内のオブジェクトに関する順位に対する分布を決定するステップは、ＧＬＳ（Grotschel,Lovasz and Schrijver）手順を使用でき、
セット内のオブジェクトに関する順位のシーケンスを選択するステップは、確率的（stochastic）サンプリング、低不一致シーケンス（Low-Discrepancy Sequences）、加算繰り返しシーケンス（additive-recurrence sequences）、ストライドスケジューリング（Stride Scheduling）またはｍ－バランス（m-balancing）の一つ以上を含むことができ、
セット内のオブジェクトは、複数のクエリを含むことができ、
セット内のオブジェクトは、クエリに応じて識別されることができ、
セット内のオブジェクトは、複数の推薦を含むことができ、
セット内のオブジェクトは、地図位置に応じて識別されることができ、
出力するステップは、選択された順位のシーケンスにより順位付けする複数のオブジェクトのセットの少なくともサブセットを、デバイスのディスプレイ上にディスプレイするために提供するステップを含むことができ、
少なくとも複数のオブジェクトのセットのサブセットは、検索エンジン結果ページ上に提供されることができる。

第２、第３、第４及び第５の様態の各々によれば、本発明は、コード命令語を含むコンピュータプログラム製品、ここで、コード命令語は、プログラムがコンピュータ上で実行される際に、コンピュータが本発明の第１の様態による方法を遂行するようにする；コンピュータプログラム製品が保存されたコンピュータ読取り可能な媒体；本発明の第１の様態による方法を遂行するように構成されたプロセッサを含むデータプロセシングデバイス；及び／又は、クエリを受信し、複数のオブジェクトのセットを生成するように構成されたコンピュータ具現化の第１のステップの検索器と、本発明の第１の様態により複数のオブジェクトのセットを順位付けするように構成されたコンピュータ具現化の第２のステップのランカーとを含む情報検索のためのシステムを提供できる。

添付図面は、実施例の原理を説明するために本明細書に統合される。図面は、本発明を例示して記述した実施例だけに制限したり、それらを製造して使用する方式に制限したりするものと解釈してはならない。追加の特徴及び利点は、添付図面に例示したように、次の実施例の説明及びより具体的な部分で明確になる。
開示の方法を遂行できるアーキテクチャの例を示す図である。 開示の方法の一実施例を説明するフローチャートである。 ｎ＝４に対する例示的なペルムトヘドロンの例を示す図である。 ペルムトヘドロン内の一地点をペルムトヘドロンの複数の頂点のうちで最大ｎ個の組合せに分解する手順の例を示す図である。 ｎ＝３に対する例示的な一般化したペルムトヘドロン（例示的な方法においてエキスポヘドロン（Expohedron）と称する）の例を示す図である。 一部の方法において使用できる例示的な分解方法の意思コードを説明する図である。 エキスポヘドロン（ｎ＝３）において等価効用性曲線（equi-utility curve）及び最大効用性ソリューション（max-utility solution）の例を示す図である。 関連性タイ（Tie）（ｎ＝３）を有するエキスポヘドロンの最大効用性ソリューションの例を示す図である。 エキスポヘドロン（ｎ＝３）において最適の人口統計学的及び能力主義公正性ソリューション、並びに等価公正性曲線の例を示す図である。 エキスポヘドロン（ｎ＝３）において最適の人口統計学的及び能力主義公正性ソリューション、並びに等価公正性曲線の例を示す図である。 エキスポヘドロン（ｎ＝３）のパレートセットの例を示す図である。 例示的なパレートセット識別方法に関する意思コードを説明する図である。

１．アーキテクチャ
オブジェクトを順位付けするための開示のコンピュータ具現化方法及び実施例は、データ交換のためにインターネットのようなネットワーク１０４（無線及び／又は有線）を介して通信するサーバー１００及び一つ以上のクライアントデバイス１０２を含む、図１に示すようなアーキテクチャ（例えば、ネットワークやシステムアーキテクチャ）内で具現化できる。サーバー１００及びクライアントデバイス１０２は、データプロセッサ１１２及びメモリ１１３、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ハードディスク、ソリッドステートディスク、または他の不揮発性保存媒体を含むが、これに制限されるものではない。また、メモリ１１３は、データプロセッサ１１２と通信する外部メモリ又はストレージにより全体的又は部分的に提供され得る。クライアントデバイス１０２は、サーバー１００と通信する任意のデバイスであり得る。

本明細書で提供される例示的な方法は、データプロセッサ１１２またはサーバー１００及び／又はクライアントデバイス１０２での他のプロセッサのようなプロセッサにより具現化できる。データプロセッサ１１２は、単一のプロセッサ、或いは、直列又は並列に動作する多重プロセッサを含むことができる。例示的な方法に使用されるメモリは、例えば、サーバー１００、クライアントデバイス１０２ｂ～１０２ｅ内のメモリ１１３及び／又は適切なストレージ、連結されたリモートストレージ、または任意の組合せにより実施できる。メモリは、メモリ類型及び／又は位置の組合せを含んで一つ以上のメモリ又はメモリ要素や構造を含むことができる。メモリのデータは、データ検索及びプロセシングに対する任意の適切な形式で保存できる。

サーバー１００は、専用サーバー、クラウド基盤サーバー、またはこれらの組合せ（例えば、共有型）を含むことのできるが、これらに制限されるものではない。データストリームは、サーバー１００及び／又はクライアントデバイス１０２ｂ～１０２ｅから通信され／通信されたり、それにより受信され／受信されたり、それにより生成され得る。

クライアントデバイス１０２ｂ～１０２ｅは、任意のプロセッサ基盤デバイスや端末などであり／であったり、プロセッサ基盤デバイスなどにより実行可能なクライアントアプリケーションで具現化できる。クライアントデバイスは、サーバー１００の内部に配置され／配置されたり（ローカル又はリモート、または任意の組合せ）、サーバーの外部に配置されて、サーバーと通信できる。例示的なクライアントデバイス１０２ｂ～１０２ｅは、例えば、自律走行車１０２ｂ、ロボット１０２ｃ、コンピュータ１０２ｄ、スマートフォン１０２ｅのようなモバイル通信デバイス（例えば、スマートフォンやタブレットＰＣなど）だけでなく、ＶＲ（virtual reality）、ＡＲ（augmented reality）またはＭＲ（mixed reality）デバイス、ウェアラブルコンピュータなどのような、図１に示していない多様なプロセッサ基盤デバイスを含むが、これに制限されるものではない。クライアントデバイス１０２ｂ～１０２ｅは、サーバー１００にデータを転送し／転送したり、それからデータを受信するように構成できるが、必ずしもそうである必要はなくて、サーバーによりディスプレイするために提供される特定方法の結果を表示、発表又は印刷するためのディスプレイ、スピーカー、プリンタなどのような一つ以上の出力デバイスを含むことのできるが、これに制限されるものではない。クライアントデバイスは、クライアントデバイスの組合せを含むことができる。

２．複数のオブジェクトのセットを順位付けするための方法
本明細書に提供される例示的な方法は、最適化／決定変数のセットを用いて、最適の公正性－効用性順位付けポリシー（policy）を效率的に設計するという問題を解決する。例示的な方法の第１の特徴は、理想的な順位を構成する重要な目標、特に、典型的にユーザまたは消費者の観点を示す効用性目標、及び、典型的に提供者または供給者の観点を示す公正性目標の間の核心リンクとして役割を果たす「リストの露出」変数を最適化／決定変数として選択する。

有利には、例示的な方法の第２の特徴は、一般化したペルムトヘドロンである（例えば、それにより表現され得る）決定空間においてｎ個の決定変数だけで最適化問題を表現できるが（ここで、ｎは順位付けするオブジェクトの数である）、効用性及び公正性の目標を個別的かつ正確に完全統制するためのポリシーの表現性を維持する。開示の例示的なペルムトヘドロンの頂点は、対応する順位と関連付けられた露出を示すことができ、このようなペルムトヘドロンは、本明細書において「エキスポヘドロン」として称する。ペルムトヘドロン（例えば、エキスポヘドロン）によって提供される決定空間による順位に対する（または同義語として順列に対する）任意の分布（または凸結合）を示し、この空間において効用性－公正性のトレードオフ（trade-off）を解決するために幾何学的に推論できる。特に、多重目標最適化（Multi-objective Optimization、MOO）問題の全体パレートセットは、明示的なスカラー化技術を経ることなしに容易に得られるので、必要なプロセシング時間及びリソースを低減できる。

例示的な方法は、オブジェクトに対する均一な推定品質を有する関連性点数の偏らない推定、及び、公知の構造や媒介変数を有する露出モデルを用いて最適のポリシーを決定できる。

例示的な方法は、O(n² log n)の複雑性として動作する。このような方法は幾何学的推論を適用できる。方法の大部分のステップは閉鎖型方程式により表現できる。方法の他のステップは動作を整列することにより提供できる。また、全体パレートセットは、例えば、全体境界をスキャンするスカラー化技法によらず、分析的かつ幾何学的に生成できる。

図２は、複数のオブジェクトのセットを順位付けするための開示の方法の一実施例を説明するフローチャートである。図２の実施例による方法は、サーバー１００で遂行され、例示的な方法がサーバー１００と関連付けられて記述される。しかしながら、方法は、同様に、クライアントデバイス１０２により、或いは、サーバー１００及びクライアントデバイス１０２の組合せにより、遂行できることを理解すべきである。

ステップ２０２において、サーバー１００は、外部及び／又は内部のソースを含む任意の適切なソース（複数可）から、複数のオブジェクトのセット、複数のオブジェクトのセット内の各々のオブジェクトに対する（例えば、偏らない（unbasied））関連性点数、各々が順位と関連付けられる露出のリスト、順位付け公正性目標関数及び順位付け効用性目標関数を含む目標関数を受信する。ステップ２０４において、サーバー１００は、ｎ個の決定変数を有するペルムトヘドロンを用いて決定空間を定義し、ここで、ｎは順位付けするオブジェクトの数であり、ペルムトヘドロンの頂点は、対応する順位によりセット内のオブジェクトに提供される露出の順列を示す。

ステップ２０６において、順位付け公正性目標関数及び順位付け効用性目標関数を用いて、サーバー１００は、最適公正性を示す第１の地点と最適効用性を示す第２の地点との間の露出のリストにより定義された決定空間内において、パレートセット（すなわち、すべての目標関数に対してさらに良い他のソリューションがない、例えばさらに大きい効用性及びさらに良い公正性を同時に提供する露出がない非支配ソリューションのセット）を計算する。例示的な方法から最適の公正性類型は、例えば、人口統計学的公正性及び能力主義公正性を含むことができる。後述するように、人口統計学的公正性に対する理想的な露出は同等な露出を許容するのに対し、能力主義公正性の場合、露出は関連性に基づいて定義できる（例えば、関連性ベクトルを用いて定義できる)。また他の実施例において、最適の公正性類型は（例えば、支払われる賞金を割り当てるために）公正性とは異なる既定の比率に基づいて付加的又は代替的にカスタマイゼーションできる。

例示的な公正性類型は、グループ公正性と対照的に個別公正性を考慮する。個別公正性は個別オブジェクトの水準から公平性を保証しようとするのに対し、グループ公正性はオブジェクトがグループと関連付けられ、公平性がグループ水準から保証されると仮定して、典型的に一部のグループが不利益を受けることを防止する。

ステップ２０７において、サーバー１００は、パレートセットを意思決定者に（内部的又は外部的に）出力する。ステップ２０８において、サーバー１００は、パレートセットの地点を（内部的又は外部的に）受信し、これは決定空間内のターゲット露出に変換される。このターゲット露出はセット内のオブジェクトにわたった露出に対応する。一実施例においてターゲット露出は定義された効用性／公正性トレードオフを設定する、サーバー１００の内部又は外部の意思決定者により定義され、これはケース別または一般的に固定された制約により設定される（例えば、公正性が既定の閾値の以下に低下しないという制約を設定する）。一部の実施例において意思決定者は管理者であり得る。他の実施例において意思決定者は自動化したシステムであり得る。管理者及び自動化システムの組合せも使用できる。

ステップ２１０において、パレートセットから最適のトレードオフとして意思決定者により受信されたターゲット露出を用いて、サーバー１００は、セット内のオブジェクトに対するターゲット露出を平均的に達成する順位（例えば、加重された順位のセット）に対する分布を決定し、ここで、順位に対する分布の各々の順位は決定空間内の頂点に対応する。一実施例において、順位に対する分布を決定することは次の通り遂行できる：（ｉ）決定空間の任意の頂点が決定され；（ｉｉ）線が決定空間の面と交差するまで、意思決定者から受けたターゲット露出により任意の頂点から始まる線を描き（例えば、計算し）；（ｉｉｉ）新しく交差された面が頂点となるまで、意思決定者のターゲット露出の代わりに交差地点を用いて、決定空間の交差された面において、ステップ（ｉ）及びステップ（ｉｉ）を繰り返す。ステップ（ｉ）乃至ステップ（ｉｉｉ）は、ステップ（ｉｉｉ）において交差点が頂点であることにより、セット内のオブジェクトの数だけ遂行できる。決定空間の各々の頂点は関連付けられた比率を有する。

ステップ２１２において、サーバー１００は、それらの比率により、順位に対する分布から複数のオブジェクトのセットに関する順位のシーケンスを選択することで、順位に対する分布を配布（distribution：配信）する。

他の実施例において、前述したように、図２の実施例による方法は、クライアントデバイス１０２から部分的又は完全に遂行できる。また他の実施例において、方法は、分散方式により異なるサーバーやクライアントデバイス又は複数のサーバー上で遂行できる。

例示的な一実施例において、個人化しないクエリ（例えば、匿名のユーザにより作成されたクエリ）は、既定の地図位置から一般的な関心地点に対して繰り返し受信される。この例示的な実施例において、複数のオブジェクトのセットは、レストラン、博物館、商店及びガソリンスタンドのような一般的な関心地点のリストであり得る。他の例示的な実施例において、個人化しないキーワードクエリは、検索エンジンにより繰り返し受信される。この例示的な実施例において、複数のオブジェクトのセットは、ウェブページのような文書に対するリンクのリストであり得る。時間の経過によりこのようなクエリが繰り返されることで、ターゲット露出を達成するための各順位のシーケンスにより複数のオブジェクトのセットの順序が変化することになる。

ステップ２１２において、選択された順位のシーケンスに基づいて、複数のオブジェクトのセットの一つ、全部またはサブセットが、例えば、提示（例えば、表示、発表、印刷、インポート（importing）、エクスポート（exporting）、保存など）のために用意して外部又は内部のデバイスに提供される、例えば、転送される検索エンジン結果ページ（ＳＥＲＰ）で提示され得る。例えば、複数のオブジェクト（このようなオブジェクトは選択されたシーケンス内で決定された順位に基づいて各々位置する）の一つ、サブセット又は全部を含むＳＥＲＰが生成されてディスプレイ上にディスプレイするために、サーバー１００又はクライアントデバイス１０２の端末に転送され得る。複数のオブジェクトの一つ又はサブセットが、すべてのオブジェクトの代わりにＳＥＲＰに提示される場合、このような提示されたオブジェクトは、例えば複数のオブジェクトのセット内の他のオブジェクトよりも、選択されたシーケンスで各々さらに高い順位を持つオブジェクトであり得る。

３．露出（Exposure：表示）
情報検索（ＩＲ）分野において、「注意（attention）」または「検査（examination）」としても知らされた露出は、ユーザが検索エンジン結果ページ（ＳＥＲＰ）の特定位置で（例えば、これに制限されないが、文書などのような）オブジェクトを検査する確率として定義できる。（例えば、図２のステップ２０２の（ｉｉｉ）において受信された露出のリストの一部を形成する）露出値は、アイトラッキング研究のような方法又は仲裁的収集（例えば、同一のクエリに対して同一の文書を二つの異なる順位に配置）によりキャプチャできるが、これに制限されるものではない。また、露出値は、情報検索技術分野から分かるような（例えば、Chuklinなどの“Click models for web search”(Synthesis Lectures on Information Concepts、Retrieval、and Services、7(3):1-115、July 2015に公開)に開示されたような)「クリックモデル」（すなわち、ユーザブラウジングモデル）を使用する方法により決定され得る。大部分の場合、このようなモデルは、２つのステップの自然なシーケンスによりクリック動作を説明しようとするが、まず、リストやその代表スニペット（snippet）を検査（またはそれに自分の注意を払う）した後、興味深い場合にそれをクリックする。

消費者（すなわち、ユーザ）の観点において、消費者は、ＳＥＲＰの見えにくい位置で関連オブジェクトを探すのに時間を消費しないために、より多くの関連オブジェクトがより高い露出を受けることを所望する。消費者のこのような欲求は、順位の効用性を露出ベクトル（すなわち、各々のオブジェクトに関する順位により提供される露出値から構成されるベクトル）、及び、利得ベクトル（すなわち、各々のオブジェクトの利得から構成されるベクトル、ここで、オブジェクトの利得はオブジェクトの関連性点数の任意の単調増加関数により定義される）間のドット積（dot product）で定義することで、例示的な方法により表現できる。これに制限されず、ＤＣＧ（Discounted Cumulative Gain）及びＥＲＲ（Expected Reciprocal Rank）のような公知の情報検索効用性測定は、この公式を露出モデル媒介変数の特定選択と共に反映する。例えば、ＤＣＧは、順位（ｋ）からオブジェクトの露出が１／ｌｏｇ_２(１＋ｋ)で与えられ、利得関数ｇ(ｄ)は、ｇ(ｄ)＝２^{ｒｅｌ(ｄ)}で与えられると仮定し、ここでｒｅｌ(ｄ)はｄの関連性点数である。ＥＲＲ測定は、カスケード（cascade）モデルに基づいて、露出がリスト内の以前オブジェクトの関連性によって変化すると仮定し、特に、ユーザがオブジェクトに満足する場合、リスト内の次のオブジェクトの露出は０になる。

供給者の観点において、供給者は、自分のオブジェクトがＳＥＲＰでさらに高い露出を有することを所望する。しかしながら、提供者が多いため、ユーザに提供されるオブジェクトに対する非差別的（non-disparate）処理が望ましい。

各々「効用性」目標及び「公正性」基準に対応する消費者及び提供者の観点は、両方とも「露出」の観点から本明細書に開示された例示的な方法により表現できる。露出は、理想的な順位の目標、すなわち効用性目標（例えば、ユーザ又は消費者の観点を示す）と公正性基準（例えば、オブジェクト提供者又は供給者の観点を示す）との間のリンクとして機能する。

４．ペルムトヘドロン（permutohedron）
例示的なペルムトヘドロンは、ポリトープ（polytope）であり、ここで、各々の頂点はｎ個のオブジェクト（例えば、文書）に関する特定順位又は順列に対応し、ポリトープはこのような頂点の凸包（convex hull：凸多面体)である。このポリトープは、ｎ次元空間に含まれているが、実際には（ｎ－１）次元である。例えば、図３は、ｎ＝４オブジェクトの場合において３次元オブジェクト３００を示し、これは、六角形及び正四角形のファセット（facet）が混合された球のように見える。３０２における頂点（４３１２）を考慮する。これは、ｄ_１を順位４、ｄ_２を順位３、ｄ_３を順位１、ｄ_４を順位２に置く順位を示す。３０２における頂点（４３１２）と、３０４における頂点（３４１２）とを連結するエッジ３０６をさらに考慮する。これは、２つの順位に対する任意の分布（又は凸結合）を示す。

また、３次元オブジェクト３００のすべてのファセットは、ｎ個のオブジェクトを２つのグループに部分順序化することを示す。例えば、頂点（４３１２）、（３４１２）、（２４１３）、（２３１４）、（３２１４）及び（４２１３）を含むファセット３０８は、ｄ_３が常に第一（すなわち、ｄ_３@順位１）であり、３つの他の文書が任意の順序に後続する部分順序を示し；頂点（３２１４）、（２３１４）、（１３２４）、（１２３４）、（２１３４）及び（３１２４）を含むファセット３１０は、ｄ_４が常に最後（すなわち、ｄ_４@順位４）であり、３つの他の文書が順序と無関係に前にくる部分順序を示し；頂点（２４１３）、（１４２３）、（１３２４）及び（２３１４）を含む正四角形ファセット３１２は、ｄ_１及びｄ_３が最初２つの位置に対して任意の順序であり、ｄ_２及びｄ_４が最後２つの位置に対して任意の順序に後続する（すなわち、（ｄ_２及びｄ_４）の前に（ｄ_１及びｄ_３）である）部分順序を示す。

一般に、次元が減少する階層（例えば、ｎ＝４の場合、ファセット→エッジ→頂点）に沿ってファセットの概念を一般化する次元（ｎ－ｋ）の各々の面は、ｎ個のオブジェクトのｋグループへの所定の部分的順序化と関連して、できるだけすべての分布（または凸結合）を示す。また、図３に示すように、３０２における頂点（４３１２）と、３０４における頂点（３４１２）とを連結するエッジ３０６は、次の部分順序に対応する：ｄ_３が第一、ｄ_４が第二、ｄ_１及びｄ_２が任意の順序に後続する。

５．分解
カラテオドリの定理（Caratheodory’s theorem）によれば、ｄ次元空間に含まれたｍ個の地点（ｖ_ｉ）から構成されるセット

の凸包内の任意の地点は、これらの地点のうちで最大（ｄ＋１）個の凸結合に分解できる。

ペルムトヘドロンを特別な場合と見なす際に、ペルムトヘドロン（これは、ｄ＝(ｎ－１)、ｎはオブジェクトの数を示す）のｄ次元オブジェクトである）の任意の地点は、最大ｎ個の順位に対する分布に分解できる。一実施例において、ＧＬＳ手順（Grotschel、Lovasz and Schrijver）として知らされた手順を用いて、一つのこのような分解を決定できる（一般に、ただ一つよりも多い分解が可能である）。ＧＬＳ手順の例（文献[Grotschel et al.、“Geometric Algorithms and Combinatorial Optimization”(Springer Science & Business Media、December 2012に公開)]参照）は、本明細書に開示された方法に適用されるｎ＝３ポリトープを示す図４に例示している。

図４の（ａ）は、４０２において分解される地点（ｘ）を示す。図４の（ｂ）に示すように、手順はポリトープ４００（ｎ＝３）の４０４において任意の頂点（ｖ_１）を選択し、次元（ｎ－２）の面と交差するまでｖ_１からｘ（分解される地点４０２）に向かって線分を延長することにより始まる。これは、新しい地点（ｘ’）を提供し、ここで、ｘはｖ_１及びｘ’の凸結合（すなわち、ｘ＝λ_１ｖ_１＋（１－λ_１）ｘ’)で表現される。

図４の（ｃ）に示すように、（ｎ－２）次元面上の地点（ｘ’）はｘ’の面に属する任意の頂点（ｖ_２と称する）を選択し、次元（ｎ－３）の面と交差するまで線分（ｖ_２－ｘ’）を延長することで、同じ手順により自体的に分解できる。図４の（ｃ）に示す例の場合、ｎ＝３であるので、この面が頂点（ｖ_３）であり、手順がこの地点で中止され、初期地点（ｘ）は３つの頂点の凸結合で表現される（すなわち、ｘ＝λ_１ｖ_１＋（１－λ_１）λ_２ｖ_２＋（１－λ_１）（１－λ_２）ｖ_３）。一般に、ｎの値が高いほど、このような再帰ステップが繰り返され、毎度次元（０）の面（すなわち、頂点）に到達するまで減少する次元の面を考慮する。

６．表記法
本明細書で説明された例示的な順位付け方法をより詳細に記述する。次の表記法が例示的な方法の特徴を公式的に記述するために使用される：
ａ）ｑは単一（例えば、匿名）のユーザ（例えば、消費者）により無限繰り返されるクエリであり；クエリは、一般の「情報検索」の意味のテキストクエリである必要はなくて、広い意味で理解されるべきであり；例えば、クエリは、また「推薦」設定において、任意のトリガコンテキスト（trigger context）を含むことができる。

ｂ）クエリ（ｑ）に対し、ｎ個のオブジェクト（例えば、文書、関心地点（ＰＯＩ）、推薦など）の固定候補セット、D = (d₁,…,d_n）があり、ここで、クエリ（ｑ）に対する関連性点数はρ = (ρ₁,…, ρ_n)で表され；
ｃ）順位付けポリシー（π(ｑ)）は、ｍ個の順位に対する分布（例えば、凸結合）であり、m<=n σ_i (i = 1,…,m)であり：

であり、ここで、各々の順位（σ_i）は、各々のオブジェクト（d_j）を順位（σ_i(d_j)）にマッピングする。最大ｎ個の順位に対する分布（m<=n）を使用することは、例示的な方法で使用されたようなペルムトヘドロンにおいてカラテオドリの定理の結果である。後述するように、順位付けポリシー（π(ｑ)）は、α_i個の係数により提供された比率にできるだけ近い順位のシーケンスに配布できる。目標は、効用性及び公正性基準を含む多重目標最適化問題と関連して、最適のポリシーのセット（π(ｑ)）を探すものである。

７．順位付けポリシーの最適化
例示的な方法は、本明細書においてπ(ｑ)で表される順位付けポリシーを使用でき、これは、全部（例えば、消費者向け効用性及び供給者向け公正性）を単一のセットの決定／最適化変数の側面で表現することで、有用かつ公正であり、これらの変数は本明細書において「制御レバ」として称する。制御レバは、

で表される露出ベクトルを定義する。このベクトルは、オブジェクト別にインデクシングされる（第１の成分は文書（ｄ_１）などに対応する)。これは、頂点座標が順位を示すペルムトヘドロンを用いて定義された決定空間で直接作業する代わりに、本明細書においてエキスポヘドロンとして称する修正のポリトープが開示の方法により使用できることを意味し、ここで、頂点座標は対応する順位と関連付けられた露出を示す。換言すれば、エキスポヘドロンの頂点は、対応する順位によりオブジェクトに提供される露出の順列を示す。ペルムトヘドロンとエキスポヘドロンとの間には１：１対応があり得るが、エキスポヘドロンは制御レバ空間（すなわち、決定空間）を直接示す。

で表される露出ベクトルを更に参照すれば：順位付けポリシーは、最大ｍ個の順位（m<=n）に対する分布、

であり、ここで、

は順位（σ_i）がオブジェクトに提供する露出のベクトルである。

このような最適化問題は多重目標最適化問題として表現できる。パレートセット（すなわち、実行可能な非支配ソリューションのセット）は幾何学的推論により決定できる。次いで、この決定されたパレートセットの特定トレードオフは、例えば、意思決定者により選択又は決定されることができ、ここで、トレードオフは決定空間内の一つのターゲット地点（すなわち、ターゲット露出）である。この地点は、前述したカラテオドリの定理から知られる通り、最大ｎ個の順位の凸結合として分解できる。

一旦、このような組合せが決定される場合、これ（すなわち、順位に対する分布からの複数のオブジェクトのセットの順序化）は、公正なスケジューリング戦略により配布でき、これは、一実施例において黄金比低不一致シーケンスのような低不一致シーケンスを使用する（２０２０年６月インターネット上においてdemofox.orgに公開された“Weighted Round Robin(Weighted Random Integers)Using the Golden Ratio Low Discrepancy Sequence”参照)。当業者は、これに制限されず、ｍ－バランスワード（m-balanced word）または同等にストライドスケジューリングと類似なアルゴリズム（これに制限されない）のような代替的な実施例において、他のスケジューリング戦略が使用され得ることを理解すべきである。

例示的な方法の利点は、幾何学的推論を用いて、様々なステップ又は大部分のステップを遂行できるという点であり、これは、実際に簡単な代数的閉鎖型ソリューションにつながる。例示的な方法の追加の利点は、これらがO(n² log(n))の時間複雑性を与えるという点である。例示的な方法のまた他の利点は、これらが例えばｎ_！次元空間やｎ^２次元空間の代りに、ｎ次元空間で動作するという点である。結果として、例示的な方法により使用された決定／最適化変数の数はｎより大きくなく、これは最大ｎ個の順位に対する分布として任意の最適ソリューションを具現化できるようにする。

「位置基盤モデル（Position-Based Model、PBM）」として称する一般の種類の露出モデルに関する例示的な方法が提供され得る。このような系列のモデルは、オブジェクトの露出がその順位のみに依存すると仮定する。次いで、各々の順位（ｋ）は媒介変数（γk）と関連付けられ、これはこの順位がユーザにより検査される確率を示す。他の種類のモデルが例示的な方法を用いてプロセスできる。

８．ＰＢＭモデルと関連付けられたエキスポヘドロン
実施例において、例示的な方法は、ｎ個の媒介変数の固定セット

を特徴とするＰＢＭ類型露出モデルを使用する。一般性を喪失せず、γ_kが降順に整列されると仮定する。これは、実際によく発生しても、検査確率が順位によって減少することを必ず意味するものではない。このモデルにおいて、順位リスト内のオブジェクト（例えば、文書）の露出の和が常に同一であり、

で表される。ｎ＝３に関するエキスポヘドロンの特定例を図５に示す。露出の総和は例示的な方法で一定であるので、例示的なエキスポヘドロンは、３Ｄ空間に含まれた平面に置かれる。図５はその平面上の投影を示す。

図５に示すエキスポヘドロン内の任意の地点は特定露出ベクトルを示し、このベクトルは最大３個の異なる順列または順位の分布により実現できる。六角形５００の重心５０２は、各々のオブジェクト（例えば、文書）に対する同じ露出（すなわち、人口統計学的公正性）に対応し、但し、３個の異なる順位にわたって均一な分布として実現できる。

地点がエキスポヘドロンに属するか否かを確認する簡単な数学的方法があり、この方法は、本明細書に説明されたような例示的な方法として活用される。これは、数学において主要化（majorization）条件として称し、∈がγにより主要化するとき（これは、

で表される）、かつそのときに限り地点

がエキスポヘドロンに属するということを規定する。

主要化の数学的定義は、次の通りである：

及び

であり、ｘ↓はｘと同じ成分を有するが、降順に整列されたベクトルである。

本明細書で使用される「領域」は、同じ順序の座標（すなわち、露出）を有する地点のセットとして定義される。より具体的に、このような地点は、昇順に整列された成分のインデックスが同一であるようにベクトルに対応できる。例えば、ｐｙｔｈｏｎの場合、これは、ａｒｇｓｏｒｔ関数の出力が同じアレイに対応する。エキスポヘドロンには、頂点の数だけの領域があり、各々の領域が一つの頂点だけを含む。例示的な領域は、無限（unbounded）ピラミッドとして、その頂点は重心であり、その半軸（semi-axis）は、エキスポヘドロンの重心と、領域が含む固有な頂点に隣接した各々のファセットの重心とを連結する線に対応する。

により提供された座標を有するエキスポヘドロンの決定空間内の一つの地点が与えられる場合、例示的な方法は、以下を含み／含んだり考慮することができ、これらの各々は以下のセクションにより詳細に説明する：
この決定空間で順位付けポリシー(π(q)）の効用性を定義し；
この決定空間で順位付けポリシーに対して異なる公正性測定を定義し；
多重目標最適化（Multi-objective Optimization、MOO）問題に対応するパレートセット（非支配ポリシーのセット）を決定して効用性及び公正性のバランスを維持し；
このパレートセットに対する意思決定者によるターゲット露出の特定選択を最大ｎ個の順位に対する分布として分解し；
効率的かつ効果的なスケジューリング戦略により最大ｎ個の順位に対する分布を配布する。

９．ＰＢＭ－エキスポヘドロンにおける効用性
例示的な効用性基準は、関連性点数が高いか、或いは、より一般的に利得の高いオブジェクトがさらに高い露出を有さなければならないと規定する。一般性を喪失せず、ρは、

である意味から、与えられたＰＢＭに対して常数の露出ベクトルと同じ単位で正規化した利得のベクトル（または、利得関数が恒等として選択された場合、関連性点数）として定義される。これは、ρが露出ベクトルと同じ超平面上に位置し、それらが投影されたエキスポヘドロン上で共同に直接比較されたり、構成されたり、または視覚化したりできることを意味する。

効用性は、例えば、関連性ベクトル及び露出ベクトル間のドット積で表現できる：

結果として、エキスポヘドロンにおいて等価効用性表面は、超平面７０２、７０４、７０６に対し、図７に例示したように、法線がρと同じ超平面である。効用性に関する定義は、２^関連性（２^relevance）としての利得関数及び露出媒介変数の特定選択に関する情報検索の効用性に対する標準割引累積利得（Discounted Cumulative Gain、DCG）定義に対応し、すなわち：

である。

このような効用性の数学的表現が与えられる場合、エキスポヘドロンの最大効用性順位付けポリシーは、ρに対する投影、すなわち

が最大のエキスポヘドロンの面上に位置した地点（∈）（または一部の例示的な方法では地点のセット）を用いて探すことができる（例えば、図７の面７１０上の地点７０８を参照）。この最大効用性順位を探すために、エキスポヘドロンのすべての地点を投影する必要なしに、単一の整列作業を必要とするρと同じ領域にある頂点のみに対して投影してよい。これは、情報検索の確率順位原則と同じ公式である（文献[Stephen Robertson、“The Probability Ranking Principle in IR”、Journal of Documentation、33:294-304、December 1977]]参照）。

関連性ベクトルがタイ（tie）を有する場合（すなわち、関連性ベクトルの少なくとも２つの要素が同じ場合）、図８にタイと共に示すように（関連性ベクトル[０.７、０.７、０.４]に示すように）、全体面８０２は、最大効用性ソリューションのセットを構成する。

１０．ＰＢＭ－エキスポヘドロンにおける公正性
エキスポヘドロンフレームワークにおいて例示的な公正性基準が表現される。個別人口統計学的公正性の基準は、理想的にすべてのオブジェクト（例えば、文書）が同じ露出を有さなければならないと明示する。露出の和が常数であるので、これは人口統計学的公正性ポリシーのターゲット露出がエキスポヘドロンの重心であることを意味する：

したがって、公正性の基準は、２次関数、例えば重心に対する近接性（または、距離縮小）として定義できる：

能力主義公正性を考慮すれば、理想的な露出ベクトルは、関連性ベクトル又は一般的にρ'で表されるメリット（merit）ベクトルに比例しなければならず、ここで、オブジェクトのメリットは、このオブジェクトの関連性点数または同等にその利得の単調増加関数として定義される（

という意味から、露出ベクトルと同じ単位に正規化したメリットベクトルとして作業するとき、比例常数はここで１と同様である）。ρ及びρ’は、これらを連結する単調増加関係により同じ領域に位置する。ρ及びρ’は、必ずしもそうである必要はないが、同一に選択されて関連性点数ベクトルと同一であり得る（すなわち、利得及びメリット関数が恒等関数として選択される）。公式的に、露出（∈）を有するポリシーの能力主義公正性は、２次関数、例えば、正規化した関連性ベクトルに対する近接性（または距離縮小）として定義できる：

ρ及びρ'が同一に選択された、図９に示すようにエキスポヘドロン（ｎ＝３）９００において、人口統計学的公正性９０２及び能力主義公正性９０４に対し、等価公正性表面はβ又はρを中心とした超球体であり、最適の人口統計学的及び能力主義公正性の等価公正性曲線は、各々最適の公正性地点９０２、９０４を囲む円であり、ここで、ベクトル９０６は関連性ベクトルである。

メリットベクトルがエキスポヘドロンの外部にある場合、すなわち、

である場合（すなわち、主要化条件を満たさない）が発生し得る。このとき、純粋比例関係をアフィン（affine）関係に緩和させることができ、オフセットは相変らずエキスポヘドロンにある間はできるだけ小さい（例えば、文献[Biega et al.、“Overview of the TREC 2019 Fair Ranking Track”、arXiv:2003.11650、March 2020]、及び文献[Diaz et al.、“Evaluating Stochastic Rankings with Expected Exposure”、Proceedings of the 29^th ACM International Conference on Information & Knowledge Management、pages 275-284、October 2020]に表現されたような公正性定義）。これは、メリットベクトル軸及びエキスポヘドロンの境界の交差点にあるターゲットベクトルを選択するものと同様である。

図１０は、メリットベクトル１００２により識別される最適地点１００４がエキスポヘドロン１０００の外部にあるため、実行不可能な例を示す。この新しい実現可能なターゲットベクトルは地点１００６に表示される。これは、次の通り計算できる：

で表される。

関連性ベクトル軸及びエキスポヘドロンの境界の交差点は、正規化したメリット

のアフィン変換（図１０において「アフィン変換」として称する）により与えられる：

であり、これは

であり、ｂが条件∀k < nを保証する最小値であることを表現し；

であり、これは

であることを表現する。

実行可能な能力主義公正性の地点を選択するためのアフィン変換に対する代替的なソリューションは、直交投影を計算するものであり、これに関して、図１０に示す例に対する結果が地点１００８に表示される。

１１．ＰＢＭ－エキスポヘドロンにおけるパレートセット
効用性と公正性を個別的に計算する方法及び最適化する方法を決定すれば、多重目標効用性－公正性問題の完全なパレートセットを計算できる。

方法を直観的かつ幾何学的に説明すれば、例示的な計算方法は、パレートセットの一つの極端（extreme：エクストリーム）、すなわち「全的に公正な」ソリューションから始まる。次いで、全体のパレートセットを描く（例えば、計算する）ために、利得ベクトルの方向に（計算的に）沿う。これらのすべての地点は、エキスポヘドロンの他の地点により支配されず、公正性及び効用性間の最適のトレードオフに対応することがわかる。利得ベクトルの方向を常に沿う場合、エキスポヘドロンの境界が必ず特定地点で交差することになり、これは、ソリューションがそれ以上実現不可能であることを意味する。次いで、直に交差した（ｎ－２）次元ファセット上に投影された利得ベクトルの方向に（計算的に）沿う。この新しい方向に沿うことで、今度は（ｎ－３）次元である新しい面が交差され、もう一度その新しい面上に投影された利得ベクトルの方向に沿うことになる。任意の面の利得ベクトルの投影を探すことは、閉形式表現（closed-form expression）に該当する。この経路追跡手順は、最終的に非支配最大効用性ソリューションに到達するまで計算的に再度繰り返される。その経路に沿ってすべての地点は、効用性－公正性トレードオフの強力な非支配ソリューションに対応し、換言すれば、経路はパレートセットである。

前述した経路追跡手順がｎ＝３及び恒等関数（すなわち、文書のメリット及び利得がその関連性点数と同一である）として選択された利得及びメリット関数に関して図１１に例示している。パレートセットは、人口統計学的公正性の基準が使用される場合に１１０２から１１１０まで、能力主義公正性の基準が使用される場合に１１０６から１１１０まで、定義される。人口統計学的公正性の基準が使用される場合、パレートセットはグラフの重心１１０２から始まり、線分１１０４の方向（これは利得ベクトル軸である）に沿うが、これはグラフ上の能力主義公正性地点１１０６を通過して、オブジェクト（例えば、文書）ｄ_１及びｄ_２が最初２つの順位で順列される混合順位に対応するエッジ１１０８またはファセットと交差し、次いで、グラフ上で星１１１０で表示される最大効用性ソリューションに到達するまで、このファセットに沿う。能力主義公正性の基準が使用される場合、パレートセットは地点１１０６から始まるべきである。

より公式的に記述すれば、パレート最適セットは、i = 1,...,(n－1)である場合、

を

に連結する（ｎ－１）個の線分の和集合である。次に、一般性を喪失せず、表記の単純性のために、オブジェクト（例えば、文書）が利得の降順、すなわちρ₁>=ρ₂>=...>=ρ_nである

に整列されると仮定する。初期地点

は、人口統計学的又は能力主義公正性を考慮するか否かにより、β又はρ’である（

に代替することは不可能である）。パレートセットを設定する際に、地点は常に同じ領域に位置する（すなわち、最大効用性またはＰＲＰ頂点の領域；すべての領域が頂点に重心を有するため、重心はすべての領域に属するという点に注意する）。その理由は、対応する露出ベクトルの成分の順序が、利得ベクトルの方向のベクトルがこのような露出ベクトルに増分的に追加される場合、面に投影されても変更されないからである。

パレートセット構築方法の一実施例が意思コードとして図１２に説明されている。より具体的に、図１２は、パレートセット識別のための意思コードを説明し、これは（一般性を喪失せず）利得ベクトル

各々の順位と関連付けられたＰＢＭ媒介変数のベクトル（γ）、及び、初期地点

が、最高値を持つものから最小値を持つものの順に整列される、整列された保存領域にあると仮定する。

１２．ＰＢＭ－エキスポヘドロンにおけるＧＬＳ分解
本明細書に説明されたように、例えば、意思決定者により選択され得るパレートセット内の一つの地点は、決定空間内でターゲット露出に変換できる。パレートセット内のこの地点は最大ｎ個の順位の凸結合に分解できる。この分解問題を始まるために、例示的な方法は、前述した一般ＧＬＳ手順を特殊化し、エキスポヘッドのポリトープの構造に適用できる。

分解を実現するための一実施例が、図６の意思コードとして説明される。図６の分解方法は、一つの地点がファセット（または、さらに低い次元の面）にある場合、このファセット（または面）上の頂点は、地点が位置した領域の頂点を選択することにより（これは地点の成分を整列して遂行され得る）、探すことができるという事実を利用する（図６の５行参照）。このステップは、O(n log n)の複雑性を有することに注意する。

図６の９行で例示的な方法は、ファセット（すなわち、面）に到達するまで、v⁽ⁱ⁾ → x⁽ⁱ⁾線分を延長する地点を探し、この交差地点（x⁽ⁱ⁺¹⁾）は再帰的に分解される新しい地点を定義する。ループの各々の繰り返しにおいて、新しい地点（x⁽ⁱ⁺¹⁾）は次元（ｎ－ｉ）の面上にあり、これは最終地点が常に頂点（次元＝０）となることを意味する。交差点を探すことは、「主要化（Majorization）」条件の根（すなわち、条件値が真から偽に行く地点）を探すものと同一であるので、図６の９行で主要化基準を使用して二分法（Bisection method）（すなわち、提供された関数の根を探す数値的方法）が適用されて方法の中止時点を感知する。また、主要化基準は、面（λ）との交差点で効率的な上端終点を探すために活用できる（ここで、効率的な上端終点は「真の交差点からあまり遠くない」ことを意味するために本明細書で使用される）。この終点の計算は、図６の６行乃至８行で遂行される。

二分法そのものは、ｎと独立的な多数の繰り返し（例えば、５乃至１０回の繰り返し）を有する。二分法内で主要化条件を確認しようとすれば、O(n log n)複雑度が必要なので、この方法の全体の複雑度はO(n² log n)である。

１３．低不一致シーケンスによるポリシー配布
ターゲット露出を順位による分布に分解する場合、順位のシーケンスの形態で分布を配布するために、様々な方法のうち、任意の方法を単独または組合せにより使用できる。

例えば、確率的サンプリング（すなわち、乱数生成器）が順位に対する分布を配布するのに使用できる。他の実施例において、低不一致シーケンスが使用され得る（例えば、文献[Martin Roberts、“The unreasonable effectiveness of quasirandom sequences”、Apr 2018参照）。

低不一致シーケンス（ＬＤＳ）は、すべてのｔに対して順位R₁,R₂,…,R_tの下位シーケンスが低不一致を有するように提供される（すなわち、順位の比率が所望の比率、すなわち無限シーケンスの比率に近い)。低不一致シーケンスは、典型的に均一分布にできるだけ近い[０、１]間隔の類似乱数シーケンスであり、[０、１]にあるこのような浮動小数点シーケンスは、生成された浮動小数点を比率の累積値と比較することで、所望の比率を有する順位のシーケンスに変換できる。

無理数（クロネッカー（Kronecker）、ワイル（Weyl）又はリヒトマイヤー（Richtmyer）シーケンスであると称する）に基づいた加法－再帰シーケンスの使用は、実施例において、特に一部の意味で最も無理数である黄金費に対して使用され得る。シーケンスの一般的な再帰形式は、次の通りである：

であり、これは、ＬＤＳの加法－再帰シーケンスクラスに対する最適の不一致を達成する値である。

低不一致シーケンスの以外の効率的なサンプリング戦略の系列が、代替的又は付加的に使用され得る。例えば、ストライドスケジューリングまたは同等にｍ－バランスワードに基づいた戦略も使用でき、非常に類似の性能を提供できる。

例示的な問題に関して表現すれば、ｍ－バランスワードの生成器は、同じ長さの下位シーケンスの任意の対から、任意の順位の頻度が最大ｍだけ変化する順位のシーケンスを生成する。換言すれば、この生成器は、生成されたシーケンスがターゲット比率に最大限近い比率を有する順位を算出するように保証する。理論に拘束されることを希望しないが、理論上に最も良い達成可能なｍは、例示の場合に最大ｎ－１である。特定分布の順位の分布が提供される場合、順位のｍ－バランスシーケンスを效率的に生成できる例示的なアルゴリズムが、文献[Shinya Sano、Naoto Miyoshi、and Ryohei Kataoka.2004.m-Balanced words:A generalization of balanced words. Theoretical Computer Science 314、1-2(Feb.2004)、97-120.https://doi.org/10.1016/j.tcs.2003.11.021]のアルゴリズム（１）に提供される。この生成器は、例えば、文献[C.A.Waldspurger及びE.Weihl.W.1995.Stride Scheduling:Deterministic Proportional-Share Resource Management.Technical Report.Massachusetts Institute of Technology、USA]に記述されたように、同時プロセスに対するリソース（ＣＰＵ）管理で公正なシーケンスを生成するのに使用される、公知のストライドスケジューリングアルゴリズムと同様である。

１４．コンピュータプログラム製品
オブジェクトを順位付けするために説明された例示的な方法は、コンピュータプログラム製品として提供でき、これは（例えば、サーバー１００及びクライアントデバイス１０２のデータプロセッサ１１２を使用して）、この方法を実行するためのコード命令語、及びこのようなコード命令語を保存するためにこのコンピュータプログラム製品と共に提供されるコンピュータ装備（例えば、サーバー１００及びクライアントデバイス１０２のメモリ１１３を使用する）により読み取り可能な保存手段を含むことができる。

１５．一般
前述した説明は、本質的に例示的なものだけであり、本開示内容、そのアプリケーションまたは使用を制限するものではない。本開示内容の広範囲な教示は多様な形態で具現化できる。したがって、本開示内容は特定例を含むが、本開示内容の真の範囲はそれらに制限されるものではない。これは図面、明細書及び特許請求の範囲の研究により他の変形が明白になるからである。方法内の一つ以上のステップは、本開示内容の原理を変更せず、異なる順序に（または同時に）実行され得ることを理解しなければならない。また、各々の実施例は、所定の特徴を持つものと前述されたが、本開示内容の任意の実施例と関連して記述されたこれらの特徴のうち、任意の一つ以上は任意の他の実施例の特徴で具現化され／具現化されたり結合され得るが、その組合せは明示的に記述されない。換言すれば、記述された実施例は相互排他的でなく、一つ以上の実施例の互いの順列は本開示内容の範囲内にある。本明細書に引用された任意の文献は、これらの文献が先行技術を構成するということを認定せず、その全体が参考としてここに含まれる。

各モジュールは、一つ以上のインタフェース回路を含むことができる。一部の例において、インタフェース回路は、近距離通信網（ＬＡＮ）、インターネット、広域通信網（ＷＡＮ）またはこれらの組合せにより連結された有線又は無線インタフェースを含むことができる。本開示内容の任意の提供されたモジュールの機能は、インタフェース回路により連結された多数のモジュールに分散できる。例えば、多数のモジュールが負荷バランス（load balancing）を許容することができる。他の例において、サーバー（リモート又はクラウドと知らされる）モジュールは、クライアントモジュールの代わりに一部の機能を達成できる。各々のモジュールは、コードを用いて具現化できる。前記使用された用語コードは、ソフトウェア、ファームウエア及び／又はマイクロコードを含むことができ、プログラム、ルーチン、機能、クラス、データ構造及び／又はオブジェクトを称することができる。

本明細書のメモリ回路は、コンピュータ読取り可能な媒体のサブセットである。本明細書のコンピュータ読取り可能な媒体は（例えば、搬送波上において）、媒体を介して伝播される一時的な電気又は電磁気信号を含まず；したがって、コンピュータ読み取り可能な媒体は、類型及び非一時的なものとみなすことができる。非一時的及び類型のコンピュータ読取り可能な媒体の非制約的な例は、不揮発性メモリ回路（例えば、フラッシュメモリ回路、消去可能なプログラム可能読取り専用メモリ回路、またはマスク読取り専用メモリ回路）、揮発性メモリ回路（例えば、静的ランダムアクセスメモリ回路、動的ランダムアクセスメモリ回路）、磁気保存媒体（例えば、アナログ又はデジタル磁気テープまたはハードディスクドライブ）、及び、光学保存媒体（例えば、ＣＤ、ＤＶＤまたはブルーレイディスク）を含む。

本出願に説明されたシステム及び方法は、コンピュータプログラムで具現化された一つ以上の特定機能を実行するように、汎用コンピュータを構成することにより生成された特殊目的コンピュータにより部分的又は完全に具現化できる。前述した機能ブロック、フローチャート構成要素及びその他の要素は、熟練された技術者又はプログラマの日常的な作業により、コンピュータプログラムに変換できるソフトウェア仕様として役割を果たす。

コンピュータプログラムは、少なくとも一つのプロセッサ実行可能な命令語を含む。コンピュータプログラムは、また、保存されたデータを含むか、或いは、それに依存し得る。コンピュータプログラムは、特殊目的コンピュータのハードウェアと相互作用する基本入／出力システム（ＢＩＯＳ）、特殊目的コンピュータの特定デバイスと相互作用するデバイスドライバ、一つ以上の運営体制、ユーザアプリケーション、背景サービス、背景アプリケーションなどを含むことができる。

前述した実施例の変形例及び他の特徴及び機能、またはその代替を、好ましくは多くの異なるシステムまたは応用により組合わせることができる。また、現在予測不可能な多様な代替、修正、変形、または改善が、当業者により後続的になされることができ、これらは前記説明及び特許請求の範囲内に属するものと理解しなければならない。

Claims (23)

1. 複数のオブジェクトのセットを順位付けするためのコンピュータで実施される方法であって、
   前記コンピュータのプロセッサが、前記複数のオブジェクトのセット及び複数の目標関数のセットを受信するステップ；
   前記プロセッサが、位置基板モデル（position-Based Model, PBM）に関連付けられたパームトヘドロン（permutohedron）を用いて、ｎ個の決定変数を有する決定空間を定義するステップであって、前記決定変数は情報検索結果に対応するオブジェクトの露出の順位付けについて最適化の対象になる変数であり、前記決定空間は前記決定変数によって規定される空間であり、ｎは順位付けするオブジェクトの数である、ステップ；
   前記プロセッサが、前記複数の目標関数のセットに対する、多重目標最適化（Multi-objective Optimization, MOO）問題に対応するパレートセットを決定するステップであって、前記パレートセットは、前記決定空間から関連する露出の順位付けの凸結合に基づいて決定されたファセットの重心からエッジに交差し、前記ファセットの頂点に到達する経路であり、前記決定するステップは、幾何学的推論を使用して決定される、ステップ；
   前記プロセッサが、パレート点を前記パレートセット内として、前記決定空間を用いて、前記セット内の前記オブジェクトに関する順位に対する分布を、ＧＬＳ（Grotschel、Lovasz and Schrijver）手順を使用して決定するステップであって、前記分布内の各々の順位に係数が関連付けられる、ステップ；
   前記プロセッサが、係数により前記順位に対する分布から前記セット内の前記オブジェクトに関する一連の順位を選択するステップであって、前記セット内の前記オブジェクトに関する一連の順位を選択するステップには、確率的サンプリング、低不一致シーケンス、加算繰り返しシーケンス、ストライドスケジューリングまたはｍ－バランスの一つ以上を使用するステップが含まれる、ステップ；
   前記プロセッサが、前記選択された一連の順位を出力するステップ；及び、
   前記プロセッサが、前記セット内の各々のオブジェクトに対する関連性点数及び順位と各々関連付けられた、前記セット内の前記オブジェクトに提供される露出のリスト、順位付け公正性目標関数、及び順位付け効用性目標関数を受信するステップ；を含み、
   前記複数の目標関数のセットは、２次関数及び線形関数を含み、
   前記２次関数は公正性関数を含み、前記線形関数は効用性関数を含み、前記公正性関数は、前記決定変数から構成されるベクトルとターゲットベクトルとの間の差の正規化した関数であり、前記効用性関数は、ユーザが結果のセットにアクセスする関連性点数が高いことを示す線形関数である、コンピュータで実施される方法。
2. 前記複数の目標関数のセットは、公正性関数及び効用性関数を含み、前記公正性関数は、前記決定変数から構成されるベクトルとターゲットベクトルとの間の差の正規化した関数であり、前記効用性関数は、ユーザがアクセスする関連性点数が高いことを示す線形関数である、請求項１に記載のコンピュータで実施される方法。
3. 前記公正性関数は、正規化した関数である、請求項１又は２に記載のコンピュータで実施される方法。
4. 前記正規化した関数は、自乗Ｌ２－ｎｏｒｍ関数である、請求項３に記載のコンピュータで実施される方法。
5. 前記プロセッサが、前記目標関数のセットに対する前記パレートセットを決定するステップは、前記プロセッサが、前記順位付け公正性目標関数及び前記順位付け効用性目標関数を使用して、前記決定空間内においてカラテオドリの定理を用いて前記パレートセットを計算するステップを含む、請求項１に記載のコンピュータで実施される方法。
6. 前記プロセッサが、前記決定空間を用いて、前記セット内の前記オブジェクトに関する前記順位に対する分布を決定するステップは、前記セット内の前記オブジェクトの数に対し：
   （ｉ）前記プロセッサが、前記決定空間の任意の頂点を決定するステップ；
   （ｉｉ）前記プロセッサが、線が前記決定空間の面と交差するまで、ターゲット露出により前記任意の頂点から始まる前記線を描くステップ；及び、
   （ｉｉｉ）前記プロセッサが、新しく交差された前記面が頂点となるまで、前記ターゲット露出の代わりに、前記新しい交差地点を用いて、前記決定空間の前記交差された面上において、（ｉ）及び（ｉｉ）を繰り返すステップ；をさらに含み、
   前記決定空間の各々の頂点は、前記順位に対する分布において関連付けられた係数を有する、請求項５に記載のコンピュータで実施される方法。
7. 前記複数の目標関数のセットは、公正性関数及び効用性関数を含み、
   前記公正性関数は、正規化した関連性ベクトルに対する近接性として定義できる能力主義公正性に基づく、請求項１に記載のコンピュータで実施される方法。
8. 前記複数の目標関数のセットは、公正性関数及び効用性関数を含み、
   前記公正性関数は、各々のオブジェクトに対する同じ露出に対応する人口統計学的公正性に基づく、請求項１に記載のコンピュータで実施される方法。
9. 前記セット内の前記オブジェクトは、複数のクエリを含む、請求項１に記載のコンピュータで実施される方法。
10. 前記セット内の前記オブジェクトは、複数の文書を含む、請求項１に記載のコンピュータで実施される方法。
11. 前記セット内の前記オブジェクトは、クエリに応じて識別される、請求項１に記載のコンピュータで実施される方法。
12. 前記セット内の前記オブジェクトは、複数の推薦を含む、請求項１に記載のコンピュータで実施される方法。
13. 前記セット内の前記オブジェクトは、地図位置に応じて識別される、請求項１に記載のコンピュータで実施される方法。
14. 前記プロセッサが、前記出力するステップは、
    前記プロセッサが、前記選択された順位のシーケンスにより順位付けされた前記複数のオブジェクトのセットの少なくともサブセットを、デバイスのディスプレイ上にディスプレイするために提供するステップを含む、請求項１に記載のコンピュータで実施される方法。
15. 前記複数のオブジェクトのセットの前記少なくともサブセットは、検索エンジン結果ページ上に提供される、請求項１に記載のコンピュータで実施される方法。
16. 非一時的な機械読取り可能な命令語を含むコンピュータプログラムであって、
    前記命令語は、コンピュータ上で実行されると、前記コンピュータのプロセッサが以下の方法を遂行するようにし、前記方法は：
    複数のオブジェクトのセット及び複数の目標関数のセットを受信するステップ；
    位置基板モデル（position-Based Model, PBM）に関連付けられたパームトヘドロンを用いて、ｎ個の決定変数を有する決定空間を定義するステップであって、前記決定変数はオブジェクトの露出の順位付けについて最適化の対象になる変数であり、前記決定空間は情報検索結果に対応する前記決定変数によって規定される空間であり、ｎは順位付けするオブジェクトの数である、ステップ；
    前記複数の目標関数のセットに対する、多重目標最適化（Multi-objective Optimization, MOO）問題に対応するパレートセットを決定するステップであって、前記パレートセットは、前記決定空間から関連する露出の順位付けの凸結合に基づいて決定されたファセットの重心からエッジに交差し、前記ファセットの頂点に到達する経路であり、前記決定するステップは、幾何学的推論を使用して決定される、ステップ；
    パレート点を前記パレートセット内とし、前記決定空間を用いて、前記セット内の前記オブジェクトに関する順位に対する分布を、ＧＬＳ（Grotschel、Lovasz and Schrijver）手順を使用して決定するステップであって、前記分布内の各々の順位に係数が関連付けられる、ステップ；
    係数により前記順位に対する分布から前記セット内の前記オブジェクトに関する一連の順位を選択するステップであって、前記セット内の前記オブジェクトに関する一連の順位を選択するステップには、確率的サンプリング、低不一致シーケンス、加算繰り返しシーケンス、ストライドスケジューリングまたはｍ－バランスの一つ以上を使用するステップが含まれる、ステップ；
    前記選択された一連の順位を出力するステップ；及び、
    前記セット内の各々のオブジェクトに対する関連性点数及び順位と各々関連付けられた、前記セット内の前記オブジェクトに提供される露出のリスト、順位付け公正性目標関数、及び順位付け効用性目標関数を受信するステップ；を含む、コンピュータプログラム。
17. 方法を遂行するように構成されたプロセッサを含むデータプロセシングデバイスであって、
    前記方法は、
    前記プロセッサが、複数のオブジェクトのセット及び複数の目標関数のセットを受信するステップ；
    前記プロセッサが、位置基板モデル（position-Based Model, PBM）に関連付けられたパームトヘドロンを用いて、ｎ個の決定変数を有する決定空間を定義するステップであって、前記決定変数は情報検索結果に対応するオブジェクトの露出の順位付けについて最適化の対象になる変数であり、前記決定空間は前記決定変数によって規定される空間であり、ｎは順位付けするオブジェクトの数である、ステップ；
    前記プロセッサが、前記複数の目標関数のセットに対する、多重目標最適化（Multi-objective Optimization, MOO）問題に対応するパレートセットを決定するステップであって、前記パレートセットは、前記決定空間から関連する露出の順位付けの凸結合に基づいて決定されたファセットの重心からエッジに交差し、前記ファセットの頂点に到達する経路であり、前記決定するステップは、幾何学的推論を使用して決定される、ステップ；
    前記プロセッサが、パレート点を前記パレートセット内とし、前記決定空間を用いて、前記セット内の前記オブジェクトに関する順位に対する分布を、ＧＬＳ（Grotschel、Lovasz and Schrijver）手順を使用して決定するステップであって、前記分布内の各々の順位に係数が関連付けられるステップ；
    前記プロセッサが、係数により前記順位に対する分布から前記セット内の前記オブジェクトに関する一連の順位を選択するステップであって、前記セット内の前記オブジェクトに関する一連の順位を選択するステップには、確率的サンプリング、低不一致シーケンス、加算繰り返しシーケンス、ストライドスケジューリングまたはｍ－バランスの一つ以上を使用するステップが含まれる、ステップ；
    前記プロセッサが、前記選択された一連の順位を出力するステップ；及び、
    前記プロセッサが、前記セット内の各々のオブジェクトに対する関連性点数及び順位と各々関連付けられた、前記セット内の前記オブジェクトに提供される露出のリスト、順位付け公正性目標関数、及び順位付け効用性目標関数を受信するステップ；を含む、データプロセシングデバイス。
18. 前記データプロセシングデバイスは、２つのステップの情報検索システムのための第２のステップのランカーに統合される、請求項１７に記載のデータプロセシングデバイス。
19. 前記データプロセシングデバイスは、サーバーを含む、請求項１７又は１８に記載のデータプロセシングデバイス。
20. 前記データプロセシングデバイスは、クライアントデバイスを含む、請求項１７又は１８に記載のデータプロセシングデバイス。
21. 情報検索システムであって、
    クエリを受信し、複数のオブジェクトのセットを生成するように構成されたコンピュータで実施される第１のステップの検索器；及び、
    コンピュータで実施される第２のステップのランカー；を含み、前記コンピュータで実施される第２のステップのランカーは、
    前記複数のオブジェクトのセット及び複数の目標関数のセットを受信し、
    位置基板モデル（position-Based Model, PBM）に関連付けられたパームトヘドロンを用いて、ｎ個の決定変数を有する決定空間を定義することであって、前記決定変数は情報検索結果に対応するオブジェクトの露出の順位付けについて最適化の対象になる変数であり、前記決定空間は前記決定変数によって規定される空間であり、ｎは順位付けするオブジェクトの数であり、
    前記複数の目標関数のセットに対する、多重目標最適化（Multi-objective Optimization, MOO）問題に対応するパレートセットを決定することであって、前記パレートセットは、前記決定空間から関連する露出の順位付けの凸結合に基づいて決定されたファセットの重心からエッジに交差し、前記ファセットの頂点に到達する経路であり、前記決定することは、幾何学的推論を使用して決定され、
    パレート点を前記パレートセット内とし、前記決定空間を用いて、前記セット内の前記オブジェクトに関する順位に対する分布を、ＧＬＳ（Grotschel、Lovasz and Schrijver）手順を使用して決定することであって、前記分布内の各々の順位に係数が関連付けられ、
    係数により前記順位に対する分布から前記セット内の前記オブジェクトに関する一連の順位を選択することであって、前記セット内の前記オブジェクトに関する一連の順位を選択するステップには、確率的サンプリング、低不一致シーケンス、加算繰り返しシーケンス、ストライドスケジューリングまたはｍ－バランスの一つ以上を使用することが含まれ、
    前記選択された一連の順位を出力し、
    前記セット内の各々のオブジェクトに対する関連性点数及び順位と各々関連付けられた、前記セット内の前記オブジェクトに提供される露出のリスト、順位付け公正性目標関数、及び順位付け効用性目標関数を受信するように構成される、情報検索システム。
22. 前記出力することは、前記ランカーが、前記選択された順位のシーケンスにより順位付けされた前記複数のオブジェクトのセットの少なくともサブセットを、デバイスのディスプレイ上にディスプレイするために提供することを含む、請求項２１に記載の情報検索システム。
23. 前記複数のオブジェクトのセットの前記少なくともサブセットは、サーバー又はクライアントデバイスのディスプレイ上にディスプレイするために、検索エンジン結果ページに提供される、請求項２２に記載の情報検索システム。