View in EDS

Tractability-preserving transformations of global cost functions.

Saved in:
Bibliographic Details
Title: Tractability-preserving transformations of global cost functions.
Authors: Allouche, David1, Bessiere, Christian2, Boizumault, Patrice3, de Givry, Simon1, Gutierrez, Patricia4, Lee, Jimmy H.M.5, Leung, Ka Lun5, Loudni, Samir3, Métivier, Jean-Philippe3, Schiex, Thomas1 thomas.schiex@toulouse.inra.fr, Wu, Yi5
Source: Artificial Intelligence. Sep2016, Vol. 238, p166-189. 24p.
Subjects: Graphical modeling (Statistics), Cost functions, Artificial intelligence, Dynamic programming, Feasibility problem (Mathematical optimization)
Abstract: Graphical model processing is a central problem in artificial intelligence. The optimization of the combined cost of a network of local cost functions federates a variety of famous problems including CSP, SAT and Max-SAT but also optimization in stochastic variants such as Markov Random Fields and Bayesian networks. Exact solving methods for these problems typically include branch and bound and local inference-based bounds. In this paper we are interested in understanding when and how dynamic programming based optimization can be used to efficiently enforce soft local consistencies on Global Cost Functions, defined as parameterized families of cost functions of unbounded arity. Enforcing local consistencies in cost function networks is performed by applying so-called Equivalence Preserving Transformations (EPTs) to the cost functions. These EPTs may transform global cost functions and make them intractable to optimize. We identify as tractable projection-safe those global cost functions whose optimization is and remains tractable after applying the EPTs used for enforcing arc consistency. We also provide new classes of cost functions that are tractable projection-safe thanks to dynamic programming. We show that dynamic programming can either be directly used inside filtering algorithms, defining polynomially DAG-filterable cost functions, or emulated by arc consistency filtering on a Berge-acyclic network of bounded-arity cost functions, defining Berge-acyclic network-decomposable cost functions. We give examples of such cost functions and we provide a systematic way to define decompositions from existing decomposable global constraints. These two approaches to enforcing consistency in global cost functions are then embedded in a solver for extensive experiments that confirm the feasibility and efficiency of our proposal. [ABSTRACT FROM AUTHOR]
Copyright of Artificial Intelligence is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 118151376
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Tractability-preserving transformations of global cost functions.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Allouche%2C+David%22">Allouche, David</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Bessiere%2C+Christian%22">Bessiere, Christian</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Boizumault%2C+Patrice%22">Boizumault, Patrice</searchLink><relatesTo>3</relatesTo><br /><searchLink fieldCode="AR" term="%22de+Givry%2C+Simon%22">de Givry, Simon</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Gutierrez%2C+Patricia%22">Gutierrez, Patricia</searchLink><relatesTo>4</relatesTo><br /><searchLink fieldCode="AR" term="%22Lee%2C+Jimmy+H%2EM%2E%22">Lee, Jimmy H.M.</searchLink><relatesTo>5</relatesTo><br /><searchLink fieldCode="AR" term="%22Leung%2C+Ka+Lun%22">Leung, Ka Lun</searchLink><relatesTo>5</relatesTo><br /><searchLink fieldCode="AR" term="%22Loudni%2C+Samir%22">Loudni, Samir</searchLink><relatesTo>3</relatesTo><br /><searchLink fieldCode="AR" term="%22Métivier%2C+Jean-Philippe%22">Métivier, Jean-Philippe</searchLink><relatesTo>3</relatesTo><br /><searchLink fieldCode="AR" term="%22Schiex%2C+Thomas%22">Schiex, Thomas</searchLink><relatesTo>1</relatesTo><i> thomas.schiex@toulouse.inra.fr</i><br /><searchLink fieldCode="AR" term="%22Wu%2C+Yi%22">Wu, Yi</searchLink><relatesTo>5</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Artificial+Intelligence%22">Artificial Intelligence</searchLink>. Sep2016, Vol. 238, p166-189. 24p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Graphical+modeling+%28Statistics%29%22">Graphical modeling (Statistics)</searchLink><br /><searchLink fieldCode="DE" term="%22Cost+functions%22">Cost functions</searchLink><br /><searchLink fieldCode="DE" term="%22Artificial+intelligence%22">Artificial intelligence</searchLink><br /><searchLink fieldCode="DE" term="%22Dynamic+programming%22">Dynamic programming</searchLink><br /><searchLink fieldCode="DE" term="%22Feasibility+problem+%28Mathematical+optimization%29%22">Feasibility problem (Mathematical optimization)</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Graphical model processing is a central problem in artificial intelligence. The optimization of the combined cost of a network of local cost functions federates a variety of famous problems including CSP, SAT and Max-SAT but also optimization in stochastic variants such as Markov Random Fields and Bayesian networks. Exact solving methods for these problems typically include branch and bound and local inference-based bounds. In this paper we are interested in understanding when and how dynamic programming based optimization can be used to efficiently enforce soft local consistencies on Global Cost Functions, defined as parameterized families of cost functions of unbounded arity. Enforcing local consistencies in cost function networks is performed by applying so-called Equivalence Preserving Transformations (EPTs) to the cost functions. These EPTs may transform global cost functions and make them intractable to optimize. We identify as tractable projection-safe those global cost functions whose optimization is and remains tractable after applying the EPTs used for enforcing arc consistency. We also provide new classes of cost functions that are tractable projection-safe thanks to dynamic programming. We show that dynamic programming can either be directly used inside filtering algorithms, defining polynomially DAG-filterable cost functions, or emulated by arc consistency filtering on a Berge-acyclic network of bounded-arity cost functions, defining Berge-acyclic network-decomposable cost functions. We give examples of such cost functions and we provide a systematic way to define decompositions from existing decomposable global constraints. These two approaches to enforcing consistency in global cost functions are then embedded in a solver for extensive experiments that confirm the feasibility and efficiency of our proposal. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Artificial Intelligence is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=118151376
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.artint.2016.06.005
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 24
        StartPage: 166
    Subjects:
      – SubjectFull: Graphical modeling (Statistics)
        Type: general
      – SubjectFull: Cost functions
        Type: general
      – SubjectFull: Artificial intelligence
        Type: general
      – SubjectFull: Dynamic programming
        Type: general
      – SubjectFull: Feasibility problem (Mathematical optimization)
        Type: general
    Titles:
      – TitleFull: Tractability-preserving transformations of global cost functions.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Allouche, David
      – PersonEntity:
          Name:
            NameFull: Bessiere, Christian
      – PersonEntity:
          Name:
            NameFull: Boizumault, Patrice
      – PersonEntity:
          Name:
            NameFull: de Givry, Simon
      – PersonEntity:
          Name:
            NameFull: Gutierrez, Patricia
      – PersonEntity:
          Name:
            NameFull: Lee, Jimmy H.M.
      – PersonEntity:
          Name:
            NameFull: Leung, Ka Lun
      – PersonEntity:
          Name:
            NameFull: Loudni, Samir
      – PersonEntity:
          Name:
            NameFull: Métivier, Jean-Philippe
      – PersonEntity:
          Name:
            NameFull: Schiex, Thomas
      – PersonEntity:
          Name:
            NameFull: Wu, Yi
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 09
              Text: Sep2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 00043702
          Numbering:
            – Type: volume
              Value: 238
          Titles:
            – TitleFull: Artificial Intelligence
              Type: main
ResultId 1