python - LabelPropagation - 如何避免被零除？

Question

使用 LabelPropagation 时，我经常遇到这个警告(恕我直言，这应该是一个错误，因为它完全无法传播):

/usr/local/lib/python3.5/dist-packages/sklearn/semi_supervised/label_propagation.py:279: RuntimeWarning: invalid value encountered in true_divide self.label_distributions_ /= normalizer

所以在尝试了几次 RBF 内核后，我发现参数 gamma 有影响。

编辑:

问题来自these lines :

        if self._variant == 'propagation':
            normalizer = np.sum(
                self.label_distributions_, axis=1)[:, np.newaxis]
            self.label_distributions_ /= normalizer

我不明白 label_distributions_ 怎么可以全为零，尤其是当它的定义是:

self.label_distributions_ = safe_sparse_dot(
graph_matrix, self.label_distributions_)

Gamma 对 graph_matrix 有影响(因为 graph_matrix 是调用内核函数的 _build_graph() 的结果)。好的。但还是。出了点问题

旧帖(编辑前)

我提醒你如何为传播计算图权重:W = exp(-gamma * D), D 数据集所有点之间的成对距离矩阵。

问题是:np.exp(x) 如果 x 非常小则返回 0.0。
假设我们有两个点 i 和 j 使得 dist(i, j) = 10。

>>> np.exp(np.asarray(-10*40, dtype=float)) # gamma = 40 => OKAY
1.9151695967140057e-174
>>> np.exp(np.asarray(-10*120, dtype=float)) # gamma = 120 => NOT OKAY
0.0

实际上，我不是手动设置 Gamma ，而是使用this paper 中描述的方法。 (第 2.4 节)。

那么，如何避免这种除以零来获得正确的传播？

我能想到的唯一方法是在每个维度上标准化数据集，但是我们会丢失数据集的一些几何/拓扑属性(例如，2x10 的矩形变成 1x1 的正方形) p>

---

可重现的例子:

在这个例子中，最糟糕的是:即使 gamma = 20，它也会失败。

In [11]: from sklearn.semi_supervised.label_propagation import LabelPropagation

In [12]: import numpy as np

In [13]: X = np.array([[0, 0], [0, 10]])

In [14]: Y = [0, -1]

In [15]: LabelPropagation(kernel='rbf', tol=0.01, gamma=20).fit(X, Y)
/usr/local/lib/python3.5/dist-packages/sklearn/semi_supervised/label_propagation.py:279: RuntimeWarning: invalid value encountered in true_divide
  self.label_distributions_ /= normalizer
/usr/local/lib/python3.5/dist-packages/sklearn/semi_supervised/label_propagation.py:290: ConvergenceWarning: max_iter=1000 was reached without convergence.
  category=ConvergenceWarning
Out[15]: 
LabelPropagation(alpha=None, gamma=20, kernel='rbf', max_iter=1000, n_jobs=1,
         n_neighbors=7, tol=0.01)

In [16]: LabelPropagation(kernel='rbf', tol=0.01, gamma=2).fit(X, Y)
Out[16]: 
LabelPropagation(alpha=None, gamma=2, kernel='rbf', max_iter=1000, n_jobs=1,
         n_neighbors=7, tol=0.01)

In [17]: 

Answer 1

基本上你是在做一个 softmax 函数，对吧？

防止softmax上溢/下溢的一般方法是(来自here)

# Instead of this . . . 
def softmax(x, axis = 0):
    return np.exp(x) / np.sum(np.exp(x), axis = axis, keepdims = True)

# Do this
def softmax(x, axis = 0):
    e_x = np.exp(x - np.max(x, axis = axis, keepdims = True))
    return e_x / e_x.sum(axis, keepdims = True)

这将 e_x 限制在 0 和 1 之间，并确保 e_x 的一个值将始终为 1(即元素 np .argmax(x))。这可以防止上溢和下溢(当 np.exp(x.max()) 大于或小于 float64 可以处理时)。

在这种情况下，由于您无法更改算法，因此我将输入 D 并使 D_ = D - D.min() 应为在数值上等同于上述内容，因为 W.max() 应该是 -gamma * D.min() (因为您只是在翻转符号)。关于 D_

的算法

编辑:

按照下面@PaulBrodersen 的建议，您可以基于 sklearn 实现 here 构建“安全”的 rbf 内核:

def rbf_kernel_safe(X, Y=None, gamma=None): 

      X, Y = sklearn.metrics.pairwise.check_pairwise_arrays(X, Y) 
      if gamma is None: 
          gamma = 1.0 / X.shape[1] 

      K = sklearn.metrics.pairwise.euclidean_distances(X, Y, squared=True) 
      K *= -gamma 
      K -= K.max()
      np.exp(K, K)    # exponentiate K in-place 
      return K 

然后在你的传播中使用它

LabelPropagation(kernel = rbf_kernel_safe, tol = 0.01, gamma = 20).fit(X, Y)

可惜我只有v0.18，不接受LabelPropagation的用户自定义内核函数，所以无法测试。

EDIT2:

检查您的来源以了解为什么您有如此大的 gamma 值让我想知道您是否使用了 gamma = D.min()/3，这是不正确的。定义是sigma = D.min()/3 而w中sigma的定义是

w = exp(-d**2/sigma**2)  # Equation (1)

这将使正确的 gamma 值 1/sigma**2 或 9/D.min()**2