Как работает pytorch backprop через argmax? - PullRequest
Новая
       106

Как работает pytorch backprop через argmax?

0 голосов
/ 03 марта 2019

Я строю Kmeans в pytorch, используя градиентный спуск по центроидным точкам, вместо максимизации ожидания.Потеря - это сумма квадратных расстояний каждой точки до ближайшего центроида.Чтобы определить, какой центроид является ближайшим к каждой точке, я использую argmin, который не везде дифференцируем.Тем не менее, pytorch по-прежнему может выполнять обратное преобразование и обновление весов (местоположений центроидов), обеспечивая схожую производительность с sklearn kmeans для данных.

Есть идеи, как это работает, или как я могу понять это в pytorch?Обсуждение Python GitHub предполагает, что argmax не дифференцируем: https://github.com/pytorch/pytorch/issues/1339.

Пример кода ниже (на случайных точках): 

import numpy as np
import torch

num_pts, batch_size, n_dims, num_clusters, lr = 1000, 100, 200, 20, 1e-5

# generate random points
vector = torch.from_numpy(np.random.rand(num_pts, n_dims)).float()

# randomly pick starting centroids
idx = np.random.choice(num_pts, size=num_clusters)
kmean_centroids = vector[idx][:,None,:] # [num_clusters,1,n_dims]
kmean_centroids = torch.tensor(kmean_centroids, requires_grad=True)

for t in range(4001):
    # get batch
    idx = np.random.choice(num_pts, size=batch_size)
    vector_batch = vector[idx]

    distances = vector_batch - kmean_centroids # [num_clusters, #pts, #dims]
    distances = torch.sum(distances**2, dim=2) # [num_clusters, #pts]

    # argmin
    membership = torch.min(distances, 0)[1] # [#pts]

    # cluster distances
    cluster_loss = 0
    for i in range(num_clusters):
        subset = torch.transpose(distances,0,1)[membership==i]
        if len(subset)!=0: # to prevent NaN
            cluster_loss += torch.sum(subset[:,i])

    cluster_loss.backward()
    print(cluster_loss.item())

    with torch.no_grad():
        kmean_centroids -= lr * kmean_centroids.grad
        kmean_centroids.grad.zero_()

Ответы [ 2 ]

0 голосов
/ 09 июля 2019

Представьте себе: 

t = torch.tensor([-0.0627,  0.1373,  0.0616, -1.7994,  0.8853, 
                  -0.0656,  1.0034,  0.6974,  -0.2919, -0.0456])
torch.argmax(t).item() # outputs 6

Мы увеличиваем t[0] для некоторых, δ близко к 0, будет ли это обновлять argmax?Не будет, поэтому мы постоянно имеем дело с 0 градиентами.Просто игнорируйте этот слой или предположите, что он заморожен.

То же самое относится к argmin или любой другой функции, в которой зависимая переменная находится в дискретных шагах.

0 голосов
/ 04 марта 2019

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

Почему он работает?Если бы у вас был только один кластер (чтобы операция argmax не имела значения), ваша функция потерь была бы квадратичной с минимальным значением средних точек данных.Теперь с несколькими кластерами вы можете видеть, что ваша функция потерь кусочно (в более высоких измерениях думать объемно) квадратичной - для любого набора центроидов [C1, C2, C3, ...] каждая точка данных назначается некоторому центроиду CN, а потеря локально квадратичный.Степень этого местоположения определяется всеми альтернативными центроидами [C1', C2', C3', ...], для которых присвоение, исходящее из argmax, остается неизменным;в пределах этой области argmax может рассматриваться как константа, а не функция, и, следовательно, производная от loss четко определена.

Теперь, на самом деле, вряд ли вы сможете обработать argmaxкак константа, но вы все равно можете рассматривать наивную производную «argmax-is-a-constant» как указывающую приблизительно на минимум, потому что большинство точек данных, вероятно, действительно принадлежат к одному кластеру между итерациями.И как только вы подобрались достаточно близко к локальному минимуму, так что точки больше не меняют свои назначения, процесс может сходиться к минимуму.

Другой, более теоретический способ взглянуть на это, это то, что вы делаетеаппроксимация максимизации ожидания.Обычно у вас будет шаг «вычислить назначения», который отражается argmax, и шаг «свести к минимуму», который сводится к поиску минимизирующих центров кластеров с учетом текущих назначений.Минимум задается d(loss)/d([C1, C2, ...]) == 0, который для квадратичной потери дается аналитически с помощью точек данных в каждом кластере.В вашей реализации вы решаете то же уравнение, но с шагом градиентного спуска.Фактически, если бы вы использовали схему обновления 2-го порядка (Ньютона) вместо градиентного спуска 1-го порядка, вы бы неявно воспроизводили именно базовую ЭМ-схему.

...