лишние данные

Любопытный пример того, как ненужные данные помогают решить задачу:

"Есть стандартная задача, когда автомобиль из пункта А в пункт Б едет со скоростью 60км/ч, а затем не останавливаясь разворачивается и обратно в пункт А едет со скоростью 40км/ч. Вопрос какая средняя скорость автомобиля на всем пути? Ответ очевидно 48км/ч. 95% школьников прекрасно знают, что S=vt, но не могут решить эту задачу с первого раза. При этом если сказать что расстояние между А и Б равно 120 км, то 95% школьников с легкостью решат эту задачу."

(из фейсбука)

компьютерные новости

Несколько накопившихся ссылок из мира компьютерных наук. Будет интересно программистам и сочувствующим, наверное.

1. В области машинного обучения есть тема интересная "враждебных примеров". Это когда вы, предположим, натренировали нейронную сеть так, что она почти без ошибок называет, какое животное на картинке; но оказывается, что можно взять, скажем, фотографию щенка, которую она распознает, и изменить совсем немного, так, что на ней все еще тот же щенок, ни один человек не спутает ни с чем другим - но нейронная сеть теперь уверена, что это бегемот. В каком-то смысле это демонстрирует уязвимость лучших на сегодня алгоритмов, хотя об этом тоже есть разные мнения (например, можно сказать, что зрительные иллюзии - похожее явление у людей; но там все же другое - это отдельный класс картинок, а не так, что любую картинку можно исказить совсем немного).

https://arxiv.org/abs/1710.08864 в этой недавней статье показывают, что можно находить враждебные примеры, в которых меняется всего один пиксель (в картинке 32x32), и нейронная сеть меняет свою классификацию.

http://www.labsix.org/physical-objects-that-fool-neural-nets/ тут строят враждебные примеры, которые остаются враждебными даже при съемке с разных ракурсов. Делают игрушечную черепашку, которую гуглевский алгоритм распознает как ружье, как ее ни верти и не двигай.

2. 15 Years of Chess Engine Development. Интересный пост на реддите, автор которого запустил четыре разные версии шахматных программ за последние 15 лет - на одном и том же компьютере (ноутбуке 2006-го года, замедленном примерно до скоростей 2002-го года). Результат, для меня по крайней мере, очень анти-интуитивный - прогресс в качестве игры шахматных программ за эти 15 лет был гигантский, и лучшая из них победила Deep Fritz 2002 года (в то время сыгравший вничью с чемпионом мира Крамником) со счетом 99 побед и одна ничья из 100 партий. То есть не только огромный рывок в скорости самих компьютеров с 2002 года обеспечивает неоспоримую победу машин над людьми в шахматах, но и сами программы, даже если бы скорость оставалась такой же, тоже ее обеспечивают. У меня нет хорошего понимания, откуда программы последних лет "выжимают" такое чудовищное алгоритмическое преимущество.

3. Скотт Ааронсон дает ссылку на новую книгу Ави Видгерсона (очень известного ученого в области CS) Mathematics and Computation, выложенную на его сайте. Это панорамный обзор всей области теории сложности (computational complexity), включая сюда и знаменитые нерешенные задачи типа P/NP, и квантовые вычисления, и основы машинного обучения, и многое еще. Без доказательств - это обзор, а не учебник - и написано вроде бы ясным языком и с интересными объяснениями. Я до сих пор только мельком успел посмотреть, но обязательно хочу прочитать.