A Pseudo-Boolean Set Covering Machine

详细信息    查看全文

• 作者：Pascal Germain (1) pascal.germain@ift.ulaval.ca
  Sébastien Giguère (1) sebastien.giguere.8@ulaval.ca
  Jean-Francis Roy (1) jean-francis.roy.1@ulaval.ca
  Brice Zirakiza (1) brice.zirakiza.1@ulaval.ca
  Fran?ois Laviolette (1) francois.laviolette@ift.ulaval.ca
  Claude-Guy Quimper (1) claude-guy.quimper@ift.ulaval.ca
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7598
• 期：1
• 页码：916-924
• 全文大小：276.3 KB
• 参考文献：1. Achterberg, T.: SCIP-a framework to integrate constraint and mixed integer programming. Konrad-Zuse-Zentrum für Informationstechnik (2004)
  2. Bishop, C.M.: Pattern Recognition and Machine Learning (Information Science and Statistics). Springer-Verlag New York, Inc., Secaucus (2006)
  3. Cortes, C., Vapnik, V.: Support-vector networks. Machine Learning 20(3), 273–297 (1995)
  4. Floyd, S., Warmuth, M.: Sample compression, learnability, and the vapnik-chervonenkis dimension. Machine Learning 21, 269–304 (1995)
  5. Hussain, Z., Szedmak, S., Shawe-Taylor, J.: The linear programming set covering machine (2004)
  6. Lynce, R.: Parallel search for boolean optimization (2011)
  7. Manquinho, V., Marques-Silva, J.: On using cutting planes in pseudo-boolean optimization. Journal on Satisfiability, Boolean Modeling and Computation 2, 209–219 (2006)
  8. Marchand, M., Shawe-Taylor, J.: The set covering machine. Journal of Machine Learning Research 3, 723–746 (2002)
  9. Marchand, M., Sokolova, M.: Learning with decision lists of data-dependent features. J. Mach. Learn. Res. 6, 427–451 (2005)
• 作者单位：1. Département d’informatique et de génie logiciel, Université Laval, Québec, Canada
• ISSN：1611-3349

文摘

The Set Covering Machine (SCM) is a machine learning algorithm that constructs a conjunction of Boolean functions. This algorithm is motivated by the minimization of a theoretical bound. However, finding the optimal conjunction according to this bound is a combinatorial problem. The SCM approximates the solution using a greedy approach. Even though SCM seems very efficient in practice, it is unknown how it compares to the optimal solution. To answer this question, we present a novel pseudo-Boolean optimization model that encodes the minimization problem. It is the first time a Constraint Programming approach addresses the combinatorial problem related to this machine learning algorithm. Using that model and recent pseudo-Boolean solvers, we empirically show that the greedy approach is surprisingly close to the optimal.