View in EDS

Learning constraints through partial queries.

Saved in:
Bibliographic Details
Title: Learning constraints through partial queries.
Authors: Bessiere, Christian1 (AUTHOR) bessiere@lirmm.fr, Carbonnel, Clément1 (AUTHOR), Dries, Anton2 (AUTHOR), Hebrard, Emmanuel3 (AUTHOR), Katsirelos, George4,5 (AUTHOR), Narodytska, Nina6 (AUTHOR), Quimper, Claude-Guy7 (AUTHOR), Stergiou, Kostas8 (AUTHOR), Tsouros, Dimosthenis C.8,9 (AUTHOR), Walsh, Toby10,11 (AUTHOR)
Source: Artificial Intelligence. Jun2023, Vol. 319, pN.PAG-N.PAG. 1p.
Subjects: Active learning, Constraint programming
Abstract: Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcq2 , that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcq2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcq2 in practice, especially in the case where QuAcq2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcq2 requires significantly fewer queries to learn a network than its predecessor QuAcq1. [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: 163163972
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Learning constraints through partial queries.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bessiere%2C+Christian%22">Bessiere, Christian</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> bessiere@lirmm.fr</i><br /><searchLink fieldCode="AR" term="%22Carbonnel%2C+Clément%22">Carbonnel, Clément</searchLink><relatesTo>1</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Dries%2C+Anton%22">Dries, Anton</searchLink><relatesTo>2</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Hebrard%2C+Emmanuel%22">Hebrard, Emmanuel</searchLink><relatesTo>3</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Katsirelos%2C+George%22">Katsirelos, George</searchLink><relatesTo>4,5</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Narodytska%2C+Nina%22">Narodytska, Nina</searchLink><relatesTo>6</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Quimper%2C+Claude-Guy%22">Quimper, Claude-Guy</searchLink><relatesTo>7</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Stergiou%2C+Kostas%22">Stergiou, Kostas</searchLink><relatesTo>8</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Tsouros%2C+Dimosthenis+C%2E%22">Tsouros, Dimosthenis C.</searchLink><relatesTo>8,9</relatesTo> (AUTHOR)<br /><searchLink fieldCode="AR" term="%22Walsh%2C+Toby%22">Walsh, Toby</searchLink><relatesTo>10,11</relatesTo> (AUTHOR)
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Artificial+Intelligence%22">Artificial Intelligence</searchLink>. Jun2023, Vol. 319, pN.PAG-N.PAG. 1p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Active+learning%22">Active learning</searchLink><br /><searchLink fieldCode="DE" term="%22Constraint+programming%22">Constraint programming</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcq2 , that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcq2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcq2 in practice, especially in the case where QuAcq2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcq2 requires significantly fewer queries to learn a network than its predecessor QuAcq1. [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=163163972
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.artint.2023.103896
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 1
        StartPage: N.PAG
    Subjects:
      – SubjectFull: Active learning
        Type: general
      – SubjectFull: Constraint programming
        Type: general
    Titles:
      – TitleFull: Learning constraints through partial queries.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bessiere, Christian
      – PersonEntity:
          Name:
            NameFull: Carbonnel, Clément
      – PersonEntity:
          Name:
            NameFull: Dries, Anton
      – PersonEntity:
          Name:
            NameFull: Hebrard, Emmanuel
      – PersonEntity:
          Name:
            NameFull: Katsirelos, George
      – PersonEntity:
          Name:
            NameFull: Narodytska, Nina
      – PersonEntity:
          Name:
            NameFull: Quimper, Claude-Guy
      – PersonEntity:
          Name:
            NameFull: Stergiou, Kostas
      – PersonEntity:
          Name:
            NameFull: Tsouros, Dimosthenis C.
      – PersonEntity:
          Name:
            NameFull: Walsh, Toby
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 06
              Text: Jun2023
              Type: published
              Y: 2023
          Identifiers:
            – Type: issn-print
              Value: 00043702
          Numbering:
            – Type: volume
              Value: 319
          Titles:
            – TitleFull: Artificial Intelligence
              Type: main
ResultId 1