Fedot

View the Project on GitHub ITMO-NSS-team/FEDOT.Docs

Алгоритм идентификации структуры композитных моделей

Построение цепочки моделей машинного обучения (МО) для решения прикладных задач.

Для каждой решаемой задачи модифицированный алгоритм генетического программирования формирует цепочку из нескольких моделей МО, содержащихся в заданном множестве. Цепочка может содержать два типа узлов:

  1. Secondary nodes. Узлы, объединяющие несколько моделей (входные признаки формируются из предсказаний моделей, объединенных данным узлом)
  2. Primary nodes. Узлы, являющиеся самостоятельными моделями (модели первого уровня, входными признаками которых являются непосредственно признаки решаемой задачи)

alt-текст

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

Входные данные

  1. Ресурсы алгоритма (composer_requirements)
    • primary и secondary - два множества моделей, которые могут быть использованы в качестве Primary nodes и Secondary nodes соответственно, взятые из сформированного репозитория моделей.
    • num_of_generations - Количество поколений эволюционного алгоритма.
    • pop_size - размер популяции деревьев.
    • max_depth - максимальная глубина дерева.
    • max_arity - максимальная арность узла типа Secondary node (максимальное количество моделей, которые может объединять узел).
    • crossover_prob - веротяности скрещивания в алгоритме генетического программирования.
    • mutation_prob - вероятность мутации в методе генетического программирования.
  2. База данных решаемой задачи.
  3. Метрика оценки качества решения (берется из существующего репозитория метрик качества quality_metrics_repository.py).

В качестве примера, если необходимо передать в алгоритм метрику качества ROC-AUC, необходимо инициализировать ее следующим образом:

metric_function = MetricsRepository().metric_by_id(ClassificationMetricsEnum.ROCAUC)

Выходные данные

Выходными данными является дерево моделей МО найденное эволюционным алгоритмом, сконвертированное при помощи метода _tree_to_chain в цепочку моделей МО.

Описание принципа работы

Решения в генетическом программирования представляются в виде деревьев. Деревья могут быть n-арными, то есть количество подвершин каждой вершины дерева может быть не больше чем n. Обычно в генетическом программировании вершины дерева являются элементами одного из двух множеств: терминального (T) или функционального (F). В функциональное множество входят функции, которые используются для формирования решения, а в терминальное множество набор констант и переменных. В рамках же данного фреймворка аналогом функциональных узлов являются Secondary nodes, а аналогом терминальных узлов Primary nodes.

Представим подробное описание алгоритма:

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

Схема работы алгоритма генетического программирования для составления цепочек моделей:

1. Инициализация

На первом этапе генерируется популяция деревьев. Для инициализации в методе генетического программирования используется метод выращивания. При использовании данного метода вершины типа primary node могут располагаться на любой глубине (кроме нулевой, так как на ней всегда располагается функциональный узел), но максимальная глубина вершины в дереве равна d (параметр задаваемый пользователем).

2. Вычисление пригодности индивидов

Производится согласно метрике качества выбранной из репозитория.

3. Селекция

В разработанной реализации использовалась турнирная селекция индивидов реализованная в методе tournament_selection. Согласно данной стратегии, для отбора одного индивидов, которые будут участвовать в скрещивании в качестве родителей создается группа из n индивидов популяции (n>2), выбранных случайным образом. Из этой группы отбирается индивид, обладающий наибольшей пригодностью, остальные индивиды отбрасываются. Число n называется размером турнира, обычно выбирают размеры турниров: n=2,n=5 и n=9. Достоинства данного типа селекции: простота, отсутствие требования ранжирования индивидов, что требует гораздо больше вычислительных ресурсов.

alt-текст

Программно селекция реализована следующим образом:

def tournament_selection(fitnesses, group_size=5):
    selected = []
    pair_num = 0
    for j in range(len(fitnesses) * 2):
        if not j % 2:
            selected.append([])
            if j > 1:
                pair_num += 1

        tournir = [randint(0, len(fitnesses) - 1) for _ in range(group_size)]
        fitness_obj_from_tour = [fitnesses[tournir[i]] for i in range(group_size)]

        selected[pair_num].append(tournir[np.argmin(fitness_obj_from_tour)])

    return selected

4. Скрещивание

Был использован стандартный тип скрещивания реализованный в методе standard_crossover. После выбора родителей на этапе селекции для каждой родительской пары: 1) У каждого из имеющихся родителей выбирается точка скрещивания. 2) Родители обмениваются поддеревьями, находящимися ниже точки скрещивания.

alt-текст

Программно скрещивание реализовано следующим образом:

def standard_crossover(tree1, tree2, max_depth, 
                       crossover_prob, pair_num=None, 
                       pop_num=None):
    if tree1 is tree2 or random.random() > crossover_prob:
        return deepcopy(tree1)
    tree1_copy = deepcopy(tree1)
    rn_layer = randint(0, tree1_copy.get_depth_down() - 1)
    rn_self_layer = randint(0, tree2.get_depth_down() - 1)
    if rn_layer == 0 and rn_self_layer == 0:
        return deepcopy(tree2)

    changed_node = choice(tree1_copy.get_nodes_from_layer(rn_layer))
    node_for_change = choice(tree2.get_nodes_from_layer(rn_self_layer))

    if rn_layer == 0:
        return tree1_copy

    if changed_node.get_depth_up() + node_for_change.get_depth_down() - \
       node_for_change.get_depth_up() < max_depth + 1:
        changed_node.swap_nodes(node_for_change)
        return tree1_copy
    else:
        return tree1_copy

4. Мутация

В методе standard_mutation была реализована схема точечной мутации. Случайно выбранный узел в дереве меняется на случайно выбранный элемент того же типа. Т.е. выбранный узел заменяется случайно выбранным элементом множества допустимых моделей для узлов типа primary nodes, если этот узел принадлежит данному типу, или элементом множества допустимых узлов для secondary nodes, если узел имеет тип secondary node.

alt-текст

Программно мутация реализована следующим образом:

def standard_mutation(root_node, secondary_requirements, 
                      primary_requirements, probability=None):
    if not probability:
        probability = 1.0 / root_node.get_depth_down()

    def _node_mutate(node):
        if node.nodes_from:
            if random.random() < probability:
                node.eval_strategy.model = random.choice(secondary_requirements)
            for child in node.nodes_from:
                _node_mutate(child)
        else:
            if random.random() < probability:
                node.eval_strategy.model = random.choice(primary_requirements)

    result = deepcopy(root_node)
    _node_mutate(node=result)

    return result

Как использовать алгоритм для прикладных задач

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

Связывание в внешними функциями реализововано через механику callback-ов - т.е. в алегоритм-оптимизатор в качестве внешнего параметра передается объект/функция, которая, например, может отслеживать изменения в популяции. В конце каждой итерации алгоритма вызывается функция sellf.history_callback(), куда передаются нужные параметры (значения фитнес-функции, лучшие/худшие индивиды и т.д.). А уже в самом callback-е реализовано произвольную функциональность - вывод в консоль, визуализация и т.д. Пример подобной реализации можно изучить в документации Keras.

Эволюционные операторы предпочтительно выделить в отдельные скрипты и разбить их на типы: selection.py, crossover.py, mutation.py и т.д.

Экспериментальные исследования

Запуск на тестовой задаче (цепочка простых математических операторов): alt-текст