¿Por qué el núcleo de Dirac es semidefinido positivo?

Question

Leí un artículo Núcleo gráfico de Weisfeiler-Lehman . En este documento, dice:

Que el núcleo base $k$ sea una función que cuenta los pares de etiquetas de nodos que coinciden en dos grafos: $k\left(G, G^{\prime}\right)=\sum_{v \in V} \sum_{\nu^{\prime} \in V^{\prime}} \delta\left(\ell(v), \ell\left(v^{\prime}\right)\right)$ , donde $\delta$ es el núcleo de Dirac, es decir, es 1 cuando sus argumentos son iguales y 0 en caso contrario. Entonces $k_{W L}^{(h)}\left(G, G^{\prime}\right)=k_{W L s u b t r e e}^{(h)}\left(G, G^{\prime}\right)$ para todos $G$ , $G'$ .

Creo que la matriz Gram del núcleo de Dirac es una matriz con todos los 1 en la diagonal, y las demás posiciones de la matriz Gram pueden ser 0 o 1. ¿Por qué el kernel de Dirac es un kernel válido? ¿O por qué la matriz de Gram del kernel de Dirac es PSD?

Answer 1

He intentado hacer alguna prueba de la pregunta por mí mismo, pero no estoy muy seguro.

Quiero probar $\delta$ es un núcleo válido. $\delta$ El núcleo se representa de la siguiente manera:

\begin{equation} k\left(v_{1}, v_{2}\right)=\left\{\begin{array}{lr} 1 & \text { if } \ell\left(v_{1}\right)=\ell\left(v_{2}\right) \\ 0 & \text { otherwise } \end{array} \derecho. \Fin de la ecuación.

donde $\ell\left(v_{1}\right)$ es la etiqueta del nodo $v_1$ . Consideramos que $\ell\left(\cdot\right)$ es un mapeo de un solo punto, y entonces la función kernel $k\left(v_{1}, v_{2}\right)$ sea equivalente a $k\left(v_{1}, v_{2}\right) = <onehot(\ell\left(v_{1}\right)), onehot(\ell\left(v_{2}\right))> = <\phi(v_1),\phi(v_2)>$ , donde $\phi: V \to \mathcal{H}$ y $\mathcal{H} = \mathbb{R}^{num\_labels}$ . Por lo tanto, para un conjunto no vacío $V$ , $k$ es un núcleo válido y es psd.

Answer 2

La matriz del núcleo de Dirac es "diagonalmente dominante" (la magnitud del elemento diagonal es mayor que la suma de las magnitudes de los elementos no diagonales de esa fila/columna). Una matriz real simétrica diagonalmente dominante con entradas diagonales no negativas es semidefinida positiva. La dominancia diagonal puede ser problemática para los métodos del núcleo.

En cuanto a por qué es un núcleo válido. Consideremos un espacio de características en el que hubiera una característica correspondiente a cada posible vector de entrada. Así que si su espacio de entrada fuera el espacio de todas las cadenas de longitud, 3 compuestas del alfabeto 'a', 'b' y 'c', entonces el espacio de características tendría una característica que fuera uno si la cadena de entrada fuera 'aaa', y cero en caso contrario, y uno para 'aab', y otro para 'aba', ... y así sucesivamente. El producto interno en ese espacio de características sería el núcleo de Dirac. Un razonamiento similar podría aplicarse a los espacios de entrada continuos, pero requeriría un espacio de características de dimensiones infinitas.

Tenga en cuenta que cuando regularizamos un método de kernel, normalmente estamos añadiendo un múltiplo del kernel de Dirac a la matriz del kernel original, por lo que si no fuera un kernel válido, esa regularización destruiría inmediatamente la interpretación del modelo de kernel como un modelo simple (¿lineal?) construido en un espacio de características fijo inducido por el kernel.

Answer 3

El núcleo de Dirac es un núcleo válido ya que es semidefinido positivo.

En otras palabras, como su matriz es definida positiva, se deduce que el núcleo de Dirac es un núcleo válido. Véase Teorema de Mercer para más referencias.

Para ver que es semidefinida positiva, sólo basta con observar que todas las entradas de la matriz gram son no negativas, es decir, los elementos de la diagonal, ya que se elevarán al cuadrado: $\forall v.\ell(v)^2 \geq 0$