Automatic Relevance Determination или машинное обучение когда данных очень мало

    Когда речь заходит про машинное обучение, обычно подразумевают большие объемы данных — миллионы или даже миллиарды транзакций, из которых надо сделать сложный вывод о поведении, интересах или текущем cостоянии пользователя, покупателя или какого-нибудь аппарата (робота, автомобиля, дрона или станка).
    Однако в жизни обычного аналитика самой обычной компании много данных встречается нечасто. Скорее даже наоборот — у вас будет мало или очень мало данных — буквально десятки или сотни записей. Но анализ все же нужно провести. Причем не какой попало анализ, а качественный и достоверный.


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


    Для этого вы можете воспользоваться методами байесовой статистики, например, Automatic Relevance Determination. Это относительно новый метод, предложенный в 1992 Дэвидом Макаем (все началось с его докторской диссертации (PDF)). Предельно краткое, но непонятное изложение метода можно найти в этой PDF-презентации. Понятное, но излишне многословное объяснение можно посмотреть здесь:



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


    Посмотрим, как это работает на практике. Итак, у нас есть исходные данные — всего 30 точек (например, данные о 30 магазинах). Причем у каждого магазина по 30 признаков. И ваша задача — создать регрессионную модель (например, предсказать объем продаж по данным о местоположении, формату, торговой площади, конфигурации, численности персонала и другим параметрам магазина).
    Строить обычную линейную регрессию в таких условиях будет чистой воды безумием. Давайте еще больше усугубим проблему тем, что лишь 5 признаков на самом деле имеют значение, а остальные — совершенно не отноcящиеся к делу данные.


    Таким образом, пусть реальная зависимость представлена формулой Y = w * X + e, где e — случайная нормальная ошибка, а коэффициенты w равны [1, 2, 3, 4, 5, 0, 0, ....,0], то есть только первые пять коэффициентов ненулевые, а признаки с 6-го по 30-й вообще никак не влияют на реальное значение Y. Однако мы этого не знаем. У нас есть только данные — X и Y — а коэффициенты w нам надо рассчитать.


    Теперь запустим ARD:


    import numpy as np
    from sklearn.linear_model import ARDRegression
    
    N = 30
    
    # данные о магазинах (в данном примере случайные)
    X = np.random.random(size=(N,N)) * 10 + 1
    
    # реальные коэффициенты [1 2 3 4 5 0 0 ... 0]
    w = np.zeros(N)
    w[:5] = np.arange(5) + 1
    
    # добавим случайную ошибку
    e = np.random.normal(0, 1, size=N)
    
    # данные о продажах
    Y = np.dot(X, w) + e
    
    ard = ARDRegression()
    ard.fit(X, Y)
    
    print ard.coef_

    И получаем просто впечатляющий результат:


    array([ 1.01,  2.14,  2.95,  3.89,  4.79,  0.,  0.,  0.,   0.,  0.01,  
            0.,    0.,    0.31,  0.04, -0.05,  0. , 0.,  0.01, 0.,  0.,  
            0.,    0.,    0.01,  0.,    0.,    0.,  0.,  0.17, 0.,  0.  ])

    Напомню, что реальные коэффициенты равны:


    array([ 1.,  2.,  3.,  4.,  5.,  0.,  0., 0.,  0., 0.,
            0.,  0.,  0.,  0.,  0., 0.,  0.,  0.,  0., 0.,
            0.,  0.,  0.,  0.,  0., 0.,  0.,  0.,  0., 0. ])

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


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


    array([ 0.39  2.07  3.16  2.86  4.8  -0.21 -0.13  0.42  0.6  -0.21 
           -0.96  0.03 -0.46  0.57  0.89  0.15  0.24  0.11 -0.38 -0.36 
           -0.28 -0.01  0.43 -1.22  0.23  0.15  0.12  0.43 -1.11 -0.3 ])

    линейной регрессии с L2-регуляризацией:


    array([-0.36  1.48  2.67  3.44  3.99 -0.4   1.01  0.58 -0.81  0.78
           -0.13 -0.23 -0.26 -0.24 -0.38 -0.24 -0.38 -0.25  0.54 -0.31 
           -0.21 -0.42  0.14  0.88  1.09  0.66  0.12 -0.07  0.08 -0.58])

    И они обе не выдерживают никакой критики.


    А вот линейная регрессия с L1-регуляризацией дает похожий результат:


    array([ 0.68  1.9   2.88  3.86  4.88 -0.05  0.09  0.   0.    0. 
            0.    0.    0.    0.    0.    0.    0.    0.   0.    0. 
            0.    0.    0.01  0.    0.    0.    0.    0.   0.    0.  ])

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


    В общем, ARD — метод замечательный, но есть нюанс. Как и многие (можно даже сказать, почти все) байесовы методы, ARD чрезвычайно сложен с вычислительной точки зрения (хотя и хорошо параллелится). Поэтому на данных объемом несколько десятков-сотен точек он работает быстро (доли секунды), на нескольких тысячах — медленно (десятки-сотни секунд), а на десятках и сотнях тысяч — о-о-о-очень медленно (минуты и часы). Кроме того, ему необходим огромный объем оперативной памяти.


    Однако это не так страшно. Если у вас много данных, то вы смело можете пользоваться классическими стат.методами, и они дадут достаточно хороший результат. Серьезные проблемы начинаются, когда данных мало, и обычные методы уже не работают. И тогда на помощь приходит байес.


    ARD активно применяется в разнообразных kernel-методах, например, Relevance Vector Machine (RVM) — это Support Vector Machine (SVM) вместе с ARD. Также он удобен в классификаторах, когда вам необходимо оценить значимость имеющихся признаков. В общем, попробуйте — и вам понравится.

    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 23
    • 0
      Спасибо за статью. Скажите, а есть ли какие-либо автоматические способы определить, когда ARD уже можно заменить на классические методы? Иными словами, когда можно сказать, что исходных данных достаточно, чтобы классические подходы достаточно точно работали? Ставить ограничение на количество точек или считать время работы алгоритма — чур не предлагать :)
      • +2

        Тут очень многое зависит от данных: их полноты, консистентности, содержащейся в них неопределенности и, конечно же, формы распределений.
        Если данные идеальны, то для построения модели с 10 переменными, вам нужно ровно 10 точек данных.
        Но в реальной жизни идеальные данные не встречаются. В них всегда есть неполнота и случайность.


        Обычные бизнесовые данных зачастую происходят из экспоненциального семейства распределений (нормального, Пуассона, Бернулли, логистического и т.д.).
        Для них можно использовать эмпирическое правило: N = C * p2,
        где N — кол-во точек данных, p — размерность данных (кол-во признаков), С — константа, зависящая от имеющейся в данных неопределенности, по сути от модельной ошибки или степени невязки между параметрами и прогнозируемой переменной (обычное значение 3-10).


        Так что если у вас 30 признаков, то желательно иметь не менее 3000 точек, а при 10 признаках — не менее 300.

      • 0

        А можно очень просто про L1 и L2 регуляризацию? Или хорошую сслылку.

        • –1
          L2 регуляризация — это дополнительный критерий в функции ошибки обучения:
          loss = cross_entry(predictions, y) + lamda * sqr(w)

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

          L1 регуляризация — тоже дополнительный критерии в функции ошибки. Только в данном случае добавляется ошибка не квадратичные значения а абсолютное значения весов, и «подталкивает» функции иметь меньше значения и меньше не нулевых значении. Тем самым вызывает разреженность в матрице весов.
          loss = cross_entropy(predictions, y) + lambda * abs(w)

          • 0
            Написал комментарии 28-го — был на модерации. Автору Roman_Kh видимо не понравилось что я указал на неверное использование L2 регуляризации (для линейной функции) и не стал одобрять комментарий. Хабр только сегодня по запросу одобрил.
            Не согласны/убеждены что я неверно описал? Можно вместе с минусом написать комментарии с чем не согласны…
            • 0

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

              • +1

                Минус я поставил, потому что, извините, лучше никакого объяснения, чем такое.
                Формулы на питоне, в первой же 2 опечатки. L2-регуляризация — это добавление квадратов весов, а не корней (по-вашему норм, что производная в бесконечность уходит, если веса малы? как оптимизировать?)
                "Смысл приминения в том что при переобучении нелинейных функции значения весов сильно увеличиваются." — тут я вообще не вкурил.
                Вам тоже так объясняли основы машинного обучения?

                • 0

                  В паскале была функция sqr(x) = x2

                  • 0

                    Простите, не распознал под гримом столь модный в data science язык.

                  • –2
                    yorko, спасибо за комментарий. Теперь можно аргументировать в интернете :)
                    Как указал Роман, тут sqr — сокращенное от square. (sqrt — square root) Я предполагаю минус был именно за это…
                    Язык программирование тут не причем, я мог написать как сам пишу используя tensorflow в питоне:
                      loss = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(logits, tf_train_labels))
                            
                      # L2 regularization for fully connected layer
                      regularizers = (tf.nn.l2_loss(fc1_weights)
                                            tf.nn.l2_loss(fc2_weights))
                      loss += 5e-4 * regularizers
                    

                    Но решил использовать нечто вроде псевдо кода.
                    loss = cross_entry(predictions, y) + lamda * sqr(w)


                    В общем смысл не меняется, можно в функцию ошибки, например кросентропии (log likelihood) либо среднего квадратичного отклонения (mean squared error) добавить нужную нам критерии регуляризации.
                    • –2
                      «Смысл приминения в том что при переобучении нелинейных функции значения весов сильно увеличиваются.» — тут я вообще не вкурил.

                      Извините, что я пишу не ясно.
                      При переобучении сеть начинается подгонятся под обучаемую выборку. В этом процессе, значении весов будут увеличиваться, функция сети (hypothesis function) будет все более и более сложной. Например от линейной к квадратичным, до десятой степени и т.п.
                      image
                      График слева: черная линия — функция сети, жирные точки — обучаемая выборка, x — тестовая выборка.
                      Для решения данной проблемы, ограничивают область возможных значении для весов от начала координат (origin).
                      Надеюсь, выразился яснее.
                      • –1
                        Ведите себя профессионально, не нравится когда указывают на провалы в знании?
                        Не знаете как ведет себя сеть при переобучении? Однако, data scientist-ы.
                        Для чего тогда тут сделаны дискусии, если уходите от нормального обсуждения.
                        • +1

                          Спасибо, что пояснили, что такое переобучение! :)


                          L2 регулярузацию используют в случае если имеются нелинейные функции

                          Что вы имеете в виду под нелинейностью? Полиномиальные признаки?
                          Если что, Ridge-регрессия — все еще линейная, и даже существующее у нее аналитическое решение линейно по ответам:


                          • –2
                            Не за что!
                            «Смысл приминения в том что при переобучении нелинейных функции значения весов сильно увеличиваются.» — тут я вообще не вкурил.
                            Спасибо, что пояснили, что такое переобучение!

                            В же не были согласны с тем что при одном из вариантов переобучения веса будут увеличиваться.
                            Что вы имеете в виду под нелинейностью?
                            Ridge-регрессия — все еще линейная, и даже существующее у нее аналитическое решение линейно по ответам

                            Стоит добавить — в случае Метода Наименьших Квадратов.

                            Для линейных обычно есть аналитическое решение. В случае МНК, только в отдельных случаях является приемлимым вариант с ridge-regression.
                            «In a Bayesian context, this is equivalent to placing a zero-mean normally distributed prior on the parameter vector.».
                            Будет перекос в решении на нормальное распределение (с центром 0) в значении веса, что очевидно так как мы добавили квадрат этого веса.

                            О L2 регуляризации линейной функции наглядно:
                            image
                            Имеется линеяная функция y=Ax + b.
                            Если добавить L2 регуляризацию, то в решении будет браться коэффицент с меньшим весом (чем среднее отклонение) так как мы добавили в ошибку квадратичное значение. В нашей формуле из многих значении A — перекос будет в сторону меньших значении. Что неверно в общем случае.
                            • 0
                              yorko: Ridge-регрессия — все еще линейная, и даже существующее у нее аналитическое решение линейно по ответам

                              erko: Стоит добавить — в случае Метода Наименьших Квадратов.
                              Для линейных обычно есть аналитическое решение. В случае МНК, только в отдельных случаях является приемлимым вариант с ridge-regression.

                              Вы бы хоть с первоисточниками ознакомились: Ridge-регрессия была впервые введена в 1970 году в работе "Ridge Regression: Biased Estimation for Nonorthogonal Problems".
                              И в ней оптимизируемый функционал определен как сумма квадратов ошибок и квадратов коэффициентов регрессии.
                              Иными словами (пусть и несколько некорректно), ridge-регрессия — это, по определению, линейная регрессия МНК с L2-регуляризацией.

                              • –2
                                Roman_Kh,
                                Не вижу противоречии в своем утверждении. Да, излишнее было указывать МНК, но это не означает что в МНК в общем решении верно использвание ridge-регрессия.

                                В википедии: The standard approach is ordinary least squares linear regression. However, if no x satisfies the equation or more than one x does—that is the solution is not unique—the problem is said not to be well posed.
                                Вот в таком случае можно использовать ridge-regression.

                                В публикации: Biased Estimation for
                                Nonorthogonal Problems — само название говорит что решение будет пристрастным. Да в некоторых случаях вынуждены добавлять пристрастность, так как данные могут быть статистически не полными.
                                Иными словами (пусть и несколько некорректно) ..

                                Ну именно о данном утверждении yorko не согласен был.
                • +1

                  Формулой: L1-регуляризация заключается в добавлении суммы модулей весов модели к оптимизируемому функционалу, а L2 — в добавлении суммы квадратов весов. Отличие вроде небольшое, но задача оптимизации сильно меняется.


                  На практике: регрессия с L1-регуляризацией (LASSO) часто используется для отбора признаков, поскольку в результате оптимизации некоторые веса становятся в точности нулевыми. Из набора признаков, сильно коррелирующих между собой, выберется только один.
                  L2-регуляризация (гребневая- или Ridge-регрессия) решает проблему мультиколлинеарности, которая в реальных данных есть почти всегда. Веса в модели не нулевые, и по качеству чаще Ridge работает лучше (в терминах функции потерь на кросс-валидации или отложенной выборке), чем Lasso, поскольку меньше ограничивает модель (в то время как Lasso явно зануляет коэффициенты перед некоторыми признаками).


                  В реальных задачах регуляризация нужна всегда, и если задача выбора признаков остро не стоит, лучше использовать L2. Если коротко, можно в документации Scikit-learn почитать или на Cross-Validated. А толково — в Hastie и Tibshirani.

                • +1

                  А как контролировать переобучение, когда данных мало?


                  В классической постановке есть разные оценки обобщающей способности, и то VC-оценка, growth function и даже сложность Радемахера, как я понял, все еще сильно завышены в большинстве случаев.


                  На малых данных, получается, Computational Learning Theory нам не в помощь. На кросс-валидации мы тоже переобучимся, если много параметров будем перебирать. Возможно ли вообще какие-то гарантии давать в таком случае?


                  Проблема, как я вижу, особенно остра в случае медицинских данных.

                  • 0
                    Вообще, по хорошему, по кросс-валидации надо либо подбирать параметры, либо оценивать качество, но не обе вещи вместе — иначе оценка качества будет завышенной. То есть правильнее рассматривать весь алгоритм обучения (включая выбор параметров) как чёрный ящик, и для него проводить кросс-валидацию — таким образом получается «двухуровневая» кросс-валидация.
                    • 0

                      Это да… только NestedCV за разумное время посчитается только как раз на малых данных. Или когда квантовые компьютеры заработают :)
                      Вопрос скорее про теоретическую верхнюю грань для ошибки в случае малых данных.

                      • 0
                        Ну так на немаленьких данных такое (двухуровневость) обычно и не нужно :)

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

                  Самое читаемое