{"id":297285,"date":"2020-01-17T15:00:42","date_gmt":"2020-01-17T15:00:42","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=297285"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=297285","title":{"rendered":"\u041e\u0431\u0437\u043e\u0440 \u0440\u0430\u0431\u043e\u0442\u044b \u00abLearnability Can Be Undecidable\u00bb"},"content":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/raiffeisenbank\/blog\/484306\/\">\n<p>\u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u043e\u0438\u043c \u0432\u043e\u043b\u044c\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0441\u043a\u0430\u0437\u043e\u043c \u0440\u0430\u0431\u043e\u0442\u044b <a href=\"https:\/\/www.nature.com\/articles\/s42256-018-0002-3\">Learnability can be undecidable, Shai Ben-David, et al.<\/a><\/p>\n<p>  <\/p>\n<p>\u041d\u0435\u0434\u0430\u0432\u043d\u043e \u043d\u0430 \u0425\u0430\u0431\u0440\u0435 \u0432\u044b\u0448\u043b\u0430 \u0441\u0442\u0430\u0442\u044c\u044f <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/484238\/\">\u041c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u043e\u0441\u044c \u0441 \u043d\u0435\u0440\u0435\u0448\u0435\u043d\u043d\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439<\/a>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u043c \u043e\u0434\u043d\u043e\u0438\u043c\u0435\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0437\u043e\u0440\u0430 \u0432 Nature News \u0441\u0442\u0430\u0442\u044c\u0438 \u0428\u0430\u0439 \u0411\u0435\u043d-\u0414\u0430\u0432\u0438\u0434\u0430. \u041e\u0434\u043d\u0430\u043a\u043e, \u0438\u0437-\u0437\u0430 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438 \u0438 \u043a\u0440\u0430\u0442\u043a\u043e\u0441\u0442\u0438 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0431\u0437\u043e\u0440\u0430 \u043c\u043d\u0435 \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u0436\u0435 \u0431\u044b\u043b\u043e \u0432 \u0441\u0442\u0430\u0442\u044c\u0435. \u0417\u043d\u0430\u044f \u0428\u0430\u0439 \u0411\u0435\u043d-\u0414\u0430\u0432\u0438\u0434\u0430, \u043a\u0430\u043a \u0430\u0432\u0442\u043e\u0440\u0430 \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u043e\u0439 \u043a\u043d\u0438\u0433\u0438 &quot;Understanding Machine Learning: From Theory to Algorithms&quot;, \u044f \u0437\u0430\u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u043b\u0441\u044f \u044d\u0442\u043e\u0439 \u0442\u0435\u043c\u043e\u0439, \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u043b\u0441\u044f \u0441 \u044d\u0442\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u043e\u0439 \u0438 \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u043b\u0441\u044f \u0442\u0443\u0442 \u0438\u0437\u043b\u043e\u0436\u0438\u0442\u044c \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u043c\u043e\u043c\u0435\u043d\u0442\u044b.<\/p>\n<p>  <\/p>\n<p>\u0421\u0440\u0430\u0437\u0443 \u0441\u043a\u0430\u0436\u0443, \u0447\u0442\u043e \u0441\u0442\u0430\u0442\u044c\u044f \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u043b\u043e\u0436\u043d\u0430\u044f \u0438, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u044f \u0443\u043f\u0443\u0441\u0442\u0438\u043b \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0430\u0436\u043d\u044b\u0435 \u043c\u043e\u043c\u0435\u043d\u0442\u044b, \u043d\u043e \u043c\u043e\u0439 \u043e\u0431\u0437\u043e\u0440 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u043b\u043d\u044b\u043c, \u0447\u0435\u043c \u0442\u043e\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u0436\u0435 <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/484238\/\">\u0435\u0441\u0442\u044c<\/a> \u043d\u0430 \u0425\u0430\u0431\u0440\u0435.<\/p>\n<p><a name=\"habracut\"><\/a>  <\/p>\n<h1 id=\"neskolko-slov-ob-pac-obuchaemosti-v-celom\">\u041d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043b\u043e\u0432 \u043e\u0431 PAC-\u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u0438 \u0432 \u0446\u0435\u043b\u043e\u043c<\/h1>\n<p>  <\/p>\n<p>\u041f\u0435\u0440\u0432\u043e\u0435, \u0447\u0442\u043e \u043c\u0435\u043d\u044f \u0441\u043c\u0443\u0442\u0438\u043b\u043e \u0432 \u043e\u0431\u0437\u043e\u0440\u0435 \u0438\u0437 Nature News \u044d\u0442\u043e \u0442\u043e, \u0447\u0442\u043e \u0441\u0430\u043c\u0430 \u043f\u043e \u0441\u0435\u0431\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u0438 \u0431\u044b\u043b\u0430 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u043a\u0430\u043a \u0447\u0442\u043e-\u0442\u043e \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u043d\u043e\u0432\u043e\u0435. \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u044d\u0442\u043e \u0434\u0430\u0432\u043d\u043e \u0438 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0438\u0437\u0443\u0447\u0435\u043d\u043d\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430. <\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u043f\u043e\u043d\u044f\u0442\u0438\u0439 \u0434\u043b\u044f \u0442\u0435\u0445, \u043a\u0442\u043e \u043d\u0435 \u0437\u043d\u0430\u043a\u043e\u043c \u0441 \u0432\u043e\u043f\u0440\u043e\u0441\u043e\u043c<\/b><\/p>\n<div class=\"spoiler_text\">\n<p><strong>\u0420\u0438\u0441\u043a<\/strong> \u2014 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7ba\/e90\/fb1\/7bae90fb14e6874c5e27a28b342cd03b.svg\" alt=\"$y, \\hat{y}$\" data-tex=\"inline\"><\/math> \u2014 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0438 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0442\u0440\u0430\u0436\u0430\u0435\u0442 \u0442\u043e, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u044b \u043e\u0448\u0438\u0431\u043b\u0438\u0441\u044c \u0432 \u043d\u0430\u0448\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u0438. \u041c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043e\u0442\u0440\u0430\u0436\u0430\u0435\u0442 \u043c\u0435\u043d\u044c\u0448\u0443\u044e \u043e\u0448\u0438\u0431\u043a\u0443. \u0421\u0430\u043c\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0438 \u044d\u0442\u043e \u0438\u043d\u0434\u0438\u043a\u0430\u0442\u043e\u0440\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/5c6\/f0f\/a26\/5c6f0fa26adc848749e1389acb3b6a49.svg\" alt=\"$\\mathbb{1}(y \\neq \\hat{y})$\" data-tex=\"inline\"><\/math>. \u0414\u043b\u044f \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u0438 \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u0441\u0440\u0435\u0434\u043d\u0435\u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0435 \u043e\u0442\u043a\u043b\u043e\u043d\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c05\/a15\/819\/c05a158196af3a168136c987935c6df7.svg\" alt=\"$\\sqrt{y^2 - \\hat{y}^2}$\" data-tex=\"inline\"><\/math>. \u041e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0438 \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b. \u0414\u0440\u0443\u0433\u043e\u0435 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u043d\u044f\u0442\u0438\u044f \u2014 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0442\u0435\u0440\u044c.<\/p>\n<p>  <\/p>\n<p><strong>\u0421\u0440\u0435\u0434\u043d\u0438\u0439 \u0440\u0438\u0441\u043a<\/strong> \u2014 \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0438\u0441\u043a\u0430 \u043d\u0430 \u0432\u0441\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u0412 \u0441\u0438\u043b\u0443 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u043e\u0431\u044b\u0447\u043d\u043e \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f \u0432\u0435\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u043e\u0432), \u043b\u0438\u0431\u043e \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u0432\u0435\u043b\u0438\u043a\u043e (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 1024\u04451024 \u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c\u0438 \u0432 \u043f\u0438\u043a\u0441\u0435\u043b\u044f\u0445 \u043e\u0442 0 \u0434\u043e 255), \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u043d\u0430\u043f\u0440\u044f\u043c\u0443\u044e \u043e\u0446\u0435\u043d\u0438\u0442\u044c \u044d\u0442\u0443 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0443. \u041e\u0434\u043d\u0430\u043a\u043e, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u043c\u0435\u0442\u043e\u0434\u044b \u043e\u0446\u0435\u043d\u043a\u0438 \u044d\u0442\u043e\u0439 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u044b \u0441\u0435\u0439\u0447\u0430\u0441 \u043d\u0435 \u0431\u0443\u0434\u0435\u043c \u0432\u0434\u0430\u0432\u0430\u0442\u044c\u0441\u044f. \u0418\u043c\u0435\u043d\u043d\u043e \u044d\u0442\u043e\u0442 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043c\u044b \u0432 \u0438\u0442\u043e\u0433\u0435 \u0445\u043e\u0442\u0438\u043c \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c. \u0418\u043d\u043e\u0433\u0434\u0430 \u044d\u0442\u043e\u0442 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0442\u0430\u043a\u0436\u0435 \u043e\u0448\u0438\u0431\u043a\u043e\u0439 \u043e\u0431\u043e\u0431\u0449\u0435\u043d\u0438\u044f (generalization error).<\/p>\n<p>  <\/p>\n<p><strong>\u042d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0438\u0441\u043a<\/strong> \u2014 \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0440\u0438\u0441\u043a\u0430 \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u043c \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043d\u0430\u0431\u043e\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445, \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0445 \u0438\u0437 \u0432\u0441\u0435\u0433\u043e \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u0431\u044b\u0447\u043d\u043e \u0438\u043c\u0435\u043d\u043d\u043e \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u044d\u0442\u043e\u0439 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u044b \u0437\u0430\u043d\u0438\u043c\u0430\u044e\u0442\u0441\u044f \u043d\u0430\u0448\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f.<\/p>\n<p>  <\/p>\n<p><strong>\u0417\u0430\u0434\u0430\u0447\u0430 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f<\/strong> \u2014 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438 \u0438\u043c\u0435\u044e\u0449\u0435\u0433\u043e\u0441\u044f \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 (\u0444\u0443\u043d\u043a\u0446\u0438\u044e), \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0434\u0430\u0432\u0430\u043b\u043e \u0431\u044b \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0440\u0438\u0441\u043a\u0430.<\/p>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0435\u043e\u0440\u0438\u044f \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e \u043f\u043e\u0447\u0442\u0438 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f (<strong>P<\/strong>robably <strong>A<\/strong>pproximately <strong>C<\/strong>orrect Learning, <a href=\"http:\/\/www.machinelearning.ru\/wiki\/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%92%D0%B0%D0%BB%D0%B8%D0%B0%D0%BD%D1%82%D0%B0\"><strong>PAC<\/strong><\/a>).<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0423\u043f\u0440\u043e\u0449\u0435\u043d\u043d\u043e\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 PAC-\u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f<\/b><\/p>\n<div class=\"spoiler_text\">\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c <strong>A<\/strong> \u0441\u0442\u0440\u043e\u044f\u0449\u0438\u0439 \u043f\u043e \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0435 <strong>X<\/strong> \u0440\u0430\u0437\u043c\u0435\u0440\u0430 <em>n<\/em> \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e <em>h<\/em>, \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u044e\u0449\u0443\u044e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f PAC-\u043e\u0431\u0443\u0447\u0430\u0435\u043c\u044b\u043c, \u0435\u0441\u043b\u0438 \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u043f\u043e\u0440\u043e\u0433\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/69c\/557\/5e9\/69c5575e9b1b42051069fb6122976644.svg\" alt=\"$\\epsilon$\" data-tex=\"inline\"><\/math> \u0438 \u0441\u0442\u0435\u043f\u0435\u043d\u0438 \u0443\u0432\u0435\u0440\u0435\u043d\u043d\u043e\u0441\u0442\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/dd8\/a86\/2f5\/dd8a862f53583925b661220cb68f577b.svg\" alt=\"$\\delta$\" data-tex=\"inline\"><\/math> \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0430\u043a\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u043e\u0431\u0443\u0447\u0430\u044e\u0449\u0438\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 <em>n<\/em>, \u0447\u0442\u043e \u0434\u043b\u044f \u0432\u044b\u0443\u0447\u0435\u043d\u043d\u043e\u0439 \u043d\u0430 \u043d\u0435\u043c \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <em>h<\/em> \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435: \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0440\u0438\u0441\u043a\u0430 \u043f\u0440\u0435\u0432\u044b\u0441\u0438\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/69c\/557\/5e9\/69c5575e9b1b42051069fb6122976644.svg\" alt=\"$\\epsilon$\" data-tex=\"inline\"><\/math> \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/68c\/e6c\/508\/68ce6c508e356cf2f3f9a409bcab46f3.svg\" alt=\"$1 - \\delta$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  <\/p>\n<p>\u041c\u043e\u0436\u043d\u043e \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c \u044d\u0442\u043e \u0442\u0430\u043a: \u0432\u044b\u0431\u0440\u0430\u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u0448\u0438 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u043a \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <em>h<\/em>, \u0441 \u0442\u043e\u0447\u043a\u0438 \u0437\u0440\u0435\u043d\u0438\u044f \u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0440\u0438\u0441\u043a\u0430, \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0437\u043d\u0430\u0442\u044c, \u0447\u0442\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0430\u043a\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 (\u0432\u044b\u0431\u0440\u0430\u043d\u043d\u044b\u0445, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e, \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e \u0438 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e \u0438\u0437 \u0432\u0441\u0435\u0433\u043e \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0430), \u0447\u0442\u043e \u043f\u0440\u0438 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0438 \u043d\u0430 \u043d\u0435\u043c \u043c\u044b \u0434\u043e\u0441\u0442\u0438\u0433\u043d\u0435\u043c \u044d\u0442\u0438\u0445 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0439.<\/p>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u042d\u0442\u0430 \u0442\u0435\u043e\u0440\u0438\u044f \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a 80-\u043c \u0433\u043e\u0434\u0430\u043c \u043f\u0440\u043e\u0448\u043b\u043e\u0433\u043e \u0432\u0435\u043a\u0430. \u041e\u043d\u0430, \u043e\u0434\u043d\u0430\u043a\u043e, \u043d\u0435 \u0434\u0430\u0435\u0442 \u043a\u0430\u043a\u043e\u0433\u043e-\u043b\u0438\u0431\u043e \u0438\u0437\u043c\u0435\u0440\u0438\u043c\u043e\u0433\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0442\u0440\u0430\u0436\u0430\u043b \u0431\u044b \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0441\u0442\u044c \u0442\u043e\u0433\u043e \u0438\u043b\u0438 \u0438\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043a \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044e. \u041d\u043e \u0442\u0430\u043a\u043e\u0439 \u043e\u0442\u0432\u0435\u0442 \u0434\u0430\u0435\u0442 \u0443\u0436\u0435 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u0430\u044f \u0412. \u0412\u0430\u043f\u043d\u0438\u043a\u043e\u043c \u0438 \u0410. \u0427\u0435\u0440\u0432\u043e\u043d\u0435\u043d\u043a\u0438\u0441\u043e\u043c \u0442\u0435\u043e\u0440\u0438\u044f \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f (<a href=\"http:\/\/www.machinelearning.ru\/wiki\/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%92%D0%B0%D0%BF%D0%BD%D0%B8%D0%BA%D0%B0-%D0%A7%D0%B5%D1%80%D0%B2%D0%BE%D0%BD%D0%B5%D0%BD%D0%BA%D0%B8%D1%81%D0%B0\">VC-\u0442\u0435\u043e\u0440\u0438\u044f<\/a>). \u0412 \u043e\u0441\u043d\u043e\u0432\u0435 \u044d\u0442\u043e\u0439 \u0442\u0435\u043e\u0440\u0438\u0438 \u043b\u0435\u0436\u0438\u0442 \u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c VC-\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438. VC-\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u2014 \u044d\u0442\u043e \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0442\u043e\u0440\u043d\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u0442\u043e\u0433\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438 \u0432\u0441\u0435\u043c\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438.<\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u0440\u0438\u043c\u0435\u0440<\/b><\/p>\n<div class=\"spoiler_text\">\n<p>\u0414\u043e\u043f\u0443\u0441\u0442\u0438\u043c \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0441\u0442\u0440\u043e\u044f\u0449\u0438\u0439 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0433\u0438\u043f\u0435\u0440\u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u044c \u0432 n-\u043c\u0435\u0440\u043d\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043e\u0434\u043d\u043e\u043c\u0435\u0440\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e: \u0434\u0432\u0435 \u0442\u043e\u0447\u043a\u0438 \u0432 \u0442\u0430\u043a\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c, \u0430 \u0432\u043e\u0442 \u0442\u0440\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u0443\u0436\u0435 \u043d\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f, \u0437\u043d\u0430\u0447\u0438\u0442, VC=2. \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0434\u0432\u0443\u043c\u0435\u0440\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e: \u0442\u0440\u0438 \u0442\u043e\u0447\u043a\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u043a\u043b\u0430\u0441\u0441\u0430 \u0432\u0441\u0435\u0433\u0434\u0430, \u0430 \u0432\u043e\u0442 \u0447\u0435\u0442\u044b\u0440\u0435 \u0442\u043e\u0447\u043a\u0438 \u0432\u0441\u0435\u043c\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u043c\u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u043c\u0438 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u044c \u0443\u0436\u0435 \u043d\u0435 \u0432\u044b\u0439\u0434\u0435\u0442, \u0437\u043d\u0430\u0447\u0438\u0442, VC=3.<\/p>\n<p>  <\/p>\n<p>\u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u0441\u0442\u0440\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e VC \u0434\u043b\u044f \u043a\u043b\u0430\u0441\u0441\u0430 \u0433\u0438\u043f\u0435\u0440\u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0435\u0439 \u0432 n-\u043c\u0435\u0440\u043d\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0440\u0430\u0432\u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7e7\/f6a\/bfc\/7e7f6abfc659c22769b2277142014895.svg\" alt=\"$n + 1$\" data-tex=\"inline\"><\/math>.<\/p>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0442\u0435\u043e\u0440\u0435\u043c\u0430 VC-\u0442\u0435\u043e\u0440\u0438\u0438, \u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043e\u043a, \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0442\u043e\u0442 \u0444\u0430\u043a\u0442, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 VC-\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043a\u043e\u043d\u0435\u0447\u043d\u0430\u044f, \u0442\u043e \u043e\u043d \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f PAC-\u043e\u0431\u0443\u0447\u0430\u0435\u043c\u044b\u043c. \u0411\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, VC-\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u043c \u0442\u043e\u0433\u043e, \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0431\u044b\u0441\u0442\u0440\u043e \u0441 \u0440\u043e\u0441\u0442\u043e\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u043a\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u044d\u043c\u043f\u0438\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0440\u0438\u0441\u043a\u0430 \u0441\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u0441\u0440\u0435\u0434\u043d\u0435\u0433\u043e \u0440\u0438\u0441\u043a\u0430.<\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0441\u0430\u043c\u0430 \u043f\u043e \u0441\u0435\u0431\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0438\u0437\u0443\u0447\u0435\u043d\u043d\u043e\u0439 \u0438 \u0438\u043c\u0435\u0435\u0442 \u0441\u0442\u0440\u043e\u0433\u0443\u044e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0431\u0430\u0437\u0443.<\/p>\n<p>  <\/p>\n<h1 id=\"o-chem-zhe-togda-rech-v-state-v-nature\">\u041e \u0447\u0435\u043c \u0436\u0435 \u0442\u043e\u0433\u0434\u0430 \u0440\u0435\u0447\u044c \u0432 \u0441\u0442\u0430\u0442\u044c\u0435 \u0432 Nature?<\/h1>\n<p>  <\/p>\n<p>\u0410\u0432\u0442\u043e\u0440\u044b \u043f\u0438\u0448\u0443\u0442, \u0447\u0442\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 PAC-\u0442\u0435\u043e\u0440\u0438\u0438, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u043e\u0439 \u043d\u0430 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f\u0445 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438, \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u043d\u0430 \u043d\u0435 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u0430\u044f. <\/p>\n<p>  <\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u0420\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0438 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0435\u0439 \u0438\u0437 PAC-\u0442\u0435\u043e\u0440\u0438\u0438<\/b><\/p>\n<div class=\"spoiler_text\">\n<div class=\"scrollable-table\">\n<table>\n<thead>\n<tr>\n<th>\u0417\u0430\u0434\u0430\u0447\u0430<\/th>\n<th>\u0420\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c<\/th>\n<\/tr>\n<\/thead>\n<tbody>\n<tr>\n<td>\u0411\u0438\u043d\u0430\u0440\u043d\u0430\u044f \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f<\/td>\n<td>VC-\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c<\/td>\n<\/tr>\n<tr>\n<td>\u041c\u043d\u043e\u0433\u043e\u043a\u043b\u0430\u0441\u0441\u043e\u0432\u0430\u044f \u043a\u043b\u0430\u0441\u0441\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f<\/td>\n<td>\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u041d\u0430\u0442\u0430\u0440\u0430\u0434\u0436\u0430\u043d\u0430<\/td>\n<\/tr>\n<tr>\n<td>\u0420\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f<\/td>\n<td>Fat Shattering<\/td>\n<\/tr>\n<tr>\n<td>&#8230;<\/td>\n<td>&#8230;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<\/div>\n<p>  <\/p>\n<p>\u0410\u0432\u0442\u043e\u0440\u044b \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u0437\u0430\u0434\u0430\u0447\u0438, \u0441\u0430\u043c\u0430 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0430 \u0442\u0430\u043a, \u0447\u0442\u043e \u0443\u0441\u043f\u0435\u0445 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u043d \u043a\u0430\u043a PAC-\u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u044c. \u0410\u0432\u0442\u043e\u0440\u044b \u043f\u0438\u0448\u0443\u0442: <\/p>\n<p>  <\/p>\n<p><em>\u041f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u043c, \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442 \u0441\u0430\u0439\u0442, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043c\u044b \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u043c \u0440\u0435\u043a\u043b\u0430\u043c\u0443. \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043c <strong>X<\/strong>, \u043a\u0430\u043a \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0432\u0441\u0435\u0445 \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0445 \u043f\u043e\u0441\u0435\u0442\u0438\u0442\u0435\u043b\u0435\u0439 \u044d\u0442\u043e\u0433\u043e \u0441\u0430\u0439\u0442\u0430. \u0420\u0435\u043a\u043b\u0430\u043c\u0430 \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0438\u0437 \u043d\u0435\u043a\u043e\u0435\u0433\u043e \u043f\u0443\u043b\u0430 \u0440\u0435\u043a\u043b\u0430\u043c\u044b. \u0423\u0441\u043b\u043e\u0432\u043d\u043e, \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u043e\u0435 \u043e\u0431\u044a\u044f\u0432\u043b\u0435\u043d\u0438\u0435 \u0438\u0437 \u043f\u0443\u043b\u0430 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u043e \u043d\u0430 \u043a\u0430\u043a\u0443\u044e-\u0442\u043e \u043a\u0430\u0442\u0435\u0433\u043e\u0440\u0438\u044e \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u0439: \u0441\u043f\u043e\u0440\u0442\u0438\u0432\u043d\u044b\u0435 \u043e\u0431\u044a\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u043b\u044e\u0431\u0438\u0442\u0435\u043b\u044f\u043c \u0441\u043f\u043e\u0440\u0442\u0430 \u0438 \u0442.\u0434. \u0417\u0430\u0434\u0430\u0447\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0440\u0430\u0437\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a\u0443\u044e \u0440\u0435\u043a\u043b\u0430\u043c\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0440\u0435\u043b\u0435\u0432\u0430\u043d\u0442\u043d\u0430\u044f \u043f\u043e\u0441\u0435\u0442\u0438\u0442\u0435\u043b\u044f\u043c \u0441\u0430\u0439\u0442\u0430<\/em>.<\/p>\n<p>  <\/p>\n<p>\u041f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0442\u0443\u0442 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043d\u0435 \u0437\u043d\u0430\u0435\u043c, \u043a\u0442\u043e \u0438\u043c\u0435\u043d\u043d\u043e \u043f\u043e\u0441\u0435\u0442\u0438\u0442 \u0441\u0430\u0439\u0442 \u0432 \u0431\u0443\u0434\u0443\u0449\u0435\u043c. \u0415\u0441\u043b\u0438 \u043e\u0431\u043e\u0431\u0449\u0438\u0442\u044c, \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0442\u0430\u043a\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u043f\u0438\u0441\u0430\u043d\u0430 \u0442\u0430\u043a:<\/p>\n<p>  <\/p>\n<p><em>\u0418\u043c\u0435\u044f \u043d\u0430\u0431\u043e\u0440 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b8b\/97c\/656\/b8b97c6567171cc2b6a7f303a0fa8b0a.svg\" alt=\"$F$\" data-tex=\"inline\"><\/math> \u043d\u0430\u0434 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math>, \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1ac\/e5d\/297\/1ace5d297b5676914221b9a1d3347663.svg\" alt=\"$F_{best}$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e\u0431\u044b \u0435\u0435 \u043c\u0435\u0442\u0440\u0438\u043a\u0430 \u043d\u0430\u0434 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u043c \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c3d\/2f2\/c44\/c3d2f2c44fc42edea27de7f8f67b4829.svg\" alt=\"$P$\" data-tex=\"inline\"><\/math> \u0431\u044b\u043b\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439. \u041f\u0440\u0438\u0447\u0435\u043c \u043d\u0430\u0439\u0442\u0438 \u0442\u0430\u043a\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043d\u0430\u0434\u043e, \u043e\u0441\u043d\u043e\u0432\u044b\u0432\u0430\u044f\u0441\u044c \u043d\u0430 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u043e\u043c \u043d\u0430\u0431\u043e\u0440\u0435 \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u044b\u0445 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u0445 \u0432\u0435\u043b\u0438\u0447\u0438\u043d \u0438\u0437 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c3d\/2f2\/c44\/c3d2f2c44fc42edea27de7f8f67b4829.svg\" alt=\"$P$\" data-tex=\"inline\"><\/math><\/em><\/p>\n<p>  <\/p>\n<h1 id=\"emx-obuchenie\">EMX-\u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435<\/h1>\n<p>  <\/p>\n<p>\u0428\u0430\u0439 \u0411\u0435\u043d-\u0414\u0430\u0432\u0438\u0434 \u0438 \u0435\u0433\u043e \u043a\u043e\u043b\u043b\u0435\u0433\u0438 \u0432\u0432\u043e\u0434\u044f\u0442 \u043d\u043e\u0432\u043e\u0435 \u043f\u043e\u043d\u044f\u0442\u0438\u0435 \u2014 <strong>E<\/strong>stimating the <strong>M<\/strong>a<strong>X<\/strong>imum (EMX-\u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u0438), \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043a\u0430\u043a \u0440\u0430\u0437 \u0438 \u0434\u0430\u0435\u0442 \u043a\u0440\u0438\u0442\u0435\u0440\u0438\u0438 \u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u043c\u0430\u043a\u0441\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438:<\/p>\n<p>  <\/p>\n<p><em>\u0414\u043b\u044f \u043d\u0430\u0431\u043e\u0440\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b8b\/97c\/656\/b8b97c6567171cc2b6a7f303a0fa8b0a.svg\" alt=\"$F$\" data-tex=\"inline\"><\/math>, \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math> \u0438 \u043d\u0435\u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c3d\/2f2\/c44\/c3d2f2c44fc42edea27de7f8f67b4829.svg\" alt=\"$P$\" data-tex=\"inline\"><\/math>, \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/34f\/0d5\/53d\/34f0d553da8d29d1cb181486dbd9a599.svg\" alt=\"$d = d(\\epsilon, \\delta)$\" data-tex=\"inline\"><\/math>, \u0444\u0443\u043d\u043a\u0446\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1f1\/755\/dc1\/1f1755dc10315ecba8b368b1440e2607.svg\" alt=\"$G(S)$\" data-tex=\"inline\"><\/math> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/adf\/979\/e17\/adf979e172cac9e41b8a4a1e0685b1d8.svg\" alt=\"$(\\epsilon, \\delta)$\" data-tex=\"inline\"><\/math>-EMX-\u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0439, \u0435\u0441\u043b\u0438 \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c3d\/2f2\/c44\/c3d2f2c44fc42edea27de7f8f67b4829.svg\" alt=\"$P$\" data-tex=\"inline\"><\/math>:<\/em><\/p>\n<p>  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/7d1\/69f\/5ab\/7d169f5abb71058d8c089d7dbc0e06dd.svg\" alt=\"$Pr_{S \\sim P^d}[\\mathbb{E}_P(G(S)) \\leq \\sup_{h \\in F} \\mathbb{E} (h) - \\epsilon] \\leq \\delta $\" data-tex=\"display\"><\/math><\/p>\n<p>  <\/p>\n<p>\u0422\u0430\u043a\u043e\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u0438 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0441\u043e\u043c\u043d\u0435\u043d\u043d\u043e \u0431\u043e\u043b\u0435\u0435 \u043e\u0431\u0449\u0438\u043c, \u043d\u0435\u0436\u0435\u043b\u0438 \u043a\u043e\u043d\u0446\u0435\u043f\u0446\u0438\u044f PAC.<\/p>\n<p>  <\/p>\n<h1 id=\"togda-prichem-tut-kontinuum-i-nereshennaya-problema-matematiki\">\u0422\u043e\u0433\u0434\u0430 \u043f\u0440\u0438\u0447\u0435\u043c \u0442\u0443\u0442 \u043a\u043e\u043d\u0442\u0438\u043d\u0443\u0443\u043c \u0438 &quot;\u043d\u0435\u0440\u0435\u0448\u0435\u043d\u043d\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438&quot;?<\/h1>\n<p>  <\/p>\n<p>\u0410\u0432\u0442\u043e\u0440\u044b \u0434\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0443\u044e \u0442\u0435\u043e\u0440\u0435\u043c\u0443:<br \/>  <em>EMX-\u043e\u0431\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b8b\/97c\/656\/b8b97c6567171cc2b6a7f303a0fa8b0a.svg\" alt=\"$F$\" data-tex=\"inline\"><\/math> \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c3d\/2f2\/c44\/c3d2f2c44fc42edea27de7f8f67b4829.svg\" alt=\"$P$\" data-tex=\"inline\"><\/math> \u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u0430\u043a\u0441\u0438\u043e\u043c \u0426\u0435\u0440\u043c\u0435\u043b\u043e \u2014 \u0424\u0440\u0435\u043d\u043a\u0435\u043b\u044f \u0441 \u0430\u043a\u0441\u0438\u043e\u043c\u043e\u0439 \u0432\u044b\u0431\u043e\u0440\u0430 (\u0434\u0430\u043b\u0435\u0435 ZFC).<\/em><\/p>\n<p>  <\/p>\n<p>\u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u0441\u0442\u0430\u043d\u0434\u0430\u0440\u0442\u043d\u044b\u0445 \u0430\u043a\u0441\u0438\u043e\u043c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438 \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0432 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043d\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b EMX-\u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u043d\u0438 \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f.<\/p>\n<p>  <\/p>\n<p>\u0410\u0432\u0442\u043e\u0440\u044b \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u043a\u0430\u0437\u044b\u0432\u0430\u044e\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043e\u0431\u0449\u0435\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f EMX-\u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043a\u0430\u043a\u043e\u0433\u043e-\u043b\u0438\u0431\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0430 VC-\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 (\u0438\u043b\u0438 \u043b\u044e\u0431\u043e\u0439 \u0434\u0440\u0443\u0433\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438), \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u044b\u043b \u0431\u044b \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u043c \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 EMX-\u043e\u0431\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u0438, \u0438 \u043d\u0430\u043e\u0431\u043e\u0440\u043e\u0442, EMX-\u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u044c \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043b\u0430 \u0431\u044b \u0438\u0437 \u0435\u0433\u043e \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0441\u0442\u0438. \u0411\u043e\u043b\u0435\u0435 \u0441\u0442\u0440\u043e\u0433\u043e \u0443 \u043d\u0438\u0445 \u044d\u0442\u043e \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u043e \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0432\u0438\u0434\u0435:<\/p>\n<p>  <\/p>\n<p><em>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0430\u043a\u0430\u044f \u043a\u043e\u043d\u0441\u0442\u0430\u043d\u0442\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/e1a\/229\/081\/e1a229081e8db6ee98dfb79797b987dd.svg\" alt=\"$c$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c \u0441\u043e\u0433\u043b\u0430\u0441\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u044c ZFC, \u0442\u043e \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u0441\u0432\u043e\u0439\u0441\u0442\u0432\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b58\/a0d\/be3\/b58a0dbe3124ff248e4f6f6ced4248b6.svg\" alt=\"$A(X, Y)$\" data-tex=\"inline\"><\/math>, \u0447\u0442\u043e \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 <math>$inline$m, M &gt; c$inline$<\/math> \u0434\u043b\u044f \u043b\u044e\u0431\u043e\u0433\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/6d6\/a4f\/78f\/6d6a4f78fbacd6edecc018ce8ad3e364.svg\" alt=\"$X$\" data-tex=\"inline\"><\/math> \u0438 \u043d\u0430\u0431\u043e\u0440\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b8b\/97c\/656\/b8b97c6567171cc2b6a7f303a0fa8b0a.svg\" alt=\"$F$\" data-tex=\"inline\"><\/math> \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u043b\u043e\u0441\u044c \u0431\u044b:<\/em><\/p>\n<p>  <\/p>\n<ul>\n<li><em>\u0415\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b58\/a0d\/be3\/b58a0dbe3124ff248e4f6f6ced4248b6.svg\" alt=\"$A(X, Y)$\" data-tex=\"inline\"><\/math> \u0432\u0435\u0440\u043d\u043e, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/579\/2b4\/d51\/5792b4d51b11a4fc402f1db62767bb79.svg\" alt=\"$(1\/3, 1\/3)$\" data-tex=\"inline\"><\/math>-\u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c EMX-\u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b8b\/97c\/656\/b8b97c6567171cc2b6a7f303a0fa8b0a.svg\" alt=\"$F$\" data-tex=\"inline\"><\/math> \u043d\u0435 \u043f\u0440\u0435\u0432\u044b\u0448\u0430\u0435\u0442 M;<\/em><\/li>\n<li><em>\u0415\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b58\/a0d\/be3\/b58a0dbe3124ff248e4f6f6ced4248b6.svg\" alt=\"$A(X, Y)$\" data-tex=\"inline\"><\/math> \u043b\u043e\u0436\u043d\u043e, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/579\/2b4\/d51\/5792b4d51b11a4fc402f1db62767bb79.svg\" alt=\"$(1\/3, 1\/3)$\" data-tex=\"inline\"><\/math>-\u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c EMX-\u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b8b\/97c\/656\/b8b97c6567171cc2b6a7f303a0fa8b0a.svg\" alt=\"$F$\" data-tex=\"inline\"><\/math> \u043f\u043e \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u043c\u0435\u0440\u0435 m;<\/em><\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u041d\u0430\u043e\u0431\u043e\u0440\u043e\u0442, \u044d\u0442\u043e \u0441\u043f\u0440\u0430\u0432\u0435\u0434\u043b\u0438\u0432\u043e \u0434\u043b\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, VC-\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u0434\u043b\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b58\/a0d\/be3\/b58a0dbe3124ff248e4f6f6ced4248b6.svg\" alt=\"$A(X, Y)$\" data-tex=\"inline\"><\/math> \u0440\u0430\u0432\u043d\u043e\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/136\/10e\/3d2\/13610e3d22d774199339b81278832fc5.svg\" alt=\"$VC \\leq d$\" data-tex=\"inline\"><\/math> \u044d\u0442\u043e \u0431\u0443\u0434\u0435\u0442 \u043f\u043e \u0441\u0443\u0442\u0438 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0430 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0442\u0435\u043e\u0440\u0435\u043c\u044b VC-\u0442\u0435\u043e\u0440\u0438\u0438.<\/p>\n<p>  <\/p>\n<h1 id=\"zaklyuchenie\">\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/h1>\n<p>  <\/p>\n<p>\u041f\u043e\u0441\u044b\u043b \u0440\u0430\u0431\u043e\u0442\u044b \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u043c\u0430\u043b\u043e \u0441\u0432\u044f\u0437\u0430\u043d \u0441 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0432\u043e\u043f\u0440\u043e\u0441\u0430\u043c\u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0438\u043b\u0438 \u0434\u0430\u0436\u0435 \u0441 \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u043c\u0438 \u0432\u043e\u043f\u0440\u043e\u0441\u0430\u043c\u0438 \u0442\u0435\u043e\u0440\u0438\u0438 \u0441\u0442\u0430\u0442\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u041a\u0430\u043a \u043c\u043d\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c, \u0433\u043b\u0430\u0432\u043d\u044b\u0445 \u043c\u044b\u0441\u043b\u0438 \u0432 \u0440\u0430\u0431\u043e\u0442\u0435 \u0434\u0432\u0435:<\/p>\n<p>  <\/p>\n<ul>\n<li>\u041a\u0440\u0430\u0441\u0438\u0432\u0430\u044f \u0441\u0432\u044f\u0437\u044c EMX-\u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u0438 \u0442\u0435\u043e\u0440\u0435\u043c \u0413\u0451\u0434\u0435\u043b\u044f;<\/li>\n<li>\u041f\u0440\u0438\u043d\u0446\u0438\u043f\u0438\u0430\u043b\u044c\u043d\u0430\u044f \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0439 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0441\u0442\u0438\u043a\u0438 \u043e\u0431\u0443\u0447\u0430\u0435\u043c\u043e\u0441\u0442\u0438 (\u0442\u0438\u043f\u0430 VC-\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438) \u0434\u043b\u044f \u043e\u0431\u0449\u0435\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0430 \u0437\u0430\u0434\u0430\u0447 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f.<\/li>\n<\/ul>\n<p>  <\/p>\n<p>\u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u043c\u043d\u0435 \u043b\u0438\u0447\u043d\u043e \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u043d\u0435 \u043d\u0440\u0430\u0432\u0438\u0442\u0441\u044f \u0437\u0430\u0433\u043e\u043b\u043e\u0432\u043e\u043a &quot;\u041c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u043e\u0441\u044c \u0441 \u043d\u0435\u0440\u0435\u0448\u0435\u043d\u043d\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439&quot;, \u0443\u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u043d\u044b\u0439 \u0432 <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/484238\/\">\u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0435 \u043e\u0431\u0437\u043e\u0440\u0430 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0438<\/a>. \u041d\u0430 \u043c\u043e\u0439 \u0432\u0437\u0433\u043b\u044f\u0434, \u044d\u0442\u043e \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u044b\u0439 \u043a\u043b\u0438\u043a\u0431\u0435\u0439\u0442, \u0431\u043e\u043b\u0435\u0435 \u0442\u043e\u0433\u043e, \u043e\u043d \u043f\u0440\u043e\u0441\u0442\u043e \u043d\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u0412 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u0435 \u043d\u0435 \u0438\u0434\u0435\u0442 \u0440\u0435\u0447\u044c \u043e \u0442\u043e\u043c, \u0447\u0442\u043e \u043a\u0442\u043e-\u0442\u043e \u0441 \u0447\u0435\u043c-\u0442\u043e \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u0441\u044f. \u041c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0438 PAC-\u0442\u0435\u043e\u0440\u0438\u044f \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0438, \u0442\u0430\u043a \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u044e\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c. \u0423\u043a\u0430\u0437\u0430\u043d\u043e \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e PAC-\u0442\u0435\u043e\u0440\u0438\u044f \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043e\u0431\u043e\u0431\u0449\u0435\u043d\u0430 \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435, \u0447\u0430\u0441\u0442\u043d\u044b\u0435 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f, \u043d\u0430\u0439\u0434\u0435\u043d\u044b \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u0441\u0432\u044f\u0437\u0438 \u0441 \u0442\u0435\u043e\u0440\u0435\u043c\u0430\u043c\u0438 \u0413\u0451\u0434\u0435\u043b\u044f, \u043d\u043e \u043d\u0438 \u0441\u043b\u043e\u0432\u0430 \u043e \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u043d\u0435\u0440\u0435\u0448\u0435\u043d\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0435, \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u043e\u0441\u044c \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435.<\/p>\n<\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/raiffeisenbank\/blog\/484306\/\"> https:\/\/habr.com\/ru\/company\/raiffeisenbank\/blog\/484306\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html\" id=\"post-content-body\" data-io-article-url=\"https:\/\/habr.com\/ru\/company\/raiffeisenbank\/blog\/484306\/\">\n<p>\u042d\u0442\u0430 \u0441\u0442\u0430\u0442\u044c\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u043e\u0438\u043c \u0432\u043e\u043b\u044c\u043d\u044b\u043c \u043f\u0435\u0440\u0435\u0441\u043a\u0430\u0437\u043e\u043c \u0440\u0430\u0431\u043e\u0442\u044b <a href=\"https:\/\/www.nature.com\/articles\/s42256-018-0002-3\">Learnability can be undecidable, Shai Ben-David, et al.<\/a><\/p>\n<p>  <\/p>\n<p>\u041d\u0435\u0434\u0430\u0432\u043d\u043e \u043d\u0430 \u0425\u0430\u0431\u0440\u0435 \u0432\u044b\u0448\u043b\u0430 \u0441\u0442\u0430\u0442\u044c\u044f <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/484238\/\">\u041c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u0435 \u0441\u0442\u043e\u043b\u043a\u043d\u0443\u043b\u043e\u0441\u044c \u0441 \u043d\u0435\u0440\u0435\u0448\u0435\u043d\u043d\u043e\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439<\/a>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043e\u043c \u043e\u0434\u043d\u043e\u0438\u043c\u0435\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0437\u043e\u0440\u0430 \u0432 Nature News \u0441\u0442\u0430\u0442\u044c\u0438 \u0428\u0430\u0439 \u0411\u0435\u043d-\u0414\u0430\u0432\u0438\u0434\u0430. \u041e\u0434\u043d\u0430\u043a\u043e, \u0438\u0437-\u0437\u0430 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u0435\u0439 \u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438 \u0438 \u043a\u0440\u0430\u0442\u043a\u043e\u0441\u0442\u0438 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043e\u0431\u0437\u043e\u0440\u0430 \u043c\u043d\u0435 \u043e\u0441\u0442\u0430\u043b\u043e\u0441\u044c \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u0436\u0435 \u0431\u044b\u043b\u043e \u0432 \u0441\u0442\u0430\u0442\u044c\u0435. \u0417\u043d\u0430\u044f \u0428\u0430\u0439 \u0411\u0435\u043d-\u0414\u0430\u0432\u0438\u0434\u0430, \u043a\u0430\u043a \u0430\u0432\u0442\u043e\u0440\u0430 \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u043e\u0439 \u043a\u043d\u0438\u0433\u0438 &quot;Understanding Machine Learning: From Theory to Algorithms&quot;, \u044f \u0437\u0430\u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u043b\u0441\u044f \u044d\u0442\u043e\u0439 \u0442\u0435\u043c\u043e\u0439, \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u043b\u0441\u044f \u0441 \u044d\u0442\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u043e\u0439 \u0438 \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u043b\u0441\u044f \u0442\u0443\u0442 \u0438\u0437\u043b\u043e\u0436\u0438\u0442\u044c \u043e\u0441\u043d\u043e\u0432\u043d\u044b\u0435 \u043c\u043e\u043c\u0435\u043d\u0442\u044b.<\/p>\n<p>  <\/p>\n<p>\u0421\u0440\u0430\u0437\u0443 \u0441\u043a\u0430\u0436\u0443, \u0447\u0442\u043e \u0441\u0442\u0430\u0442\u044c\u044f \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u043b\u043e\u0436\u043d\u0430\u044f \u0438, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u044f \u0443\u043f\u0443\u0441\u0442\u0438\u043b \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0430\u0436\u043d\u044b\u0435 \u043c\u043e\u043c\u0435\u043d\u0442\u044b, \u043d\u043e \u043c\u043e\u0439 \u043e\u0431\u0437\u043e\u0440 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u043b\u043d\u044b\u043c, \u0447\u0435\u043c \u0442\u043e\u0442, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0443\u0436\u0435 <a href=\"https:\/\/habr.com\/ru\/company\/otus\/blog\/484238\/\">\u0435\u0441\u0442\u044c<\/a> \u043d\u0430 \u0425\u0430\u0431\u0440\u0435.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-297285","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/297285","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=297285"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/297285\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=297285"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=297285"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=297285"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}