發(fā)帖
雷達卡
摘要翻譯：
集體圖形模型利用實例間的關聯(lián)依賴來輸出更精確的標記。然而，現有模型支持的關聯(lián)性非常有限，這限制了精度的提高。本文有兩大貢獻。首先，我們提出了一個通用的集體推理框架，它使數據實例對其標號的一組{\em性質}達成一致。通過對稱團勢鼓勵協(xié)議。我們證明了豐富的性質會帶來更大的收益，并給出了一大類這類性質的系統(tǒng)推理過程。該過程在群集圖上執(zhí)行消息傳遞，其中屬性感知消息是用特定于群集的算法計算的。這為領域自適應提供了一個僅限于推理的解決方案。我們在書目信息抽取上的實驗表明，在未見域上顯著地減少了測試錯誤。我們的第二個主要貢獻是計算來自具有對稱團勢的團簇的傳出消息的算法。我們的算法對二元標號上的任意對稱勢以及多標號上的類max-like和類multimal-like勢都是精確的。對于大多數勢，我們還提供了一個有效的基于拉格朗日松弛的算法，與精確算法相比較。我們提出了一個NP硬Potts勢的13/15近似算法，在團的大小上，運行時間為次二次。相比之下，對于具有Potts勢的圖，最著名的先前保證僅為1/2。我們的經驗表明，我們的Potts勢的方法比最好的替代方案快一個數量級，而我們的基于拉格朗日松弛的多數勢算法優(yōu)于最佳適用的啟發(fā)式--ICM。
---
英文標題：
《Generalized Collective Inference with Symmetric Clique Potentials》
---
作者：
Rahul Gupta, Sunita Sarawagi, Ajit A. Diwan
---
最新提交年份：
2009
---
分類信息：
一級分類：Computer Science 計算機科學
二級分類：Artificial Intelligence 人工智能
分類描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵蓋了人工智能的所有領域，除了視覺、機器人、機器學習、多智能體系統(tǒng)以及計算和語言（自然語言處理），這些領域有獨立的學科領域。特別地，包括專家系統(tǒng)，定理證明（盡管這可能與計算機科學中的邏輯重疊），知識表示，規(guī)劃，和人工智能中的不確定性。大致包括ACM學科類I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
Collective graphical models exploit inter-instance associative dependence to output more accurate labelings. However existing models support very limited kind of associativity which restricts accuracy gains. This paper makes two major contributions. First, we propose a general collective inference framework that biases data instances to agree on a set of {\em properties} of their labelings. Agreement is encouraged through symmetric clique potentials. We show that rich properties leads to bigger gains, and present a systematic inference procedure for a large class of such properties. The procedure performs message passing on the cluster graph, where property-aware messages are computed with cluster specific algorithms. This provides an inference-only solution for domain adaptation. Our experiments on bibliographic information extraction illustrate significant test error reduction over unseen domains. Our second major contribution consists of algorithms for computing outgoing messages from clique clusters with symmetric clique potentials. Our algorithms are exact for arbitrary symmetric potentials on binary labels and for max-like and majority-like potentials on multiple labels. For majority potentials, we also provide an efficient Lagrangian Relaxation based algorithm that compares favorably with the exact algorithm. We present a 13/15-approximation algorithm for the NP-hard Potts potential, with runtime sub-quadratic in the clique size. In contrast, the best known previous guarantee for graphs with Potts potentials is only 1/2. We empirically show that our method for Potts potentials is an order of magnitude faster than the best alternatives, and our Lagrangian Relaxation based algorithm for majority potentials beats the best applicable heuristic -- ICM.
---
PDF鏈接：
https://arxiv.org/pdf/0907.0589
提升卡
置頂卡
沉默卡
變色卡
搶沙發(fā)
千斤頂
顯身卡
京公網安備 11010802022788號
