論文の概要: The complexity of unsupervised learning of lexicographic preferences

• arxiv url: http://arxiv.org/abs/2209.11505v1
• Date: Fri, 23 Sep 2022 10:08:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-26 13:42:46.901448
• Title: The complexity of unsupervised learning of lexicographic preferences
• Title（参考訳）: 辞書選好の教師なし学習の複雑さ
• Authors: H\'el\`ene Fargier (IRIT-ADRIA, ANITI), Pierre-Fran\c{c}ois Gimenez (CIDRE), J\'er\^ome Mengin (IRIT-ADRIA, ANITI), Bao Ngoc Le Nguyen (INSA Toulouse)
• Abstract要約: 本稿では,非理論的な代替案に対するユーザの嗜好を学習する作業について考察する。 そこで我々は,これまで選択された選択肢を可能な限り高くランク付けした,ユーザの好みのモデルについて学習するアプローチを提案する。 経験的リスクは線形LP-ツリーのクラスに制限された時間内に達成できることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper considers the task of learning users' preferences on a combinatorial set of alternatives, as generally used by online configurators, for example. In many settings, only a set of selected alternatives during past interactions is available to the learner. Fargier et al. [2018] propose an approach to learn, in such a setting, a model of the users' preferences that ranks previously chosen alternatives as high as possible; and an algorithm to learn, in this setting, a particular model of preferences: lexicographic preferences trees (LP-trees). In this paper, we study complexity-theoretical problems related to this approach. We give an upper bound on the sample complexity of learning an LP-tree, which is logarithmic in the number of attributes. We also prove that computing the LP tree that minimises the empirical risk can be done in polynomial time when restricted to the class of linear LP-trees.
• Abstract（参考訳）: 本稿では,オンラインコンビネータで一般的に使用される,コンビネータの選択肢セットに対するユーザの嗜好を学習するタスクについて考察する。 多くの設定では、過去のインタラクション中に選択された選択肢のセットのみが学習者に提供される。 fargierとal。 [2018] では,これまでに選択した選択肢を可能な限り高いランクでランク付けするユーザの好みのモデルと,この設定において,特定の好みのモデルである語彙的嗜好木(LP木)を学習するアルゴリズムを提案する。 本稿では,このアプローチに関連する複雑性理論問題について考察する。 属性数に対数的であるLP木を学習する際のサンプルの複雑さに上限を与える。 また,経験的リスクを最小化するlp木を線形lp木のクラスに制限した場合,多項式時間で計算できることを証明した。

関連論文リスト

• Relative Preference Optimization: Enhancing LLM Alignment through Contrasting Responses across Identical and Diverse Prompts [95.09994361995389]
  Relative Preference Optimization (RPO) は、同一のプロンプトと関連するプロンプトの両方から、より多く、あまり好まれない応答を識別するように設計されている。 RPOは、大きな言語モデルをユーザの好みに合わせて調整し、トレーニングプロセスにおける適応性を改善する優れた能力を示している。
  論文  参考訳（メタデータ） (2024-02-12T22:47:57Z)
• Tree Learning: Optimal Algorithms and Sample Complexity [10.638365461509]
  任意の分布から抽出したラベル付きサンプルから,データの階層木表現を学習する問題について検討する。 本稿では,この問題に対する最適なサンプル境界を,学習やオンライン学習など,いくつかの学習環境において提示する。
  論文  参考訳（メタデータ） (2023-02-09T08:35:17Z)
• Context-Aware Ensemble Learning for Time Series [11.716677452529114]
  本稿では,ベースモデルの特徴ベクトルの結合である特徴のスーパーセットを用いて,ベースモデル予測を効果的に組み合わせたメタ学習手法を提案する。 我々のモデルは、ベースモデルの予測を機械学習アルゴリズムの入力として使用するのではなく、問題の状態に基づいて各時点における最良の組み合わせを選択する。
  論文  参考訳（メタデータ） (2022-11-30T10:36:13Z)
• Improved Robust Algorithms for Learning with Discriminative Feature Feedback [21.58493386054356]
  識別的特徴フィードバック(英: Discriminative Feature Feedback)は、人間の教師によって提供される特徴説明に基づく対話型学習のためのプロトコルである。 我々は、識別的特徴フィードバックモデルのための、新しい堅牢な対話型学習アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-09-08T12:11:12Z)
• Fast Offline Policy Optimization for Large Scale Recommendation [74.78213147859236]
  我々は、カタログサイズと対数的にスケールするこれらのポリシー学習アルゴリズムの近似を導出する。 私たちの貢献は3つの新しいアイデアの組み合わせに基づいている。 我々の推定器は、単純なアプローチよりも桁違いに速いが、等しく良いポリシーを生成する。
  論文  参考訳（メタデータ） (2022-08-08T11:54:11Z)
• Ensemble pruning via an integer programming approach with diversity constraints [0.0]
  本稿では、二項分類問題を考察し、最適部分集合を選択する整数プログラミング(IP)アプローチを提案する。 アンサンブルにおける最小の多様性レベルを確保するための制約も提案する。 本手法は, 文学において最もよく使われている刈り取り法と比較して, 競争力のある結果をもたらす。
  論文  参考訳（メタデータ） (2022-05-02T17:59:11Z)
• Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
  この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。 古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2022-02-09T19:22:34Z)
• Sample Complexity of Tree Search Configuration: Cutting Planes and Beyond [98.92725321081994]
  最先端の解法は、根底にある木探索アルゴリズムを高速化するために、無数の切削平面技術を統合している。 本研究は,インスタンス分布に合わせて高い性能のカット選択ポリシーを学習するための最初の保証を証明した。
  論文  参考訳（メタデータ） (2021-06-08T00:57:59Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)
• Learning Choice Functions via Pareto-Embeddings [3.1410342959104725]
  本稿では,各オブジェクトが特徴ベクトルで表現される対象の集合から選択することの難しさを考察する。 本稿では,この課題に適した識別可能な損失関数を最小化する学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-07-14T09:34:44Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。