Liu Yang liuy@cs.cmu.edu     My CV 8003 GHC, School of Computer Science, Carnegie Mellon University Pittsburgh, PA 15213-3891 Tel: (517) 526-2509 (cell)     (412) 268-6289 (office) I am a Ph.D. student in the School of Computer Science at Carnegie Mellon University. My advisors are Avrim Blum and Jaime Carbonell. My area of research is Theoretical Computer Science. I'm particularly interested in Property Testing, Algorithmic Economics, Active Learning, Computational (Statistical) Learning Theory, and Optimization. I am currently on the job market.

Mathematical Theories of Interaction with Oracles: Research Statement Topics I've been working on: Sublinear Algorithms, Active (and Passive) Property Testing Differential Privacy, Privacy-Preserving Property Testing Online Allocation Problems under Economies of Scale ("Buy-in-Bulk" Online Matching) Prior Estimation for Mechanism Design, Prior Estimation for VC Classes, Transfer Learning Learning from Pairwise Similarity Queries, Learning DNF with Representation-Specific Queries Streaming Algorithms, Buy-in-Bulk Active Learning, Active Learning with Drifting Distributions Active Learning w/ Convex Losses, Sample Complexity for Active Learning w/ Various Noises Theory of (Bayesian) Active Learning Online Learning, Semi-supervised Learning, Distance Metric Learning Computer Vision, Medical Vision: Algorithm Design & Optimization

Teaching and Service

• Teaching Statement
• Invited Guest Lectures on Property Testing, Theory of Active Learning, Transfer Learning in 15-859(B) Machine Learning Theory (Spring 2012), taught by Avrim Blum in the Computer Science Dept., CMU.
  Here is my recent Talk on Theory of Transfer Learning at CMU Machine Learning Lunch Seminar, October 31, 2011. Slides.
• Teaching assistant for 15-750 Graduate Algorithms (Spring 2011), taught by Manuel Blum in the Computer Science Dept., CMU.
• Invited Guest Lecture on Online Learning Mistake Bound Model in 15-750 Graduate Algorithms (Spring 2011), taught by Manuel Blum in the Computer Science Dept., CMU.
• Invited Guest Lecture on Prior Estimation for VC Classes in 36-755 Advanced Statistical Theory I (Fall 2011), taught by Steve Hanneke in the Dept. of Statistics, CMU.
• Teaching assistant for 15-355 Modern Computer Algebra (Fall 2011), taught by Victor Adamchik in the Computer Science Dept., CMU. Invited guest lecture on Gröbner Bases in 15-355.
• Program Committee: ICML 2012. Reviewer: ICML 2009, COLT 2011, CVPR 2012, J. Machine Learning Research, IEEE Trans Pattern Anal Mach Intell. (TPAMI), Machine Vision & Applications.
• Here is my recent talk on Active Learning, Drifting Distributions, and Convex Surrogate Losses at CMU Machine Learning Lunch Seminar, April 30, 2012. Slides.

Selected Publications

Preprints and Working Papers

• Mathematical Theories of Interaction with Oracles. Ph.D. thesis (draft), 2012. Thesis Committee: Avrim Blum, Manuel Blum, Jaime Carbonell, Sanjoy Dasgupta, Yishay Mansour .
• Active Property Testing. With Nina Balcan, Eric Blais, Avrim Blum. Submitted to FOCS 2012. [arXiv:1111.0897v2].
  Here is my talk on Active Testing at CMU Theory Lunch, November 9, 2011. Slides .
• Pricing with Decreasing Marginal Cost. With Avrim Blum and Yishay Mansour. Manuscript.
• Liu Yang, Avrim Blum and Jaime Carbonell. Learnability of DNF with Representation-Specific Queries. Submitted to FOCS 2012.
  Here is my recent talk on this work at CMU Theory Lunch, April 11, 2012. Slides .
• Liu Yang, Steve Hanneke and Jaime Carbonell. Bounds on the Minimax Rate for Estimating a Prior over a VC Class from Independent Learning Tasks. Manuscript.
• Liu Yang and Steve Hanneke. Activized Learning with Uniform Classification Noise. Manuscript.
• Surrogate Losses in Passive and Active Learning. With Steve Hanneke. In submission to the Annals of Statistics.
• Minimax Bounds for Active Learning under Tsybakov Noise. With Steve Hanneke. Working paper.

2011

• Thesis Proposal: Active Perspectives on Computational Learning and Testing. Slides.
  
• Liu Yang. Active Learning with a Drifting Distribution. Advances in Neural Information Processing Systems (NIPS) 2011.
• Liu Yang, Steve Hanneke and Jaime Carbonell. A Theory of Transfer Learning with Applications to Active Learning. Machine Learning Jounal. (To Appear).
• Liu Yang, Steve Hanneke and Jaime Carbonell. Identifiability of Priors from Bounded Sample Sizes with Applications to Transfer Learning . The 24th Annual Conference on Learning Theory (COLT), Budapest, Hungary, 2011.
• Liu Yang, Steve Hanneke and Jaime Carbonell. The Sample Complexity of Self-Verifying Bayesian Active Learning. International Conference on Artificial Intelligence and Statisitcs (AISTATS), 2011.

2010

• Liu Yang, Steve Hanneke and Jaime Carbonell. Characterizing Optimal Rates for Lossy Coding with Finite-Dimensional Metrics. Manuscript.
• Liu Yang, Steve Hanneke and Jaime Carbonell. Bayesian Active Learning Using Arbitrary Binary Valued Queries. Proceedings of the 21st International Conference on Algorithmic Learning Theory (ALT), 2010.
• Steve Hanneke and Liu Yang. Negative Results for Active Learning with Convex Losses. International Conference on Artificial Intelligence and Statisitcs (AISTATS), 2010.

2009

• Liu Yang and Jaime Carbonell. Cost Complexity of Proactive Learning via a Reduction to Realizable Active Learning. Tech report CMU-ML-09-113.
• Liu Yang and Jaime Carbonell. Adaptive Proactive Learning with Cost-Reliability Tradeoff. Tech report CMU-ML-09-114.
• Liu Yang, Rong Jin and Jieping Ye. Online Learning by Ellipsoid Method. The International Conference on Machine Learning (ICML), 2009.
• Liu Yang, Rong Jin, Lily Mummert, Rahul Sukthankar, Adam Goode, Bin Zheng, Stephen Hoi and Madadev Satyanarayanan. A Boosting Framework for Visuality-Preserving Distance Metric Learning and its Application to Medical Image Retrieval. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010 January, 32(1):30-44..

2008

• Liu Yang, Rong Jin and Rahul Sukthankar. Semi-supervised Learning with Weakly-Related Unlabeled Data: Towards Better Text Categorization. Advances in Neural Information Processing Systems (NIPS) 2008.
• Liu Yang, Rong Jin, Rahul Sukthankar and Frederic Jurie. Unifying Discriminative Visual Codebook Generation with Classifier Training for Object Category Recognition.Proceedings of Computer Vision and Pattern Recognition, 2008.(Oral Presentation)

2007

• Liu Yang, Rong Jin and Rahul Sukthankar. Bayesian Active Distance Metric Learning. Proceedings of UAI, 2007. (Oral Presentation)
• Liu Yang, Rong Jin, Caroline Pantofaru and Rahul Sukthankar. Discriminative Cluster Refinement: Improving Object Category Recognition Given Limited Training Data. Proceedings of Computer Vision and Pattern Recognition, 2007.
• Liu Yang, Rong Jin and Rahul Sukthankar. Resource-Constrained Supervised Dimensionality Reduction. Proceedings of IJCAI Workshop on Multimodal Information Retrieval, 2007.
• Liu Yang, Rong Jin and Rahul Sukthankar, Bin Zheng, Lily Mummert, Mahadev Satyanarayanan, Mei Chen and Drazen Jukic. Learning Distance Metrics for Interactive Search-Assisted Diagnosis of Mammograms. Proceedings of SPIE Medical Imaging (Oral Presentation), 2007.

2006

• Liu Yang, Rong Jin, Rahul Sukthankar and Yi Liu. An Efficient Algorithm for Local Distance Metric Learning. (Oral Prensentation) Proceedings of AAAI, 2006.
• Yi Liu, Rong Jin and Liu Yang. Semi-supervised Multi-label Learning by Constrained Non-negative Matrix Factorization. (Oral Prensentation) Proceedings of AAAI, 2006.

Invited Talks

• Learnability of DNF with Representation-Specific Queries. April 11, 2012. CMU Theory Lunch, Algorithms and Complexity Theory Group, Carnegie Mellon University.
• Active Testing. November 9, 2011. CMU Theory Lunch, Algorithms and Complexity Theory Group, Carnegie Mellon University.
• Identifiability of Priors from Bounded Sample Sizes with Applications to Transfer Learning. October 31, 2011. Carnegie Mellon Machine Learning Lunch Seminar, Carnegie Mellon University.
• Discriminative Cluster Refinement: Improving Object Category Recognition Given Limited Training Data. July 19, 2007. Vision and Media Lab, Simon Fraser University, Burnaby, BC, Canada.
• Improving Object Recognition by Discriminative Cluster Refinement. June 11, 2007. The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA.
• Local Distance Metric Learning. July 21, 2006. Biomedical Imaging and Analysis Lab, Computer Science and Artificial Intelligence Laboratory (CSAIL), Massachusetts Institute of Technology (MIT), Cambridge.
• Applying Local Distance Metric Learning to Image Retrieval. July 21, 2006. Brigham and Women's Hospital, Harvard Medical School, Boston, Massachusetts.

Selected Conference Talks

• Mathematical Theories of Interaction with (Human) Oracles. January 9, 2012. Graduating bits: Finishing Ph.D.'s and Postdoc Short Presentation in the 3rd Innovations in Theoretical Computer Science (ITCS) conference, Cambridge, Massachusetts.
• Online Learning by Ellipsoid Method. June 15, 2009. Oral Presentation in the 26th International Conference on Machine Learning, Montreal, Canada.
• Bayesian Active Distance Metric Learning. July 20, 2007. Oral Presentation in the 23rd Conference on Uncertainty in Artificial Intelligence, University of British Columbia Vancouver, BC, Canada.
• An Efficient Algorithm for Local Distance Metric Learning. July 18, 2006. AAAI-06: Twenty-First National Conference on Artificial Intelligence, Boston, Massachusetts.

DistLearnKit
Distance Metric Learning: A Comprehensive Survey [slides]
An Overview of Distance Metric Learning

[Last updated 2012]