Algorithms Seminar/Fall10
From ResearchWiki
(→Schedule: Added more text to Geometry Section.) |
(→Schedule) |
||
| Line 30: | Line 30: | ||
| colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Geometry''' | | colspan="4" bgcolor="#dddddd" style = "text-align:center" | '''Geometry''' | ||
|- | |- | ||
| - | | Sep 1 || Range Spaces and epsilon-Samples || Define important geometric-combinatorial notions: Range spaces, eps-nets, eps-samples. Prove random sampling bound for eps-samples ([http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/lec/05_vc_dim.pdf Sariel's Notes]). Show cool application of eps-nets on uncertain data in sensor nets([http://www.cs.ucsb.edu/~suri/psdir/elephants.pdf eps-Sentinals]) || | + | | Sep 1 || Range Spaces and epsilon-Samples || How well does random sampling work? Define important geometric-combinatorial notions: Range spaces, eps-nets, eps-samples. Prove random sampling bound for eps-samples ([http://valis.cs.uiuc.edu/~sariel/teach/notes/aprx/lec/05_vc_dim.pdf Sariel's Notes]). Show cool application of eps-nets on uncertain data in sensor nets([http://www.cs.ucsb.edu/~suri/psdir/elephants.pdf eps-Sentinals]) || |
|- | |- | ||
| Sep 8 || Epsilon-Quantizations and Epsilon-SIPs || Modeling questions on uncertain data with probability distributions. Review specific applications to smallest enclosing ball. ([http://www.cs.utah.edu/~jeffp/papers/uncertaintyESA09.pdf Shape Fitting on Point Sets with Probability Distributions]) || | | Sep 8 || Epsilon-Quantizations and Epsilon-SIPs || Modeling questions on uncertain data with probability distributions. Review specific applications to smallest enclosing ball. ([http://www.cs.utah.edu/~jeffp/papers/uncertaintyESA09.pdf Shape Fitting on Point Sets with Probability Distributions]) || | ||
Revision as of 06:47, 4 August 2010
Modelling Data With Uncertainty
Wed 1:25-2:45pm
MEB 3147 (LCR)
Contents |
Synopsis
We will cover many recent developments in the modeling and processing of uncertain data in computer science. The seminar will focus and the modeling, algorithmic, and data-structural foundations needed for understanding, processing, and visualizing uncertain data. First we will overview different models of uncertainty, tracing their origins and motivation (Many-world models in databases, imprecision models in geometry, probabilistic models in databases). Then we will proceed to survey recent developments in computational geometry, databases, visualization, and machine learning and statistics. Highlights in computational geometry will describe algorithmic analysis to answer basic geometry problems, either with respect to worst case bounds or by formally approximating the distributions. Work in databases has focused on data structures to quickly retrieve summary queries of large data sets with respect to the underlying data uncertainty. We will study techniques to visualize uncertainty for surfaces and volumes. This topic has been studied for longer in machine learning and statistics so we will summarize classic techniques and see some recent developments. Through this seminar, participants will gain an understanding of the state-of-the-art in modeling and processing uncertain data and will be exposed to several important open problems and exciting research directions.
Participants
- Jeff Phillips
- Suresh Venkatasubramanian
Schedule
(subject to change)
| Date | Topic | Paper(s) | Presenter |
|---|---|---|---|
| Aug 25 | Models of Data Uncertainty | Motivation behind modeling Uncertainty. Survey different models and where they arise. | Jeff Phillips |
| Geometry | |||
| Sep 1 | Range Spaces and epsilon-Samples | How well does random sampling work? Define important geometric-combinatorial notions: Range spaces, eps-nets, eps-samples. Prove random sampling bound for eps-samples (Sariel's Notes). Show cool application of eps-nets on uncertain data in sensor nets(eps-Sentinals) | |
| Sep 8 | Epsilon-Quantizations and Epsilon-SIPs | Modeling questions on uncertain data with probability distributions. Review specific applications to smallest enclosing ball. (Shape Fitting on Point Sets with Probability Distributions) | |
| Sep 15 | Geometry on Imprecise Points | Imprecision in data. eps-geometry for rounding errors (eps-Geometry). More general geometry problems: Basic Geometry Measures on Imprecise Points and maybe Largest and Smallest Convex Hulls on Imprecise Points | |
| Sep 22 | Hardness of Uncertainty Problems | Its not always easy! What is #P-Hard. Basic problems that are(Efficient Query Evaluation on Probabilistic Databases). LP-type problems. Non-LP-type problems that are #P-Hard([see Jeff for preprint]) | |
| Databases | |||
| Sep 29 | Sketching and Streaming | Sketching probabilistic data streams | |
| Oct 6 | Histograms | Histograms and wavelets on probabilistic data Probabilistic Histograms for Probabilistic Data | |
| Oct 20 | Ranking | A Unified Approach to Ranking in Probabilistic Databases with slides and Semantics of ranking queries for probabilistic data and expected ranks | |
| Oct 27 | Clustering | Approximation Algorithms for Clustering Uncertain Data | |
| Visualization | |||
| Nov 3 | Noisy Surfaces | ||
| Nov 10 | Transfer Functions | ||
| Machine Learning And Statistics | |||
| Nov 17 | Particle Filters | ||
| Nov 24 | Support Vector Machines | Support Vector Classification with Input Data Uncertainty | |
| Dec 1 | Markov Random Fields | ||
| Dec 8 | Multi-Armed Bandits | ||
