Решение задачи кластеризации методом градиентного спуска

[Theo_from_Sed]

>если вам интересно как можно решить задачу k-means кластеризации с обобщенной метрикой используя метод градиентного спуска…

Пятница, вечер… Вы — садист. :-D

[lightcaster]

Хорошая статья.

В общем математически то оба алгоритма стоят на одной ступени, но мы то знаем что один чуть выше -)

Т.е. градиент выше, или EM? :) Вообще градиентный спуск хорош тем, что его можно превратить в стохастический или minibatch и хорошенько распараллелить. Не уверен что с EM так же просто получится.

[mephistopheies]

спс
ага согласен с распараллеливанием, хотел в заключении про это добавить, но решил уже что это отдельная тема для беседы, для этого бы пришлось писать параллельную версию, замерять скорость -)

[leventov]

Не могли бы вы как-то пояснить, что такое «minibatch» и как параллелить градиентный спуск? Точнее, ясно, что градиент кластеров можно считать по отдельности, ну так в обычном k-means, вроде, тоже новые центроиды можно по отдельности считать.

[mephistopheies]

давайте объясню в контексте этой задачи. у нас k центроидов, m образов, n — размерность. всего параметров модели k*n, т.е. k центроидов длины n — это и есть параметры модели. нужно вычислить частную производную целевой функции по каждому параметку модели, т.е. для каждого параметра цикл длины m. среди n, m и k только m на практике бывает очень большим, остальные на много меньше.

мы делаем разбиение исходного множества 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

[lightcaster]

Автор сам и ответил :).

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

Ну а параллелить можно так — разбить данные на куски, взять несколько кусков в пулл и обсчитывать параллельно. Обновлять параметры по мере обсчета каждого из кусков. Хотя, думаю, есть и другие способы распараллеливания.

[leventov]

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

[ererer]

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