Кольца Барромео — это конструкция из трёх колец, обладающая интересным свойством: эти кольца не сцеплены попарно между собой, но полная конструкция из трёх колец неразделима. Ну или если перефразировать: вся конструкция неразделима, но если любое из колец магическим образом пропадает, то оставшиеся два можно разделить. Единственное известное мне практическое применение этих колец — использование в качестве логотипа пива Ballantine. В прошлом году в моей практике повстречался интересный алгоритмический баг, который у меня ассоциируется именно с этой конструкцией.

Сразу скажу, что в последующем повествовании математика заметна упрощена. Итак, я работал над некоторой системой, которая решала задачу максимизации с помощью градиентного подъема (как градиентный спуск, но для максимизации), т. е. строила следующую последовательность

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

Что-нибудь заметили?

Проиллюстрирую её на небольшом примере: допустим мы хотим найти максимум функции

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

Приводить дальше это выражение не буду, его уже можно анализировать: если , то дробь в выражении выше положительна, а значит если , то последовательность возрастает и, более того, расходится. Хмм, как-то странно для метода Ньютона. Ну да ладно, я уже достаточно написал текста для тех, кто хотел разобраться сам и не хотел спойлеров в поле зрения. Проблема в знаке дроби, там должен быть минус, можете поэкспериментировать со следующим кодом и убедиться, что при wrong_sign=True метод почти всегда расходится

def newton_method_example1(x0, wrong_sign):
    for i in range (10):
        step = (x0 - x0 ** 3) / (1 - 3 * x0 ** 2)
        x0 = x0 + (step if wrong_sign else -step)
        print(x0)

    return x0

newton_method_example1(2., True)

А вот с wrong_sign=False метод сходится, но возникает другая особенность метода Ньютона: он будет сходиться к или . Почему ? Это локальный минимум функции и, как оказывается, метод Ньютона для поиска минимума или максимума имеет одинаковую форму в отличие от градиентного спуска. Например для функций и метод Ньютона бы имел одинаковую форму

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

Итак, мы выяснили, что проблема была в знаке. Казалось бы, меняем знак и всё должно заработать, так и сделал — всё сломалось. В предыдущем примере метод Ньютона с неправильным знаком расходился, а у нас же изначально система с неправильным знаком работала, а после его замены перестала работать. Опять что-то не сходится, почему изначально всё работало, а при исправлении знака сломалось? Самое время посмотреть, что за функцию мы пытаемся оптимизировать, как оказалось это что-то вида

Интересна эта функция тем, что она выпукла, а значит метод Ньютона по идее должен искать у неё минимум. С другой стороны очевидно, что минимума у неё нет, есть максимум в нуле, в котором она еще и не дифференцируема. Что же будет, если мы применим метод Ньютона к этой функции? Давайте проверим, если , то правильный метод Ньютона будет иметь вид

а неправильный

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

• Метод Ньютона не должен работать с неправильным знаком

• Метод Ньютона не должен работать с неправильный функцией

• Градиентный спуск с неправильным знаком и неправильной функцией также не работает

• Внезапно метод Ньютона с неправильным знаком и неправильной функцией работает!

Эпилог

Как я сказал, ситуацию я довольно сильно упростил, мне понадобилось много времени, чтобы осознать происходящее в реальной системе. Пока я не увидел все три компоненты, то не осознал что и почему не работает, а они не лежали передо мной в явной форме. В описанной ситуации эффект колец Барромео негативен, но существуют и ситуации когда подобные объекты наоборот приносят пользу. Например в криптографии есть задача о разделении секрета: вам нужно научиться преобразовывать объект таким образом, чтобы его можно было разделить на частей и при этом из любых этих частей можно было восстановить исходный объект, но никаких частей недостаточно чтобы даже частично его восстановить. Решение такой задачи существует, например схема Шамира, она мало имеет общего с кольцами Барромео, но они всё еще представляют собой хорошую иллюстрацию эффекта.