{"id":285220,"date":"2017-04-19T17:45:28","date_gmt":"2017-04-19T13:45:28","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=285220"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=285220","title":{"rendered":"\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0436\u043e\u043d\u043a\u0435\u0440\u0430-\u0412\u043e\u043b\u0433\u0435\u043d\u0430\u043d\u0442\u0430 + t-SNE = \u0441\u0443\u043f\u0435\u0440-\u0441\u0438\u043b\u0430"},"content":{"rendered":"<p>\u0414\u043e:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/14b\/047\/01f\/14b04701f5234739baf7c70b58f70921.png\"\/><\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/0d8\/21e\/8bc\/0d821e8bc2fe47c6897a7c3fa1b44c8a.png\"\/><\/p>\n<p>  \u0417\u0430\u0438\u043d\u0442\u0440\u0438\u0433\u043e\u0432\u0430\u043d\u044b? \u041d\u043e \u043e\u0431\u043e \u0432\u0441\u0435\u043c \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443.<\/p>\n<h2><font color=\"#c75733\">t-SNE<\/font><\/h2>\n<p>  <a href=\"https:\/\/lvdmaaten.github.io\/tsne\/\">t-SNE<\/a> \u2014 \u044d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u043d\u0438\u0436\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0432\u0430\u0448\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0447\u0442\u043e\u0431\u044b \u0438\u0445 \u0431\u044b\u043b\u043e \u043f\u0440\u043e\u0449\u0435 \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c. \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u0435\u0442 \u0441\u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0441\u043e\u0442\u043d\u0438 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u0439 \u043a \u0432\u0441\u0435\u0433\u043e \u0434\u0432\u0443\u043c, \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u044f \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0432\u0430\u0436\u043d\u044b\u0435 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0434\u0430\u043d\u043d\u044b\u043c\u0438: \u0447\u0435\u043c \u0431\u043b\u0438\u0436\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435, \u0442\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u044d\u0442\u0438\u043c\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u043c\u0438 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438. t-SNE \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0430 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445 \u0438 \u0441\u0440\u0435\u0434\u043d\u0438\u0445 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043d\u0430\u0431\u043e\u0440\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043d\u0430\u0441\u0442\u0440\u043e\u0435\u043a \u0433\u0438\u043f\u0435\u0440\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432. \u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0435\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c 100 000 \u0442\u043e\u0447\u0435\u043a \u0438 \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0438\u0445 \u0447\u0435\u0440\u0435\u0437 \u044d\u0442\u0443 \u0432\u043e\u043b\u0448\u0435\u0431\u043d\u044b\u0439 \u0447\u0435\u0440\u043d\u044b\u0439 \u044f\u0449\u0438\u043a, \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043a\u0440\u0430\u0441\u0438\u0432\u044b\u0439 \u0433\u0440\u0430\u0444\u0438\u043a \u0440\u0430\u0441\u0441\u0435\u044f\u043d\u0438\u044f.<br \/>  <a name=\"habracut\"><\/a><br \/>  \u0412\u043e\u0442 \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u0438\u0437 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u043d\u043e\u0433\u043e \u0437\u0440\u0435\u043d\u0438\u044f. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u0434\u0430\u043d\u043d\u044b\u0445 \u043f\u043e\u0434 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435\u043c <a href=\"http:\/\/yann.lecun.com\/exdb\/mnist\/\">MNIST<\/a>, \u0441\u043e\u0437\u0434\u0430\u043d\u043d\u044b\u0439 \u042f\u043d\u043e\u043c \u041b\u0435\u043a\u0443\u043d\u043e\u043c (\u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u0441\u043e\u0437\u0434\u0430\u0442\u0435\u043b\u0435\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f \u043d\u0435\u0439\u0440\u043e\u043d\u043d\u044b\u0445 \u0441\u0435\u0442\u0435\u0439 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BE%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%BE%D0%B3%D0%BE_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BE%D1%88%D0%B8%D0%B1%D0%BA%D0%B8\">\u043c\u0435\u0442\u043e\u0434\u043e\u043c \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043e\u0448\u0438\u0431\u043a\u0438<\/a> \u2014 \u043e\u0441\u043d\u043e\u0432\u044b \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0433\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f) \u0438 \u0434\u0440\u0443\u0433\u0438\u043c\u0438. \u0415\u0433\u043e \u0447\u0430\u0441\u0442\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u043a\u0430\u043a \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u043e\u0446\u0435\u043d\u043a\u0438 \u0438\u0434\u0435\u0439, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u043d\u0435\u0439\u0440\u043e\u043d\u043d\u044b\u043c\u0438 \u0441\u0435\u0442\u044f\u043c\u0438, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0432 \u043d\u0430\u0443\u0447\u043d\u044b\u0445 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f\u0445. MNIST \u2014 \u044d\u0442\u043e 70 000 \u0447\u0435\u0440\u043d\u043e-\u0431\u0435\u043b\u044b\u0445 \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 28\u044528. \u041a\u0430\u0436\u0434\u043e\u0435 \u0438\u0437 \u043d\u0438\u0445 \u2014 \u0441\u043a\u0430\u043d \u0440\u0443\u043a\u043e\u043f\u0438\u0441\u043d\u043e\u0439 \u0446\u0438\u0444\u0440\u044b \u0438\u0437 \u043e\u0442\u0440\u0435\u0437\u043a\u0430 [0, 9]. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0441\u043f\u043e\u0441\u043e\u0431 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u201c<a href=\"http:\/\/leon.bottou.org\/projects\/infimnist\">\u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0433\u043e<\/a>\u201d \u043d\u0430\u0431\u043e\u0440\u0430 MNIST, \u043d\u043e \u043d\u0435 \u0431\u0443\u0434\u0443 \u043e\u0442\u043a\u043b\u043e\u043d\u044f\u0442\u044c\u0441\u044f \u043e\u0442 \u0442\u0435\u043c\u044b.<\/p>\n<p>  \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043e\u0431\u0440\u0430\u0437\u0435\u0446 MNIST \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/e80\/789\/b26\/e80789b264fd40fb7d7c93a26cd1c6e5.svg\" alt=\"$28 \u22c528 = 784$\" data-tex=\"inline\"\/><\/math> \u043f\u0440\u0438\u0437\u043d\u0430\u043a\u0430 \u0438 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d \u0432 \u0432\u0438\u0434\u0435 784-\u043c\u0435\u0440\u043d\u043e\u0433\u043e \u0432\u0435\u043a\u0442\u043e\u0440\u0430. \u0412\u0435\u043a\u0442\u043e\u0440\u044b \u043b\u0438\u043d\u0435\u0439\u043d\u044b, \u0438 \u0432 \u0442\u0430\u043a\u043e\u0439 \u0438\u043d\u0442\u0435\u0440\u043f\u0440\u0435\u0442\u0430\u0446\u0438\u0438 \u043c\u044b \u0442\u0435\u0440\u044f\u0435\u043c \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c\u0438 \u043f\u0438\u043a\u0441\u0435\u043b\u044f\u043c\u0438, \u043d\u043e \u0432\u0441\u0435 \u0436\u0435 \u0432 \u044d\u0442\u043e\u043c \u0435\u0441\u0442\u044c \u043f\u043e\u043b\u044c\u0437\u0430. \u0415\u0441\u043b\u0438 \u043f\u043e\u043f\u044b\u0442\u0430\u0442\u044c\u0441\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c, \u043a\u0430\u043a \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043d\u0430\u0448 \u043d\u0430\u0431\u043e\u0440 \u0434\u0430\u043d\u043d\u044b\u0445 \u0432 784D, \u043c\u043e\u0436\u043d\u043e \u0441\u043e\u0439\u0442\u0438 \u0441 \u0443\u043c\u0430, \u0435\u0441\u043b\u0438 \u0432\u044b \u043d\u0435 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u043d\u044b\u0439 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a. \u041e\u0431\u044b\u0447\u043d\u044b\u0435 \u043b\u044e\u0434\u0438 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u044f\u0442\u044c \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 3D, 2D \u0438\u043b\u0438 1D. \u041d\u0435\u044f\u0432\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u0435\u0449\u0435 \u043e\u0434\u043d\u043e \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u0435 \u2014 \u0432\u0440\u0435\u043c\u044f, \u043d\u043e \u0432\u0440\u044f\u0434 \u043b\u0438 \u043a\u0442\u043e-\u0442\u043e \u0441\u043a\u0430\u0436\u0435\u0442, \u0447\u0442\u043e \u0434\u0438\u0441\u043f\u043b\u0435\u0439 \u043a\u043e\u043c\u043f\u044c\u044e\u0442\u0435\u0440\u0430 3D \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0442\u043e\u043c\u0443, \u0447\u0442\u043e \u043e\u043d \u043e\u0431\u043d\u043e\u0432\u043b\u044f\u0435\u0442 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0443 \u0441 \u0447\u0430\u0441\u0442\u043e\u0442\u043e\u0439 100 \u0413\u0446. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0431\u044b\u043b\u043e \u0431\u044b \u0437\u0434\u043e\u0440\u043e\u0432\u043e \u0437\u043d\u0430\u0442\u044c \u0441\u043f\u043e\u0441\u043e\u0431 <i>\u043e\u0442\u043e\u0431\u0440\u0430\u0437\u0438\u0442\u044c<\/i> 784 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u044f \u0432 \u0434\u0432\u0430. \u0417\u0432\u0443\u0447\u0438\u0442 \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e? \u0412 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0442\u0430\u043a \u0438 \u0435\u0441\u0442\u044c. \u0412\u0441\u0442\u0443\u043f\u0430\u0435\u0442 \u0432 \u0438\u0433\u0440\u0443 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D1%80%D0%B8%D0%BD%D1%86%D0%B8%D0%BF_%D0%94%D0%B8%D1%80%D0%B8%D1%85%D0%BB%D0%B5_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%84%D0%B8%D0%B7%D0%B8%D0%BA%D0%B0)\">\u043f\u0440\u0438\u043d\u0446\u0438\u043f \u0414\u0438\u0440\u0438\u0445\u043b\u0435<\/a>: \u043a\u0430\u043a\u043e\u0435 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u043c\u044b \u043d\u0435 \u0432\u044b\u0431\u0435\u0440\u0435\u043c, \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439 \u043d\u0435 \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/2c0\/96e\/01b\/2c096e01b1de43efb1522918baac5cac.jpg\"\/><br \/>  <i>\u0418\u043b\u043b\u044e\u0437\u0438\u044f 3D -&gt; 2D \u043f\u0440\u043e\u0435\u043a\u0446\u0438\u0438 \u0432 <a href=\"http:\/\/www.shadowmatic.com\/\">Shadowmatic<\/a><\/i><\/p>\n<p>  \u041a \u0441\u0447\u0430\u0441\u0442\u044c\u044e, \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0434\u0432\u0438\u043d\u0443\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f:<\/p>\n<ol>\n<li>\u0418\u0441\u0445\u043e\u0434\u043d\u043e\u0435 \u043c\u043d\u043e\u0433\u043e\u043c\u0435\u0440\u043d\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u043e <i>\u0440\u0430\u0437\u0440\u0435\u0436\u0435\u043d\u043d\u043e<\/i>, \u0442\u043e \u0435\u0441\u0442\u044c \u0432\u0440\u044f\u0434 \u043b\u0438 \u043e\u043d\u043e \u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u043e \u043e\u0431\u0440\u0430\u0437\u0446\u0430\u043c\u0438 \u043e\u0434\u043d\u043e\u0440\u043e\u0434\u043d\u043e.<\/li>\n<li>\u041d\u0430\u043c \u043d\u0435 \u043d\u0443\u0436\u043d\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0442\u043e\u0447\u043d\u043e\u0435 \u043e\u0442\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435, \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e \u0437\u043d\u0430\u044f, \u0447\u0442\u043e \u0435\u0433\u043e \u043d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442. \u0412\u043c\u0435\u0441\u0442\u043e \u044d\u0442\u043e\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0434\u0440\u0443\u0433\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0438\u043c\u0435\u0435\u0442 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0438 \u0430\u043f\u043f\u0440\u043e\u043a\u0441\u0438\u043c\u0438\u0440\u0443\u0435\u0442 \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442. \u042d\u0442\u043e \u043d\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u0435\u0442 \u043f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b \u0441\u0436\u0430\u0442\u0438\u044f JPEG: \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u043d\u0435 \u0431\u044b\u0432\u0430\u0435\u0442 \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0438\u0434\u0435\u043d\u0442\u0438\u0447\u043d\u044b\u043c, \u043d\u043e \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 <i>\u043e\u0447\u0435\u043d\u044c<\/i> \u043f\u043e\u0445\u043e\u0436\u0438\u043c \u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0435.<\/li>\n<\/ol>\n<p>  \u0412\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432\u043e\u043f\u0440\u043e\u0441: \u043a\u0430\u043a\u0430\u044f \u043b\u0443\u0447\u0448\u0430\u044f \u0430\u043f\u043f\u0440\u043e\u043a\u0441\u0438\u043c\u0438\u0440\u0443\u044e\u0449\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0432 \u043f\u0443\u043d\u043a\u0442\u0435 2? \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u201c\u043b\u0443\u0447\u0448\u0435\u0439\u201d \u043d\u0435\u0442. \u041a\u0430\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043d\u0438\u0436\u0435\u043d\u0438\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u0441\u0443\u0431\u044a\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u0438 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0432\u0430\u0448\u0435\u0439 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u0439 \u0446\u0435\u043b\u0438, \u043a\u0430\u043a \u0438 \u043f\u0440\u0438 \u0432\u044b\u0431\u043e\u0440\u0435 \u043c\u0435\u0442\u043e\u0434\u0430 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/69c\/551\/138\/69c5511388734be285a48038b6329650.png\"\/><br \/>  <i>\u0420\u0430\u0437\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0438\u0437\u0430\u0446\u0438\u0438 \u043e\u0442 <a href=\"http:\/\/scikit-learn.org\/stable\/auto_examples\/cluster\/plot_cluster_comparison.html\">sklearn<\/a><\/i><\/p>\n<p>  t-SNE \u2014 \u043e\u0434\u0438\u043d \u0438\u0437 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438 \u0443\u043a\u043b\u0430\u0434\u043a\u0438 \u0433\u0440\u0430\u0444\u0430 \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438 (embedded algorithms). \u041a\u043b\u044e\u0447\u0435\u0432\u0430\u044f \u0438\u0434\u0435\u044f \u2014 \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u0442\u044c \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u201c\u043f\u043e\u0445\u043e\u0436\u0435\u0441\u0442\u0438\u201d. <a href=\"http:\/\/distill.pub\/2016\/misread-tsne\/\">\u041f\u043e\u043f\u0440\u043e\u0431\u0443\u0439\u0442\u0435 \u0441\u0430\u043c\u0438<\/a>.<\/p>\n<p>  \u0412\u0441\u0435 \u044d\u0442\u043e \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u044b, \u043e\u043d\u0438 \u0445\u043e\u0440\u043e\u0448\u0438, \u043d\u043e \u0438\u0445 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e. \u0411\u043e\u043b\u044c\u0448\u0438\u043d\u0441\u0442\u0432\u043e \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0430\u043f\u043e\u043c\u0438\u043d\u0430\u044e\u0442 \u043e\u0431\u043b\u0430\u043a\u043e \u0441 \u043a\u043e\u043d\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u043a\u043b\u0430\u0441\u0442\u0435\u0440\u0430\u043c\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, MNIST \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/523\/925\/844\/52392584430149b9ad49f0ef01d38478.png\"\/><br \/>  <i>MNIST \u043f\u043e\u0441\u043b\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f t-SNE<\/i><\/p>\n<h2><font color=\"#c75733\">\u041b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/font><\/h2>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0440\u0435\u0437\u043a\u043e \u0441\u0432\u0435\u0440\u043d\u0435\u043c \u0432 \u0441\u0442\u043e\u0440\u043e\u043d\u0443 \u0438 \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u043c\u0441\u044f \u0441 \u043f\u043e\u043d\u044f\u0442\u0438\u0435\u043c <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5\">\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/a> (linear programming, LP). \u0418\u0437\u0432\u0438\u043d\u0438\u0442\u0435, \u043d\u043e \u044d\u0442\u043e \u043d\u0435 \u043d\u043e\u0432\u044b\u0439 \u0448\u0430\u0431\u043b\u043e\u043d \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, Javascript \u0444\u0440\u0435\u0439\u043c\u0432\u043e\u0440\u043a \u0438\u043b\u0438 \u0441\u0442\u0430\u0440\u0442\u0430\u043f. \u042d\u0442\u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0430:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/fcd\/a68\/31b\/fcda6831bd7b35c4a58fc56ff511d131.svg\" alt=\"$\\arg \\min \\vec{c} \\cdot \\vec{x}\\tag{1}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/286\/3b7\/c84\/2863b7c843ff835acdcc1f6255981ea5.svg\" alt=\"$A\\cdot\\vec{x}\\le\\vec{b}\\tag{2}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/2cc\/e5d\/7a2\/2cce5d7a2c258743dd4bfdbe6c525fb0.svg\" alt=\"$\\vec{x}\\ge0\\tag{3}$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  \u041c\u044b \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u0441\u043a\u0430\u043b\u044f\u0440\u043d\u043e\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/1ca\/ad5\/71b\/1caad571bac51deb6986f2fff3cd73af.svg\" alt=\"$\\vec{c}$\" data-tex=\"inline\"\/><\/math> \u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/0dd\/413\/01d\/0dd41301d0657c23744e7189b5ee570c.svg\" alt=\"$\\vec{x}$\" data-tex=\"inline\"\/><\/math> \u0441 \u0443\u0447\u0435\u0442\u043e\u0432 \u0441\u0438\u0441\u0442\u0435\u043c\u044b \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432, \u0437\u0430\u0432\u0438\u0441\u044f\u0449\u0438\u0445 \u043e\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/0dd\/413\/01d\/0dd41301d0657c23744e7189b5ee570c.svg\" alt=\"$\\vec{x}$\" data-tex=\"inline\"\/><\/math>, \u0438 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f, \u0447\u0442\u043e \u0432\u0441\u0435 \u0435\u0433\u043e \u043a\u043e\u043e\u0440\u0434\u0438\u043d\u0430\u0442\u044b \u043d\u0435\u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u044b. LP \u2014 \u0445\u043e\u0440\u043e\u0448\u043e \u0438\u0437\u0443\u0447\u0435\u043d\u043d\u0430\u044f \u0442\u0435\u043c\u0430 \u0432 \u0442\u0435\u043e\u0440\u0438\u0438 \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438; \u043a\u0430\u043a \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u044d\u0442\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0437\u0430 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0#.D0.A1.D1.82.D1.80.D0.BE.D0.B3.D0.BE_.D0.B8_.D1.81.D0.BB.D0.B0.D0.B1.D0.BE_.D0.BF.D0.BE.D0.BB.D0.B8.D0.BD.D0.BE.D0.BC.D0.B8.D0.B0.D0.BB.D1.8C.D0.BD.D0.BE.D0.B5_.D0.B2.D1.80.D0.B5.D0.BC.D1.8F\">\u0441\u043b\u0430\u0431\u043e \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f<\/a> \u2014 \u043e\u0431\u044b\u0447\u043d\u043e \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/70c\/9de\/548\/70c9de548f12a27cb4e9c3b759df2c3a.svg\" alt=\"$O(n^3)$\" data-tex=\"inline\"\/><\/math>, \u0433\u0434\u0435 <i>n<\/i> \u2014 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 (\u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0438). \u041d\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0438 \u0430\u043f\u043f\u0440\u043e\u043a\u0441\u0438\u043c\u0438\u0440\u0443\u044e\u0449\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u044e\u0449\u0438\u0435\u0441\u044f \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u042d\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442 \u0443\u043c\u043d\u043e\u0436\u0435\u043d\u0438\u0435 \u043c\u0430\u0442\u0440\u0438\u0446 \u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e \u0440\u0430\u0441\u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0435\u043d\u043d\u044b. \u0420\u0430\u0439 \u0434\u043b\u044f \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u0430!<\/p>\n<p>  \u041a LP \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0441\u0432\u0435\u0434\u0435\u043d\u044b \u043d\u0430 \u0443\u0434\u0438\u0432\u043b\u0435\u043d\u0438\u0435 \u043c\u043d\u043e\u0433\u043e \u0437\u0430\u0434\u0430\u0447. \u0412\u043e\u0437\u044c\u043c\u0435\u043c, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A2%D1%80%D0%B0%D0%BD%D1%81%D0%BF%D0%BE%D1%80%D1%82%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0\">\u0442\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443<\/a>.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/5f1\/6cc\/d9f\/5f16ccd9f91b41eeba94772b4beaa5a0.png\"\/><br \/>  <i>\u0422\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430: \u043f\u0443\u043d\u043a\u0442\u044b \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f (S) \u0438 \u043f\u0443\u043d\u043a\u0442\u044b \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u044f (D)<\/i><\/p>\n<p>  \u0415\u0441\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0443\u043d\u043a\u0442\u043e\u0432 \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438 \u043f\u0443\u043d\u043a\u0442\u043e\u0432 \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043d\u0435\u0440\u0430\u0432\u043d\u044b. \u041a\u0430\u0436\u0434\u044b\u0439 \u043f\u0443\u043d\u043a\u0442 \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u044f \u043d\u0443\u0436\u0434\u0430\u0435\u0442\u0441\u044f \u0432 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u0442\u043e\u0432\u0430\u0440\u0430. \u041a\u0430\u0436\u0434\u044b\u0439 \u043f\u0443\u043d\u043a\u0442 \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0438\u043c\u0435\u0435\u0442 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u043d\u044b\u0435 \u0440\u0435\u0441\u0443\u0440\u0441\u044b \u0438 \u0441\u0432\u044f\u0437\u0430\u043d \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043f\u0443\u043d\u043a\u0442\u0430\u043c\u0438 \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u044f. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c: \u043a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/91a\/ddc\/c34\/91addcc34e7774177a3693afc6e65ab5.svg\" alt=\"$C_iD_j$\" data-tex=\"inline\"\/><\/math> \u0438\u043c\u0435\u0435\u0442 \u0441\u0432\u043e\u044e \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/574\/813\/927\/574813927a79f1be0fda12ac27338325.svg\" alt=\"$c_{ij}$\" data-tex=\"inline\"\/><\/math>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043f\u043e\u0441\u0442\u0430\u0432\u043e\u043a \u0441 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c\u0438 \u0437\u0430\u0442\u0440\u0430\u0442\u0430\u043c\u0438.<\/p>\n<p>  \u0421\u0442\u0440\u043e\u0433\u043e \u0433\u043e\u0432\u043e\u0440\u044f,  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/ce9\/b1d\/281\/ce9b1d2817bcbbbb8f74a1ce2a2a38a5.svg\" alt=\"$\\arg\\min\\sum_{i=1}^S\\sum_{j=1}^Dx_{ij}c_{ij}\\tag{4}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/851\/a5b\/534\/851a5b534e8fbae97c49c57bbe726442.svg\" alt=\"$x_{ij}\\ge0,\\tag{5}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/cfa\/07c\/938\/cfa07c938d394932e5ee483b9da84b90.svg\" alt=\"$\\sum_{j=1}^Dx_{ij}\\le w_{S_i},\\tag{6}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/72a\/149\/6c8\/72a1496c8910a1dae36994851990cfcd.svg\" alt=\"$\\sum_{i=1}^Sx_{ij} \\le w_{D_j}, \\tag{7}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/093\/cea\/474\/093cea47444b4d4887052402825c160f.svg\" alt=\"$\\sum_{i=1}^S\\sum_{j=1}^Dx_{ij} = \\min(\\sum_{i=1}^Sw_{S_i}, \\sum_{j=1}^Dw_{D_j}). \\tag{8}$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u043b\u0438\u0431\u043e \u0432 \u043f\u0443\u043d\u043a\u0442\u0430\u0445 \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0437\u0430\u043a\u043e\u043d\u0447\u0438\u0442\u0441\u044f \u0442\u043e\u0432\u0430\u0440, \u0438\u043b\u0438 \u0441\u043f\u0440\u043e\u0441 \u043d\u0430 \u0442\u043e\u0432\u0430\u0440 \u0438\u0441\u0441\u044f\u043a\u043d\u0435\u0442. \u0415\u0441\u043b\u0438 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/1f2\/2ed\/00c\/1f22ed00cca7a5a2aaddb3ad243804dc.svg\" alt=\"$\\sum_{i=1}^Sw_{S_i} = \\sum_{j=1}^Dw_{D_j}$\" data-tex=\"inline\"\/><\/math>, \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 <b>8<\/b> \u043c\u043e\u0436\u043d\u043e \u043d\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0438 \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/376\/d55\/34f\/376d5534fb85bd769a00032005ac8373.svg\" alt=\"$\\sum_{i=1}^S\\sum_{j=1}^Dx_{ij} = \\sum_{i=1}^Sw_{S_i} = \\sum_{j=1}^Dw_{D_j} = 1.$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u201c\u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u201d \u0438 \u201c\u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435\u201d \u043d\u0430 \u201c\u0437\u0435\u043c\u043b\u044e\u201d, \u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/3d3\/77c\/c6c\/3d377cc6c08b320ecb3660463354e3ae.svg\" alt=\"$\\min\\sum_{i=1}^S\\sum_{j=1}^Dx_{ij}c_{ij}$\" data-tex=\"inline\"\/><\/math> \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u0442 \u043d\u0430\u0441 \u043a \u0437\u0430\u0434\u0430\u0447\u0435 \u0437\u0435\u043c\u043b\u0435\u043a\u043e\u043f\u0430 (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Earth_mover&#39;s_distance\">Earth Mover\u2019s Distance<\/a>, EMD): \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0440\u0430\u0431\u043e\u0442\u0443, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0443\u044e \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0442\u0430\u0441\u043a\u0438\u0432\u0430\u043d\u0438\u044f \u0437\u0435\u043c\u043b\u0438 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043a\u0443\u0447 \u0432 \u0434\u0440\u0443\u0433\u0438\u0435. \u0422\u0435\u043f\u0435\u0440\u044c \u0432\u044b \u0437\u043d\u0430\u0435\u0442\u0435, \u0447\u0442\u043e \u0434\u0435\u043b\u0430\u0442\u044c, \u0435\u0441\u043b\u0438 \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u0440\u044b\u0442\u044c \u044f\u043c\u044b \u0432 \u0437\u0435\u043c\u043b\u0435.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/521\/f83\/3ee\/521f833ee6784a57b18d87be6e4bf165.png\"\/><br \/>  <i>Earth Mover\u2019s Distance<\/i><\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0436\u0435 \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u201c\u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u201d \u0438 \u201c\u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435\u201d \u201c\u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c\u0430\u043c\u0438\u201d, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0441\u0430\u043c\u044b\u0439 \u0440\u0430\u0441\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0435\u043d\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439 \u044d\u043f\u043e\u0445\u0438 \u201c\u0434\u043e \u0433\u043b\u0443\u0431\u043e\u043a\u043e\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f\u201d (<a href=\"https:\/\/www.cs.cmu.edu\/~efros\/courses\/LBMV07\/Papers\/rubner-jcviu-00.pdf\">\u043f\u0440\u0438\u043c\u0435\u0440 \u0441\u0442\u0430\u0442\u044c\u0438<\/a>). \u042d\u0442\u043e\u0442 \u043c\u0435\u0442\u043e\u0434 \u043b\u0443\u0447\u0448\u0435, \u0447\u0435\u043c \u043d\u0430\u0438\u0432\u043d\u044b\u0439 L2, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u043d \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u044f \u043f\u043e \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u043e\u0439 \u0432\u0435\u043b\u0438\u0447\u0438\u043d\u0435, \u043d\u043e \u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u0432 \u0440\u0430\u0441\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u0438.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/eeb\/28e\/f93\/eeb28ef937bf414ba20ac5f9610793bc.png\"\/><br \/>  <i>EMD \u043b\u0443\u0447\u0448\u0435 \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0433\u0438\u0441\u0442\u043e\u0433\u0440\u0430\u043c\u043c, \u0447\u0435\u043c \u0415\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435<\/i><\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u201c\u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435\u201d \u0438 \u201c\u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u0435\u201d \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0447\u0442\u043e \u043c\u044b \u043f\u0440\u0438\u0434\u0435\u043c \u043a <a href=\"http:\/\/jmlr.org\/proceedings\/papers\/v37\/kusnerb15.pdf\">Word Mover\u2019s Distance<\/a>, \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u043c\u0443 \u0441\u043f\u043e\u0441\u043e\u0431\u0443 \u0441\u0440\u0430\u0432\u043d\u0438\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0434\u0432\u0443\u0445 \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f <a href=\"https:\/\/en.wikipedia.org\/wiki\/Word2vec\">word2vec<\/a> \u0434\u043b\u044f \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u0438\u044f \u0432\u0435\u043a\u0442\u043e\u0440\u043d\u044b\u0445 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0441\u043b\u043e\u0432.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/5e3\/cce\/399\/5e3cce399b524b48bda5c1f25ffbacbb.png\"\/><br \/>  <i>Word Mover\u2019s Distance.<\/i><\/p>\n<p>  \u0415\u0441\u043b\u0438 \u043c\u044b \u0440\u0430\u0441\u0441\u043b\u0430\u0431\u0438\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u044f <b>5-8<\/b>, \u0432\u044b\u0431\u0440\u043e\u0441\u0438\u0432 <b>8<\/b>, \u043f\u0440\u0438\u043d\u044f\u0432 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/6ef\/0c0\/1d2\/6ef0c01d2a1ef4a80ac6fadde4270a71.svg\" alt=\"$w_{S_i} = w_{D_i} = 1$\" data-tex=\"inline\"\/><\/math> \u0438 \u043f\u0440\u0435\u0432\u0440\u0430\u0442\u0438\u0432 \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430 <b>6<\/b> \u0438 <b>7<\/b> \u0432 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f, \u0434\u043e\u0431\u0430\u0432\u0438\u0432 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b\u0435 \u0438\u043c \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430, \u0442\u043e \u043f\u043e\u043b\u0443\u0447\u0438\u043c <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BD%D0%B0%D0%B7%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D1%8F%D1%85\">\u0437\u0430\u0434\u0430\u0447\u0443 \u043e \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445<\/a> (Linear Assignment Problem, LAP):  <\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/ce9\/b1d\/281\/ce9b1d2817bcbbbb8f74a1ce2a2a38a5.svg\" alt=\"$\\arg\\min\\sum_{i=1}^S\\sum_{j=1}^Dx_{ij}c_{ij}\\tag{9}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/851\/a5b\/534\/851a5b534e8fbae97c49c57bbe726442.svg\" alt=\"$x_{ij}\\ge0,\\tag{10}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/942\/e3e\/646\/942e3e64662380d0feca3c08c6c7e17b.svg\" alt=\"$\\sum_{j=1}^Dx_{ij} = 1,\\tag{11}$\" data-tex=\"display\"\/><\/math><\/p>\n<p><math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/11d\/0d7\/bdf\/11d0d7bdf27b2bc5326d9b61daca85f4.svg\" alt=\"$\\sum_{i=1}^Sx_{ij} = 1.\\tag{12}$\" data-tex=\"display\"\/><\/math><\/p>\n<p>  \u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0442\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438, \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/fc5\/d5e\/0be\/fc5d5e0be81a7c382c18e7915a51c661.svg\" alt=\"$x_{ij}\\in\\{0,1\\}$\" data-tex=\"inline\"\/><\/math> \u2014 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0434\u0432\u043e\u0438\u0447\u043d\u043e. \u0418\u043d\u044b\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0438\u043b\u0438 \u0432\u0435\u0441\u044c \u0442\u043e\u0432\u0430\u0440 \u0438\u0437 \u043f\u0443\u043d\u043a\u0442\u043e\u0432 \u043e\u0442\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442 \u0432 \u043f\u0443\u043d\u043a\u0442\u044b \u043f\u043e\u0442\u0440\u0435\u0431\u043b\u0435\u043d\u0438\u044f, \u0438\u043b\u0438 \u043d\u0438\u0447\u0442\u043e \u043d\u0438\u043a\u0443\u0434\u0430 \u043d\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442.<\/p>\n<h2><font color=\"#c75733\">t-SNE LAP<\/font><\/h2>\n<p>  \u041a\u0430\u043a \u043c\u044b \u043f\u043e\u043d\u044f\u043b\u0438 \u0438\u0437 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0440\u0430\u0437\u0434\u0435\u043b\u0430, t-SNE, \u043a\u0430\u043a \u0438 \u0432\u0441\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0443\u043a\u043b\u0430\u0434\u043a\u0438 \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438, \u0432\u044b\u0434\u0430\u0435\u0442 \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435 \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443 \u0440\u0430\u0441\u0441\u0435\u044f\u043d\u0438\u044f. \u0425\u043e\u0442\u044f \u044d\u0442\u043e \u0438\u0434\u0435\u0430\u043b\u044c\u043d\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f \u043d\u0430\u0431\u043e\u0440\u043e\u0432 \u0434\u0430\u043d\u043d\u044b\u0445, \u0438\u043d\u043e\u0433\u0434\u0430 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043f\u043e\u0442\u0440\u0435\u0431\u043d\u043e\u0441\u0442\u044c \u0443\u043b\u043e\u0436\u0438\u0442\u044c \u0438\u0441\u0445\u043e\u0434\u043d\u0443\u044e \u0434\u0438\u0430\u0433\u0440\u0430\u043c\u043c\u0443 \u043d\u0430 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0439 \u0441\u0435\u0442\u043a\u0435. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a\u0430\u044f \u0443\u043a\u043b\u0430\u0434\u043a\u0430 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u0430 source{d}\u2026 \u0441\u043a\u043e\u0440\u043e \u0443\u0437\u043d\u0430\u0435\u043c, \u0437\u0430\u0447\u0435\u043c.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/d91\/360\/778\/d9136077845648ddaa665da6c69aeebe.png\"\/><br \/>  <i>\u041f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0430\u044f \u0441\u0435\u0442\u043a\u0430<\/i><\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f t-SNE \u0438\u0437\u043e\u0431\u0440\u0430\u0437\u0438\u043c \u0432\u043c\u0435\u0441\u0442\u043e \u0442\u043e\u0447\u0435\u043a \u0446\u0438\u0444\u0440\u044b MNIST; \u0432\u043e\u0442 \u043a\u0430\u043a \u044d\u0442\u043e \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/b6d\/692\/70a\/b6d69270a5594cf49fd28290c34bac6a.png\"\/><br \/>  <i>\u0426\u0438\u0444\u0440\u044b MNIST \u043f\u043e\u0441\u043b\u0435 t-SNE<\/i><\/p>\n<p>  \u041d\u0435 \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u043f\u043e\u043d\u044f\u0442\u043d\u043e. \u0412\u043e\u0442 \u0437\u0434\u0435\u0441\u044c \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 LAP: \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438 \u043a\u0430\u043a \u043f\u0430\u0440\u043d\u043e\u0435 \u0435\u0432\u043a\u043b\u0438\u0434\u043e\u0432\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u043e\u0431\u0440\u0430\u0437\u0446\u0430\u043c\u0438 t-SNE \u0438 \u0443\u0437\u043b\u0430\u043c\u0438 \u0441\u0435\u0442\u043a\u0438, \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c \u043f\u043b\u043e\u0449\u0430\u0434\u044c \u0441\u0435\u0442\u043a\u0438 \u0440\u0430\u0432\u043d\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/b6a\/38c\/424\/b6a38c4246945216cac3711bfa15e9a2.svg\" alt=\"$||S|| = ||D||$\" data-tex=\"inline\"\/><\/math>, \u0438 \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0440\u0435\u0448\u0438\u043c \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443. \u041d\u043e \u043a\u0430\u043a? \u041c\u044b \u043f\u043e\u043a\u0430 \u043d\u0435 \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u0430\u043b\u0438 \u043d\u0438 \u043e\u0431 \u043e\u0434\u043d\u043e\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435.<\/p>\n<h3>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0436\u043e\u043d\u043a\u0435\u0440\u0430-\u0412\u043e\u043b\u0433\u0435\u043d\u0430\u043d\u0442\u0430<\/h3>\n<p>  \u041e\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043e\u0433\u0440\u043e\u043c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043e\u0431\u0449\u0435\u0433\u043e \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A1%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81-%D0%BC%D0%B5%D1%82%D0%BE%D0%B4\">\u0441\u0438\u043c\u043f\u043b\u0435\u043a\u0441-\u043c\u0435\u0442\u043e\u0434\u0430<\/a> \u0438 \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044f \u043a\u0440\u0430\u0439\u043d\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u043c\u0438 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430\u043c\u0438. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0435 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u043f\u043e\u0434 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443, \u043e\u0431\u044b\u0447\u043d\u043e \u0441\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0445\u043e\u0442\u044f \u0438 \u043e\u0431\u043b\u0430\u0434\u0430\u044e\u0442 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u043c\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438.<\/p>\n<p>  <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%92%D0%B5%D0%BD%D0%B3%D0%B5%D1%80%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC\">\u0412\u0435\u043d\u0433\u0435\u0440\u0441\u043a\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c<\/a> \u2014 \u043e\u0434\u0438\u043d \u0438\u0437 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043c\u0435\u0442\u043e\u0434\u043e\u0432, \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0439 \u0432 1950-\u0445. \u0415\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u2014 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/post_images\/70c\/9de\/548\/70c9de548f12a27cb4e9c3b759df2c3a.svg\" alt=\"$O(n^3)$\" data-tex=\"inline\"\/><\/math>. \u041e\u043d \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f \u0438 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438, \u0438 \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u0435\u043d \u0432\u043e \u043c\u043d\u043e\u0433\u0438\u0445 \u043f\u0440\u043e\u0435\u043a\u0442\u0430\u0445. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u0435\u0434\u0430\u0432\u043d\u043e \u043e\u043d \u0441\u0442\u0430\u043b \u0447\u0430\u0441\u0442\u044c\u044e <a href=\"https:\/\/docs.scipy.org\/doc\/scipy-0.18.1\/reference\/generated\/scipy.optimize.linear_sum_assignment.html\">s\u0441ipy<\/a>. \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u043e\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0435 \u0431\u044b\u0441\u0442\u0440\u043e \u043d\u0430 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043e\u0431\u044a\u0435\u043c\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 scipy \u2014 <b>\u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e<\/b> \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u044b\u0439. \u042f \u043f\u0440\u043e\u0436\u0434\u0430\u043b \u0447\u0430\u0441, \u0447\u0442\u043e\u0431\u044b \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c 2500 \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 MNIST, \u0430 Python \u0432\u0441\u0435 \u0435\u0449\u0435 \u043f\u0435\u0440\u0435\u0432\u0430\u0440\u0438\u0432\u0430\u043b \u0436\u0435\u0440\u0442\u0432\u0443.<\/p>\n<p>  \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0436\u043e\u043d\u043a\u0435\u0440\u0430-\u0412\u043e\u043b\u0433\u0435\u043d\u0430\u043d\u0442\u0430 (<a href=\"https:\/\/link.springer.com\/article\/10.1007\/BF02278710\">Jonker-Volgenant<\/a>, JV) \u2014 \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434, \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0439 \u0432 1987. \u0412 \u0435\u0433\u043e \u043e\u0441\u043d\u043e\u0432\u0435 \u0442\u0430\u043a\u0436\u0435 \u043f\u0440\u043e\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0435\u0439 \u0430\u0443\u0433\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u043e\u0439 \u0446\u0435\u043f\u0438, \u0430 \u0435\u0433\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0442\u0430\u043a\u0436\u0435 \u043a\u0443\u0431\u0438\u0447\u0435\u0441\u043a\u0430\u044f, \u043d\u043e \u0432 \u043d\u0435\u043c \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0445\u0438\u0442\u0440\u044b\u0445 \u043f\u0440\u0438\u0435\u043c\u043e\u0432, \u0440\u0430\u0437\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0449\u0430\u0435\u0442\u0441\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u043d\u0430\u0433\u0440\u0443\u0437\u043a\u0430. \u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043c\u043d\u043e\u0433\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0443\u043a\u043b\u0430\u0434\u043a\u0438 \u0433\u0440\u0430\u0444\u043e\u0432, \u0432\u043a\u043b\u044e\u0447\u0430\u044f JV, \u0431\u044b\u043b\u0430 \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u043e \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0430 \u0432 \u0441\u0442\u0430\u0442\u044c\u0435 2000 \u0433\u043e\u0434\u0430 <a href=\"http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X99001729\">Discrete Applied Mathematics<\/a>. \u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435 \u0431\u044b\u043b\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c:<\/p>\n<blockquote><p>\u201c\u0423 JV \u0445\u043e\u0440\u043e\u0448\u0430\u044f \u0438 \u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u0430\u044f \u0441\u0440\u0435\u0434\u043d\u044f\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043d\u0430 \u0432\u0441\u0435\u0445 \u043a\u043b\u0430\u0441\u0441\u0430\u0445 (\u0437\u0430\u0434\u0430\u0447 \u2014 \u043f\u0440\u0438\u043c. \u0430\u0432\u0442\u043e\u0440\u0430), \u0438 \u044d\u0442\u043e \u043b\u0443\u0447\u0448\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043a\u0430\u043a \u0434\u043b\u044f \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u044b\u0445, \u0442\u0430\u043a \u0438 \u0434\u043b\u044f \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0437\u0430\u0434\u0430\u0447\u201d.<\/p><\/blockquote>\n<p>  \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0443 JV \u0435\u0441\u0442\u044c \u0438 \u043d\u0435\u0434\u043e\u0441\u0442\u0430\u0442\u043e\u043a. \u041e\u043d \u043e\u0447\u0435\u043d\u044c \u0442\u043e\u043b\u0435\u0440\u0430\u043d\u0442\u0435\u043d \u043a \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u044f\u043c \u043c\u0435\u0436\u0434\u0443 \u043f\u0430\u0440\u0430\u043c\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043c\u0430\u0442\u0440\u0438\u0446\u0435 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0435\u0439. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u043c\u044b \u0438\u0449\u0435\u043c \u043a\u0440\u0430\u0442\u0447\u0430\u0439\u0448\u0438\u0439 \u043f\u0443\u0442\u044c \u0432 \u0433\u0440\u0430\u0444\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0438 \u043d\u0430 \u044d\u0442\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u043f\u043e\u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0434\u0432\u0435 \u043e\u0447\u0435\u043d\u044c \u0431\u043b\u0438\u0437\u043a\u0438\u0435 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0438, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0438\u0441\u043a\u0443\u0435\u0442 \u0443\u0439\u0442\u0438 \u0432 \u0431\u0435\u0441\u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439 \u0446\u0438\u043a\u043b. \u0415\u0441\u043b\u0438 \u043c\u044b \u0432\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0414\u0435\u0439\u043a\u0441\u0442\u0440\u044b, \u0442\u043e \u043e\u0431\u043d\u0430\u0440\u0443\u0436\u0438\u043c, \u0447\u0442\u043e \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0438\u0436\u0435\u043d\u0438\u0438 \u043f\u0440\u0435\u0434\u0435\u043b\u0430 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0441 \u043f\u043b\u0430\u0432\u0430\u044e\u0449\u0435\u0439 \u0442\u043e\u0447\u043a\u043e\u0439, \u043c\u043e\u0433\u0443\u0442 \u043f\u0440\u043e\u0438\u0437\u043e\u0439\u0442\u0438 \u0443\u0436\u0430\u0441\u043d\u044b\u0435 \u0432\u0435\u0449\u0438. \u041e\u0431\u044b\u0447\u043d\u044b\u0439 \u0432\u044b\u0445\u043e\u0434 \u0438\u0437 \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u0438 \u2014 \u0443\u043c\u043d\u043e\u0436\u0438\u0442\u044c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u0442\u043e\u0438\u043c\u043e\u0441\u0442\u0435\u0439 \u043d\u0430 \u043d\u0435\u043a\u043e\u0435 \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u0447\u0438\u0441\u043b\u043e.<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/d4b\/0f0\/377\/d4b0f037789748a0953fca782b12c4b5.jpg\"\/><\/p>\n<p>  \u0418 \u0432\u0441\u0435-\u0442\u0430\u043a\u0438 \u0441\u0430\u043c\u043e\u0435 \u0437\u0430\u043c\u0430\u043d\u0447\u0438\u0432\u043e\u0435 \u0432 JV \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0433\u043e \u043b\u0435\u043d\u0438\u0432\u043e\u0433\u043e \u0438\u043d\u0436\u0435\u043d\u0435\u0440\u0430, \u043a\u0430\u043a \u044f, \u2014 \u044d\u0442\u043e \u043f\u0430\u043a\u0435\u0442 \u043d\u0430 Python 2, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0441\u043e\u0431\u043e\u0439 \u043e\u0431\u0435\u0440\u0442\u043a\u0443 <a href=\"http:\/\/www.magiclogic.com\/assignment.html\">\u0434\u0440\u0435\u0432\u043d\u0435\u0439<\/a> \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043d\u0430 C: <a href=\"https:\/\/github.com\/hrldcpr\/pyLAPJV\">pyLAPJV<\/a>. \u042d\u0442\u043e\u0442 \u043a\u043e\u0434 \u043d\u0430 C \u0431\u044b\u043b \u043d\u0430\u043f\u0438\u0441\u0430\u043d <a href=\"https:\/\/www.linkedin.com\/in\/roy-jonker-9a183310\/\">\u0420\u043e\u0435\u043c \u0414\u0436\u043e\u043d\u043a\u0435\u0440\u043e\u043c<\/a> \u0432 1996 \u0433\u043e\u0434\u0430 \u0434\u043b\u044f \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0438 MagicLogic Optimization, \u043f\u0440\u0435\u0437\u0438\u0434\u0435\u043d\u0442\u043e\u043c \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043e\u043d \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e pyLAPJV \u0431\u043e\u043b\u044c\u0448\u0435 \u043d\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442\u0441\u044f, \u0432 \u043d\u0435\u0439 \u0435\u0441\u0442\u044c \u043d\u0435\u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u0441 \u0432\u044b\u0432\u043e\u0434\u043e\u043c \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u044f \u0438\u0441\u043f\u0440\u0430\u0432\u0438\u043b \u0432 <a href=\"https:\/\/github.com\/hrldcpr\/pyLAPJV\/pull\/2\">\u043f\u0443\u043b\u043b-\u0440\u0435\u043a\u0432\u0435\u0441\u0442\u0435 #2<\/a>. \u041a\u043e\u0434 \u043d\u0430 C \u043d\u0430\u0434\u0435\u0436\u0435\u043d, \u043d\u043e \u0432 \u043d\u0435\u043c \u043d\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u0441\u0442\u044c \u0438\u043b\u0438 SIMD-\u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u0438. \u041c\u044b, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u043c, \u0447\u0442\u043e JV \u043f\u043e \u0441\u0432\u043e\u0435\u0439 \u043f\u0440\u0438\u0440\u043e\u0434\u0435 \u043e\u0434\u043d\u043e\u043f\u043e\u0442\u043e\u0447\u0435\u043d, \u0438 \u0435\u0433\u043e \u043d\u0435 \u0442\u0430\u043a \u043f\u0440\u043e\u0441\u0442\u043e \u0440\u0430\u0441\u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0442\u044c, \u0442\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u043c\u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u0435\u0433\u043e \u043f\u043e\u0447\u0442\u0438 \u0432\u0434\u0432\u043e\u0435, \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0432 \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u0437\u0430\u0442\u0440\u0430\u0442\u043d\u044b\u0439 \u044d\u0442\u0430\u043f \u2014 \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u0438\u0435 \u0430\u0443\u0433\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u043e\u0439 \u0446\u0435\u043f\u0438 \u2014 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e <a href=\"https:\/\/ru.wikipedia.org\/wiki\/AVX\">AVX2<\/a>. \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0441\u044f \u043f\u0430\u043a\u0435\u0442 <a href=\"https:\/\/github.com\/src-d\/lapjv\">src-d\/lapjv<\/a> \u043d\u0430 Python 3, \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0439 \u043f\u043e\u0434 \u043b\u0438\u0446\u0435\u043d\u0437\u0438\u0435\u0439 MIT.<\/p>\n<p>  \u0421\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u0438\u0435 \u0430\u0443\u0433\u043c\u0435\u043d\u0442\u0430\u043b\u044c\u043d\u043e\u0439 \u0446\u0435\u043f\u0438 \u0432 \u0441\u0432\u043e\u0435\u0439 \u043e\u0441\u043d\u043e\u0432\u0435 \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0438 \u0432\u0442\u043e\u0440\u043e\u0433\u043e \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435. \u0417\u0432\u0443\u0447\u0438\u0442 \u043f\u0440\u043e\u0441\u0442\u043e, \u043a\u0430\u043a \u0438 \u0435\u0441\u0442\u044c \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u043d\u0435\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043a\u043e\u0434 \u043d\u0430 C \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 20 \u0441\u0442\u0440\u043e\u043a. \u0412\u0435\u0440\u0441\u0438\u044f \u0432 AVX \u0432 4 \u0440\u0430\u0437\u0430 \u0431\u043e\u043b\u044c\u0448\u0435: \u043c\u044b \u043f\u043e\u0441\u044b\u043b\u0430\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043d\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 SIMD, \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c <a href=\"https:\/\/software.intel.com\/en-us\/node\/524074\">blending<\/a>, \u0430 \u0437\u0430\u0442\u0435\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0440\u0443\u0433\u0438\u0435 \u0437\u0430\u043a\u043b\u0438\u043d\u0430\u043d\u0438\u044f \u0447\u0435\u0440\u043d\u043e\u0439 \u043c\u0430\u0433\u0438\u0438 SIMD, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u044f \u043d\u0430\u0443\u0447\u0438\u043b\u0441\u044f, \u043f\u043e\u043a\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u043b \u043d\u0430\u0434 <a href=\"https:\/\/github.com\/Samsung\/veles.sound_feature_extraction\/blob\/master\/TRANSFORMS.md\">libSoundFeatureExtraction<\/a> \u0432 Samsung.<\/p>\n<pre><code class=\"cpp\">template &lt;typename idx, typename cost&gt; __attribute__((always_inline)) inline std::tuple&lt;cost, cost, idx, idx&gt; find_umins(     idx dim, idx i, const cost *assigncost, const cost *v) {   cost umin = assigncost[i * dim] - v[0];   idx j1 = 0;   idx j2 = -1;   cost usubmin = std::numeric_limits&lt;cost&gt;::max();   for (idx j = 1; j &lt; dim; j++) {     cost h = assigncost[i * dim + j] - v[j];     if (h &lt; usubmin) {       if (h &gt;= umin) {         usubmin = h;         j2 = j;       } else {         usubmin = umin;         umin = h;         j2 = j1;         j1 = j;       }     }   }   return std::make_tuple(umin, usubmin, j1, j2); }<\/code><\/pre>\n<p>  <i>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0434\u0432\u0443\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, C++<\/i><\/p>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041f\u043e\u043a\u0430\u0437\u0430\u0442\u044c \u043a\u043e\u0434<\/b><\/p>\n<div class=\"spoiler_text\">\n<pre><code class=\"cpp\">template &lt;typename idx&gt; __attribute__((always_inline)) inline std::tuple&lt;float, float, idx, idx&gt; find_umins(     idx dim, idx i, const float *assigncost, const float *v) {   __m256i idxvec = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);   __m256i j1vec = _mm256_set1_epi32(-1), j2vec = _mm256_set1_epi32(-1);   __m256 uminvec = _mm256_set1_ps(std::numeric_limits&lt;float&gt;::max()),          usubminvec = _mm256_set1_ps(std::numeric_limits&lt;float&gt;::max());   for (idx j = 0; j &lt; dim - 7; j += 8) {     __m256 acvec = _mm256_loadu_ps(assigncost + i * dim + j);     __m256 vvec = _mm256_loadu_ps(v + j);     __m256 h = _mm256_sub_ps(acvec, vvec);     __m256 cmp = _mm256_cmp_ps(h, uminvec, _CMP_LE_OQ);     usubminvec = _mm256_blendv_ps(usubminvec, uminvec, cmp);     j2vec = _mm256_blendv_epi8(         j2vec, j1vec, reinterpret_cast&lt;__m256i&gt;(cmp));     uminvec = _mm256_blendv_ps(uminvec, h, cmp);     j1vec = _mm256_blendv_epi8(         j1vec, idxvec, reinterpret_cast&lt;__m256i&gt;(cmp));     cmp = _mm256_andnot_ps(cmp, _mm256_cmp_ps(h, usubminvec, _CMP_LT_OQ));     usubminvec = _mm256_blendv_ps(usubminvec, h, cmp);     j2vec = _mm256_blendv_epi8(         j2vec, idxvec, reinterpret_cast&lt;__m256i&gt;(cmp));     idxvec = _mm256_add_epi32(idxvec, _mm256_set1_epi32(8));   }   float uminmem[8], usubminmem[8];   int32_t j1mem[8], j2mem[8];   _mm256_storeu_ps(uminmem, uminvec);   _mm256_storeu_ps(usubminmem, usubminvec);   _mm256_storeu_si256(reinterpret_cast&lt;__m256i*&gt;(j1mem), j1vec);   _mm256_storeu_si256(reinterpret_cast&lt;__m256i*&gt;(j2mem), j2vec);    idx j1 = -1, j2 = -1;   float umin = std::numeric_limits&lt;float&gt;::max(),         usubmin = std::numeric_limits&lt;float&gt;::max();   for (int vi = 0; vi &lt; 8; vi++) {     float h = uminmem[vi];     if (h &lt; usubmin) {       idx jnew = j1mem[vi];       if (h &gt;= umin) {         usubmin = h;         j2 = jnew;       } else {         usubmin = umin;         umin = h;         j2 = j1;         j1 = jnew;       }     }   }   for (int vi = 0; vi &lt; 8; vi++) {     float h = usubminmem[vi];     if (h &lt; usubmin) {       usubmin = h;       j2 = j2mem[vi];     }   }   for (idx j = dim & 0xFFFFFFF8u; j &lt; dim; j++) {     float h = assigncost[i * dim + j] - v[j];     if (h &lt; usubmin) {       if (h &gt;= umin) {         usubmin = h;         j2 = j;       } else {         usubmin = umin;         umin = h;         j2 = j1;         j1 = j;       }     }   }   return std::make_tuple(umin, usubmin, j1, j2); }<\/code><\/pre>\n<p>  <\/div>\n<\/div>\n<p>  <i>\u041d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0435 \u0434\u0432\u0443\u0445 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439, \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043a\u043e\u0434 \u0441 \u0438\u043d\u0441\u0442\u0440\u0443\u043a\u0446\u0438\u044f\u043c\u0438 AVX2<\/i><\/p>\n<p>  \u041d\u0430 \u043c\u043e\u0435\u043c \u043d\u043e\u0443\u0442\u0431\u0443\u043a\u0435 lapjv \u0443\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u0442 2500 \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432 MNIST \u0437\u0430 5 \u0441\u0435\u043a\u0443\u043d\u0434, \u0438 \u0432\u043e\u0442 \u043e\u043d \u2014 \u0434\u0440\u0430\u0433\u043e\u0446\u0435\u043d\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/633\/149\/dba\/633149dba5344845b2e780998f1a8eba.png\"\/><br \/>  <i>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445 \u0434\u043b\u044f MNIST \u043f\u043e\u0441\u043b\u0435 t-SNE<\/i><\/p>\n<h3>Notebook<\/h3>\n<p>  \u0414\u043b\u044f \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0438 \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0441\u0442\u0430 \u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b <a href=\"http:\/\/jupyter.org\/\">Jupiter Notebook<\/a> (\u0438\u0441\u0445\u043e\u0434\u043d\u0438\u043a <a href=\"https:\/\/gist.github.com\/vmarkovtsev\/74e3a973b19113047fdb6b252d741b42\">\u0437\u0434\u0435\u0441\u044c<\/a>).<\/p>\n<h2><font color=\"#c75733\">\u0417\u0430\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435<\/font><\/h2>\n<p>  \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0443\u043a\u043b\u0430\u0434\u043a\u0438 \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432, \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 t-SNE, \u043d\u0430 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u0443\u044e \u0441\u0435\u0442\u043a\u0443. \u041e\u043d \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f (LAP) \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0414\u0436\u043e\u043d\u043a\u0435\u0440\u0430-\u0412\u043e\u043b\u0433\u0435\u043d\u0430\u043d\u0442\u0430, \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u0432 <a href=\"https:\/\/github.com\/src-d\/lapjv\">src-d\/lapjv<\/a>. \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043c\u0430\u0441\u0448\u0442\u0430\u0431\u0438\u0440\u043e\u0432\u0430\u043d \u043d\u0430 10 000 \u043e\u0431\u0440\u0430\u0437\u0446\u043e\u0432.  <\/p>\n<blockquote>\n<div class=\"spoiler\"><b class=\"spoiler_title\">\u041e, \u0430 \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0435 \u043a \u043d\u0430\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c? \ud83d\ude42<\/b><\/p>\n<div class=\"spoiler_text\"><a href=\"http:\/\/wunderfund.io\"><b>wunderfund.io<\/b><\/a> \u2014 \u043c\u043e\u043b\u043e\u0434\u043e\u0439 \u0444\u043e\u043d\u0434, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442\u0441\u044f <a href=\"https:\/\/en.wikipedia.org\/wiki\/High-frequency_trading\">\u0432\u044b\u0441\u043e\u043a\u043e\u0447\u0430\u0441\u0442\u043e\u0442\u043d\u043e\u0439 \u0430\u043b\u0433\u043e\u0442\u043e\u0440\u0433\u043e\u0432\u043b\u0435\u0439<\/a>. \u0412\u044b\u0441\u043e\u043a\u043e\u0447\u0430\u0441\u0442\u043e\u0442\u043d\u0430\u044f \u0442\u043e\u0440\u0433\u043e\u0432\u043b\u044f \u2014 \u044d\u0442\u043e \u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u043e\u0435 \u0441\u043e\u0440\u0435\u0432\u043d\u043e\u0432\u0430\u043d\u0438\u0435 \u043b\u0443\u0447\u0448\u0438\u0445 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u043e\u0432 \u0438 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u043e\u0432 \u0432\u0441\u0435\u0433\u043e \u043c\u0438\u0440\u0430. \u041f\u0440\u0438\u0441\u043e\u0435\u0434\u0438\u043d\u0438\u0432\u0448\u0438\u0441\u044c \u043a \u043d\u0430\u043c, \u0432\u044b \u0441\u0442\u0430\u043d\u0435\u0442\u0435 \u0447\u0430\u0441\u0442\u044c\u044e \u044d\u0442\u043e\u0439 \u0443\u0432\u043b\u0435\u043a\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u0441\u0445\u0432\u0430\u0442\u043a\u0438.<\/p>\n<p>  \u041c\u044b \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0435\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u0438 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u043e \u0430\u043d\u0430\u043b\u0438\u0437\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 low latency \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u043a\u0435 \u0434\u043b\u044f \u0443\u0432\u043b\u0435\u0447\u0435\u043d\u043d\u044b\u0445 \u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u0435\u0439 \u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0441\u0442\u043e\u0432. \u0413\u0438\u0431\u043a\u0438\u0439 \u0433\u0440\u0430\u0444\u0438\u043a \u0438 \u043d\u0438\u043a\u0430\u043a\u043e\u0439 \u0431\u044e\u0440\u043e\u043a\u0440\u0430\u0442\u0438\u0438, \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0431\u044b\u0441\u0442\u0440\u043e \u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0442\u0441\u044f \u0438 \u0432\u043e\u043f\u043b\u043e\u0449\u0430\u044e\u0442\u0441\u044f \u0432 \u0436\u0438\u0437\u043d\u044c.<\/p>\n<p>  \u041f\u0440\u0438\u0441\u043e\u0435\u0434\u0438\u043d\u044f\u0439\u0442\u0435\u0441\u044c \u043a \u043d\u0430\u0448\u0435\u0439 \u043a\u043e\u043c\u0430\u043d\u0434\u0435: <a href=\"http:\/\/wunderfund.io\">wunderfund.io<\/a><\/div>\n<\/div>\n<\/blockquote>\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:\/\/habrahabr.ru\/post\/326750\/\"> https:\/\/habrahabr.ru\/post\/326750\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u0414\u043e:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/14b\/047\/01f\/14b04701f5234739baf7c70b58f70921.png\"\/><\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435:<\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/files\/0d8\/21e\/8bc\/0d821e8bc2fe47c6897a7c3fa1b44c8a.png\"\/><\/p>\n<p>  \u0417\u0430\u0438\u043d\u0442\u0440\u0438\u0433\u043e\u0432\u0430\u043d\u044b? \u041d\u043e \u043e\u0431\u043e \u0432\u0441\u0435\u043c \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443.<\/p>\n<h2><font color=\"#c75733\">t-SNE<\/font><\/h2>\n<p>  <a href=\"https:\/\/lvdmaaten.github.io\/tsne\/\">t-SNE<\/a> \u2014 \u044d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u043d\u0438\u0436\u0430\u0442\u044c \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c \u0432\u0430\u0448\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0447\u0442\u043e\u0431\u044b \u0438\u0445 \u0431\u044b\u043b\u043e \u043f\u0440\u043e\u0449\u0435 \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c. \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u0435\u0442 \u0441\u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0441\u043e\u0442\u043d\u0438 \u0438\u0437\u043c\u0435\u0440\u0435\u043d\u0438\u0439 \u043a \u0432\u0441\u0435\u0433\u043e \u0434\u0432\u0443\u043c, \u0441\u043e\u0445\u0440\u0430\u043d\u044f\u044f \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u0432\u0430\u0436\u043d\u044b\u0435 \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0434\u0430\u043d\u043d\u044b\u043c\u0438: \u0447\u0435\u043c \u0431\u043b\u0438\u0436\u0435 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0440\u0430\u0441\u043f\u043e\u043b\u0430\u0433\u0430\u044e\u0442\u0441\u044f \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435, \u0442\u0435\u043c \u043c\u0435\u043d\u044c\u0448\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u044d\u0442\u0438\u043c\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u0430\u043c\u0438 \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 \u0441\u043e\u043a\u0440\u0430\u0449\u0435\u043d\u043d\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438. t-SNE \u043d\u0435\u043f\u043b\u043e\u0445\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0430 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u0438\u0445 \u0438 \u0441\u0440\u0435\u0434\u043d\u0438\u0445 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043d\u0430\u0431\u043e\u0440\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u043e\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043d\u0430\u0441\u0442\u0440\u043e\u0435\u043a \u0433\u0438\u043f\u0435\u0440\u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u043e\u0432. \u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0435\u0441\u043b\u0438 \u0432\u0437\u044f\u0442\u044c 100 000 \u0442\u043e\u0447\u0435\u043a \u0438 \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u0438\u0445 \u0447\u0435\u0440\u0435\u0437 \u044d\u0442\u0443 \u0432\u043e\u043b\u0448\u0435\u0431\u043d\u044b\u0439 \u0447\u0435\u0440\u043d\u044b\u0439 \u044f\u0449\u0438\u043a, \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043a\u0440\u0430\u0441\u0438\u0432\u044b\u0439 \u0433\u0440\u0430\u0444\u0438\u043a \u0440\u0430\u0441\u0441\u0435\u044f\u043d\u0438\u044f.  <\/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-285220","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/285220","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=285220"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/285220\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=285220"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=285220"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=285220"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}