Democratic approximation of lexicographic preference models

ABSTRACT

Previous algorithms for learning lexicographic preference models (LPMs) produce a "best guess" LPM that is consistent with the observations. Our approach is more democratic: we do not commit to a single LPM. Instead, we approximate the target using the votes of a collection of consistent LPMs. We present two variations of this method---variable voting and model voting---and empirically show that these democratic algorithms outperform the existing methods. We also introduce an intuitive yet powerful learning bias to prune some of the possible LPMs. We demonstrate how this learning bias can be used with variable and model voting and show that the learning bias improves the learning curve significantly, especially when the number of observations is small.

REFERENCES

• 1: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, 1997
• 2: Dombi, J., Imreh, C., & Vincze, N. (2007). Learning lexicographic orders. European Journal of Operational Research, 183, 748--756.
• 3: Fishburn, P. (1974). Lexicographic Orders, Utilities and Decision Rules: A Survey. Management Science, 20, 1442--1471.
• 4: Quesada, A. (2003). Negative results in the theory of games with lexicographic utilities. Economics Bulletin, 3, 1--7.
• 5: Ronald L. Rivest, Learning Decision Lists, Machine Learning, v.2 n.3, p.229-246, November 1987 [doi>10.1023/A:1022607331053]
• 6: Michael Schmitt , Laura Martignon, On the Complexity of Learning Lexicographic Strategies, The Journal of Machine Learning Research, 7, p.55-83, 12/1/2006

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Special function approximations

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory