文献

J-GLOBAL ID：201802256512053458   整理番号：18A0328293

単調Boole関数を用いた高次劣モジュラ関数の効率的最小化【Powered by NICT】

Efficient minimization of higher order submodular functions using monotonic Boolean functions

著者 (5件)： Ramalingam Srikumar (School of Computing, University of Utah, USA) ,  Russell Chris (Alan Turing Institute, UK) ,  Russell Chris (University of Edinburgh, UK) ,  Ladicky L’ubor (ETH, Zurich, Switzerland) ,  Torr Philip H.S. (University of Oxford, Oxford, UK)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 220  ページ： 1-19  発行年： 2017年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 劣モジュラ関数最小化は,機械学習,経済,ゲーム理論,コンピュータビジョン,および他の多くの応用の広範な重要な問題である。一般ソルバはO(n3log2Nの複雑さを有している。Eは機能を評価するのに必要な時間であるE+n4log O(1)n),nはの変数(Leeetal.,2015)数である。一方,いくつかの変数だけを含むクリーク上で定義された多くの劣モジュラコスト関数の和として記述できることを劣モジュラ関数の特別なサブクラスで定義されている多くのコンピュータビジョンと機械学習問題。そのような関数では,これらのサブクラスの擬似Boole(または多項式)表現(Borosとハンマー,2002)は度(または,またはクリークサイズ)kがk≪nである。本研究では,劣モジュラ関数のこの有用なサブクラスの最小化のための効率的なアルゴリズムを開発した。これを行うために,次数kの劣モジュラ関数を変換二次にする新しいマッピングを定義した。基礎となるアイデアは,高次の項をモデル化するための補助変数を使用することであると変換が入念に作製した線形計画法を用いて明らかにした。特に,単調Boole関数として補助変数をモデル化し,可能な限り少数の補助変数として用いたコンパクトな変換を得ることを可能にした。mは,すべての高次項を形質転換二次のものに関与する補助変数の総数が形質転換した二次関数を効率的にO((n + m)3)の時間計算量を持つ標準最大流アルゴリズムを用いて最小化することができた。より詳しくいえば,ここでは,四次関数のための筆者らのアプローチが既存のアプローチで用いられる30またはそれ以上の変数とは対照的にほんの2補助変数を必要とすることを示す。一般的な場合では,数またはDedekind数を用いた次数kの関数を変換するために必要な補助変数,は22Kの既存の限界よりも実質的に低いに対する上限を与えた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 機械学習 ,  *Boole関数 ,  コンピュータビジョン ,  多項式 ,  費用関数 ,  ゲーム理論 ,  線形計画法 ,  アルゴリズム ,  モデリング
準シソーラス用語： 時間計算量 ,  次数 ,  ハンマ ,  ソルバ ,  *劣モジュラ関数 , 【Automatic Indexing@JST】

著者キーワード (5件)： 劣モジュラ関数 ,  二次擬ブール関数 ,  単調ブール関数 ,  Dedekind数 ,  Max flow/mincutアルゴリズム

分類 (2件)： 計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (3件)： Boole関数 ,  劣モジュラ関数 ,  最小化