Generating CP-Nets Uniformly at Random

Authors

  • Thomas Allen University of Kentucky
  • Judy Goldsmith University of Kentucky
  • Hayden Justice The Gatton Academy, WKU
  • Nicholas Mattei Data61 and University of New South Wales
  • Kayla Raines University of Kentucky

DOI:

https://doi.org/10.1609/aaai.v30i1.10115

Keywords:

preferences, CP-nets, uniform generation, directed acyclic graphs, dags

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 naive 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.

Downloads

Published

2016-02-21

How to Cite

Allen, T., Goldsmith, J., Justice, H., Mattei, N., & Raines, K. (2016). Generating CP-Nets Uniformly at Random. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). https://doi.org/10.1609/aaai.v30i1.10115

Issue

Section

Technical Papers: Knowledge Representation and Reasoning