Residual-Guided Look-Ahead in AND/OR Search for Graphical Models

We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are di...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of artificial intelligence research 2017-10, Vol.60, p.287-346
Main Authors: Lam, William, Kask, Kalev, Larrosa, Javier, Dechter, Rina
Format: Article
Language:English
Subjects:
Artificial intelligence
Combinatorial analysis
Combinatorial optimization
Empirical analysis
Exact solutions
Graphic methods
Heuristic
Informàtica
Informàtica teòrica
Luminance distribution
Mètodes gràfics
Optimització combinatòria
Optimization
Searching
Àrees temàtiques de la UPC
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c299t-fcff4f52a923c67c462e9807771a43c2c45d523eea7996184b752b5419bcb7913
cites
container_end_page 346
container_issue
container_start_page 287
container_title The Journal of artificial intelligence research
container_volume 60
creator Lam, William
Kask, Kalev
Larrosa, Javier
Dechter, Rina
description We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are distributed in the search space, guided by the mini-bucket heuristic. We present and analyze methods for compiling the local bucket-errors (exactly and approximately) and show that they can be used to yield an effective tool for balancing look-ahead overhead during search. This can be especially instrumental when memory is restricted, accommodating the generation of only weak compiled heuristics. We illustrate the impact of the proposed schemes in an extensive empirical evaluation for both finding exact solutions and anytime suboptimal solutions.
doi_str_mv 10.1613/jair.5475
format article
fullrecord <record><control><sourceid>proquest_csuc_</sourceid><recordid>TN_cdi_csuc_recercat_oai_recercat_cat_2072_341278</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2554081701</sourcerecordid><originalsourceid>FETCH-LOGICAL-c299t-fcff4f52a923c67c462e9807771a43c2c45d523eea7996184b752b5419bcb7913</originalsourceid><addsrcrecordid>eNpNkE1LAzEQhoMoWKsH_0HAk4dt87mzuVmqVqFaqHoO2WxCU9emJt2D_94uLehhmHkP78PwIHRNyYiWlI_XJqSRFCBP0IASKAsFEk7_3efoIuc1IVQJVg3Q3dLl0HSmLWZdaFyD5zF-FpOVMw0OGzx5vR8vlvjNmWRX2MeEZ8lsV8GaFr_ExrX5Ep1502Z3ddxD9PH48D59KuaL2fN0Mi8sU2pXeOu98JIZxbgtwYqSOVURAKBGcMuskI1k3DkDSpW0EjVIVktBVW1rUJQPET1wbe6sTs66ZM1ORxP-Qj-MANNcUAbVvnNz6GxT_O5c3ul17NJm_6ZmUgpSUSA9-fZITjHn5LzepvBl0o-mRPdSdS9V91L5Lw1nZxY</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2554081701</pqid></control><display><type>article</type><title>Residual-Guided Look-Ahead in AND/OR Search for Graphical Models</title><source>Publicly Available Content Database</source><creator>Lam, William ; Kask, Kalev ; Larrosa, Javier ; Dechter, Rina</creator><creatorcontrib>Lam, William ; Kask, Kalev ; Larrosa, Javier ; Dechter, Rina</creatorcontrib><description>We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are distributed in the search space, guided by the mini-bucket heuristic. We present and analyze methods for compiling the local bucket-errors (exactly and approximately) and show that they can be used to yield an effective tool for balancing look-ahead overhead during search. This can be especially instrumental when memory is restricted, accommodating the generation of only weak compiled heuristics. We illustrate the impact of the proposed schemes in an extensive empirical evaluation for both finding exact solutions and anytime suboptimal solutions.</description><identifier>ISSN: 1076-9757</identifier><identifier>EISSN: 1076-9757</identifier><identifier>EISSN: 1943-5037</identifier><identifier>DOI: 10.1613/jair.5475</identifier><language>eng</language><publisher>San Francisco: AI Access Foundation</publisher><subject>Artificial intelligence ; Combinatorial analysis ; Combinatorial optimization ; Empirical analysis ; Exact solutions ; Graphic methods ; Heuristic ; Informàtica ; Informàtica teòrica ; Luminance distribution ; Mètodes gràfics ; Optimització combinatòria ; Optimization ; Searching ; Àrees temàtiques de la UPC</subject><ispartof>The Journal of artificial intelligence research, 2017-10, Vol.60, p.287-346</ispartof><rights>2017. Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the associated terms available at https://www.jair.org/index.php/jair/about</rights><rights>info:eu-repo/semantics/openAccess</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c299t-fcff4f52a923c67c462e9807771a43c2c45d523eea7996184b752b5419bcb7913</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2554081701?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>230,314,776,780,881,25731,27901,27902,36989,44566</link.rule.ids></links><search><creatorcontrib>Lam, William</creatorcontrib><creatorcontrib>Kask, Kalev</creatorcontrib><creatorcontrib>Larrosa, Javier</creatorcontrib><creatorcontrib>Dechter, Rina</creatorcontrib><title>Residual-Guided Look-Ahead in AND/OR Search for Graphical Models</title><title>The Journal of artificial intelligence research</title><description>We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are distributed in the search space, guided by the mini-bucket heuristic. We present and analyze methods for compiling the local bucket-errors (exactly and approximately) and show that they can be used to yield an effective tool for balancing look-ahead overhead during search. This can be especially instrumental when memory is restricted, accommodating the generation of only weak compiled heuristics. We illustrate the impact of the proposed schemes in an extensive empirical evaluation for both finding exact solutions and anytime suboptimal solutions.</description><subject>Artificial intelligence</subject><subject>Combinatorial analysis</subject><subject>Combinatorial optimization</subject><subject>Empirical analysis</subject><subject>Exact solutions</subject><subject>Graphic methods</subject><subject>Heuristic</subject><subject>Informàtica</subject><subject>Informàtica teòrica</subject><subject>Luminance distribution</subject><subject>Mètodes gràfics</subject><subject>Optimització combinatòria</subject><subject>Optimization</subject><subject>Searching</subject><subject>Àrees temàtiques de la UPC</subject><issn>1076-9757</issn><issn>1076-9757</issn><issn>1943-5037</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNpNkE1LAzEQhoMoWKsH_0HAk4dt87mzuVmqVqFaqHoO2WxCU9emJt2D_94uLehhmHkP78PwIHRNyYiWlI_XJqSRFCBP0IASKAsFEk7_3efoIuc1IVQJVg3Q3dLl0HSmLWZdaFyD5zF-FpOVMw0OGzx5vR8vlvjNmWRX2MeEZ8lsV8GaFr_ExrX5Ep1502Z3ddxD9PH48D59KuaL2fN0Mi8sU2pXeOu98JIZxbgtwYqSOVURAKBGcMuskI1k3DkDSpW0EjVIVktBVW1rUJQPET1wbe6sTs66ZM1ORxP-Qj-MANNcUAbVvnNz6GxT_O5c3ul17NJm_6ZmUgpSUSA9-fZITjHn5LzepvBl0o-mRPdSdS9V91L5Lw1nZxY</recordid><startdate>20171001</startdate><enddate>20171001</enddate><creator>Lam, William</creator><creator>Kask, Kalev</creator><creator>Larrosa, Javier</creator><creator>Dechter, Rina</creator><general>AI Access Foundation</general><scope>AAYXX</scope><scope>CITATION</scope><scope>8FE</scope><scope>8FG</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>P62</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>XX2</scope></search><sort><creationdate>20171001</creationdate><title>Residual-Guided Look-Ahead in AND/OR Search for Graphical Models</title><author>Lam, William ; Kask, Kalev ; Larrosa, Javier ; Dechter, Rina</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c299t-fcff4f52a923c67c462e9807771a43c2c45d523eea7996184b752b5419bcb7913</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Artificial intelligence</topic><topic>Combinatorial analysis</topic><topic>Combinatorial optimization</topic><topic>Empirical analysis</topic><topic>Exact solutions</topic><topic>Graphic methods</topic><topic>Heuristic</topic><topic>Informàtica</topic><topic>Informàtica teòrica</topic><topic>Luminance distribution</topic><topic>Mètodes gràfics</topic><topic>Optimització combinatòria</topic><topic>Optimization</topic><topic>Searching</topic><topic>Àrees temàtiques de la UPC</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Lam, William</creatorcontrib><creatorcontrib>Kask, Kalev</creatorcontrib><creatorcontrib>Larrosa, Javier</creatorcontrib><creatorcontrib>Dechter, Rina</creatorcontrib><collection>CrossRef</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Recercat</collection><jtitle>The Journal of artificial intelligence research</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Lam, William</au><au>Kask, Kalev</au><au>Larrosa, Javier</au><au>Dechter, Rina</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Residual-Guided Look-Ahead in AND/OR Search for Graphical Models</atitle><jtitle>The Journal of artificial intelligence research</jtitle><date>2017-10-01</date><risdate>2017</risdate><volume>60</volume><spage>287</spage><epage>346</epage><pages>287-346</pages><issn>1076-9757</issn><eissn>1076-9757</eissn><eissn>1943-5037</eissn><abstract>We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are distributed in the search space, guided by the mini-bucket heuristic. We present and analyze methods for compiling the local bucket-errors (exactly and approximately) and show that they can be used to yield an effective tool for balancing look-ahead overhead during search. This can be especially instrumental when memory is restricted, accommodating the generation of only weak compiled heuristics. We illustrate the impact of the proposed schemes in an extensive empirical evaluation for both finding exact solutions and anytime suboptimal solutions.</abstract><cop>San Francisco</cop><pub>AI Access Foundation</pub><doi>10.1613/jair.5475</doi><tpages>60</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1076-9757
ispartof The Journal of artificial intelligence research, 2017-10, Vol.60, p.287-346
issn 1076-9757
1076-9757
1943-5037
language eng
recordid cdi_csuc_recercat_oai_recercat_cat_2072_341278
source Publicly Available Content Database
subjects Artificial intelligence
Combinatorial analysis
Combinatorial optimization
Empirical analysis
Exact solutions
Graphic methods
Heuristic
Informàtica
Informàtica teòrica
Luminance distribution
Mètodes gràfics
Optimització combinatòria
Optimization
Searching
Àrees temàtiques de la UPC
title Residual-Guided Look-Ahead in AND/OR Search for Graphical Models
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-02T10%3A13%3A00IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_csuc_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Residual-Guided%20Look-Ahead%20in%20AND/OR%20Search%20for%20Graphical%20Models&rft.jtitle=The%20Journal%20of%20artificial%20intelligence%20research&rft.au=Lam,%20William&rft.date=2017-10-01&rft.volume=60&rft.spage=287&rft.epage=346&rft.pages=287-346&rft.issn=1076-9757&rft.eissn=1076-9757&rft_id=info:doi/10.1613/jair.5475&rft_dat=%3Cproquest_csuc_%3E2554081701%3C/proquest_csuc_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c299t-fcff4f52a923c67c462e9807771a43c2c45d523eea7996184b752b5419bcb7913%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2554081701&rft_id=info:pmid/&rfr_iscdi=true