Posts

Comments

Comment by Fred Guth on Leslie Valiant discusses the the "probably approximately correct," or PAC, model of machine learning. · 2018-12-21T06:09:12.285Z · LW · GW

I disagree with you. PAC is about how to analyse learning algorithms in terms of sample complexity. It is not about AdaBoost, nor Neural networks, or whatever. Actually, the learning algorithm is a black box in the PAC model (or metamodel if you prefer).

I think the name is perfect and evergreen. The same way we want to analyse the correctness of algorithms and know its time (or resource) complexity, for learning algorithms you also have another dimension which is how much data you need (sample complexity).

PAC is trying to answer what is the bound on the size of training dataset needed to achieve a certain prediction correctness with a certain confidence (probability).