Loading...
Please wait, while we are loading the content...
Similar Documents
Learning in the Presence of Malicious Errors (1993)
| Content Provider | CiteSeerX |
|---|---|
| Author | Kearns, Michael Li, Ming |
| Abstract | In this paper we study an extension of the distribution-free model of learning introduced by Valiant [23] (also known as the probably approximately correct or PAC model) that allows the presence of malicious errors in the examples given to a learning algorithm. Such errors are generated by an adversary with unbounded computational power and access to the entire history of the learning algorithm's computation. Thus, we study a worst-case model of errors. Our results include general methods for bounding the rate of error tolerable by any learning algorithm, efficient algorithms tolerating nontrivial rates of malicious errors, and equivalences between problems of learning with errors and standard combinatorial optimization problems. 1 Introduction In this paper, we study a practical extension to Valiant's distribution-free model of learning: the presence of errors (possibly maliciously generated by an adversary) in the sample data. The distribution-free model typically makes the idealize... |
| File Format | |
| Volume Number | 22 |
| Journal | SIAM Journal on Computing |
| Language | English |
| Publisher Date | 1993-01-01 |
| Access Restriction | Open |
| Subject Keyword | Malicious Error Distribution-free Model Learning Algorithm Standard Combinatorial Optimization Problem Entire History Pac Model Unbounded Computational Power Efficient Algorithm General Method Nontrivial Rate Sample Data Practical Extension Worst-case Model |
| Content Type | Text |
| Resource Type | Article |
