Эта статья является моим вольным пересказом работы Learnability can be undecidable, Shai Ben-David, et al.
Недавно на Хабре вышла статья Машинное обучение столкнулось с нерешенной математической проблемой, которая является переводом одноименного обзора в Nature News статьи Шай Бен-Давида. Однако, из-за особенностей тематики и краткости оригинального обзора мне осталось совершенно непонятно, что же было в статье. Зная Шай Бен-Давида, как автора прекрасной книги "Understanding Machine Learning: From Theory to Algorithms", я заинтересовался этой темой, ознакомился с этой работой и постарался тут изложить основные моменты.
Сразу скажу, что статья довольно сложная и, возможно, я упустил некоторые важные моменты, но мой обзор будет более полным, чем тот, который уже есть на Хабре.
