Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Машиналық оқытудың математикалық талдауының аясы
Framework for mathematical analysis of machine learning
Есептеулік оқыту теориясында, ықтималды түрде шамамен дұрыс (PAC) оқыту – машиналық оқытудың математикалық талдауының аясы болып табылады. Оны 1984 жылы Лесли Валиант ұсынған. Бұл аяда оқушы үлгілерді қабылдайды және белгілі бір мүмкін функциялар класынан жалпылау функциясын (гипотеза деп аталады) таңдауы керек. Мақсат – жоғары ықтималдылықпен (яғни, "ықтималды" бөлігі), таңдалған функцияның жалпылау қатесі төмен болуы ("шамамен дұрыс" бөлігі). Оқушы кез келген кездейсоқ жуықтау қатынасын, табыс ықтималдығын немесе үлгілердің таралуын ескере отырып, түсініктерді үйренуге қабілетті болуы керек. Бұл модель кейін шуды (бұрыс жіктелген үлгілерді) қарастыру үшін кеңейтілді. PAC аясының маңызды жаңалығы – есептеу күрделілігі теориясының ұғымдарын машиналық оқытуға енгізу болып табылады. Атап айтқанда, оқушы тиімді функцияларды (мысал мөлшерінің полиномымен шектелген уақыт және кеңістік талаптары) табуы күтіледі, ал оқушының өзі тиімді процедураны іске асыруы керек (түсінік мөлшерінің полиномымен шектелген мысалдар саны, жуықтау және ықтималдық шектерімен түзетілген).
In computational learning theory, probably approximately correct (PAC) learning is a framework for mathematical analysis of machine learning. It was proposed in 1984 by Leslie Valiant. In this framework, the learner receives samples and must select a generalization function (called the hypothesis) from a certain class of possible functions. The goal is that, with high probability (the "probably" part), the selected function will have low generalization error (the "approximately correct" part). The learner must be able to learn the concept given any arbitrary approximation ratio, probability of success, or distribution of the samples. The model was later extended to treat noise (misclassified samples). An important innovation of the PAC framework is the introduction of computational complexity theory concepts to machine learning. In particular, the learner is expected to find efficient functions (time and space requirements bounded to a polynomial of the example size), and the learner itself must implement an efficient procedure (requiring an example count bounded to a polynomial of the concept size, modified by the approximation and likelihood bounds).
Анықтамалар мен терминология
PAC үйренетін нәрсенің анықтамасын беру үшін алдымен кейбір терминологияны енгізуіміз керек. Келесі анықтамалар үшін екі мысал қолданылады. Біріншісі – бинарлық мәнді суретті кодтайтын биттер массиві берілген таңбаларды тану мәселесі. Екінші мысал – аралықтың ішіндегі нүктелерді оң, ал аралықтан тыс нүктелерді теріс деп дұрыс жіктеуге болатын аралықты табу мәселесі. барлық үлгілердің кодтауы немесе инстанция кеңістігі деп аталатын жиын болсын. Таңбаларды тану мәселесінде инстанция кеңістігі ал аралық мәселесінде инстанция кеңістігі , барлық шектелген аралықтардың жиынтығы болып табылады, мұнда барлық нақты сандардың жиынтығын білдіреді. Ұғым – бұл ішкі жиын. Бір ұғым – "P" әрпінің суретін кодтайтын биттердің барлық үлгілерінің жиынтығы. Екінші мысалдан алынған ұғым – әрқайсысында тек оң нүктелер бар ашық аралықтардың жиынтығы. Ұғым классы – бұл үстінен ұғымдардың жиынтығы. Бұл 4 байланысқан скелетке айналған (шрифт ені 1) биттер массивінің барлық ішкі жиынтығы болуы мүмкін. – бұл ықтималдық үлестірілімін пайдаланып мысалға қосқан және дұрыс белгіні берген процедура, яғни 1 егер болса, ал басқа жағдайда 0. Енді, берілген, алгоритм және полиномы бар деп есептейік (және сыныптың басқа да тиісті параметрлері), сонда үлестірілімі бойынша алынған өлшемді үлгі берілгенде, кем дегенде ықтималдығымен орта қатесі немесе одан кем гипотезаны шығарады, бұл үлестірілімімен бірдей. Егер алгоритм үшін жоғарыдағы мәлімдеме әрбір ұғым үшін және үстінен әрбір үлестірілім үшін, сондай-ақ барлық үшін дұрыс болса, онда (тиімді) PAC үйренеді (немесе үлестірімге тәуелсіз PAC үйренеді). Сондай-ақ – бұл үшін PAC оқу алгоритмі деуге болады.
In order to give the definition for something that is PAC learnable, we first have to introduce some terminology. For the following definitions, two examples will be used. The first is the problem of character recognition given an array of bits encoding a binary valued image. The other example is the problem of finding an interval that will correctly classify points within the interval as positive and the points outside of the range as negative. Let be a set called the instance space or the encoding of all the samples. In the character recognition problem, the instance space is In the interval problem the instance space, , is the set of all bounded intervals in , where denotes the set of all real numbers. A concept is a subset One concept is the set of all patterns of bits in that encode a picture of the letter "P". An example concept from the second example is the set of open intervals, , each of which contains only the positive points. A concept class is a collection of concepts over This could be the set of all subsets of the array of bits that are skeletonized 4 connected (width of the font is 1). Let be a procedure that draws an example, , using a probability distribution and gives the correct label , that is 1 if and 0 otherwise. Now, given , assume there is an algorithm and a polynomial in (and other relevant parameters of the class ) such that, given a sample of size drawn according to , then, with probability of at least , outputs a hypothesis that has an average error less than or equal to on with the same distribution Further if the above statement for algorithm is true for every concept and for every distribution over , and for all then is (efficiently) PAC learnable (or distribution free PAC learnable). We can also say that is a PAC learning algorithm for .