<mark id="oztn4"></mark>
0
| 本文作者： 叢末 | 2019-05-10 19:04 | 專題：IJCAI：國際人工智能聯合會議 |
雷鋒網 AI 科技評論按：作為人工智能領域最頂級的國際學術會議之一，IJCAI 今日公布了最終論文接收結果，引起了該領域的密切關注。據悉，IJCAI 2019 今年一共收到 4752 篇有效提交論文，最終的論文收錄數量為 850 篇，接收率為 17.9% 。雖然今年論文投稿量與收錄量比去年（論文投稿量為 3470 篇、收錄量為 710 篇）都要高，但最終的接收率要比去年的 20.5% 低不少。
論文收錄結果出爐后，有人歡喜有人愁：一方面，各位落選者先后抒發了自己的遺憾；而另一方面，各位論文被收錄的實力派也紛紛曬出了自己收到的論文收錄通知。針對大家在 IJCAI 2019 論文收錄方面的更多疑問，后續雷鋒網 AI 科技評論會在 IJCAI 2019 程序委員會主席（Sarit Kraus）的專訪中為大家帶來答案。而在此之前，我們不妨先來溫習一下 IJCAI 近 20 年以來摘得「杰出論文獎」（Distinguished Paper Award）的二十九篇論文，并從這些最佳論文中一窺 AI 這些年來的發展軌跡。
SentiGAN：通過混合對抗性網絡生成情感文本
SentiGAN: Generating Sentimental Texts via Mixture Adversarial Networks
論文摘要：在自然語言生成領域，生成不同情感標簽的文本越來越多受到關注。近來，生成式對抗網絡（GAN）在文本生成中表現出色。然而，通過 GAN 生成的文本往往在面臨質量差、缺乏多樣性和模式崩潰（mode collapse ）的問題。在這篇論文中，我們提出了一個新的框架——SentiGAN，包含有多個生成器和一個多類別判別器，以解決上述問題。在該框架中，多個生成器同時訓練，旨在無監督環境下產生不同情感標簽的文本。我們提出了一個基于懲罰的目標函數，使每個生成器都能在特定情感標簽下生成具有多樣性的樣本。此外，使用多個生成器和一個多類判別器，可以使每個生成器專注于準確地生成自己的特定情感標簽的例子。在四個數據集上的實驗結果表明，我們的模型在情感準確度和生成文本的質量方面始終優于當前幾種最先進的文本生成方法。
論文地址：https://www.ijcai.org/proceedings/2018/0618.pdf
通過大多數動態對觀點傳播中的共識形成進行推理
Reasoning about Consensus when Opinions Diffuse through Majority Dynamics
論文摘要：該論文研究了社會圖上的意見傳播問題。在社會圖中，智能體持有二元意見，并且社會壓力導致他們遵從大多數鄰居所表示的意見。在這種背景下，考慮有關少數/多數是否能夠將其支持的意見傳播到所有其他智能體的問題。研究結果表明，無論底層圖如何，總是存在一個由半數智能體組成的群體可以消除相反的意見。相反地，少數群體的影響力取決于給定圖的某些特征，這些特征的識別便是 NP 難問題（NP-hard）。而決定這兩種觀點是否可以在某種穩定的配置中共存也是 NP 難的。
論文地址：https://www.ijcai.org/proceedings/2018/0007.pdf
R-SVM+：具有私有信息的魯棒學習
R-SVM+: Robust Learning with Privileged Information
論文摘要：在實際應用場景中，訓練數據和測試數據質量的干凈度往往難以讓人滿意。由于缺少解決數據中潛在噪聲的有效策略，現有方法的效果在特權信息學習（learning using privileged information，LUPI）范式中可能面臨很大的挑戰。本文基于嚴格的理論分析，提出了一種新的魯棒 SVM+（R-SVM+）算法。我們在 SVM+ 框架下的 LUPI 范式中研究了樣本標簽數據和特權標簽數據的擾動下界，這個擾動下界會誤導模型做出錯誤的決策。通過最大化下界，學到的模型在擾動下的容忍度將會增大。據此，我們給模型引入了新的正則化函數，用于升級 SVM+ 的變體。將 R-SVM+ 的目標函數轉化為二次規劃問題，利用現成的求解方法可以很容易進行優化求解。實證結果展現了 R-SVM+ 的必要性和算法的有效性。
論文地址：https://www.ijcai.org/proceedings/2018/0334.pdf
在基于領域本體的查詢中，從連接性查詢到實例查詢
From Conjunctive Queries to Instance Queries in Ontology-Mediated Querying
論文摘要：我們考慮基于 ALC 族和連接查詢的表達性描述邏輯的本體中介查詢（ontology-mediated queries，OMQs），研究基于實例查詢（instance queries，IQs）的 OMQ 的可重寫性。我們的結果包括這種重寫何時能精確表征以及決定重寫性的嚴格復雜性界限。我們還給出了判定給定 MMSNP 語句是否等價于 CSP 的相關問題的嚴格復雜度界限。
論文地址：https://www.ijcai.org/proceedings/2018/0250.pdf
玩的是什么游戲？從游戲中的正態與拓展性端到端學習
What Game are We Playing? End-to-end Learning in Normal and Extensive from Games
論文摘要：雖然人工智能最近的研究在求解大型、零和、擴展形式的博弈方面取得了很大進展，但過去大多數工作中的基本假設都是博弈本身的參數是智能體已知的。本文討論相對未被充分探索但同樣重要的「逆」設置，其中并不是所有智能體都知道底層博弈的參數，它們必須通過觀察來學習。我們提出一個可微的、端到端的學習框架來處理這個任務。特別地，我們考慮博弈的正則化版本，等價于隨機最優反應均衡（quantal response equilibrium）的特定形式，并改進：1） 在正規形式博弈和擴展形式博弈中尋找這種平衡點的原始-對偶牛頓（primal-dual Newton）方法；2） 反向傳播方法使我們能夠通過解本身來計算所有相關博弈參數的梯度。這最終讓我們通過端到端的訓練來學習博弈，通過將「可微的博弈求解器」有效地集成到更大的深層網絡體系結構的循環中。我們展示了該學習方法在多種設置中的有效性，包括撲克和安全博弈任務。
論文地址：https://www.ijcai.org/proceedings/2018/0055.pdf
圖注意力機制的帶有常識知識的對話生成
Commonsense Knowledge Aware Conversation Generation with Graph Attention
論文摘要：常識知識對于許多自然語言處理任務來說至關重要。本文提出了一種新的開放領域會話生成模型，以展示大規模常識知識如何促進語言理解和生成。在給定用戶帖子的情況下，模型從知識庫中檢索相關知識圖，然后用靜態圖注意力機制對圖進行編碼，以增強帖子的語義信息，從而支持對帖子的更好理解。之后，在單詞生成過程中，該模型通過動態圖注意力機制仔細地讀取檢索到的知識圖和每個圖中的知識三元組，以便于更好地生成。這是第一次嘗試在對話生成中使用大規模常識知識。此外，與現有模型分別和獨立地使用知識三元組（實體）不同，我們的模型將每個知識圖作為一個整體來處理，從而在圖中編碼更結構化、連接的語義信息。實驗表明，該模型能夠產生比現有基準更合適、信息量更大的響應。
論文地址：https://www.ijcai.org/proceedings/2018/0643.pdf
圖相似性的簡并框架
A Degeneracy Framework for Graph Similarity
論文摘要：精確測量圖形之間的相似性是許多學科應用的核心問題。大多數現有的確定圖相似性的方法要么關注圖的局部性質，要么關注圖的全局性質。然而，即使從局部或全局的角度來看，圖形看起來非常相似，但它們可能在不同的尺度上表現出不同的結構。本文提出了一個通用的圖相似性框架，該框架考慮了多個不同尺度上的結構。該框架利用圖的 k 核（k-core）分解來構建嵌套子圖的層次結構。應用該框架導出了四種圖核（graph kernels）的變體：圖核、最短路徑核、Weisfeiler-Lehman 子樹核和金字塔匹配圖核。該框架不僅限于圖核，而是可以應用于任何圖比較算法。該框架在多個用于圖分類的基準數據集上進行了評估。在大多數情況下，基于核的內核在分類精度方面比基本內核有顯著的提高，而它們的時間復雜度仍然非常優秀。
論文地址：https://www.ijcai.org/proceedings/2018/0360.pdf
使用限制 Datalog 程序進行聲明性數據分析的基本原理
Foundations of Declarative Data Analysis Using Limit Datalog Programs
論文摘要：受聲明性數據分析應用的啟發，我們研究了 Datalog?，這是一個帶有整數運算功能的實際數據記錄（positive Datalog）的擴展。這一語言被認為是不可判定的，因此我們提出了兩個分段。在 limit Datalog? 中，謂語被公理化以保持最小/最大數值，從而允許我們表明事實蘊含（fact entailment）是結合中的完整 coNExpTime 和數據復雜性中的完整 coNP。此外，額外的穩定性需求致使復雜性分別降至 ExpTime 和 PTime。最終，我們證明穩定的 Datalog? 能夠表達很多有用的數據分析任務，因此我們的研究成果為高級信息系統的發展打下了堅實的基礎。
論文地址：https://www.ijcai.org/proceedings/2017/0156.pdf
一般游戲玩法中的基于約束的對稱性檢測
Constraint-Based Symmetry Detection in General Game Playing
論文摘要：對稱檢測有望成為減少游戲搜索樹的一種方法。在一般游戲玩法（GGP）中，任何游戲由游戲描述語言（GDL）中的一組規則緊湊地表示，用于對稱檢測的最先進的方法依賴于與 GDL 描述相關聯的規則圖的游戲。雖然這種基于規則的對稱檢測方法可以應用于各種樹搜索算法，但它們僅涵蓋在 GDL 描述中顯而易見的有限數量的對稱性。在本文中，我們開發了利用約束編程技術的隨機游戲中的對稱檢測的替代方法。GDL 游戲中的極小值優化問題被當做隨機約束滿足問題（SCSP），可以將其視為一級 SCSP 序列。Minimax 對稱性根據這些一階約束網絡的微結構補充推斷。基于這種方法的理論分析，我們實驗性地展示了隨機約束求解器 MAC-UCB 結合基于約束的對稱性檢測，要顯著優于標準的蒙特卡洛樹搜索算法與基于規則的對稱檢測的結合。這種約束驅動的方法也通過我們的 AI 在最后一次 GGP 比賽中獲得的出色成績得到驗證。
論文地址：https://www.ijcai.org/proceedings/2017/0040.pdf
通過知識片段遷移來實現一般異構遷移的距離度量學習
General Heterogeneous Transfer Distance Metric Learning via Knowledge Fragments Transfer
論文摘要：遷移學習旨在通過利用其他相關任務的信息（或遷移知識）來提高目標學習任務的表現。近來，遷移距離度量學習（TDML）吸引了很多研究者的興趣，但是大多數這些方法假設源和目標學習任務的特征表示是一樣的。因此，它們不適用于數據來自異構域（特征空間，模態甚至語義）的應用程序。雖然一些現有的異構傳輸學習（HTL）方法能夠處理這樣的問題，但它們在實際應用中缺乏靈活性，而學習的轉換通常被限制為線性的。因此，我們開發了基于知識片段的通用和靈活的異構 TDML（HTDML）框架遷移策略。在我們提出的 HTDML 中，可以使用任何（線性或非線性）距離度量學習算法來預先學習源度量。然后，從預先學習的源度量中提取一組知識片段，幫助目標度量學習。此外，可以為目標域學習線性或非線性距離度量。針對場景分類和對象識別的廣泛實驗，也證明了我們所提出的這一方法的優越性。
論文地址：https://www.ijcai.org/proceedings/2017/0341.pdf
用于泛化規劃的層次有限狀態控制器
Hierarchical Finite State Controllers for Generalized Planning
論文摘要：有限狀態控制器（Finite State Controllers，FSC）是一種緊湊地表征順序規劃的有效方式。通過在過渡上施加適當的條件，FSC 也能表征解決給定領域內的一系列的規劃問題。這篇論文介紹了分層 FSC的概念，它通過允許控制器調用其它控制器來進行規劃。其中證明分層 FSC 可以比個體 FSC更緊湊地表征一般規劃。此外，其調用機制允許以模塊化的方式生成分層 FSC，甚至應用遞歸方式。論文還介紹了能讓經典規劃者生成分層 FSC 的匯編，這能解決很有挑戰性的一般規劃問題。此匯編以來自特定領域的規劃問題集合作為輸入，然后輸出一個單一經典規劃問題，這種解決方案對應著一個分層 FSC。
論文地址：https://www.ijcai.org/Proceedings/16/Papers/458.pdf
用于非凸優化的遞歸分解
Recursive Decomposition for Nonconvex Optimization
論文摘要：連續優化是人工智能多個領域的一個重要的問題，包括計算機視覺、機器人、概率推理與機器學習。遺憾的是，大多數現實世界的優化問題都是非標準技術，所以即使是像隨機重啟和模擬退火這樣的延伸，標準凸面技術也只能找到局部最優解。我們觀察到，在許多情況下，目標函數的局部模式有組合結構，因此，組合優化的思路可以支撐。在此基礎上，我們提出一個非凸優化問題的分解辦法。類似于 DPLL 風格的 SAT 方法和概率推理中的遞歸調節，我們的算法將變量遞歸后，簡化并分解目標函數成近似獨立的子函數，直到剩余的功能很簡單能夠用標準技術進行優化，如梯度下降。根據圖形的劃分來選擇變量，確保分解的可能性。我們的分析表明，RDIS 的建立的可以解決一大類非凸優化梯度下降的問題指數隨機重新啟動。實驗結果表明，在運動和蛋白質折疊的結構的相關問題上，RDIS 優于標準技術。
論文地址：https://www.ijcai.org/Proceedings/15/Papers/042.pdf
用于后驗估算的貝葉斯主動學習
Bayesian Active Learning for Posterior Estimation
論文摘要：該論文研究了在可能性評估代價高昂前提下，在貝葉斯設定中積極的后驗估算。現有技術的后驗估算依賴于后驗代表性樣本的形成。這種方法并不能支撐可能性評估方面考的效率。為了進行有效的查詢，我們將后驗估算放在有效的回歸框架中進行。對于選擇在哪里評估可能性，我們提出兩個近視的查詢策略，并對他們進行高斯過程。通過一系列的合成實驗和真實的例子，證實我們的方法比現有的技術和其他啟發式后驗估算有著更顯著的查詢效率。
論文地址：https://www.ijcai.org/Proceedings/15/Papers/507.pdf
通過隨機向量實現高維度貝葉斯優化
Bayesian Optimization in High Dimensions via Random Embeddings
論文摘要：貝葉斯優化技術已成功應用于機器人、決策規劃、傳感器安置、推薦、廣告、智能化用戶界面和自動算法成形。盡管取得這些成功，該方法僅限于中等規模的問題，而貝葉斯優化的幾次研討會已將其放到更高的維度作為一個領域的圣杯。在本文中，我們引入一個新的隨機嵌入的思路，來應對這一問題。由此產生的隨機嵌入貝葉斯優化算法（REMBO）很簡單，并適用于絕對連續變量領域。實驗證明該方法有效解決高維問題，包括流行的混合整數線性規劃求解器的自動參數配置。
論文地址：https://www.ijcai.org/Proceedings/13/Papers/263.pdf
簡單時態問題的靈活性及去耦
Flexibility and Decoupling in the Simple Temporal Problem
論文摘要：在本文中，我們重點尋找一個合適的度量，以確定簡單時態問題（STP）的適應性。在評估一些已經提出的適應性指標之后，我們推斷這些指標未能捕捉到在 STP 指定事件之間的相關性，導致了對現有系統適應性的高估。我們建議，在不相關的時間間隔基礎上，對 STP 事件的允許啟動時間使用一個直觀且更易于接受的適應性指標。這個指標被證明可以計算在低多項式的時間。作為一個靈活計算的副產品，我們得到一個分解的 STN 幾乎免費：對事件空間里每一個可能的 k-partitioning，都可以在 O(k)-time 進行分解計算。更重要的是，我們證明了與當前普遍觀點相反的事實：這樣的分解不影響原始 STP 的適應性。
論文地址：https://www.ijcai.org/Proceedings/13/Papers/356.pdf
博爾達計數下的無加權聯合操縱是 NP 難題
Unweighted Coalitional Manipulation Under the Borda Rule is NP-Hard
論文摘要：Borda 投票規則是一個基于位置的積分規則，面向 M 個候選人，規定第一位選舉候選人獲得 M－1 分，第二位獲得 M－2 分，以此類推。總分最高的候選人成為最終的勝出者。Borda 規則下的無加權聯合操縱問題的計算復雜度，一直都是一個突出的開放性問題：是否可以添加一定的額外投票數（稱為操縱器）選舉一位杰出的候選人成為勝出者？我們通過顯示 NP 難度來解決這個開放的問題，即使是有兩個操縱器和三個輸入票。此外，我們還討論了這個難題結果的擴展和局限性。
論文地址：https://www.ijcai.org/Proceedings/11/Papers/021.pdf
2D 與 3D 歐幾里得空間中連接約束的判別
On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces
論文摘要：我們研究了（無量詞）空間約束語言，它具有相等、接觸和連通性謂詞，以及在低維歐幾里德空間經過解釋的區域上的布爾運算。 我們的實驗表明，推理的復雜性根據空間的維度和所考慮的區域類型而發生巨大變化。 例如，具有內部連通性謂詞（并且沒有接觸）的邏輯對于 R 的 2 次方中的多邊形或常規閉合集、R 的 3 次方中的多面體上的 EXPTIME-complete 問題以及 R 的 3 次方中的常規閉合集上的 NP-complete 問題都是不可判定的。
論文地址：https://www.ijcai.org/Proceedings/11/Papers/165.pdf
對于蒙特卡洛樹搜索的嵌套輸出策略的調整
Nested Rollout Policy Adaptation for Monte Carlo Tree Search
論文摘要：蒙特卡洛樹搜索（MCTS）方法最近在游戲、規劃和優化等領域的取得成功。MCTS 是利用輸出來指導搜索；其中一個展示的是隨機決策樹在每一層的下降路徑，直到到達葉子。MCTS 的結果會受到適當的策略強烈影響并使輸出結果出現偏差。以往的 MCTS 工作中，大多都使用靜態隨機或特定領域的策略。在決定性的優化問題上，我們描述了一種新的方法，即動態模擬搜索中的輸出策略。我們的出發點是 Cazenave 的原始嵌套蒙特卡洛搜索（NMCS），相比直接操縱決策樹本身，我們在嵌套搜索的每個層級上使用梯度上升的輸出策略。我們以這一新的嵌套輸出策略調整（NRPA）算法為基準并檢測其表現。我們的測試問題是填字游戲和五子棋。在適當的時間規模下，相比 NMCS，NRPA 可以大大提高搜索效率，并在較長的時間的維度下，在測試問題中的改進也都超過了以往所有的解決方式。新的五子棋解決方案在保持了超過 30 年人類記錄的基礎上實現了提升。
論文地址：https://www.ijcai.org/Proceedings/11/Papers/115.pdf
Horn SHIQ 本體論的結果驅動推導
Consequence-Driven Reasoning for Horn SHIQ Ontologies
論文摘要：我們為 Horn SHIQ 本體論提出了一個新的推理程序——可將 SHIQ 本體論轉換為一階邏輯的 Horn 片段。與傳統的本體推理程序相比，該推理程序不構建模型或模型表示，而是通過推導新的結論性公理來實現。它與 EL ++本體論所謂的基于完成的程序關聯度很高，且可被視為后者其中的一項擴展。 實際上，我們提出的程序在理論上對于 Horn SHIQ 本體以及 EL ++ 和 SHIQ 的常見片段是最佳的。該程序在大型醫學本體上進行的初步實證評估表明，與現有的本體推理機相比，我們的程序有了明顯的改進。具體而言，該程序的實現能夠對 Galen 可用性最高的 OWL 版本進行分類。 據我們所知，目前還沒有其他推理機能夠對這一本體進行分類。
論文地址：https://www.ijcai.org/Proceedings/09/Papers/336.pdf
使用查詢實現學習條件偏愛網絡
Learning Conditional Preference Networks with Queries
論文摘要：我們研究了在等價精確學習和成員查詢的著名模型中誘發 CP-nets 的問題，目標是通過引導用戶通過一系列的查詢確定一個二進制值的偏好序列。每個示例都是對產出結果的優勢度測試。在此設置中，我們表明了非循環的 CP-nets 僅根據等值查詢是不具備學習性的，但如果給定的示例被限制交換，它們在成員查詢的幫助下是可以學習的。任意示例中的樹形 CP-nets 都具有相似的屬性。事實上，針對查詢復雜度僅為屬性數的對數問題，成員查詢允許我們提供屬性有效的算法。這個結果強調了該模型在更多屬性的領域中啟用 CP-nets 的有效性。
論文地址：https://www.ijcai.org/Proceedings/09/Papers/319.pdf
大規模多級隨機整數程序的在線預測算法性能分析
Performance Analysis of Online Anticipatory Algorithms for Large Multistage Stochastic Integer Programs
論文摘要：盡管近年來在算法方面取得了重大進展，然而現存方法距離為大規模、多級隨機組合優化問題找到最佳策略還存在很遠一段距離。該論文研究了一種互補的方法——在線預測算法，該算法通過解決多個場景的預測松弛問題在每個步驟做出決策。在線預測算法在多個應用中都實現了令人驚喜的好結果，同時這篇論文旨在闡述得出這一結果的過程。特別地，該論文在在線預測算法實現了良好的預期效用并研究了在算法中出現的各類誤差（包括預測誤差和抽樣誤差等）的情況下得到了充分條件。實驗顯示，針對對數個場景，抽樣誤差可以忽略不計，而預測誤差對于現有的應用來說，無論在理論上還是實驗中，都更難以綁定且非常小。
論文地址：https://www.aaai.org/Papers/IJCAI/2007/IJCAI07-319.pdf
使用貝葉斯網絡實現從超聲圖像進行自動化心臟壁異常活動探測
Automated Heart Wall Motion Abnormality Detection From Ultrasound Images using Bayesian Networks
論文摘要：冠心病可以通過評估左心室超聲圖像中心臟壁的局部運動來診斷。我們描述了一個強大的全自動化技術，通過檢測和自動跟蹤左心室的心內膜和外膜來檢測患病心臟病。基于局部很整個左心室壁的運動，心臟壁區域和整個心臟會被劃分為正常區域和非正常區域。為了利用心臟的結構信息，我們對這個問題應用貝葉斯網絡，并通過使用結構學習算法的數據，了解心臟壁面區域之間的關系。我們通過心臟解剖學知識和醫生描述的醫學規則檢查了獲得的結構的有效性。貝葉斯網絡分類器僅依賴于一個小的子集，該子集的數值特征通過時間追蹤和濾波器的選擇方法提取對偶輪廓。我們的數值結果證實了我們的系統在醫院日常實踐中收集的超聲心動圖中是可靠和準確的，我們的系統就是為現實的使用而建立。
論文地址：https://www.ijcai.org/Proceedings/07/Papers/082.pdf
在 SAT 本地搜索中構建結構
Building Structure into Local Search for SAT
論文摘要：在本文中，我們表明本地搜索技術能有效地發掘問題結構信息，并且在結構化問題的例子的表現中產生顯著的改善。在 Ostrowski 等人的早期工作的基礎上，我們描述了如何將變量相關性信息內置到本地搜索中，以便只有獨立變量被考慮反轉。通過使用模型依賴于使用關口的變量的依賴框架，其每次反轉的成本效應就可以被動態計算。困難結構基準問題的實驗研證實了我們的新方法顯著優于此前報道的最佳本地搜索技術。
論文地址：https://www.ijcai.org/Proceedings/07/Papers/380.pdf
學習協調分類器
Learning Coordination Classifiers
論文摘要：我們提出了一種只需學習單個基本分類器的新的集成分類方法，它的思路是學習一個能同時預測測試標簽對的分類器，而不是學習單個測試標簽的多個預測器，然后通過在數據上傳播圖上的信念來協調各個標簽的分配。我們認為即便對于獨立的同分布（iid）數據，該方法在統計上也能發揮很好的激勵作用。 實際上，實驗結果顯示，這一方法在一系列 iid 數據集和一組基本分類器上的分類準確度，都要優于單一樣本分類器。與增強類似，該技術通過分類器組合的基本形式來控制方差，從而增加表征能力。
論文地址：https://www.ijcai.org/Proceedings/05/Papers/1585.pdf
解決跳棋問題
Solving Checkers
論文摘要：AI 在游戲程序方面取得了巨大的成功，能夠與人類最好的玩家媲美。而具有大型存儲器和磁盤的快速、充裕的機器的可用性則為解決一款游戲問題創造了可能性。在這之前，一些相對簡單或小型的游戲已經實現了。在這篇論文中，我們提出了解決跳棋游戲的新思路和新算法。跳棋游戲是一款廣受歡迎的競技游戲，存在 10 的 20 次方個可能位置的搜索空間。本論文展示了我們的第一個實驗結果，解決了其中一個最具挑戰性的跳棋開局問題——白旗先行導致平局。解決大概 50 多場開局問題將會讓跳棋的游戲理論價值得到肯定。
論文地址：https://www.ijcai.org/Proceedings/05/Papers/0515.pdf
信息抽取冗余的概率模型
A Probabilistic Model of Redundancy in Information Extraction
論文摘要：無監督信息抽取（UIE）是一項從文本中提取知識的任務，該任務無需使用手動標注訓練樣本。無監督信息抽取和信息抽取二者的一個基本問題就是評估抽取信息的正確率。在網頁等大型資料庫中，不同的檔案中往往存在重復地提取相同的知識的情況。那信息抽取的這種冗余會怎樣影響正確率呢？
這篇論文介紹了一個組合的「ball-and-urns」模型，該模型能夠計算出樣本大小、冗余以及來自多個不同抽取規則的確證對于抽取信息的正確率的影響。我們描述了在實踐中估計模型參數的方法，并通過實驗證明，對于 UIE 來說，該模型的對數似然性平均比使用逐點互信息（PMI）以及此前在工作中使用的 noisy-or 模型的對數似然性要高出 15 倍。對于監督信息抽取而言，該模型的性能可與支持向量機以及邏輯回歸媲美。
論文地址：https://www.ijcai.org/Proceedings/05/Papers/1390.pdf
德州撲克的游戲理論最優策略近似
Approximating Game-Theoretic Optimal Strategies for Full-scale Poker
論文摘要：德州撲克的游戲理論最優策略的首個完全近似的計算問題得到解決。該論文將幾種抽象技術進行組合以表示大小為 O（10 的 18 次方）的兩位玩家的德州撲克游戲，同時使用每個大小都為 O（10 的 7 次方）的密切相關的模型。 盡管大小系數減少了 1000 億，但最終模型仍保留了真實游戲的關鍵屬性和結構。 將抽象游戲的線性編程解決方案用來創建大幅改進的撲克游戲程序，不僅能夠擊敗強大的人類玩家，還能與世界級的選手對戰。
論文地址： https://www.ijcai.org/Proceedings/03/Papers/097.pdf
即時定位與地圖構建的稀疏連接樹濾波器
Thin Junction Tree Filters for Simultaneous Localization and Mapping
論文摘要：即時定位與地圖構建（SLAM）是移動機器人的一個基本問題：當機器人在未知環境中進行導航時，它必須逐步構建周圍環境的地圖，并同時在該地圖內對自身進行定位。一種常用的解決方案是將 SLAM 視為估計問題，并應用卡爾曼濾波器，這種方法很講究，但無法很好地擴展：信念狀態的大小和濾波器更新的時間復雜度都會在地圖中的地標數量上呈二次方增長。本文提出了一種過濾技術，它將信念狀態的易處理近似維持為一個稀疏連接樹。連接樹隨著過濾器的更新增長，并通過有效的最大似然投影周期性地「變稀疏」，因而其推斷仍然易于處理。當應用于 SLAM 問題時，這些稀疏連接樹濾波器具有線性空間信念狀態和線性時間濾波操作。進一步的近似所生成的濾波操作通常是恒定時間的。本論文對一系列 SLAM 問題進行的實驗，也對這種方法進行了驗證。
論文地址：https://www.ijcai.org/Proceedings/03/Papers/166.pdf
基于架構的因果關系的復雜結果
Complexity Results for Structure-Based Causality
論文摘要：我們給出了 Pearl 結構模型中因果關系的計算復雜性的精確圖像，在該模型中，我們關注變量之間的因果關系、事件因果關系以及概率因果關系。至于變量之間的因果關系，我們考慮因果不相關的概念、原因、上下語境中的原因、直接原因和間接原因。針對事件因果關系，我們分析了必要和可能原因的概念的復雜度，以及 Halpern 和 Pearl 所提出的弱和實際原因的復雜概念。在此過程中，我們也證明了 Halpern 和 Pearl 所提出的一個開放式猜想，并展示了其他的語義結果。然后，我們分析了與概率因果無關的概率概念的復雜性、事件的可能原因以及事件的發生，而忽略其他事件。除此之外，我們還考慮涉及反事實公式的決策和優化問題。據我們所知，該領域迄今為止尚未考慮結構模型方法中因果關系的復雜度方面，而我們的實驗結果中則體現了這一問題。雷鋒網
論文地址：https://www.sciencedirect.com/science/article/pii/S0004370202002710
雷峰網原創文章，未經授權禁止轉載。詳情見轉載須知。
專題
本專題其他文章
