Комментарии 8
>если вам интересно как можно решить задачу k-means кластеризации с обобщенной метрикой используя метод градиентного спуска…
Пятница, вечер… Вы — садист. :-D
Пятница, вечер… Вы — садист. :-D
+1
Хорошая статья.
Т.е. градиент выше, или EM? :) Вообще градиентный спуск хорош тем, что его можно превратить в стохастический или minibatch и хорошенько распараллелить. Не уверен что с EM так же просто получится.
В общем математически то оба алгоритма стоят на одной ступени, но мы то знаем что один чуть выше -)
Т.е. градиент выше, или EM? :) Вообще градиентный спуск хорош тем, что его можно превратить в стохастический или minibatch и хорошенько распараллелить. Не уверен что с EM так же просто получится.
+1
спс
ага согласен с распараллеливанием, хотел в заключении про это добавить, но решил уже что это отдельная тема для беседы, для этого бы пришлось писать параллельную версию, замерять скорость -)
ага согласен с распараллеливанием, хотел в заключении про это добавить, но решил уже что это отдельная тема для беседы, для этого бы пришлось писать параллельную версию, замерять скорость -)
0
Не могли бы вы как-то пояснить, что такое «minibatch» и как параллелить градиентный спуск? Точнее, ясно, что градиент кластеров можно считать по отдельности, ну так в обычном k-means, вроде, тоже новые центроиды можно по отдельности считать.
0
давайте объясню в контексте этой задачи. у нас k центроидов, m образов, n — размерность. всего параметров модели k*n, т.е. k центроидов длины n — это и есть параметры модели. нужно вычислить частную производную целевой функции по каждому параметку модели, т.е. для каждого параметра цикл длины m. среди n, m и k только m на практике бывает очень большим, остальные на много меньше.
мы делаем разбиение исходного множества X на систему непересекающихся множеств XSubs, где каждое такое подмножество размера batchSize, назовем переменной nabla аккумулированный крадиент, ну а далее как то так
где CalculateGradientOnDataSet(Y, i, j) считает сумму частных производных параметра i,j на множестве Y
если batchSize = m то это называется full batch
если 1 < batchSize < m то это mini batch
если batchSize = 1 то говорят об online learning
мы делаем разбиение исходного множества X на систему непересекающихся множеств XSubs, где каждое такое подмножество размера batchSize, назовем переменной nabla аккумулированный крадиент, ну а далее как то так
var nabla[,] = new double[k, n];
Parallel.Foreach(Y in XSubs)
{
for (int i = 0; i < k; i++)
{
for (int j = 0; j < n; i++)
{
nabla[i, j] = CalculateGradientOnDataSet(Y, i, j);
}
}
}
где CalculateGradientOnDataSet(Y, i, j) считает сумму частных производных параметра i,j на множестве Y
если batchSize = m то это называется full batch
если 1 < batchSize < m то это mini batch
если batchSize = 1 то говорят об online learning
+1
Автор сам и ответил :).
Вобщем, да, minibatch — это разновидность стохастического градиентного спуска, где мы считаем следующий шаг спуска на основе части выборки, а не на всем объеме данных, как в классическом градиентном спуске. Это во-первых, ускоряет обсчет градиента, во-вторых позволяет (теоретически) избежать локальных минимумов.
Ну а параллелить можно так — разбить данные на куски, взять несколько кусков в пулл и обсчитывать параллельно. Обновлять параметры по мере обсчета каждого из кусков. Хотя, думаю, есть и другие способы распараллеливания.
Вобщем, да, minibatch — это разновидность стохастического градиентного спуска, где мы считаем следующий шаг спуска на основе части выборки, а не на всем объеме данных, как в классическом градиентном спуске. Это во-первых, ускоряет обсчет градиента, во-вторых позволяет (теоретически) избежать локальных минимумов.
Ну а параллелить можно так — разбить данные на куски, взять несколько кусков в пулл и обсчитывать параллельно. Обновлять параметры по мере обсчета каждого из кусков. Хотя, думаю, есть и другие способы распараллеливания.
0
Ни в коей степени не преуменьшая вашу работу, хочу заметить, что k-means — это тоже реализация градиентного спуска. Просто система уравнений частных производных при этом решается не аналитически (что, как вы верно заметили, возможно не во всякой метрике), а итеративными приближениями.
+1
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Решение задачи кластеризации методом градиентного спуска