报告题目：Random Gradient Descent Tree: A Combinatorial Approach for SVM with Outliers

报告人：Jinhui Xu (徐金辉) 教授（State University of New York at Buffalo）

时间：2016年7月25日上午10:00-11:00

地点：天赐庄校区理工楼633室

报告摘要：Support Vector Machine (SVM) is a fundamental technique in machine learning. A long time challenge facing SVM is how to deal with outliers (caused by mislabeling), as they could make the classes in SVM nonseparable. Existing techniques, such as soft margin SVM, ν-SVM, and Core-SVM, can alleviate the problem to certain extent, but cannot completely resolve the issue. Recently, there are also techniques available for explicit outlier removal. But they suffer from high time complexity and cannot guarantee quality of solution. In this paper, we present a new combinatorial approach, called Random Gradient Descent Tree (or RGD-tree), to explicitly deal with outliers; this results in a new algorithm called RGD-SVM. Our technique yields provably good solution and can be efficiently implemented for practical purpose. The time and space complexities of our approach only linearly depend on the input size and the dimensionality of the space, which are significantly better than existing ones. Experiments on benchmark datasets suggest that our technique considerably outperforms several popular techniques in most of the cases.

报告人介绍：Dr. Xu is currently a professor of Computer Science and Engineering at the University at Buffalo (the State University of  New York). He received his B.S. and M.S. degrees in Computer Science from the University of Science and Technology of China (USTC), and his Ph.D. degree in Computer Science and Engineering from the University of Notre Dame in 2000. Dr. Xu's research interest lies in the fields of Algorithms, Computational Geometry, Combinatorial Optimization, Machine Learning, and their applications in several applied areas. His recent research has focused on the development of geometric algorithms and machine learning methods for problems arising in medicine (medical imaging and interventional procedures for intracranial aneurysms), biology (determining the spatial patterns of chromosome organization inside the cell nucleus, as well as their alterations in cell differentiation, cell cycle, and progression of diseases such as cancer), networking, and 3D printing. Dr. Xu's research has been supported by National Science Foundation (NSF), National Institute of Health (NIH), NYSTAR, IBM, and University at Buffalo. He is a recipient of UB Exceptional Scholar: Sustained Achievement Award (2015), SEAS Senior Researcher of the Year Award (2015), the NSF CAREER Award (2005) and the IBM Faculty Partnership Award (2001).