Generating CP-nets uniformly at random

Thomas E. Allen; Judy Goldsmith; Hayden E. Justice; Nicholas Mattei; Kayla Raines

Generating CP-nets uniformly at random

Thomas E. Allen, Judy Goldsmith, Hayden E. Justice, Nicholas Mattei, Kayla Raines

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

11 Scopus citations

Abstract

Conditional preference networks (CP-nets) are a commonly studied compact formalism for modeling preferences. To study the properties of CP-nets or the performance of CP-net algorithms on average, one needs to generate CP-nets in an equiprobable manner. We discuss common problems with näive generation, including sampling bias, which invalidates the base assumptions of many statistical tests and can undermine the results of an experimental study. We provide a novel algorithm for provably generating acyclic CP-nets uniformly at random. Our method is computationally efficient and allows for multi-valued domains and arbitrary bounds on the indegree in the dependency graph.

Original language	English
Title of host publication	30th AAAI Conference on Artificial Intelligence, AAAI 2016
Pages	872-878
Number of pages	7
ISBN (Electronic)	9781577357605
State	Published - 2016
Event	30th AAAI Conference on Artificial Intelligence, AAAI 2016 - Phoenix, United States Duration: Feb 12 2016 → Feb 17 2016

Publication series

Name	30th AAAI Conference on Artificial Intelligence, AAAI 2016

Conference

Conference	30th AAAI Conference on Artificial Intelligence, AAAI 2016
Country/Territory	United States
City	Phoenix
Period	2/12/16 → 2/17/16

Bibliographical note

Publisher Copyright:
© Copyright 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

ASJC Scopus subject areas

Artificial Intelligence

Cite this

@inproceedings{26cf3d598e07400f929182f0dfea1516,

title = "Generating CP-nets uniformly at random",

abstract = "Conditional preference networks (CP-nets) are a commonly studied compact formalism for modeling preferences. To study the properties of CP-nets or the performance of CP-net algorithms on average, one needs to generate CP-nets in an equiprobable manner. We discuss common problems with n{\"a}ive generation, including sampling bias, which invalidates the base assumptions of many statistical tests and can undermine the results of an experimental study. We provide a novel algorithm for provably generating acyclic CP-nets uniformly at random. Our method is computationally efficient and allows for multi-valued domains and arbitrary bounds on the indegree in the dependency graph.",

author = "Allen, {Thomas E.} and Judy Goldsmith and Justice, {Hayden E.} and Nicholas Mattei and Kayla Raines",

note = "Publisher Copyright: {\textcopyright} Copyright 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 30th AAAI Conference on Artificial Intelligence, AAAI 2016 ; Conference date: 12-02-2016 Through 17-02-2016",

year = "2016",

language = "English",

series = "30th AAAI Conference on Artificial Intelligence, AAAI 2016",

pages = "872--878",

booktitle = "30th AAAI Conference on Artificial Intelligence, AAAI 2016",

}

TY - GEN

T1 - Generating CP-nets uniformly at random

AU - Allen, Thomas E.

AU - Goldsmith, Judy

AU - Justice, Hayden E.

AU - Mattei, Nicholas

AU - Raines, Kayla

PY - 2016

Y1 - 2016

N2 - Conditional preference networks (CP-nets) are a commonly studied compact formalism for modeling preferences. To study the properties of CP-nets or the performance of CP-net algorithms on average, one needs to generate CP-nets in an equiprobable manner. We discuss common problems with näive generation, including sampling bias, which invalidates the base assumptions of many statistical tests and can undermine the results of an experimental study. We provide a novel algorithm for provably generating acyclic CP-nets uniformly at random. Our method is computationally efficient and allows for multi-valued domains and arbitrary bounds on the indegree in the dependency graph.

AB - Conditional preference networks (CP-nets) are a commonly studied compact formalism for modeling preferences. To study the properties of CP-nets or the performance of CP-net algorithms on average, one needs to generate CP-nets in an equiprobable manner. We discuss common problems with näive generation, including sampling bias, which invalidates the base assumptions of many statistical tests and can undermine the results of an experimental study. We provide a novel algorithm for provably generating acyclic CP-nets uniformly at random. Our method is computationally efficient and allows for multi-valued domains and arbitrary bounds on the indegree in the dependency graph.

UR - http://www.scopus.com/inward/record.url?scp=85007180297&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85007180297&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85007180297

T3 - 30th AAAI Conference on Artificial Intelligence, AAAI 2016

SP - 872

EP - 878

BT - 30th AAAI Conference on Artificial Intelligence, AAAI 2016

T2 - 30th AAAI Conference on Artificial Intelligence, AAAI 2016

Y2 - 12 February 2016 through 17 February 2016

ER -

Generating CP-nets uniformly at random

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this