Трудновыявляемые ошибки в алгоритмах

[mihaild]

Anton_Peplov в сообщении #1647106 писал(а):

Похоже, мы понимаем под прослеживаемостью разные вещи

Ghost_of_past сказал бы, что Вы говорите об эпистемологической прослеживаемости, а epros - о гносеологической (или наоборот, я не помню которая про что). В смысле Вы говорите, что магии не бывает, у всех сбоев есть причина, а epros - что на практике это слабо отличимо от того, что магия бывает.

Anton_Peplov в сообщении #1647097 писал(а):

Вот только встречается ли такое в реальной жизни?

Да. Я видел довольно много случаев, после нескольких дней безуспешной отладки принимается решение подпереть костылем (у нас не должно быть вызовов функции с вот такими значениями аргументов, а они происходят; ну давайте поменяем контракт функии, и скажем, что она может и такое принимать).

[Ghost_of_past]

(Оффтоп)

mihaild в сообщении #1647109 писал(а):

В смысле Вы говорите, что магии не бывает, у всех сбоев есть причина, а epros - что на практике это слабо отличимо от того, что магия бывает.

Первая - онтологическая прослеживаемость, вторая - эпистемологическая/гносеологическая. Тут все просто: онтологическое - как оно устроено в объективной реальности, гносеологическое/эпистемологическое - как доступно в нашем познании объективной реальности.

А вообще тема - интересное ответвление от моей рекомендации книг по философии математики и неопозитивизма...

[tolstopuz]

Недавно завершилась эпопея по доказательству того, что $BB(5)=47176870$.

Расшифрую: рассматривались все возможные машины Тьюринга с бинарным алфавитом и пятью состояниями. Каждая из них запускалась на пустой ленте, цель - найти машину, которая в конце концов останавливается, но работает до останова наибольшее число циклов.

В $1990$ году была найдена машина, которая работает до остановки $47176870$ циклов. Остальные $34$ года были посвящены доказательству того, что несколько десятков подозрительных машин действительно не останавливаются. История в чем-то похожа на теорему о четырех красках: в $2003$ году была написана мутная программа из $6000$ строк на Паскале, которая помогла выделить $164$ машины с неизвестной судьбой, список был позже сокращен до $43$. И, наконец, в этом году было опубликовано доказательство на Coq.

https://www.quantamagazine.org/amateur- ... -20240702/
https://bbchallenge.org/
https://github.com/ccz181078/Coq-BB5

Если возникают такие проблемы с изучением поведения программ из $10$ клеточек по нескольку бит информации в каждой, что уж говорить о более сложных.

[Sender]

tolstopuz в сообщении #1647112 писал(а):

Если возникают такие проблемы с изучением поведения программ из $10$ клеточек по нескольку бит информации в каждой, что уж говорить о более сложных.

У программиста есть возможность выбирать, как именно он реализует тот или иной алгоритм, есть масса возможностей облегчить читаемость/анализируемость куда более длинного кода, начиная от структурного программирования. Большинство практических задач вряд ли требует для своего решения разбираться с аналогами гипотезы Коллатца.

[epros]

mihaild в сообщении #1647109 писал(а):

Вы говорите об эпистемологической прослеживаемости, а epros - о гносеологической (или наоборот, я не помню которая про что). В смысле Вы говорите, что магии не бывает, у всех сбоев есть причина, а epros - что на практике это слабо отличимо от того, что магия бывает.

Интересное объяснение. Пожалуй соглашусь и добавлю, что по моим понятиям "онтологической" прослеживаемости не бывает, ибо она про "объективную реальность", коя является вариантом чайника Рассела - можно воображать себе о ней что угодно, но из живущих её никто не видел.

tolstopuz в сообщении #1647112 писал(а):

Недавно завершилась эпопея по доказательству того, что $BB(5)=47176870$.

В некотором смысле это продолжает мой пример с поиском нечётного совершенного числа. На самом деле таких задач, в которых из простых начальных условий возникает неожиданно огромная (возможно - бесконечная) вычислительная сложность, полно. Просто "нормальные" программисты типовых бизнес-приложений стараются таких ситуаций избегать, поэтому возникает иллюзия, что -

Sender в сообщении #1647116 писал(а):

Большинство практических задач

- не про это. Но нет, как раз большинство реальных приложений проверены очень поверхностно - только на типовых сценариях. Шаг в сторону - и начинаются сюрпризы в виде неожиданного поведения.

[realeugene]

Ghost_of_past в сообщении #1647111 писал(а):

Первая - онтологическая прослеживаемость, вторая - эпистемологическая/гносеологическая. Тут все просто: онтологическое - как оно устроено в объективной реальности, гносеологическое/эпистемологическое - как доступно в нашем познании объективной реальности.

Получилась отличная иллюстрация того, почему я избегаю использования подобной терминологии. Не нужна и сразу заводит обсуждение в тупик, так как никто, даже авторы того или иного высказывания, часто не понимают, что пишут.

-- 23.07.2024, 09:39 --

epros в сообщении #1647117 писал(а):

по моим понятиям "онтологической" прослеживаемости не бывает, ибо она про "объективную реальность", коя является вариантом чайника Рассела - можно воображать себе о ней что угодно, но из живущих её никто не видел.

Всё-таки "объективная реальность" - полезный физический термин. Позволяет двум учёным о чём-нибудь договориться.

-- 23.07.2024, 09:41 --

epros в сообщении #1647117 писал(а):

как раз большинство реальных приложений проверены очень поверхностно - только на типовых сценариях. Шаг в сторону - и начинаются сюрпризы в виде неожиданного поведения.

Какая мера большинства?

Всё-таки обнаружение неожиданного поведения в наиболее популярных библиотеках - отдельная цель причастных к ним.

-- 23.07.2024, 09:50 --

Anton_Peplov в сообщении #1647092 писал(а):

Конечно, обученная нейросеть работает по алгоритму (ух ты, я говорю как Webpack!), но этот алгоритм она вырабатывает сама в процессе обучения. Алгоритм работы большой нейросети слишком велик для понимания человеком и (почти) не дробится на осмысленные для человека блоки.

Вы подразумеваете нечто, отличное от понятия "алгоритм". Реакция нейросети вычисляется довольно простым алгоритмом, написанным человеком, но она зависит от массива внешних для алгоритма данных - таблицы с коэффициентами. Называть этот массив данных алгоритмом, на мой взгляд, нельзя.

[ozheredov]

realeugene в сообщении #1647120 писал(а):

Реакция нейросети вычисляется довольно простым алгоритмом, написанным человеком, но она зависит от массива внешних для алгоритма данных - таблицы с коэффициентами. Называть этот массив данных алгоритмом, на мой взгляд, нельзя.

Пусть надо вычислить $y$ по имеющемуся $x$. $y=x$ и $y=-x$ разные алгоритмы или один? А $y=\exp(x)$ и $y=\sin(x)$? А если обе функции вычисляются разложением в ряд в окрестности нуля?

[Anton_Peplov]

epros в сообщении #1647117 писал(а):

Пожалуй соглашусь и добавлю, что по моим понятиям "онтологической" прослеживаемости не бывает, ибо она про "объективную реальность", коя является вариантом чайника Рассела - можно воображать себе о ней что угодно, но из живущих её никто не видел.

Я бы не хотел погружаться в философию. Я отстаиваю более простой тезис: любой баг можно найти, приложив достаточно усилий. С тем, что "достаточно" может означать "слишком много, чтобы кто-то это сделал на практике", я и не думал спорить. Хотя, наверное, в коммерческом программировании такие ситуации действительно возникают чаще, чем я думал. Программы нынче очень сложные, что ж делать. Другое дело, что некоторые приведенные примеры мне не понравились, и я их оспорил.

realeugene в сообщении #1647120 писал(а):

Вы подразумеваете нечто, отличное от понятия "алгоритм".

Отнюдь. Я пользуюсь определением алгоритма в самом строгом смысле: машина Тьюринга и эквивалентные ей формализмы.

realeugene в сообщении #1647120 писал(а):

массива внешних для алгоритма данных - таблицы с коэффициентами

Вы подразумеваете синаптические веса? Насколько я знаю, после завершения обучения нейросети они уже не меняются. А значит, их можно рассматривать не как входные данные, а как часть алгоритма. Хотя для программиста это, конечно, не вбитые в код константы.

Впрочем, можно и не рассматривать. Говоря, что алгоритм работы обученной нейросети слишком сложен для понимания человеком, я подразумевал нечто иное. Разумеется, человек понимает, что такое сложить сигнал с некоторыми весами и передать результат в функцию активации, и прочие вещи в таком духе. Чего он не понимает, так это как подобные действия приводят к результату. На какие признаки опирается нейросеть, отличая котиков от песиков? Почему для вычисления этих признаков нужна именно такая топология сети, именно такие синаптические веса? А черт его знает. Даже если у нас есть вычисленные вектора признаков, в человеческом языке нет названий для этих признаков, нет стоящих за названиями понятий, нет взаимосвязей между понятиями. Нейросеть записывает свои знания на языке, недоступном человеку. Как недавно сказал один умный человек, математики не отвечают на вопрос "зачем", а разработчики нейросетей - на вопрос "почему".

[realeugene]

ozheredov в сообщении #1647123 писал(а):

Пусть надо вычислить $y$ по имеющемуся $x$. $y=x$ и $y=-x$ разные алгоритмы или один? А $y=\exp(x)$ и $y=\sin(x)$? А если обе функции вычисляются разложением в ряд в окрестности нуля?

Это вообще не алгоритмы. Это - вопросы. Алгоритмы - это последовательности инструкций для абстрактной машины, для каждой инструкции строго определено, как она преобразует состояние этой машины (состоянием машины могут быть строки в некотором алфавите).

-- 23.07.2024, 11:59 --

Anton_Peplov в сообщении #1647124 писал(а):

Как недавно сказал один умный человек, математики не отвечают на вопрос "зачем", а разработчики нейросетей - на вопрос "почему".

Отлично!

[ozheredov]

realeugene в сообщении #1647126 писал(а):

Алгоритмы - это последовательности инструкций для абстрактной машины

Если пользоваться

Anton_Peplov в сообщении #1647124 писал(а):

определением алгоритма в самом строгом смысле: машина Тьюринга и эквивалентные ей формализмы.

то $x$ и $-x$ совершенно точно разные алгоритмы. Беда в том, что данная парадигма бесполезна для практики тестирования и отладки - нужно нечто на гораздо более высоком уровне абстракции. В рамках этого "нечта" $x$ и $-x$ это один и тот же алгоритм, равно как и множество "школьных" нейросетей с разными наборами весов весов, где самих весов порядка сотни. Но две нейросети с одной и той же топологией связей и одними и теми же принципами активации, наделенные двумя разными векторами весов размерности миллиард - это (с точки зрения практики дебагинга) два разных алгоритма. Вопрос, с какой по счёту песчинки....

[photon]

(Оффтоп)

Anton_Peplov в сообщении #1647069 писал(а):

Изолируем кусок данных, на котором программа сбоит, выполняем ее пошагово и смотрим

Что в многопоточных приложениях может оказаться нетривиальной задачей.

[epros]

Anton_Peplov в сообщении #1647124 писал(а):

Говоря, что алгоритм работы обученной нейросети слишком сложен для понимания человеком, я подразумевал нечто иное. Разумеется, человек понимает, что такое сложить сигнал с некоторыми весами и передать результат в функцию активации, и прочие вещи в таком духе. Чего он не понимает, так это как подобные действия приводят к результату.

Хочу заметить, что точно в таком же смысле нормальному человеку слишком сложно понимать "как приходит к результату" любой достаточно сложный код, даже если это не нейросеть. Вот я, когда просил Алису перестроить маршрут, даже не подозревал о существовании на карте офиса компании с названием "Без платных дорог". Наверное, если бы я заранее просмотрел все объекты на карте и обратил внимание на этот, то такой ответ Алисы на мой запрос не стал бы для меня особой неожиданностью. Суть не в том, нейросеть это или нет, а в том, что мы не в состоянии проконтролировать все данные, которые перелопачивает алгоритм.

Так что чисто теоретически, может быть, и можно считать, что "любой баг можно найти, приложив достаточно усилий", но на практике эти усилия обычно таковы, что никто не может их себе позволить.

[Geen]

epros в сообщении #1647219 писал(а):

но на практике эти усилия обычно таковы, что никто не может их себе позволить.

Вопрос даже не в этом. Вопрос в том, что очень часто мы вообще не можем сформулировать что именно мы хотим. Более того, у разных пользователей "алгоритма" могут быть противоположные мнения.

[epros]

Geen, да, согласен, это тоже есть. Просто заказчик обычно формулирует требования к поведению алгоритма только для нескольких типовых сценариев. Он даже не задумывается над тем, что возможен миллион не типовых ситуаций, и уж конечно он не станет все их выявлять и подробно определять, что алгоритм должен делать в этом случае.

[StepV]

Если говорить о взаимодействии заказчика и исполнителя, то у вас все перевернуто наоборот.

epros в сообщении #1647227 писал(а):

заказчик обычно формулирует требования к поведению алгоритма только для нескольких типовых сценариев.

Заказчик никогда не формирует требования к отдельным алгоритмам (только очень крайний случай, когда требуется что-то специализированное). Заказчик формирует требования к задаче: вход, выход, перечисление функций.

epros в сообщении #1647227 писал(а):

Он даже не задумывается над тем, что возможен миллион не типовых ситуаций, и уж конечно он не станет все их выявлять и подробно определять, что алгоритм должен делать в этом случае

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