Contact

Stefanie Jegelka

Adresse: Spemannstr. 38
72076 Tübingen
Raum Nummer: 204

 

Bild von Jegelka, Stefanie

Stefanie Jegelka

Position: Doktorand  Abteilung: 

I am a Ph.D. student at MPI Tuebingen and ETH Zurich, and supervised by Prof. Jeff Bilmes. For my Diplom (Master), I studied Bioinformatics in Tuebingen and Austin. I am particularly interested in

  • submodular functions
  • more generally, discrete and combinatorial problems in machine learning and computer vision
  • (approximate) optimization (that is, algorithms that are useable and also come with some theoretical guarantees)
  • online learning
  • kernel methods, e.g. for clustering and ICA
  • theoretical aspects of clustering
  • applications in computer vision and biology

I have co-organized the NIPS workshop on Discrete Optimization in Machine Learning and given invited talks at the COSA workshop at the Technical University in Munich, Cornell University, TTI, UC Berkeley and TU Munich.

Below is a summary of projects and links to code.

 

Structured problems with submodular cost

Our generic setting is as follows: take a combinatorial optimization problem, and replace the usual sum-of-weights cost by a nonlinear, submodular function. This makes the problem much harder but has very useful applications and relations to questions in machine learning. In particular, we worked on this setting with graph cuts. The resulting cooperative cuts find applications wherever graph cuts can be used: for example in computer vision (e.g. for image segmentation), approximate inference, or approximate faster minimization of submodular functions. (Download data/code for image segmentation with cooperative cuts)
In addition, we derived online algorithms for structured sequential decision problems (e.g., online spanning tree, or s-t cut) with submodular cost (in contrast, almost all previous results are for linear costs). (All this was work with Jeff Bilmes.)
During our work, we came across several functions that are actually not submodular (but maybe some people hoped them to be), and thus I am collecting those functions in a bag of submodular non-examples.

 

Clustering & Graph Cuts

Nearest Neighbor Clustering: we developed a generic algorithm to minimize popular clustering objective functions, such as Normalized Cut or k-means. This method is consistent, thanks to pooling neighboring points. (with Ulrike von Luxburg, Sebastien Bubeck, Michael Kaufmann).
Download Demo Code

Generalized Clustering via Kernel Embeddings: The concept of clustering can be generalized to finding distributions that are maximally separated. The standard case is to measure separation by means of the distribution (k-means). MMD, the maximum mean discrepancy in a feature space, allows to also take higher-order moments into account. As a result, it is possible to e.g. separate two Gaussians with the same mean but different variance. Interestingly, maximizing MMD is closely related to kernel k-means and various other clustering criteria. (with Ulrike von Luxburg, Bernhard Schoelkopf, Arthur Gretton, Bharath Sriperumbudur)

Approximation Algorithms for Tensor Clustering: We prove an approximation factor for tensor clustering (i.e., "cutting a big cube into little cubes") for maybe the simplest possible algorithm. Various divergences are possible, such as Euclidean distance, Bregman divergences etc. (with Suvrit Sra, Arindam Banerjee)

Solution Stability in Linear Programming Relaxations: Graph Partitioning and Unsupervised Learning. Data is often noisy. If there are several good solutions to an optimization problem (here, graph partitioning), then the noise can be the determining part to make one solution optimal. However, how much do we want to trust this solution, if a small perturbation in the data suddenly makes another solution the best? this work proposes a method to test the stability of an optimal graph cut solution to perturbation of the edge weights (i.e., noise).We also show that several common clustering and graph partitioning objectives fall in our framework. (with Sebastian Nowozin)

 

Kernel Independent Component Analysis

Fast Kernel ICA: We developed a Newton-like method for kernel ICA that uses HSIC as the independence criterion. The algorithm is faster than previous gradient descent algorithms, and retains the advantages of Kernel ICA (with Hao Shen, Arthur Gretton).
Download Code for Fast kernel ICA


available upon request

Präferenzen: 
Referenzen pro Seite: Jahr: Medium:

  
Zeige Zusammenfassung

Artikel (2):

Shen H, Jegelka S und Gretton A (September-2009) Fast Kernel-Based Independent Component Analysis IEEE Transactions on Signal Processing 57(9) 3498-3511.
pdf
Jegelka S, Bednar JA und Miikkulainen R (Februar-2006) Prenatal development of ocular dominance and orientation maps in a self-organizing model of V1 Neurocomputing 69(10-12) 1291-1296.

Beiträge zu Tagungsbänden (12):

Jegelka S, Lin H und Bilmes J (Januar-2012) On Fast Approximate Submodular Minimization In: Advances in Neural Information Processing Systems 24, , Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS 2011), Curran, Red Hook, NY, USA, 460-468.
pdf
Jegelka S und Bilmes J (Juli-2011) Approximation Bounds for Inference using Cooperative Cut, 28th International Conference on Machine Learning (ICML 2011), International Machine Learning Society, Madison, WI, USA, 577-584.
pdf
Jegelka S und Bilmes J (Juli-2011) Online submodular minimization for combinatorial structures, 28th International Conference on Machine Learning (ICML 2011), International Machine Learning Society, Madison, WI, USA, 345-352.
pdfpdf
Jegelka S und Bilmes J (Juni-2011) Multi-label cooperative cuts, CVPR 2011 Workshop on Inference in Graphical Models with Structured Potentials, 1-4.
pdf
Jegelka S und Bilmes J (Juni-2011) Submodularity beyond submodular energies: coupling edges in graph cuts, IEEE Conference on Computer Vision and Pattern Recognition (CVPR 2011), IEEE, Piscataway, NJ, USA, 1897-1904.
pdf
Jegelka S und Bilmes J (Dezember-2010) Online algorithms for submodular minimization with combinatorial constraints, NIPS 2010 Workshop on Discrete Optimization in Machine Learning: Structures, Algorithms and Applications (DISCML), 1-6.
pdf
Jegelka S und Bilmes J (Dezember-2009) Notes on Graph Cuts with Submodular Edge Weights, NIPS 2009 Workshop on Discrete Optimization in Machine Learning: Submodularity, Sparsity & Polyhedra (DISCML), 1-6.
pdf
Jegelka S, Sra S und Banerjee A (Oktober-2009) Approximation Algorithms for Tensor Clustering In: Algorithmic Learning Theory, , 20th International Conference on Algorithmic Learning Theory (ALT 2009), Springer, Berlin, Germany, 368-383, Series: Lecture Notes in Computer Science ; 5809.
pdf
Jegelka S, Gretton A, Schölkopf B, Sriperumbudur BK und von Luxburg U (September-2009) Generalized Clustering via Kernel Embeddings In: KI 2009: Advances in Artificial Intelligence, , 32nd Annual Conference on Artificial Intelligence (KI), Springer, Berlin, Germany, 144-152, Series: Lecture Notes in Computer Science ; 5803.
pdfpdf
Nowozin S und Jegelka S (Juni-2009) Solution Stability in Linear Programming Relaxations: Graph Partitioning and Unsupervised Learning, 26th International Conference on Machine Learning (ICML 2009), ACM Press, New York, NY, USA, 769-776.
pdf
von Luxburg U, Bubeck S, Jegelka S und Kaufmann M (September-2008) Consistent Minimization of Clustering Objective Functions In: Advances in neural information processing systems 20, , Twenty-First Annual Conference on Neural Information Processing Systems (NIPS 2007), Curran, Red Hook, NY, USA, 961-968.
pdf
Shen H, Jegelka S und Gretton A (März-2007) Fast Kernel ICA using an Approximate Newton Method, 11th International Conference on Artificial Intelligence and Statistics (AISTATS 2007), International Machine Learning Society, Madison, WI, USA, 476-483, Series: JMLR Workshop and Conference Proceedings ; 2.
pdf

Beiträge zu Büchern (1):

Jegelka S und Gretton A: Brisk Kernel Independent Component Analysis, 225-250. In: Large Scale Kernel Machines, (Ed) L. Bottou, MIT Press, Cambridge, MA, USA, (September-2007).
pdf

Technische Berichte (5):

Jegelka S und Bilmes J: Cooperative Cuts for Image Segmentation, UWEETR-1020-0003, University of Washington, DC, USA, (August-2010).
Jegelka S und Bilmes J: Cooperative Cuts: Graph Cuts with Submodular Edge Weights, 189, Max Planck Institute for Biological Cybernetics, Tuebingen, Germany, (März-2010).
pdf
Sra S, Jegelka S und Banerjee A: Approximation Algorithms for Bregman Clustering Co-clustering and Tensor Clustering, 177, Max-Planck Institute for Biological Cybernetics, Tübingen, Germany, (September-2008).
pdf
Kulis B, Sra S und Jegelka S: Scalable Semidefinite Programming using Convex Perturbations, TR-07-47, University of Texas, Austin, TX, USA, (September-2007).
Shen H, Jegelka S und Gretton A: Geometric Analysis of Hilbert Schmidt Independence criterion based ICA contrast function, PA006080, National ICT Australia, Canberra, Australia, (Oktober-2006).

Poster (1):

Lippert C, Stegle O, Jegelka S, Altun Y und Borgwardt KM (September-2009): Predicting related traits from SNP markers by multi-task learning, German Conference on Bioinformatics (GCB 2009), Halle, Germany.

Abschlussarbeiten (1):

Jegelka S: Statistical Learning Theory Approaches to Clustering, Eberhard-Karls-Universität Tübingen, Germany, (November-2007). Diplom thesis
pdf

Vorträge (4):

Jegelka S (Oktober-7-2011): Cooperative Cuts: a new use of submodularity in image segmentation, Second I.S.T. Austria Symposium on Computer Vision and Machine Learning, Klosterneuburg, Austria.
Jegelka S (März-14-2011) Invited Lecture: Cooperative Cuts, COSA Workshop: Combinatorial Optimization, Statistics, and Applications, München, Germany.
Jegelka S und Bilmes J (Juli-2010) Abstract Talk: Cooperative Cuts: Graph Cuts with Submodular Edge Weights, 24th European Conference on Operational Research (EURO XXIV), Lisboa, Portugal 171.
Jegelka S, Gretton A und Achlioptas D (Dezember-2005) Invited Lecture: Kernel ICA for Large Scale Problems, NIPS 2005 Workshop on Large Scale Kernel Machines, Whistler, Canada.

Export als:
BibTeX, XML, pubman, Edoc, RTF
Last updated: Montag, 22.05.2017