|
|
|
|
BEN RUBINSTEIN
PROJECTS- Ongoing Projects
- Security of Machine Learning in Systems (SecML)
- Sample Compression, Mistake Bounds and Concept Class Representations
- Algorithmic Stability of ERM under Multiple Risk Minimizers
- Past Projects
| Security of Machine Learning in Systems - ONGOING PROJECT |
|---|
PROJECT DESCRIPTIONThis work assesses the security of machine learning algorithms in computer systems operating in adversarial environments. I am interested in the experimental and theoretical analysis of existing systems, such as email spam filtering, network anomaly detection, automatic worm signature generation, and detection of phishing webpage. Work within these domains involves designing attacks on learners, devising effective counter-measures, and producing theoretical guarantees on a learner's robustness (or lack thereof) to adversarially compromised data.
A second complementary goal is the theoretical understanding of inherent trade-offs between generalization and security in whole families of learners, and across varying levels of adversarial information & control. While SecML offers a practical venue for worst-case analysis, opportunities come with the challenge of incorporating realistic threat models of adversarial capabilities that do not feature in existing studies.
See also the project descriptions in the RAD Lab's SecML project page and the 2007 EECS Research Summaries.
COLLABORATORS
Marco A. Barreno (now Google), Peter L. Bartlett (Berkeley CS and Stat), Jack Chi (Berkeley CS), Ling Huang (Intel Research Berkeley), Anthony D. Joseph (Berkeley CS and Intel Research Berkeley), Blaine Nelson (Berkeley CS), Udam Saini (Berkeley CS), Charles Sutton (Berkeley CS), Nina Taft (Intel Research Berkeley), Doug Tygar (Berkeley CS & I School), Kai Xia (Berkeley CS)
PRESENTATIONS
- Conference poster, Evading Anomaly Detection through Variance Injection Attacks on PCA, at RAID08, MIT, Boston, MA, September 2008.
- Seminar at Yahoo! Research, Security of Machine Learning, Machine Learning Reading Group, Santa Clara, CA, June 2008.
- Qualifying exam, Fundamental Limits on the Security of Systems that Learn at Berkeley EECS Department, May 2008.
- Workshop talk, Exploiting machine learning to subvert your spam filter, at LEET08, San Francisco, CA, April 2008.
- Workshop poster, Attacking SpamBayes: Compromising a Statistical Spam Filter at the NIPS07 Workshop on Machine Learning in Adversarial Environments for Computer Security, Dec 2007.
- Marco Barreno, Peter L. Bartlett, Fuching Jack Chi, Anthony D. Joseph, Blaine Nelson, Benjamin I. P. Rubinstein and J. D. Tygar, Open Problems in the Security of Learning. Accepted into The First ACM Workshop on AISec, 2008
- B. I. P. Rubinstein, B. Nelson, L. Huang, A. D. Joseph, S.-H. Lau, N. Taft and J. D. Tygar, Compromising PCA-based anomaly detectors for network-wide traffic. UC Berkeley, Department of EECS technical report UCB/EECS-2008-73, May 29 2008
- B. I. P. Rubinstein, B. Nelson, L. Huang, A. D. Joseph, S.-H. Lau, N. Taft and J. D. Tygar, Evading Anomaly Detection through Variance Injection Attacks on PCA (Extended Abstract). To appear in the 11th International Symposium on Recent Advances in Intrusion Detection (RAID 2008), 2008.
- B. Nelson, M. Barreno, F. J. Chi, A. D. Joseph, B. I. P. Rubinstein, U. Saini, C. Sutton, J. D. Tygar and K. Xia, Exploiting machine learning to subvert your spam filter, in the Proceedings of the First Usenix Workshop on Large-Scale Exploits and Emergent Threats (LEET), 2008.
| Sample Compression, Mistake Bounds and Concept Class Representations - ONGOING PROJECT |
|---|
PROJECT DESCRIPTIONThis work explores a number of related problems in statistical learning theory centered around general geometric representations of concept classes. Concept classes on a finite domain X correspond to subsets of the Boolean |X|-cube, and connecting points differing on only one component by edges forms what's called the one-inclusion graph. A deep relationship between Valiant's Probably Approximately Correct (PAC) learning model and the one-inclusion graph has emerged.
A bound on the one-inclusion graph density by the underlying concept class's Vapnik-Chervonenkis (VC) dimension leads to a bound on the worst-case expected risk of the graph's prediction strategy. In our NIPS06 paper we tightened the graph density bound, resolving a conjecture of Kuzmin & Warmuth's, and by bounding one-inclusion hypergraph density were able to develop mistake bounds for multi-class classification. The full-length paper explored cubical complex characterizations of concept classes that are maximum (having the largest cardinality for their VC-dimension) and maximal (experiencing an increase to VC-dimension with the addition of any new concept). In particular we extended the result of Dudley that all VC-1 maximum classes have one-inclusion trees, to VC-d maximum classes being contractible d-dimensional cubical complexes (algebraic topology's higher dimensional analogue of the tree).
Our motivation for studying maximum/maximal classes is Littlestone & Warmuth's long-standing Sample Compression Conjecture. Sample compression schemes of size k compress a labeled sample of n>k examples down to a sub-sequence of length at most k, from which the original n labels can be reconstructed. The conjecture states that concept classes of VC-dimension d admit compression schemes of size O(d), which to-date is only known to be true for maximum classes; compressing maximal classes is necessary and sufficient for compressing all classes. We have resolved several conjectures of Kuzmin & Warmuth relating to their proposed Min-Peeling scheme. In our COLT08 paper we represent maximum classes as arrangements of Euclidean, Hyperbolic or Piecewise-Linear hyperplanes and compress these maximum classes by sweeping their arrangements. These results bring new geometric understanding to familiar concept classes, the VC-dimension, and an elegant approach to sample compression.
See also the project descriptions in the 2006, 2007 EECS Research Summaries.
COLLABORATORS
Peter L. Bartlett (Berkeley CS and Stats), J. Hyam Rubinstein (Melbourne University Maths & Stats)
PRESENTATIONS
- Departmental Colloquium Representing maximum classes and sample compression, Department of Mathematics, Oklahoma State University, U.S.A., October 2008. (JHR)
- Topology Seminar Representing maximum classes and sample compression, Mathematisches Forschungsinstitut Oberwolfach, Germany, September 2008. (JHR)
- Departmental Colloquium Representing maximum classes and sample compression, Department of Mathematics and Statistics, University of Melbourne, Australia, August 2008. (slides) (JHR)
- Departmental Colloquium Learning theory, compression and hyperplane arrangements, Department of Mathematics, University of Auckland, New Zealand, July 2008. (JHR)
- Conference talk Mistake Bounds and Compression in Learning Theory, Geometry and Lie Theory (GL07): A Conference Marking Gus Lehrer's 60th Birthday, University of Sydney, Sydney, Australia, July 2007. (JHR)
- Conference talk Geometric & Topological Representations of Maximum Classes with Applications to Sample Compression, at COLT08, University of Helsinki, Helsinki, Finland, July 2008.
- Conference poster Shifting, One-Inclusion Mistake Bounds and Tight Multiclass Expected Risk Bounds, at NIPS06, Vancouver, B.C., Canada, December 2006.
- 'Impromptu' conference talk Shifting, One-Inclusion Mistake Bounds and Tight Multiclass Expected Risk Bounds, at COLT06, Carnegie Mellon University, Pittsburgh, PA, June 2006.
- Departmental seminar Multi-class learning and mistake bounds, Department of Computer Science and Software Engineering, the University of Melbourne, Australia, February 2006. (JHR)
- B. I. P. Rubinstein and J. H. Rubinstein, Geometric & Topological Representations of Maximum Classes with Applications to Sample Compression, in the 21st Annual Conference on Learning Theory (COLT'08), 2008.
- B. I. P. Rubinstein, P. L. Bartlett and J. H. Rubinstein, Shifting: One-Inclusion Mistake Bounds and Sample Compression, invited paper in the Special Issue on Learning Theory 2006 in the Journal of Computer and System Sciences, in press, 2008.
- B. I. P. Rubinstein, P. L. Bartlett and J. H. Rubinstein, Shifting: One-Inclusion Mistake Bounds and Sample Compression, EECS Department, University of California, Berkeley, Technical Report No. UCB/EECS-2007-86, June 25, 2007.
- B. I. P. Rubinstein, P. L. Bartlett and J. H. Rubinstein, Shifting, One-Inclusion Mistake Bounds and Tight Multiclass Expected Risk Bounds, Advances in Neural Information Processing Systems (NIPS06) 19, 2007.
| Algorithmic Stability of ERM under Multiple Risk Minimizers - ONGOING PROJECT |
|---|
PROJECT DESCRIPTIONThe property of algorithmic stability intuitively quantifies how much the image of a learning map may change under small perturbations to the training sample (similar to continuity for topological spaces). Many definitions of stability have been proposed and shown to be necessary and/or sufficient for learnability; and in some cases the presence of stability provides the easiest avenue to deriving risk bounds for a given learning algorithm. In this project, we positively resolve a conjecture of Kutin and Niyogi on the effect of multiple risk minimizers on the rate of a certain notion of stability. The probability of instability with respect to sample size undergoes a phase transition when the number of risk minimizers increases past one.
See also the project description in the 2007 EECS Research Summaries.
COLLABORATORS
Aleksandr Simma (Berkeley Computer Science).
[ top ]
| Low-level Microarray Analysis: Detecting the Presence of mRNA Transcripts - PAST PROJECT |
|---|
PROJECT DESCRIPTIONDNA microarrays are a powerful and widely used tool for massively parallel measurement of gene expression (levels of genome-wide mRNA transcripts in a cell) - an important characteristic of cell state. Gene discovery, disease explanation and diagnosis, and drug discovery are common applications of gene expression analysis. In order to gain biologically useful information such as gene expression level or differential expression from the raw data produced by microarray assays, it is necessary to transform this low-level data in some intelligent way.
In this investigation the classification task of detecting presence or absence of gene expression for the Affymetrix GeneChip oligonucleotide microarray is explored. New detection algorithms based on statistical rank-sum tests and various robust averages are compared to algorithms based on the popular robust multi-array average (RMA) expression level estimator, the Affymetrix Microarray Suite 5.0 (MAS5) expression level estimator and the MAS5 detection algorithm, using several spike-in datasets. Receiver Operating Characteristic (ROC) analysis is used to compare these algorithms, resulting in the conclusion that the new algorithms have superior detection performance in a range of practical situations. In particular the ROC Convex Hull (ROCCH) method of Provost and Fawcett is used to derive optimality conditions based on assumed misclassification costs and class priors. In addition to allowing comparison of detection algorithms based on the class prior and misclassification cost ranges relevant to the particular problem at hand, the ROCCH method allows principled selection of threshold parameters for the chosen detection algorithm.
COLLABORATORS
Simon Cawley (Affymetrix), Rao Kotagiri (Melbourne University CS), Jon McAuliffe (now UPenn Wharton Statistics), Marimuthu Palaniswami (Melbourne University EE), Terence P. Speed (Berkeley Statistics and WEHI Bioinformatics).
PRESENTATIONS
- Workshop talk, Detecting Gene Expression with Oligonucleotide Microarrays, Affymetrix GeneChip Microarray Low-level Workshop, August 2003
- Division seminar, Detecting Gene Expression with Oligonucleotide Microarrays (Part II), Division of Genetics & Bioinformatics, the Walter and Eliza Hall Institute of Medical Research (WEHI), August 2003
- Postgraduate seminar, Detecting Gene Expression with Oligonucleotide Microarrays, Department of Computer Science & Software Engineering, the University of Melbourne, February 2003
- Division seminar, Detecting Gene Expression with Oligonucleotide Microarrays, Division of Genetics & Bioinformatics, the Walter and Eliza Hall Institute of Medical Research (WEHI), December 2002
- B. I. P. Rubinstein, J. McAuliffe, S. Cawley, M. Palaniswami, K. Ramamahonorao and T. P. Speed, Machine Learning in Low-level Microarray Analysis, position paper in ACM SIGKDD Explorations (Special Issue on Microarray Data Mining), 5(2), December, 2003.
FUNDING
- Ben Rubinstein - Victorian Government Information and Communication Technology Scholarship, 2003 - 2004.
- Ben Rubinstein - The Cooperative Research Centre for Discovery of Genes for Common Human Diseases (Gene CRC), Undergraduate Research Opportunities Program (UROP) Scholarship, 2002.
| Quantum Algorithm Design through Evolutionary Computing - PAST PROJECT |
|---|
PROJECT DESCRIPTIONDue to the unintuitive nature of quantum algorithms, it has been difficult for researchers to discover new algorithms for tomorrow's quantum computers. Thus for some time it has been desirable to automate part of the design process. Evolutionary computing is an area of study that has proven useful when applied to automated design, especially where humans find manual design difficult. This project investigated the generation of quantum algorithms using genetic programming, a popular technique within the evolutionary computing community. The problem tackled is an instance of supervised learning where the GP is given pairs of inputs and outputs produced by some (hypothetical) quantum computer, and the task of the GP is to search for a quantum algorithm/circuit that can fit these pairs and thereby approximate the behavior of the computer.
PRESENTATIONS
- Conference talk, Evolving Quantum Circuits using Genetic Programming, IEEE Congress on Evolutionary Computation 2001 in Seoul, South Korea, May 2001
- B. Rubinstein. Evolving Quantum Circuits using Genetic Programming, in Proceedings of the 2001 IEEE Congress on Evolutionary Computation (CEC2001), pp. 114-121, IEEE Press, 2001.
- B. Rubinstein. Evolving Quantum Circuits using Genetic Programming, in Genetic Algorithms and Genetic Programming at Stanford 2000, edited by J. R. Koza, pp. 325-334, Stanford Bookstore, Stanford University, CA, 2000.
- Ben Rubinstein - IEEE Computer Society Lance Stafford Larson Scholarship for best undergraduate computer science paper worldwide, 2002
- Ben Rubinstein - IEEE Neural Network Council Student Travel Grant, to present at CEC01 in Seoul, South Korea, 2001
| Maintained by: | Ben Rubinstein |
| Last updated: | Mon Aug 28 17:30:29 PDT 2008 |