Learning to learn. Создаём self-improving AI

    Learning to learn


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

    Цели эксперимента:

    1) Создать алгоритм оптимизации, который можно некоторым стандартным способом приспособить к любой оптимизационной задаче или множеству задач. Под словом «приспособить» я имею в виду «сделать, чтобы алгоритм очень хорошо справлялся с этой задачей».
    2) Подстроить алгоритм под одну задачу и посмотреть, как изменилась его эффективность на других задачах.

    Почему алгоритмы оптимизации вообще важны?


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

    Список задач


    Задачи у нашего алгоритма будут следующие:

    1) Задача на полиномиальную регрессию. Дана некоторая функция, надо построить кривую, которая будет аппроксимировать график этой функции графиком многочлена 7-ой степени. Оптимизатор подбирает коэффициенты регрессии. Метрика качества в этой задаче равна среднему отклонению между реальным графиком и аппроксимацией. У функции много локальных оптимумов, но она гладкая.
    2) Задача на квадратичную функцию. Метрика качества q=(k1-10)^2+(k2+15)^2+(k3+10*k4-0.06)^2+…, то есть она равна сумме квадратов от неких линейных функций от коэффициентов, которые подбирает оптимизатор. У функции много минимумов, но она гладкая.
    3) Задача на дискретную функцию. Метрика качества рассчитывается по алгоритму вида: q=1; если(k1>-2){q+=3}; если(k1<0.2){q+=15};…, то есть график функции от любой переменной будет выглядеть как некоторая ступенчатая линия. У функции мало локальных оптимумов, но она негладкая.

    В качестве тренировочной задачи я буду применять задачу 2 (на квадратичную функцию), в качестве тестовых – остальные две.

    Оптимизатор


    В качестве оптимизирующего алгоритма я буду использовать свой самописный ансамбль алгоритмов, который я назвал Абатуром. Данный ансамбль включает в себя несколько вариантов покоординатного спуска, градиентный спуск, эволюцию, алгоритм пчелиного роя. И управляющий алгоритм, который с разной вероятностью вызывает разные модули.

    Так выглядит основной блок принятия решений в Абатуре.

    for i=1:sz(2)
    %optimizerData.optimizers - массив оптимизирующих алгоритмов
                reputation(i)=optimizerData.optimizers{i}.reputation;
    %optimizerData.optimizers{i}.reputation - один из параметров Абатура, он настраивается в ходе обучения
                reputationR(i)=reputation(i)*(1+0.5*randD());
    end;
    [ampl,arg]=max(reputationR);
    [newK,dt]=feval(optimizerData.optimizers{arg}.name,optimizerData);
    optimizerData.dt=optimizerData.dt+dt;
    valNew=feval(optimizerData.func,newK);
    if(valNew>=valOld)
                optimizerData.kArr=newK;
                valOld=valNew;
    end;
    

    Пример оптимизатора для Абатура. Градиентный спуск
    function [kArrOld,dt] = constrainedGrad(optimizerData)
        kStep=optimizerData.k(16);% k - один из параметров. Настраивается извне оптимизирующим алгоритмом. В данной ситуации размер шага.
        stepGrad=optimizerData.k(19);%размер шага для измерения градиента. Тоже величина, оптимизируемая извне
        sz=size(optimizerData.kArr);
        kArrOld=optimizerData.kArr;
        valOld=feval(optimizerData.func,kArrOld);
        trg=randDS(sz(2))<optimizerData.k(17);
        grad=zeros(sz);
        dt=1+floor(optimizerData.k(18))*sum(trg);
        for j=1:optimizerData.k(18)
            for i=1:sz(2)
                if(trg(i))
                    kArrOld(i)=kArrOld(i)+stepGrad;
                    grad(i)=(feval(optimizerData.func,kArrOld)-valOld)/stepGrad;
                    kArrOld(i)=kArrOld(i)-stepGrad;
                else
                    grad(i)=0;
                end;
            end;
            kArrOld=kArrOld+grad*kStep;
            valNew=feval(optimizerData.func,kArrOld);
            if(valNew>valOld)
                valOld=valNew;
            else
                kArrOld=kArrOld+grad*kStep;
            end;
        end;
    end
    


    Другой оптимизатор для Абатура. Одна из эволюционных стратегий
    function [kArrOld,dt] = evolutionLight(optimizerData)
        dt=abs(round(optimizerData.k(32))*round(optimizerData.k(37)));
          kArrOld=evolutionRaw(optimizerData.func,optimizerData.kArr,optimizerData.k(32),optimizerData.k(33),optimizerData.k(34),optimizerData.k(35),optimizerData.k(36),optimizerData.k(37)); 
    %Входные данные для evolution raw: оптимизируемая функция, стартовая точка, размер популяции, число альфачей (тех, кто размножается), дисперсия стартового распределения, вероятность мутации, дисперсия гена при мутации, число поколений
    end
    


    optimizerData.k — это массив параметров Абатура. Как видно в коде выше, эти параметры определяют всё: шаги градиентного спуска, размеры популяций, вероятности срабатывания того или иного оптимизатора.

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

    Метрика качества learning to learn


    Для оптимизации способности к оптимизации надо каким-то способом измерять эту самую способность к оптимизации. Я применял метрику lrvt (logarithm-relative-value-time).
    Lrvt=((log(abs(valOld/valNew))/log(10)))/log(dt+10)
    ValOld – метрика качества до оптимизации
    ValNew – метрика качества после оптимизации
    Dt – количество вычислений оптимизируемой функции в ходе оптимизации.

    Эту метрику я не придумал единоразово, это результат длительной эволюции моих метрик качества. Эта метрика коррелирует с valOld/valNew, то есть с количественным значением апгрейда и антикоррелирует с dt, то есть затратами времени на апгрейд.

    Испытание 1. Градиентный спуск.


    Запустим алгоритм градиентного спуска на всех трёх перечисленных задачах – просто, чтобы было, с чем сравнивать Абатур. По горизонтальной оси откладывается номер шага, по вертикальной – метрика качества (идеальное решение найдено, если она равна 0).

    1) Регрессия.



    Градиентный спуск снизил q с 1.002 до 0.988 за 100 тактов. Слабовато, но стабильно.

    2) Квадратичная функция



    Градиентный спуск снизил q со 140 до примерно 5 за 100 тактов. Сильно, но алгоритм уже вышел в насыщение.

    3) Дискретная функция



    Градиентный спуск снизил q со 3663.06 до 3662.98 за 100 тактов. Очень слабо, очень непостоянно.

    Испытание 2. Абатур с настройками по умолчанию.


    Теперь запустим на этих же задачах Абатур со стандартными настройками.

    1) Регрессия



    Снизил q с 1 до 0.91 за 20 тактов (за остальные 80 тактов он ничего не сделал). Слабовато, но намного сильнее, чем градиентный спуск (который снизил с 1.002 до 0.988). И крайне нестабильно.

    2) Квадратичная функция.



    Снизил q со 189 до 179 за 50 тактов (градиентный спуск снизил q со 140 до примерно 5). В данной ситуации Абатур показал себя нестабильным и малоэффективным.

    3) Дискретная функция.



    Снизил q со 3663.27 до 3662.98. Очень слабо, очень нестабильно.

    Испытание 3. Абатур обученный.

    Обучаем Абатур на квадратичной функции. В качестве обучающего алгоритма используем Абатур со стандартными настройками.

    1) Регрессия.

    Синими линиями показан процесс оптимизации до обучения. Красными – после.



    Абатур обученный улучшил значение с примерно 1 до примерно 0.17. Намного лучше и старого Абатура, и градиентного спуска.

    2) Квадратичная функция.



    Абатур обученный улучшил значение с примерно 190 до числа меньше 1. Намного лучше и старого Абатура, и градиентного спуска.

    3) Дискретная функция



    Абатур обученный улучшил значение с примерно 3600 до 0.01. Намного лучше и старого Абатура, и градиентного спуска (которые вообще не справились).

    Резюме


    1) Обучаемый алгоритм оптимизации создан. Оболочка для его обучения создана.
    2) Я обучил Абатур на одной задаче. Он стал лучше решать все перечисленные задачи. Следовательно, алгоритм подобрал эвристики, которые в сумме пригодны для решения любой задачи из списка.

    Источники литературы:


    1) “Learning to learn by gradient descent by gradient descent”
    2) “Metalearning”
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 7

      +4

      Как ИИ вы назовёте так он и учиться будет :)

        0
        По поводу второй задачи
        > q=(k1-10)^2+(k2+15)^2+(k3+10*k4-0.06)^2+
        >она равна сумме квадратов от неких линейных функций
        >У функции много локальных оптимумов, но она гладкая.
        Это же просто что-то в духе МНК. И тут либо есть глобальный минимум, либо бесконечное число равнозначных минимумов (зависит от того, SPD ли матрица вторых производных, или же semi positive definite).

        Я неправ?
          0
          Я так понимаю, вы говорили о СЛАУ. Да, вы правы — у нас либо один глобальный минимум (в данном случае нет), либо бесконечно много равнозначных минимумов.
          И для этой задачи есть и иные способы решения, кроме численного — просто эту задачу зачастую применяют для тестирования алгоритмов оптимизации.
            0
            Я просто не уверен что в этом случае можно применять термин «локальный минимум»
              0
              Вы весьма внимательны!
          +1
          Ну и сильно не хватает подробного описания «Абатура», каким образом происходит обучение, и т.д.
            0
            Пожалуй, вы правы. Добавил подробности в раздел «Оптимизатор».

          Only users with full accounts can post comments. Log in, please.