Jeff on Noisy Learning at 1:30 pm (Mar 10)

Topic: Identification in the limit from positive data with noise

Details: We consider the problem of identifying formal languages in the limit when the presentations of positive data are corrupted by noise. Two kinds of noise are considered separately: when the data systematically omits positive examples and when negative examples intrude into the data presentation. It is shown that while noise is problematic in general, we can identify conditions under which string extension learning can succeed or succeed as well as anyone could reasonably expect.