我在pytorch中使用渐变下降在质心位置上构建Kmeans,而不是期望最大化。损失是每个点到其最近质心的平方距离的总和。为了确定哪个质心最接近每个点,我使用argmin,这在任何地方都是不可区分的。但是,pytorch仍然可以反向提升并更新权重(质心位置),从而在数据上提供类似的sklearn kmeans性能。
任何想法如何工作,或如何在pytorch中解决这个问题?关于pytorch 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_()
正如alvas在评论中指出的那样,argmax
是不可区分的。但是,一旦计算并将每个数据点分配给一个集群,就可以很好地定义相对于这些集群位置的损失导数。这就是你的算法所做的。
它为什么有效?如果你只有一个集群(这样argmax
操作无关紧要),你的损失函数将是二次的,数据点的平均值最小。现在有了多个聚类,你可以看到你的损失函数是分段的(在更高维度上认为是体积方向的)二次方 - 对于任何一组质心[C1, C2, C3, ...]
,每个数据点被分配给一些质心CN
并且损失是局部二次的。这个地方的范围是由所有替代质心[C1', C2', C3', ...]
给出的,来自argmax
的任务保持不变;在这个区域内,argmax
可以被视为常数而不是函数,因此loss
的导数是明确定义的。
现在,实际上,你不太可能将argmax
视为常数,但你仍然可以将天真的“argmax-is-a-constant”导数视为指向最小值,因为大多数数据点可能确实属于迭代之间的相同集群。一旦你足够接近局部最小值,使点不再改变它们的分配,过程可以收敛到最小。
另一个更理论化的方法是,你正在做一个期望最大化的近似值。通常,您将拥有“计算分配”步骤(由argmax
镜像)和“最小化”步骤,该步骤归结为在给定当前分配的情况下找到最小化的聚类中心。最小值由d(loss)/d([C1, C2, ...]) == 0
给出,对于二次损失,通过每个簇内的数据点进行分析。在您的实现中,您将使用梯度下降步骤求解相同的等式。实际上,如果您使用二阶(牛顿)更新方案而不是一阶梯度下降,那么您将隐式地再现基线EM方案。
想象一下:
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
或其中因变量处于不连续步骤的任何其他函数也是如此。