Conference Presentation
Kathryn McKinley
- The speaker highlights significant inaccuracies in current sensor-based applications, such as GPS, where errors arise from sensor occlusion, government interference, satellite communication issues, and varying signal quality.
- Existing tools lack the programming models necessary to interpret estimates produced by sensors and machine learning algorithms, which provide probabilistic rather than perfect answers.
- A new programming model introduces an "uncertain type" system that allows developers to treat estimates (e.g., speed) similarly to base types while embedding statistical semantics directly into the runtime.
- The system utilizes hypothesis testing for conditionals rather than strict boolean checks, evaluating whether a value (e.g., speed > 4 mph) is more likely than not based on the underlying probability distribution.
- Developers must provide error models for data sources (e.g., modeling GPS error as a Rayleigh distribution), shifting the expertise burden from data consumers to data providers.
- The runtime constructs a Bayesian network lazily, evaluating expressions only when a conditional is encountered to optimize efficiency based on required precision.
- The implementation includes mechanisms for users to control confidence levels, explicitly allowing the specification of acceptable false positive and false negative rates.
- In a specific test case with several hundred data points, a naive implementation yielded 30 false positives; the uncertain type system reduced this to four using a >50% probability threshold, and to zero using a 90% confidence threshold.
- Contextual information is integrated via Bayesian inference to refine estimates, such as "snapping" noisy GPS data to known road networks.
- Previously requiring thousands of lines of ad hoc heuristic code, the new model allows road-snapping logic to be implemented in approximately two lines using Bayesian constructs and composition operators.
- The runtime employs a new algorithm called "sequential likelihood reweighting" to enable efficient higher-order inference within the restricted programming model.
- Traditional assertions are insufficient for probabilistic programs that rely on approximate computing or differential privacy, leading to the proposal of "probabilistic assertions" that define truth by a specific probability threshold.
- While progress has been made in proving that computed averages are close to real averages using probabilistic assertions, the speaker notes that fully proving differential privacy guarantees in implementation remains an open challenge.
- The speaker emphasizes the growing necessity of language support for reasoning about data quality in domains like agricultural sensors and news verification.
- The proposed language implementation is currently under development for open-sourcing at Microsoft, with the speaker inviting syntax feedback.