A learning criterion for stochastic rules

摘要: This paper proposes a learning criterion for stochastic rules. is developed by extending Valiant's PAC (Probably Approximately Correct) model, which deterministic Stochastic rules here refer to those probabilistically asign number of classes, lYr, each attribute vector X. The proposed based on the idea that may be regarded as probably approximately correct identification conditional probability distributions over classes given input vectors. An algorithm (an MDL algorithm) (Minimum Description Length) principle used Specifically, with finite partitioning (each specified disjoint cells domain and parameter associated them), this derives target-dependent upper bounds worst-case sample size required learn accuracy confidence. Based these bounds, proves polynomial-sample-size learnability decision lists (which are newly in analogue Rivest's lists) at most k literals (k fixed) decision, trees (a trees) depth. Sufficient conditions polynomial-time any also derived.