論文の概要: Partitioned Least Squares
- arxiv url: http://arxiv.org/abs/2006.16202v2
- Date: Sat, 29 Jun 2024 09:40:27 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-02 18:47:18.466048
- Title: Partitioned Least Squares
- Title(参考訳): 分割レストスクエア
- Authors: Roberto Esposito, Mattia Cerrato, Marco Locatelli,
- Abstract要約: 新たな定式化は凸ではなく,この問題に対処するための2つの代替手法を提供する。
完全性のために、分割数が大きすぎる場合に正確な方法の代わりに使用できる代替分岐および有界アルゴリズムを提供する。
- 参考スコア(独自算出の注目度): 3.372747046563984
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper we propose a variant of the linear least squares model allowing practitioners to partition the input features into groups of variables that they require to contribute similarly to the final result. The output allows practitioners to assess the importance of each group and of each variable in the group. We formally show that the new formulation is not convex and provide two alternative methods to deal with the problem: one non-exact method based on an alternating least squares approach; and one exact method based on a reformulation of the problem using an exponential number of sub-problems whose minimum is guaranteed to be the optimal solution. We formally show the correctness of the exact method and also compare the two solutions showing that the exact solution provides better results in a fraction of the time required by the alternating least squares solution (assuming that the number of partitions is small). For the sake of completeness, we also provide an alternative branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large, and a proof of NP-completeness of the optimization problem introduced in this paper.
- Abstract(参考訳): 本稿では, 線形最小二乗モデルの変種として, 実験者が入力特徴を変数群に分割し, 最終的な結果に類似して寄与することを提案する。
アウトプットにより、実践者はグループ内の各グループと各変数の重要性を評価することができる。
我々は,新たな定式化が凸性ではなく,最小二乗法に基づく非コンパクト法と,最小値が最適解であることが保証された指数関数数を用いた問題の修正に基づく厳密な方法の2つの方法を提案する。
正確な方法の正しさを正式に示し、また、正解が最小二乗解の交互に必要となる時間(分割数が小さいと仮定した場合)により良い結果をもたらすことを示す2つの解を比較する。
完全性のために,分割数が大きすぎる場合の正確な方法の代わりに,代替分岐と有界アルゴリズムも提供し,本論文で導入した最適化問題のNP完全性の証明を行う。
関連論文リスト
- Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
最適公正表現はいくつかの有用な構造特性を持つことを示す。
そこで,これらの近似問題は,凹凸プログラミング法により効率的に解けることを示す。
論文 参考訳(メタデータ) (2024-09-26T08:46:48Z) - Variable Substitution and Bilinear Programming for Aligning Partially Overlapping Point Sets [48.1015832267945]
本研究では,RPMアルゴリズムの最小化目的関数を用いて要求を満たす手法を提案する。
分岐とバウンド(BnB)アルゴリズムが考案され、パラメータのみに分岐し、収束率を高める。
実験による評価は,非剛性変形,位置雑音,外れ値に対する提案手法の高剛性を示す。
論文 参考訳(メタデータ) (2024-05-14T13:28:57Z) - Towards Efficient Pareto-optimal Utility-Fairness between Groups in
Repeated Rankings [7.6275971668447005]
消費者と生産者のパレート最適バランスを保証し、ランキングの列を計算する問題に対処する。
本稿では,全ての項目が露出する点を表すペルムタヘドロンであるExpohedronを用いて,上記の問題に対する新しいアプローチを提案する。
さらに,Expohedronの囲む$n$-sphereの最適化問題を緩和し,実行時間を大幅に改善する効率的な手法を提案する。
論文 参考訳(メタデータ) (2024-02-22T05:48:54Z) - Multiple Convex Objects Image Segmentation via Proximal Alternating
Direction Method of Multipliers [2.294014185517203]
前述した凸形状は、各対象に関連付けられた二項指示関数上の単純な二次不等式制約であることが判明した。
凸形状を予め確率ベースに組み込んだ画像分割モデルを提案する。
自然画像と医用画像の数値実験により,提案手法は既存の方法よりも優れていることが示された。
論文 参考訳(メタデータ) (2022-03-22T00:05:19Z) - Efficient Locally Optimal Number Set Partitioning for Scheduling,
Allocation and Fair Selection [0.0]
提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。
我々のアルゴリズムは入力集合に正の要素も整数の要素も必要としないので、より広く適用できる。
論文 参考訳(メタデータ) (2021-09-10T11:53:34Z) - Partition-based formulations for mixed-integer optimization of trained
ReLU neural networks [66.88252321870085]
本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。
1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
論文 参考訳(メタデータ) (2021-02-08T17:27:34Z) - Hybrid Trilinear and Bilinear Programming for Aligning Partially
Overlapping Point Sets [85.71360365315128]
多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。
まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。
次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-01-19T04:24:23Z) - Accelerated Sparse Bayesian Learning via Screening Test and Its
Applications [0.9916217495995309]
線形系では、過度に完備な特徴の辞書を具備した最小の解を求めるのは通常NPハードである。
本稿では,解の空間性を促進するためにパラメータ化を事前に用いた疎ベイズ学習を提案する。
論文 参考訳(メタデータ) (2020-07-08T10:21:56Z) - Aligning Partially Overlapping Point Sets: an Inner Approximation
Algorithm [80.15123031136564]
変換の値に関する事前情報がない点集合を整列するロバストな手法を提案する。
我々のアルゴリズムは変換の正規化を必要とせず、変換の値に関する事前情報がない状況に対処できる。
実験により,提案手法が最先端のアルゴリズムよりも高いロバスト性を示した。
論文 参考訳(メタデータ) (2020-07-05T15:23:33Z) - MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
非剛体形状マッチングのための凸混合整数プログラミングの定式化。
効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
論文 参考訳(メタデータ) (2020-02-28T09:54:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。