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 area of research is Theoretical Computer Science. I'm particularly interested in Property Testing, Algorithmic Economics, Computational and Statistical Learning Theory, Approximation Algorithms, and Optimization. I'm advised by Avrim Blum and Jaime Carbonell.

Mathematical Theories of Interaction with Oracles: Research Statement Topics I've been working on: Sublinear Algorithms: Active Property Testing, Active Tolerant Testing Mechanism Design: Online Allocation/Pricing Problems with Economies of Scale, Correlated Auctions, Repeated Auctions, Prior Estimation applied to Combinatorial Auctions Learning DNF with Representation-Specific Queries Theory of Transfer Learning/Online Learning/Active Learning (Theory of Bayesian Active Learning, Active Learning with Drifting Distributions and Convex Losses, Buy-in-Bulk Active Learning) Computer Vision, Interactive Search-Assisted Diagnosis (CMU Diamond and Intel Research) Learning Distance Metrics (DistLearnKit)

Lectures and Service

• Teaching Statement
• Invited lecture on Mathematical Theories of Interaction with Oracles, School of Mathematics, Institute for Advanced Study, Feb 11, 2013.
• Active Property Testing, Algorithms and Complexity Seminar, MIT CSAIL Theory of Computation, MIT, Oct 4, 2012. Slides.
• Active Property Testing, Berkeley Theory Seminar, EECS Dept., UC Berkeley, Sep 24, 2012. A more recent talk at CS Theory Group, IBM Almaden Research Center, Jan 14, 2013. And an earlier talk at CMU Theory Lunch, Nov 9, 2011. Slides.
• Invited lecture on Combinatorial Approaches to Active Learning and Transfer Learning, the Courant Institute of Mathematical Sciences, Feb 19, 2013.
• Identifiability of Priors from Bounded Sample Sizes with Applications to Transfer Learning, CMU Machine Learning Lunch Seminar, Oct 31, 2011. Slides.
• Invited lecture on A Theory of Transfer Learning with Applications to Active Learning, at the Dept. of Brain and Cognitive Sciences, MIT, hosted by Tomaso Poggio, Feb 27, 2013.
• Active Learning, Drifting Distributions, and Convex Losses, CMU Machine Learning Lunch Seminar, Apr 30, 2012. Slides. Invited talk on this work at EECS Dept., UC Berkeley, hosted by Peter Bartlett, Jan 23, 2013.
• Invited 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.
• Invited 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-750 Graduate Algorithms (Spring 2011), taught by Manuel Blum in the Computer Science Dept., CMU. Invited guest lecture on Online Learning Mistake Bound Model.
• 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.
  
• Program Committee: ICML (2012, 2013). Reviewer: ICML (2009), COLT 2011, CVPR (2012, 2013), ICCV 2013, J. Machine Learning Research, IEEE Trans Pattern Anal Mach Intell. (TPAMI).

Publications

Preprints and Working Papers

• Thesis Defense: Mathematical Theories of Interaction with Oracles. Ph.D. Thesis (draft), 2013. Thesis Committee: Avrim Blum, Manuel Blum, Jaime Carbonell, Sanjoy Dasgupta, Yishay Mansour, Joel Spencer. Slides.
• Pricing with Decreasing Marginal Cost. With Avrim Blum and Yishay Mansour. Manuscript.
• Factor Models for Correlated Auctions. With Pablo Azar and Silvio Micali. Manuscript.
• Surrogate Losses in Passive and Active Learning. With Steve Hanneke. [arXiv:1207.3772]. In submission to the Annals of Statistics.

2013

• Liu Yang, Avrim Blum and Jaime Carbonell. Learnability of DNF with Representation-Specific Queries. Innovations in Theoretical Computer Science (ITCS), 2013. Slides.
  
• Liu Yang and Steve Hanneke. Activized Learning with Uniform Classification Noise. The International Conference on Machine Learning (ICML), 2013.

2012

• Active Property Testing. With Nina Balcan, Eric Blais, Avrim Blum. FOCS 2012. [arXiv:1111.0897v2 (full version)].
• Liu Yang, Steve Hanneke and Jaime Carbonell. A Theory of Transfer Learning with Applications to Active Learning. Machine Learning, 2012.
  
• Liu Yang and Jaime Carbonell. Buy-in-Bulk Active Learning. Tech report CMU-ML-12-110.
• Liu Yang, Steve Hanneke and Jaime Carbonell. Bounds on the Minimax Rate for Estimating a Prior over a VC Class from Independent Learning Tasks. Tech report CMU-ML-12-112.

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. 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.

Selected Past Talks

• Learnability of DNF with Representation-Specific Queries. Apr 11, 2012. CMU Theory Lunch, Algorithms and Complexity Theory Group, Carnegie Mellon University.
• 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.
• 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), MIT, Cambridge.
• Applying Local Distance Metric Learning to Image Retrieval. July 21, 2006. Brigham and Women's Hospital, Harvard Medical School, Boston, Massachusetts.
• An Efficient Algorithm for Local Distance Metric Learning. July 18, 2006. AAAI-06: Twenty-First National Conference on Artificial Intelligence, Boston, Massachusetts.

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

[Last updated 2013]