Empirical mutation probability

[valer1435]

I have a suspicion that empirical mutation probabilities are different from the theoretical. What I mean:
Here when we call mutation, we iterative choose mutation until it can be applied. Obviously that mutation, f.e. "parameter_change" always can be applied because it can't performs changes affect on verification. But mutations "add_parent", "add_intermediate_node" can make pipeline incorrect. Due to above facts we can stuck in situation, when almost all mutations are "parameters change" (critical in Fedot ts forecasting task when there are a lot of constraints put on a pipeline structure).

What I assume to do:

• make experiments in GOLEM and Fedot particularly (in different tasks). Find is there a real problem
• change logic of mutation, for example give structural mutations more tries to apply it's mutations

[kasyanovse]

Results of experiments for time series forecasting is below. 5 generations.

Code for extracting data from Fedot: pd.Series([y.__name__ if callable(y) else (y if isinstance(y, str) else y.value) for y in chain(*[x.parent_operator.operators for x in chain(*fedot.history.generations) if x.parent_operator is not None])]).value_counts().

Mutation type	Probability
parameter_change_mutation	0.4125
single_change	0.308
single_drop	0.133
single_add	0.1
single_edge	0.042

[kasyanovse]

The simplest way to fix it is add new type of graph processor. It should act like verifier and also fix some problems like missing lagged nodes and another stuff.
It is not working for multidimensity data.

[valer1435]

Results for the same experiment for classification task (5 gen)

Mutation type	Probability
parameter_change_mutation	0.47
single_change	0.3
single_add	0.12
single_drop	0.1
add_resample_mutation	0.02

[valer1435]

Results for the same experiment for regression task (9 gen)

Mutation type	Probability
parameter_change_mutation	0.3
single_change	0.2
single_drop	0.17
add_resample_mutation(?)	0.15
single_add	0.1
single_edge	0.08

[kasyanovse]

Я глянул неуспешные мутации. Все вполне ожидаемо. Почти все некорректные пайплайны для задачи регрессии связаны с тем, что последняя модель в пайплайне оказывается не предиктивной моделью, а обычным трансформером (в том смысле, что она трансформирует данные).
Логично было бы подкрутить вероятность мутаций так, чтобы мутации параметров были раза в 2-3 реже, чем остальные.
@valer1435 Что скажешь?

[kasyanovse]

Регрессия. 5 поколений.

В лоб это не очень хорошо работает) Наверное, нужен балансировщик на уровне подготовки поколения, чтобы выровнять вероятность мутаций. Если ее выравнивание вообще нужно.

Mutation type	Probability
single_add	0.347328
single_change	0.255725
add_resample_mutation	0.164122
single_drop	0.087786
single_edge	0.083969
parameter_change_mutation	0.061069

[valer1435]

Я глянул неуспешные мутации. Все вполне ожидаемо. Почти все некорректные пайплайны для задачи регрессии связаны с тем, что последняя модель в пайплайне оказывается не предиктивной моделью, а обычным трансформером (в том смысле, что она трансформирует данные). Логично было бы подкрутить вероятность мутаций так, чтобы мутации параметров были раза в 2-3 реже, чем остальные. @valer1435 Что скажешь?

Я думаю, что нужно смотреть в сторону того, чтобы повторять одну и ту же мутацию до победного (или хотя бы n раз)

[nicl-nno]

Тут есть риск зацикливания, если конкретной мутацией не удастся выйти из тупика.

[valer1435]

Тут есть риск зацикливания, если конкретной мутацией не удастся выйти из тупика.

Да, поэтому предлагается пробовать несколько раз. Ну и предлагается делать более специфичные мутации для временных рядов (например добавлять сразу верку lagged+regression model)

[nicl-nno]

Думаю стоит сразу оба варианта реализовать.

[maypink]

@kasyanovse предложил повторные попытки применить мутации тоже параллелить, ввиду невозможности нормально реализовать повторные попытки применений без зависающего потока, у меня появилась следующая идея:

"предлагаю сделать хэш мапу индивидов, где ключи — uuid'ы, а значения — хэшмапы с ключами, равным индексам примененных мутаций, а значения — Optional[bool] удалось применить-не удалось или None, если попыток пока не было. индивиды в хэш мапу будут браться из текущей _population, те индвиды там чаще всего будут повторяться.

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

thereby, задача передается в руки Сергею

[kasyanovse]

Краткое резюме по тому, что есть. Тестирование проводилось в федоте на задаче предсказания временных рядов с наличием множества идеальных решений. Изначально федот, при композиции в 5 минут, находит их не очень часто (зависит от коммита в мастере).

Варианты решения проблемы:

1. Жесткая балансировка мутаций в попытках строго соблюсти требуемые пропорции вполне ожидаемо не работает. Репродюсер всегда вылетает по условию предельного количества итераций и не набирает поколение.
2. Балансировка средней жесткости с повторением непопулярных мутаций. Периодически вылетает по предельному количеству итераций (зависит от величины ограничения), соответственно не всегда набирает поколение. Субъективно хорошо ищет решения (всегда находит идеальное решение), но время композиции выросло почти на порядок. Стандартные кейсы использования федота с таймаутом в 2-5 минут становятся просто неработоспособными.
3. Мягкая балансировка с ограничением на популярные мутации. Не тестировалась, если кому-то интересно, то можно поковырять.
4. Повторение неудавшихся мутаций несколько раз. С 2-3 итерациями на каждую мутацию дает неплохое выравнивание мутаций (до идеала очень далеко), при этом работает быстро и всегда набирает поколение. НО! качество композиции не улучшилось ни на грамм. Мне даже кажется, что стало хуже, так как идеальное решение задачи находит редко. Для точной оценки нужен бенчмарк. (Кстати, хорошая идея для бенчмарка: частота нахождения идеального решения за отведенное время и количество различных идеальных вариантов.).

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

Мутация	Без повторений	С 1 повторением	С 2 повторениями
parameter_change_mutation	0.41	0.34	0.26
single_change	0.31	0.33	0.22
single_drop	0.13	0.15	0.22
single_add	0.1	0.1	0.16
single_edge	0.04	0.1	0.14

Я бы сделал такой вывод: балансировка мутаций не панацея. Ресурс времени композиции, который можно пустить на балансировку поколений, ИМХО, лучше пустить на обычную, неидеальную композицию. Но вывод субъективный, требуется бенчмарк с различными задачами. Передаю слово в #233.