|
 |
|
|
IntroductionIn March 2007, I joined the Center for Computational Learning Systems at Columbia as an Associate Research Scientist.
My field of interest is statistical learning. The main goal of statistical learning is to characterize points chosen from an unknown probability distribution when given a representative sample from that distribution.
My interests and recent research topics have included boosting, ranking, and using dynamical systems to analyze the convergence of algorithms. Currently I am working on a project involving manhole event prediction using data from ConEdison. Before my current position, I worked at New York University while on an NSF postdoctoral research fellowship. In the spring of 2004, I received a PhD in Applied and Computational Mathematics at Princeton University, under the supervision of Ingrid Daubechies and Robert Schapire.
Research and Recent Results:
P-norm Ranking
I have been using L_p norms to design ranking algorithms that concentrate on the top portion of the list, where the rest of the list must only be sufficiently well constructed. The user determines how much emphasis is placed at the top. I have also been working with Heng Ji and Ralph Grishman in the Computer Science Department at NYU who are experts in natural language processing. They are specifically interested in using re-ranking algorithms for the NLP task of name tagging in Chinese; we have found that the P-Norm Ranking algorithm performs very well for this task.
"Ranking with a P-Norm Push,"
COLT 2006, Final Version, not typeset.
Authors: Cynthia Rudin
Ranking with a P-Norm Push - PDF
"Re-Ranking Algorithms for Name Tagging,"
HLT/NAACL 2006 workshop on Joint Inference, Final Version
Authors: Heng Ji, Cynthia Rudin, Ralph Grishman
Re-Ranking Algorithms for Name Tagging - PDF
Ranking
In fall of 2004, I worked with Corinna Cortes, Mehyrar Mohri and Robert E. Schapire on problems related to ranking and boosting. We have three main results: first, we presented a margin-based bound for ranking in a general setting, using L_infinity covering numbers. Second, we produced a Smooth Margin Ranking algorithm which converges to a maximum margin solution. Finally, we gave natural (and surprising) conditions such that AdaBoost will act as a ranking algorithm. In fact, it turns out that AdaBoost (which was not designed for ranking), is asymptotically just as good for ranking as RankBoost is. The longer version of this paper (co-authored with Robert Schapire) will be available soon.
"Margin-Based Ranking and Boosting Meet in the Middle,"
COLT 2005, Version date: Febrary 11, 2005.
Authors: Cynthia Rudin, Corinna Cortes, Mehryar Mohri, Robert E. Schapire
Margin-Based Ranking Meets Boosting in the Middle - PDF
Smooth Margin Boosting
In spring 2004, I worked with Robert E. Schapire and Ingrid Daubechies on the convergence of boosting algorithms (a continuation of our work on the dynamics of AdaBoost).
We developed two maximum margin boosting algorithms (Coordinate Ascent Boosting and Approximate Coordinate Ascent Boosting) which are qualitatively similar to AdaBoost (except of course, the smooth margin algorithms maximize the margin, whereas AdaBoost does not always do this). Our algorithms use the "smooth margin" as their objective, which is a differentiable approximation of the true margin. We prove asymptotic convergence and two different types of convergence rate for these algorithms. We also prove a convergence rate for Breiman's arc-gv algorithm.
Also, there is an interesting result about AdaBoost, namely, we derive a direct relationship between AdaBoost's edge values and its asymptotic margin. We call this the "case of bounded edges".
"Analysis of Boosting Algorithms using the Smooth Margin Function"
Annals of Statistics, Accepted, March 07.
Authors: Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies
Analysis of Boosting Algorithms using the Smooth Margin - PDF
"Precise Statements of Convergence for AdaBoost and arc-gv,"
Proceedings of the Conference on Machine and Statistical Learning: Prediction and Discovery, AMS-IMS-SIAM Summer Research Conferences in the Mathematical Sciences, Snowbird Utah, Summer 2006.
Authors: Cynthia Rudin, Robert E. Schapire, and Ingrid DaubechiesPrecise Statements of Convergence for AdaBoost and arc-gv - PDF"Boosting Based on a Smooth Margin,"
COLT (Computational Learning Theory) 2004. Copyright Springer.
Authors: Cynthia Rudin, Robert E. Schapire, Ingrid Daubechies
Boosting Based on a Smooth Margin - PDF
Dynamics of AdaBoost
During the fall of 2004, I had been studying AdaBoost, specifically to understand its convergence properties. In doing so, I found that AdaBoost, when studied as a dynamical system, exhibits very rich dyamical behavior such as stable cycles. Using a small toolbox of techniques for studying dynamical systems, I was able to resolve some well-studied open questions concerning AdaBoost's convergence properties. For instance, I have proved that AdaBoost may converge to a classifier with margin significantly below the maximum value; this was contrary to the widely believed conjecture that AdaBoost always converges to a maximum margin solution. (Please note that the NIPS paper below does not have this main result, the NIPS paper came before I really solved it.)"The Dynamics of AdaBoost: Cyclic Behavior and Convergence of Margins," Journal of Machine Learning Research, December 2004.
Authors: Cynthia Rudin, Ingrid Daubechies, Robert E. Schapire
The Dynamics of AdaBoost: Cyclic Behavior and Convergence of Margins - PDF
"On the Dynamics of Boosting," NIPS (Neural Information Processing Systems) 2003.
Authors: Cynthia Rudin, Ingrid Daubechies, and Rob Schapire
On the Dynamics of Boosting - PDF
Other Papers
"Stability of Learning algorithms."
Computer Science ArXiV
Author: Cynthia RudinA Different Type of Convergence for Statistical Learning Algorithms - PDF"Equilibrium Island Arrays in Strained Solid Films,"
Journal of Applied Physics, November 15 1999 -- Volume 86, Issue 10, pp. 5530-5536.
Authors: C.D. Rudin and B.J. Spencer.Equilibrium Island Ridge Arrays in Strained Solid Films - PDF
A Powerpoint Talk:
P-Norm Ranking from COLT and Snowbird (June/July 2006) : Ranking with a P-Norm Push - PDF
Teaching:
Math 103, Fall 2002 - Calculus, includes samples of videotaped lectures (pilot program)
Links:PACM Program for Applied and Computational Mathematics, Princeton UniversityOther Stuff:PACM Conference The 2004 PACM Conference which I organized. Here is the schedule.
PACM Conference The 2002 PACM Conference which I organized. Here is the schedule and some photos.
University at Buffalo SUNY Buffalo, my undergraduate institution.
I grew up in Buffalo NY and attended SUNY Buffalo for my undergraduate degrees. I did major in math/physics, but I also majored in music theory. My husband is a biologist who doesn't do any mathematics, and no, I'm not related to the guy who wrote the book (and you're not the first one to wonder)! One of my favorite hobbies is to make homemade ice cream.
