jmlr jmlr2010 jmlr2010-22 jmlr2010-22-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Kush R. Varshney, Alan S. Willsky
Abstract: A variational level set method is developed for the supervised classification problem. Nonlinear classifier decision boundaries are obtained by minimizing an energy functional that is composed of an empirical risk term with a margin-based loss and a geometric regularization term new to machine learning: the surface area of the decision boundary. This geometric level set classifier is analyzed in terms of consistency and complexity through the calculation of its ε-entropy. For multicategory classification, an efficient scheme is developed using a logarithmic number of decision functions in the number of classes rather than the typical linear number of decision functions. Geometric level set classification yields performance results on benchmark data sets that are competitive with well-established methods. Keywords: level set methods, nonlinear classification, geometric regularization, consistency, complexity
Shotaro Akaho. SVM that maximizes the margin in the input space. Systems and Computers in Japan, 35(14):78–86, December 2004. Erin L. Allwein, Robert E. Schapire, and Yoram Singer. Reducing multiclass to binary: A unifying approach to margin classifiers. Journal of Machine Learning Research, 1:113–141, December 2000. Arthur Asuncion and David J. Newman. http://archive.ics.uci.edu/ml/, 2007. UCI machine learning repository. Available at Peter L. Bartlett and Shahar Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463–482, November 2002. Peter L. Bartlett, Michael I. Jordan, and Jon D. McAuliffe. Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473):138–156, March 2006. Gilles Blanchard, Christin Sch¨ fer, Yves Rozenholc, and Klaus-Robert M¨ ller. Optimal dyadic a u decision trees. Machine Learning, 66(2–3):209–241, March 2007. Erik M. Boczko, Todd R. Young, Minhui Xie, and Di Wu. Comparison of binary classification based on signed distance functions with support vector machines. In Proceedings of the Ohio Collaborative Conference on Bioinformatics, Athens, Ohio, June 2006. 513 VARSHNEY AND W ILLSKY Xiongcai Cai and Arcot Sowmya. Level learning set: A novel classifier based on active contour models. In Joost N. Kok, Jacek Koronacki, Ramon Lopez de Mantaras, Stan Matwin, Dunja Mladeniˇ , and Andrzej Skowron, editors, Proceedings of the 18th European Conference on Mac chine Learning, pages 79–90, Warsaw, Poland, 2007. Vicent Caselles, Ron Kimmel, and Guillermo Sapiro. Geodesic active contours. International Journal of Computer Vision, 22(1):61–79, February 1997. Thomas Cecil, Jianliang Qian, and Stanley Osher. Numerical methods for high dimensional Hamilton–Jacobi equations using radial basis functions. Journal of Computational Physics, 196 (1):327–347, May 2004. Daniel Cremers, Mikael Rousson, and Rachid Deriche. A review of statistical approaches to level set segmentation: Integrating color, texture, motion and shape. International Journal of Computer Vision, 72(2):195–215, April 2007. Michel C. Delfour and Jean-Paul Zol´ sio. Shapes and Geometries: Analysis, Differential Calculus, e and Optimization. Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 2001. Carlotta Domeniconi, Dimitrios Gunopulos, and Jing Peng. Large margin nearest neighbor classifiers. IEEE Transactions on Neural Networks, 16(4):899–909, July 2005. Richard M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. Journal of Approximation Theory, 10(3):227–236, March 1974. Richard M. Dudley. Correction to “metric entropy of some classes of sets with differentiable boundaries”. Journal of Approximation Theory, 26(2):192–193, June 1979. Bradley Efron. The efficiency of logistic regression compared to normal discriminant analysis. Journal of the American Statistical Association, 70(352):892–898, December 1975. Arnaud Gelas, Olivier Bernard, Denis Friboulet, and R´ my Prost. Compactly supported radial e basis functions based collocation method for level-set evolution in image segmentation. IEEE Transactions on Image Processing, 16(7):1873–1887, July 2007. Tin Kam Ho and Mitra Basu. Complexity measures of supervised classification problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(3):289–300, March 2002. Chih-Wei Hsu and Chih-Jen Lin. A comparison of methods for multiclass support vector machines. IEEE Transactions on Neural Networks, 13(2):415–425, March 2002. Andrey N. Kolmogorov and Vladimir M. Tihomirov. ε-entropy and ε-capacity of sets in functional spaces. American Mathematical Society Translations Series 2, 17:277–364, 1961. Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transactions on Information Theory, 47(5):1902–1914, July 2001. Sanjeev R. Kulkarni. On metric entropy, Vapnik–Chervonenkis dimension, and learnability for a class of distributions. Technical Report P-1910, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, September 1989. 514 C LASSIFICATION U SING G EOMETRIC L EVEL S ETS Yi Lin. A note on margin-based loss functions in classification. Statistics & Probability Letters, 68 (1):73–82, June 2004. Ulrike von Luxburg and Olivier Bousquet. Distance-based classification with Lipschitz functions. Journal of Machine Learning Research, 5:669–695, June 2004. Stanley Osher and Ronald Fedkiw. Level Set Methods and Dynamic Implicit Surfaces. Springer, New York, 2003. Stanley Osher and James A. Sethian. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations. Journal of Computational Physics, 79(1):12–49, November 1988. Nikos Paragios and Rachid Deriche. Geodesic active regions and level set methods for supervised texture segmentation. International Journal of Computer Vision, 46(3):223–247, February 2002. Georg P¨ lzlbauer, Thomas Lidy, and Andreas Rauber. Decision manifolds—a supervised learning o algorithm based on self-organization. IEEE Transactions on Neural Networks, 19(9):1518–1530, September 2008. Ryan Rifkin and Aldebaro Klautau. In defense of one-vs-all classification. Journal of Machine Learning Research, 5:101–141, January 2004. Frank Rosenblatt. The perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386–408, 1958. Christophe Samson, Laure Blanc-F´ raud, Gilles Aubert, and Josiane Zerubia. A level set model for e image classification. International Journal of Computer Vision, 40(3):187–197, December 2000. Bernhard Sch¨ lkopf and Alexander J. Smola. Learning with Kernels: Support Vector Machines, o Regularization, Optimization, and Beyond. MIT Press, Cambridge, Massachusetts, 2002. Clayton Scott and Robert D. Nowak. Minimax-optimal classification with dyadic decision trees. IEEE Transactions on Information Theory, 52(4):1335–1353, April 2006. Xiaotong Shen and Wing Hung Wong. Convergence rate of sieve estimates. The Annals of Statistics, 22(2):580–615, June 1994. Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8):888–905, August 2000. Gregory G. Slabaugh, H. Quynh Dinh, and G¨ zde B. Unal. A variational approach to the evolution o of radial basis functions for image segmentation. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Minneapolis, Minnesota, June 2007. Ingo Steinwart. Consistency of support vector machines and other regularized kernel classifiers. IEEE Transactions on Information Theory, 51(1):128–142, January 2005. Mark Sussman, Peter Smereka, and Stanley Osher. A level set approach for computing solutions to incompressible two-phase flow. Journal of Computational Physics, 114(1):146–159, September 1994. 515 VARSHNEY AND W ILLSKY Arkadiusz Tomczyk. Active hypercontours and contextual classification. In Halina Kwasnicka and Marcin Paprzycki, editors, Proceedings of the 5th International Conference on Intelligent Systems Design and Applications, pages 256–261, Wroclaw, Poland, September 2005. Arkadiusz Tomczyk and Piotr S. Szczepaniak. On the relationship between active contours and contextual classification. In Marek Kurzy´ ski, Edward Puchała, Michał Wo´ niak, and Andrzej n z ˙ Zołnierek, editors, Proceedings of the 4th International Conference on Computer Recognition Systems, pages 303–310, Rydzyna, Poland, 2005. Arkadiusz Tomczyk and Piotr S. Szczepaniak. Adaptive potential active hypercontours. In Leszek Rutkowski, Ryszard Tadeusiewicz, Lotfi A. Zadeh, and Jacek Zurada, editors, Proceedings of the 8th International Conference on Artificial Intelligence and Soft Computing, pages 692–701, Zakopane, Poland, June 2006. Arkadiusz Tomczyk, Piotr S. Szczepaniak, and Michal Pryczek. Active contours as knowledge discovery methods. In Vincent Corruble, Masayuki Takeda, and Einoshin Suzuki, editors, Proceedings of the 10th International Conference on Discovery Science, pages 209–218, Sendai, Japan, 2007. Aad W. van der Vaart. Asymptotic Statistics. Cambridge University Press, Cambridge, England, 1998. Vladimir N. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, 1995. Kush R. Varshney and Alan S. Willsky. Supervised learning of classifiers via level set segmentation. In Proceedings of the IEEE Workshop on Machine Learning for Signal Processing, pages 115– 120, Canc´ n, Mexico, October 2008. u Luminita A. Vese and Tony F. Chan. A multiphase level set framework for image segmentation using the Mumford and Shah model. International Journal of Computer Vision, 50(3):271–293, December 2002. Holger Wendland. Scattered Data Approximation. Cambridge University Press, Cambridge, England, 2005. Rebecca Willett and Robert D. Nowak. Minimax optimal level-set estimation. IEEE Transactions on Image Processing, 16(12):2965–2979, December 2007. Robert C. Williamson, Alexander J. Smola, and Bernhard Sch¨ lkopf. Generalization performance of o regularization networks and support vector machines via entropy numbers of compact operators. IEEE Transactions on Information Theory, 47(6):2516–2532, September 2001. Andy M. Yip, Chris Ding, and Tony F. Chan. Dynamic cluster formation using level set methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(6):877–889, June 2006. Hui Zou, Ji Zhu, and Trevor Hastie. The margin vector, admissible loss and multi-class marginbased classifiers. Technical report, University of Minnesota, 2006. Hui Zou, Ji Zhu, and Trevor Hastie. New multicategory boosting algorithms based on multicategory Fisher-consistent losses. Annals of Applied Statistics, 2(4):1290–1306, December 2008. 516