Document Open Access Logo

Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification

Authors Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, Joseph (Seffi) Naor, Roy Schwartz

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.34.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Shahar Chen
Dotan Di Castro
Zohar Karnin
Liane Lewin-Eytan
Joseph (Seffi) Naor
Roy Schwartz

Cite As Get BibTex

Shahar Chen, Dotan Di Castro, Zohar Karnin, Liane Lewin-Eytan, Joseph (Seffi) Naor, and Roy Schwartz. Correlated Rounding of Multiple Uniform Matroids and Multi-Label Classification. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.34

Abstract

We introduce correlated randomized dependent rounding where, given multiple points y^1,...,y^n in some polytope P\subseteq [0,1]^k, the goal is to simultaneously round each y^i to some integral z^i in P while preserving both marginal values and expected distances between the points. In addition to being a natural question in its own right, the correlated randomized dependent rounding problem is motivated by multi-label classification applications that arise in machine learning, e.g., classification of web pages, semantic tagging of images, and functional genomics. The results of this work can be summarized as follows: (1) we present an algorithm for solving the correlated randomized dependent rounding problem in uniform matroids while losing only a factor of O(log{k}) in the distances (k is the size of the ground set); (2) we introduce a novel multi-label classification problem, the metric multi-labeling problem, which captures the above applications. We present a (true) O(log{k})-approximation for the general case of metric multi-labeling and a tight 2-approximation for the special case where there is no limit on the number of labels that can be assigned to an object.

Subject Classification

Keywords
  • approximation algorithms
  • randomized rounding
  • dependent rounding
  • metric labeling
  • classification

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. A. Ageev and M. I. Sviridenko. Pipage rounding: a new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8:307-328, 2004. Google Scholar
  2. Arash Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and Amin Saberi. An O(log n/ log log n)-approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'10, pages 379-389, 2010. Google Scholar
  3. Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. SIAM J. Comput., 39(7):2970-2989, 2010. Google Scholar
  4. Zafer Barutçuoglu, Robert E. Schapire, and Olga G. Troyanskaya. Hierarchical multi-label prediction of gene function. Bioinformatics, 22(7):830-836, 2006. Google Scholar
  5. Hendrik Blockeel, Leander Schietgat, Jan Struyf, Saso Dzeroski, and Amanda Clare. Decision trees for hierarchical multilabel classification: A case study in functional genomics. In PKDD, pages 18-29, 2006. Google Scholar
  6. Avrim Blum, Carl Burch, and Adam Kalai. Finely-competitive paging. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS'99, pages 450-457, 1999. Google Scholar
  7. Matthew R. Boutell, Jiebo Luo, Xipeng Shen, and Christopher M. Brown. Learning multi-label scene classification. Pattern Recognition, 37(9):1757-1771, 2004. Google Scholar
  8. Yuri Boykov, Olga Veksler, and Ramin Zabih. Markov random fields with efficient approximations. In CVPR, pages 648-655, 1998. Google Scholar
  9. Niv Buchbinder, Joseph (Seffi) Naor, and Roy Schwartz. Simplex partitioning via exponential clocks and the multiway cut problem. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC'13, pages 535-544, 2013. Google Scholar
  10. Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrak. Maximizing a submodular set function subject to a matroid constraint. SIAM Journal on Computing, 2011. Google Scholar
  11. Gruia Călinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. In SODA'01, pages 8-16, 2001. Google Scholar
  12. Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 575-584, 2010. Google Scholar
  13. R Chellappa and A. Jain. Markov Random Fields: Theory and Applications. Academic Press, 1993. Google Scholar
  14. Koby Crammer and Yoram Singer. On the algorithmic implementation of multiclass kernel-based vector machines. JMLR, 2:265-292, 2002. Google Scholar
  15. Gruia Călinescu, Howard Karloff, and Yuval Rabani. An improved approximation algorithm for multiway cut. J. Comput. Syst. Sci., 60(3):564-574, 2000. Google Scholar
  16. William H. Cunningham and Lawrence Tang. Optimal 3-terminal cuts and linear programming. In IPCO'99, pages 114-125, 1999. Google Scholar
  17. E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23:864-894, 1994. Google Scholar
  18. Richard C. Dubes and Anil K. Jain. Random field models in image analysis. Journal of Applied Statistics, 16(2):131-164, 2006. Google Scholar
  19. Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar. An improved approximation algorithm for the 0-extension problem. In SODA'03, pages 257-265, 2003. Google Scholar
  20. Evelyn Fix and Joseph L. Hodges Jr. Discriminatory analysis-nonparametric discrimination: consistency properties. Technical report, DTIC Document, 1951. Google Scholar
  21. Yoav Freund and Robert E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997. Google Scholar
  22. Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. J. ACM, 53(3):324-360, 2006. Google Scholar
  23. David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, and Neal E. Young. Rounding algorithms for a geometric embedding of minimum multiway cut. Math. Oper. Res., 29(3):436-461, 2004. Google Scholar
  24. Hisashi Kashima, Satoshi Oyama, Yoshihiro Yamanishi, and Koji Tsuda. On pairwise kernels: An efficient alternative and generalization analysis. In Advances in Knowledge Discovery and Data Mining, pages 1030-1037. Springer, 2009. Google Scholar
  25. Jon M. Kleinberg and Éva Tardos. Approximation algorithms for classification problems with pairwise relationships: metric labeling and markov random fields. J. ACM, 49(5):616-639, 2002. Google Scholar
  26. V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, and Aravind Srinivasan. A unified approach to scheduling on unrelated parallel machines. J. ACM, 56(5):28:1-28:31, 2009. Google Scholar
  27. Stan Z. Li. Markov random field modeling in computer vision. Computer science workbench. Springer, 1995. Google Scholar
  28. Rajsekar Manokaran, Joseph (Seffi) Naor, Prasad Raghavendra, and Roy Schwartz. Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC'08, pages 11-20, 2008. Google Scholar
  29. Stephen Della Pietra, Vincent J. Della Pietra, and John D. Lafferty. Inducing features of random fields. IEEE Trans. Pattern Anal. Mach. Intell., 19(4):380-393, 1997. Google Scholar
  30. Guo-Jun Qi, Xian-Sheng Hua, Yong Rui, Jinhui Tang, Tao Mei, and Hong-Jiang Zhang. Correlative multi-label video annotation. In Proceedings of ACMMM'07, pages 17-26, 2007. Google Scholar
  31. J. Ross Quinlan. C4.5: Programs for Machine Learning. Elsevier, 2014. Google Scholar
  32. Prabhakar Raghavan and Clark D. Tompson. Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. Google Scholar
  33. Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. Classifier chains for multi-label classification. Machine learning, 85(3):333-359, 2011. Google Scholar
  34. Mohammad S Sorower. A literature survey on algorithms for multi-label learning. Technical report, 2010. Google Scholar
  35. A. Srinivasan. Distributions on level-sets with applications to approximation algorithms. In Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 588-597, 2001. Google Scholar
  36. Grigorios Tsoumakas and Ioannis Katakis. Multi-label classification: An overview. International Journal of Data Warehousing and Mining, 3(3):1-13, 2007. Google Scholar
  37. Grigorios Tsoumakas, Ioannis Katakis, and Ioannis Vlahavas. Mining multi-label data. In In Data Mining and Knowledge Discovery Handbook, pages 667-685, 2010. Google Scholar
  38. Naonori Ueda and Kazumi Saito. Parametric mixture models for multi-labeled text. In NIPS, pages 721-728, 2002. Google Scholar
  39. Adriano Veloso, Wagner Meira Jr., Marcos André Gonçalves, and Mohammed Javeed Zaki. Multi-label lazy associative classification. In PKDD, pages 605-612, 2007. Google Scholar
  40. Jianguo Zhang, Marcin Marszałek, Svetlana Lazebnik, and Cordelia Schmid. Local features and kernels for classification of texture and object categories: A comprehensive study. International journal of computer vision, 73(2):213-238, 2007. Google Scholar
  41. Min-Ling Zhang and Zhi-Hua Zhou. Ml-knn: A lazy learning approach to multi-label learning. Pattern Recognition, 40:2007, 2007. Google Scholar
  42. Zhi-Hua Zhou and Min-Ling Zhang. Multi-instance multi-label learning with application to scene classification. In Proceedings of NIPS, pages 1609-1616, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact