Mostrando entradas con la etiqueta Machine learning. Mostrar todas las entradas
Mostrando entradas con la etiqueta Machine learning. Mostrar todas las entradas

26 abr 2021

Álgebra Lineal Parte 2/4: Valores propios, vectores propios y subespacios propios

Posted on   by

En esta entrada vamos a regresar a la pregunta original que motivó nuestra discusión de los valores propios y vectores propios en primer lugar: dada una transformación lineal $T: V\to V$ sobre un espacio finito dimensional $V$, ¿Es posible encontrar una base $\beta$ de $V$ tal que la matriz asociada $[T]_{\beta}^{\beta}$ es una matriz diagonal?

Definición 1. Un operador lineal $T:V \to V$ sobre un espacio finito dimensional $V$ es diagonalizable si existe una base $\beta$ de $V$ tal que la matriz asociada $[T]_{\beta}^{\beta}$ es una matriz diagonal.

Esta definición también se puede formular para matrices; si $A$ es una matriz de orden $n\times n$, entonces $A$ es la matriz de $T:F^{n}\to F^{n}$ dada por la multiplicación a izquierda por $A$. En este caso podemos decir que $A$ es diagonalizable cuando $T$ es diagonalizable. De los resultados para cambios de base, esto es equivalente a decir que existe una matriz invertible $Q\in M_{n\times n}(F)$, denominada matriz de cambio de base $Q=[I]_{\beta}^{\gamma}$, para la cual $Q^{-1}A Q = [I]_{\gamma}^{\beta}[T]_{\gamma}^{\gamma}[I]_{\beta}^{\gamma} = [T]_{\beta}^{\beta}$ es una matriz diagonal.

Definición 2. Una matriz $A\in M_{n\times n}(F)$ es diagonalizables sobre $F$ si existe una matriz invertible, $Q\in M_{n\times n}(F)$ para cual $Q^{-1}AQ$ es una matriz diagonal.

Recuerden que hay que tener un particular cuidado con el campo $F$, ya que la diagonalización de una matriz depende parcialmente del campo $F$ sobre el cual se esté trabajando.

Recuerde que se dice que dos matrices $A$ y $B$ de orden $n\times n$ son similares si existe una matriz invertible $n\times n$ tal que $B= Q^{-1}AQ$. Por lo tanto, una matriz es diagonalizable precisamente cuando es similar a una matriz diagonal.

Nuestro objetivo es caracterizar las transformaciones lineales.

Polinomio característico y similaridad. Si $A$ y $B$ son similares, entonces ellas tienen el mismo polinomio característico, determinante, traza y valores propios (y sus valores propios tienen las mismas multiplicidades).

Demostración. Suponga que $B = Q^{-1}AQ$. Para el polinomio característico, se computa simplemente $\det(\lambda I - B) =$ $\det(Q^{-1}(\lambda I)Q - Q^{-1}AQ)=$ $\det(Q^{-1}(\lambda I - A)Q) = $ $ \det(Q^{-1})\det(\lambda I -A)\det(Q)= $ $\det(\lambda I - A)$.

El determinante y la traza son ambos coeficientes para el polinomio característico así que ellos son también iguales.

Finalmente, los valores propios son las raíces del polinomio característico, así que llos son los mismos y ocurren con la misma multiplicidad para $A$ y $B$.

$\Box$

Los vectores propios para matrices similares también esta cercanamente relacionados:

Valores propios y similaridad. Si $B = Q^{-1}AQ$, entonces $v$ es un vector propios de $B$ con valor propio $\lambda$ si y solo si $Qv$ es un vector propio de $A$ con valor propio $\lambda$.

Demostración. Dado que $Q$ es invertible, $v=0$ si y sólo si $Qv=0$. Ahora asumamos que $v\neq 0$. Primero suponemos que $v$ es un vector propio de $B$ con valor propio $\lambda$. Entonces $A(Qv)=Q(Q^{-1}AQ)v=Q(Bv)=Q(\lambda v) = \lambda (Qv)$, esto quiere decir que $Qv$ es un vector propio de $A$ con valor propio $\lambda$.

Inversamente, si $Qv$ es un vector propio de $A$ con valor propio $\lambda$. Entonces $Bv = Q^{-1}A(Qv) = Q^{-1}\lambda (Qv) = \lambda (Q^{-1}Qv) = \lambda v$, así $v$ es un vector propio de $B$ con valor propio $\lambda$.

Corolario. Si $B = Q^{-1}AQ$, entonces los subespacios propios para $B$ tienen las mismas dimensiones como los subespacios propios para $A$.

En esencia, diaganalizabilidad es equivalente a la existencia de una base de vectores propios:

Diagonalizabilidad. Un operador lineal $T:V\to V$ es diagonalizable si y solo si existe una base $\beta$ de $V$ que consiste de vectores propios de $T$.

Demostración. Suponga primero que $V$ tiene una base de vectores propios $\beta = \{v_1, v_2,\dots, v_n\}$ con sus respectivos valores propios $\lambda_1, \lambda_2, \dots, \lambda_n$. Entonces por hipótesis, $T(v_i)=\lambda_i v_i$, y así $[T]_{\beta}^{\beta}$ es la matriz diagonal con entradas en la diagonal principal $\lambda_1,\dots, \lambda_n$.

Inversamente, suponga que $T$ es diagonalizable y sea $\beta = \{v_1,\dots, v_n\}$ una base tal que $[T]_{\beta}^{\beta}$ es una matriz diagonal cuyas entradas son $\lambda_1, \cdots, \lambda_n.$ Entonces por hipótesis, cada $v_1$ es no cero y $T(v_i)=\lambda_i v_i$ para cada $v_i$ es un vector propio de $T$.

$\Box$

Aunque el resultado anterior da una caracterización de las transformaciones diagonalizables, no es enteramente obvio como para determinar que tal bases de vectores propios existe

Resulta que esencialmente se puede verificar esta propiedad en cada espacio propio. Se ha provado antes, que la dimensión de cada $\lambda$ - subespacio propio de $T$ es menor o igual que la multiplicidad de $\lambda$ como una raíz del polinomio característico.

Dado que que el polinomio característico tiene grado $n$, esto quiere decir que la suma de las dimensiones de los $\lambda$ - subespacios no es superios a $n$, y puede ser superior a $n$ solo cuando cada subespacio propio tiene dimensión igual a la multiplicidad de sus correspondientes valores propios.

El objetivo ahora, es mostrar que si cada subespacio propio tiene dimensión igual a la multiplicidad de sus correspondientes valores propios, entonces la matriz será diagonalizable.

Pero para hacer esto, antes se necesita un resultado intermedio acerca de la independencia de los vectores propios que tienen distintos valores propios.

Independencia de los vectores propios. Si $v_1$, $v_2$,..., $v_n$ son vectores propios de $T$ asociados a los distintos valores propios $\lambda_1, \lambda_2, \dots, \lambda_n$ cuando $v_1,\dots, v_{n}$ son linealmente independientes.

Demostración. Razonando por inducción sobre $n$. Es caso base para $n=1$ es trivial, dado que por definición un vector propio no puede ser zero. Suponga ahora que $n\leq 2$ y eque se tiene la dependencia lineal $a_1v_1+\cdots + a_nv_n=0$ para los vectores propios $v_1, \dots, v_n$ teniendo distintos valores propios $\lambda_1, \cdots \lambda_n$.

Aplicando ahora $T$ a ambos lados $T(a_1v_1+\cdots + a_nv_n) = a_1(\lambda_1 v_1) +\cdots + a_n(\lambda_n v_n) = 0$. Pero si ahora restamos la dependencia original por un factor de $\lambda_1$ se ontiene la nueva relacipon:

\begin{equation} a_2(\lambda_2-\lambda_1)v_2 + a_3(\lambda_3 - \lambda_1)v_3 + \cdots a_n(\lambda_n - \lambda_1)v_n = 0. \end{equation}

Por la hipótesis inductiva, todos los coeficientes de esta dependencia debe ser cero, y así se tienen $\lambda_k \neq \lambda_1$ para cada $k$, así se concluye que $a_2 = \cdots = a_n = 0$. Entonces $a_1 v_1 = 0$ implica que $a_1 = 0$, con lo que se concluye la prueba.

$\Box$

A continuación vamos a formalizar la noción de tener todos los valores propios en $F$.

Definición. Si $p(x)\in F[x]$, se dice que $p(x)$ es factorizable en $F$ si $p(x)$ se puede escribir como el producto de factores lineales en $F[x]$, es decir $p(x)=a(a-r_1)(x-r_2)\cdot\cdots \cdot(x-r_d)$ para algún $a, r_1, r_2, \dots, r_d\in F$.

Informalmente, un polinomio es factorizable sobre $F$ cuando todas sus raíces son elementos de $F$.

Ejemplo 1. El polinomio $x^2 -2$ no es factorizable en $\mathbb{Q}$, pero si es completamente factorizable sobre $\mathbb{R}$ dado que se puede escribir $x^2-2 =(x-\sqrt{2})(x-\sqrt{2})\in \mathbb{R}[x]$. Observe que las raíces $\sqrt{2}$ y $-\sqrt{2}$ del polinomio no son elementos de $\mathbb{Q}$ pero si son elementos de $\mathbb{R}$.

Ejemplo 2. El polinomio $x^2-1$ es factorizable sobre $\mathbb{Q}$, dado que se puede escribir $x^2-1 = (x-1)(x+1)$ en $\mathbb{Q}[x]$.

Si $A$ es una matriz de orden $n\times n$, se dice que todos sus valores propios están en $F$ cuando el polinomio característico de $A$ es factorizable en $F$.

Ahora vamos a establecer un criterio de diagonalización de matrices:

Creterio de diagonalización. Una matriz $A\in M_{n\times n}(F)$ es diagonalizable sobre $F$ si y solo si todos los valores propios están den $F$, y para cada valor propio $\lambda$, la dimensión del $\lambda$ - espacio es igual a la multplicidad de $\lambda$ como una raíz del polinomio característico.

Demostración. Si la matriz $A$ de orden $n\times n$ es diagonalizable, entonces las entradas de la diagonal de sus diagonalización son los valores propios de $A$, así ellos deberán estár en el campo escalar $F$.

Además, por teorema anterior sobre diagonalización, $V$ tiene una base $\beta$ de vectores propios para $A$. Ahora, para cualquier valor propio $\lambda_i$ de $A$, sea $b_i$ el número de elementos de $\beta$ que tienen valor propio $\lambda_i$, y sea $d_i$ la multiplicidad de $\lambda_i$ como una raíz del polinomio característico.

Por lo tanto $\sum_i b_i = n$ dado que $\beta$ es una base para $V$, y $\sum_i d_i = n$, de los resultados anteriores el polinomio característico $b_i \leq d_i$. Por lo tanto $n = \sum_i b_i \leq \sum_i d_i = n$, así $b_i = d_i$ para cada $i$.

Por otro lado, suponga que los valores propios de $A$ están en $F$ y que $b_i = d_i$ para todo $i$. Entonces sea $\beta$ la unión de las bases para cada subespacio propio de $A$. Por hipótesis, $\beta$ contiene $\sum_i b_i = \sum_i d_i = n$ vectores, así se concluye que es una base $n$ - dimensional para el espacio $V$, ahora solo debemos demostrar que son linealmente indipendientes.

Explicitamente, sea $\beta_i = \{v_{i, 1}, \dots, v_{i, j_i}\}$ la base de los $\lambda_i$ - subespacios para cada $i$, así que $\beta = \{v_{1, 1}, v_{1, 2},\dots, v_{k, j}\}$ y $Av_{i, j} = \lambda_i v_{i, j}$ para cada par $(i, j)$.

Suponga que hay dependencia $a_{1, 1} v_{1, 1} + \cdots + a_{k, j} = 0$. Sea $w_i = \sum_{j} a_{i, j} v_{i, j}$, y observe que $w_i$ tiene $Aw_i = \lambda_i w_i$, y sea $w_1 + w_2 +\cdots + w_k = 0$.

Si alguno de los $w_i$ es no nulo, entonces se tendría un dependecia linela no trivial entre los valores propios de $A$ con distinto valores propios, pero estos es imposible por teorema anterior.

Por lo tanto, cada $w_i=0$, quiere decir que $a_{i, 1}v_{i, 1}+\cdots + a_{k, j_i}v_{i, j_i} = 0$. Pero como $\beta_i$ es linealmente independiente, todos los coeficientes $a_{i, j}$ deben ser cero. Por lo tanto, $\beta$ debe ser linealmente independiente y por lo tanto es una base para $V$.

$\Box$

Corolario. Si $A\in M_{n\times n} (F)$ tiene $n$ valores propios distintos en $F$, entonces $A$ es diagonalizable sobre $F$.

Demostración. Para cada valor propio se debe tener multiplicidad uno como una raíz del polinomio característico. Dado que hay $n$ valores propios y la suma de sus multiplicidades es también $n$. Entonces la dimensión de cada valor propio es igual a uno (dado que la dimensión siempre está entre uno y la multiplicidad). Así por el teorema anterior, $A$ es diagonalizable.

$\Box$

La prueba del teorema de diagonalización da un procedimiento explicito para determinar la diagonalizabilidad y la diagonalización de una matriz. Para determinar cuando una transformación lineal $T$ (o matriz) es diagonalizable, y hallar una base $\beta$ tal que $[T]_{\beta}^{\beta}$ es diagonal (o una matriz $Q$ con $Q^{-1}AQ$ diagonal), se siguen los siguientes pasos:

  1. Encontrar el polinomio característico y los valores propios de $T$ (o $A$).
  2. Encontrar una base para cada subespacio propio de $T$ (o A).
  3. Determinar si $T$ (o $A$) es diagonalizable. Si la dimensión de cada subespacio propio es igual a número de veces que los valores propios aparecen como raíces del polinomio característico, en otro caso $T$ es no diagonalizable.
  4. Para una transformación lineal $T$ diagonalizable, sea $\beta$ una base de los vectores propios para $T$. Para una matriz $A$, la matriz $Q$ de diagonalización puede ser tomada como la matriz cuyas columnas son una base de vectores propios de $A$.

Ejemplo 3. Para $T:\mathbb{R}^{2}\to \mathbb{R}^{2}$ dado por $T(x, y)=\langle -2y, 3x + 5y\rangle$, determinar cuando $T$ es diagonalizable y si es así, hallar una base $\beta$ tal que $[T]_{\beta}^{\beta}$ es diagonal.

La matriz $A$ asociada para $T$ relativa a la base estandar es:

In [1]:
from sympy import Matrix, factor
In [2]:
A = Matrix([[0, -2], [3, 5]])

Computamos el polinomio característico

In [3]:
polynomial = A.charpoly()
factor(polynomial.as_expr())
Out[3]:
$\displaystyle \left(\lambda - 3\right) \left(\lambda - 2\right)$

Por lo tanto los valores propios son $\lambda = 2, 3$. Datoa que los valores propios son distintos, entonces $T$ es diagonalizables.

Usaremos la siguiente función para calcular las transformaciones $T_\lambda = \lambda I - A$:

In [4]:
from sympy import eye
def eigen_transformation(eigenvalue, A):
    identity = eye(A.shape[0])
    return eigenvalue * identity - A
In [5]:
T_2 = eigen_transformation(eigenvalue=2, A=A)
In [6]:
T_3 = eigen_transformation(eigenvalue=3, A=A)

Luego los espacios propios para las transformaciones propias $T_2$ y $T_3$ son:

In [7]:
T_2.nullspace()
Out[7]:
[Matrix([
 [-1],
 [ 1]])]
In [8]:
T_3.nullspace()
Out[8]:
[Matrix([
 [-2/3],
 [   1]])]

Esto quiere decir que $[1, -1]^{\top}$ es una base para el $2$ - subespacio propio, y $[-2, 3]^{\top}$ es una base para el $3$ - subespacio.

Por lo tanto para $\beta = \{[1, -1]^{\top}, [-2, 3]^{\top}\}$, se puede ver que:

\begin{equation} [T]_{\beta}^{\beta} = \begin{bmatrix} 2 & 0 \\ 0 & 3 \end{bmatrix} \end{equation}

En efecto:

In [9]:
Q = Matrix([[1, -2], [-1, 3]])
In [10]:
Q.inv()*A*Q
Out[10]:
$\displaystyle \left[\begin{matrix}2 & 0\\0 & 3\end{matrix}\right]$

Ejemplo 4. Para la matriz $A = \begin{bmatrix} 1 & -1 & -1 \\ 0 & 1 & -1 \\ 0 & 0 & 1 \end{bmatrix}$ determinar si existe una matriz diagonal $D$ y matriz $A$ con $D = Q^{-1}AQ$, y si es así, encontrarla.

In [11]:
from sympy import Matrix, factor
In [12]:
A = Matrix([[1, -1, -1], [0, 1, -1], [0, 0, 1]])

Sus valores propios son:

In [13]:
A.eigenvals()
Out[13]:
{1: 3}

Los valores propios son $\lambda = 1, 1, 1$. Esto se puede comprobar fácilmente debido a que $A$ es una matriz triangular y por lo tanto su polinomio característico es $\det(\lambda I - A) = (\lambda - 1)^3$.

Por otro lado la transformación propio $T_1$ es:

In [14]:
T_1 = eigen_transformation(eigenvalue=1, A=A)
In [15]:
T_1
Out[15]:
$\displaystyle \left[\begin{matrix}0 & 1 & 1\\0 & 0 & 1\\0 & 0 & 0\end{matrix}\right]$

Donde su espacio nulo es:

In [16]:
T_1.nullspace()
Out[16]:
[Matrix([
 [1],
 [0],
 [0]])]

Por lo tanto el $1$ - subespacio propio es generado por $[1, 0, 0]^{\top}$. Dado que la dimensionalidad de este espacio no es igual a la multiplicidad de $\lambda = 1$, entonces la matriz $A$ no es diagonalizable y por lo tanto no existen las matrices $D$ y $Q$.

Ejemplo 5. Para la matriz $\begin{bmatrix} 1 & -1 & 0 \\ 0 & 2 & 0 \\ 0 & 2 & 1 \end{bmatrix}$, determine si existe una matriz diagonal $D$ y una matriz invertible $Q$ tal que $D = Q^{-1}AQ$, si es así, encontrarlas.

In [17]:
from sympy import Matrix, factor
In [18]:
A = Matrix([[1, -1, 0], [0, 2, 0], [0, 2, 1]])
In [19]:
polynomial = A.charpoly()
In [20]:
factor(polynomial.as_expr())
Out[20]:
$\displaystyle \left(\lambda - 2\right) \left(\lambda - 1\right)^{2}$

Así, los valores propios son $\lambda = 1, 1, 2$.

Las tranformaciones propias sociadas respectivamente a cada valor de $\lambda$ son:

In [21]:
T_1 = eigen_transformation(eigenvalue=1, A=A)
In [22]:
T_2 = eigen_transformation(eigenvalue=2, A=A)

Sus respectivos subespacios serían:

In [23]:
T_1.nullspace()
Out[23]:
[Matrix([
 [1],
 [0],
 [0]]),
 Matrix([
 [0],
 [0],
 [1]])]
In [24]:
T_2.nullspace()
Out[24]:
[Matrix([
 [-1/2],
 [ 1/2],
 [   1]])]

Por lo tanto $\{[1, 0, 0]^{\top}, [0, 0, 1]^{\top}\}$ es una base para el $1$ - subespacio propio y $\{[-1, 1, 2]^{\top}$ es una base para el $2$ - subespacio propio.

Dado que la dimensionalidad de cada subespacio propio es igual a su multiplicidad de su respectivo valor propio, entonces $A$ es diagonaizable y se toma a $D$ y $Q$ como:

In [25]:
D = Matrix([[1, 0, 0], [0, 1, 0], [0, 0, 2]])
In [26]:
Q = Matrix([[1, 0, -1], [0, 0, 1], [0, 1, 2]])

Ahora hay que comprobar que $D = Q^{-1}AQ$ y en efecto se tiene:

In [27]:
D == Q.inv()*A*Q
Out[27]:
True

Observación. Se puede tomar tambień las siguientes matrices $D$ y $Q$:

In [28]:
D = Matrix([[2, 0, 0], [0, 1, 0], [0, 0, 1]])
In [29]:
Q = Matrix([[-1, 1, 0], [1, 0, 0], [2, 0, 1]])

Y nuevamente se comprueba que $D = Q^{-1}A Q$.

In [30]:
D == Q.inv()*A*Q
Out[30]:
True

Es decir no hay una razón particular para para preocuparse mucho sobre qué matriz diagonal diagonal, siempre que se organicen los vectores propios y los valores propios de manera correspondiente. También se podría haber utilizado cualquier otra base de los espacios propios para construir $Q$.

Sabiedno que una matriz es diagonalizable, esta puede ser muy útil para realizar algunos cálculos complejos.

Por ejemplo, si $A$ es una matriz diagonalizable con $D = Q^{-1}A Q$, entonces es muy fácil computar cualquier pontencia de $A$. Explicitamente, dado que se puede escribir $A = QD^{-1}$, entonces $A^{k}=(QDQ^{-1})^{k}=QD^{k}Q^{-1}$. Pero como $D$ es diagonal, entonces $D^{k}$ es simplemente una matriz diagonal cuyas entradas son las $k$ potencias de las entradas de $D$.

Ejemplo 5. Si $A = \begin{bmatrix} -2 & -6 \\ 3 & 7 \end{bmatrix}$, encontrar una formula de la $k$ potencia $A^{k}$, para un entero positivo.

In [31]:
from sympy import Matrix, factor, symbols
In [32]:
k = symbols('k')
In [33]:
A = Matrix([[-2, -6], [3, 7]])
In [34]:
A.eigenvals()
Out[34]:
{4: 1, 1: 1}

Los valores propios son $\lambda = 4, 1$. Así las transformaciones propias serían:

In [35]:
T_4 = eigen_transformation(eigenvalue=4, A=A)
In [36]:
T_1 = eigen_transformation(eigenvalue=1, A=A)

Y sus respectivos espacios nulos serían:

In [37]:
T_4.nullspace()
Out[37]:
[Matrix([
 [-1],
 [ 1]])]
In [38]:
T_1.nullspace()
Out[38]:
[Matrix([
 [-2],
 [ 1]])]

Por lo tanto una base para el $4$ - subespacio propio es $\{[-1, 1]^{\top}\}$ y una base para el $1$ - subespacio propio es $\{[-2, 1]^{\top}\}$. Así las matrices $D$ y $Q$ serían:

In [39]:
D = Matrix([[1, 0], [0, 4]])
In [40]:
Q = Matrix([[-2, -1], [1, 1]])

Luego, $D^{k}$ y $A^{k}$ son:

In [41]:
D**k
Out[41]:
$\displaystyle \left[\begin{matrix}1 & 0\\0 & 4^{k}\end{matrix}\right]$
In [42]:
A**k
Out[42]:
$\displaystyle \left[\begin{matrix}2 - 4^{k} & 2 - 2 \cdot 4^{k}\\4^{k} - 1 & 2 \cdot 4^{k} - 1\end{matrix}\right]$

Finalmente, hay que verificar que $A^{k} = QD^{k}Q^{-1}$.

In [43]:
A**k == Q* D**k * Q.inv()
Out[43]:
True

También se puede usar la diagonalización de una matriz para probar nuevos teoremas de una forma más simple. He aquí un ejemplo típico.

Definición. Si $T:V\to V$ es un operador y $p(x) = a_0 + a_1 x+\cdots a_nx^n$ es un polinomio, se define: $$p(T)= a_0 I + a_1 T + \cdots a_n T^{n}.$$ Similarmente, si $A$ es una matriz de orden $n\times n$, se define: $$p(A) = a_0 I + a_1 A + \cdots a_n A^{n}.$$ Es fácil comprobar que $Q^{-1}p(A)Q = p(Q^{-1}AQ)$.

Caley-Hamilton. Si $p(x)$ es el polinómio característico de la matriz $A$, entonces $p(A)$ es la matriz cero.

El mismo se resultado se dá para el polinomio característico del operador lineal $T:V\to V$.

Ejemplo 6. Para la matriz $\begin{bmatrix} 2 & 2 \\ 3 & 1 \end{bmatrix}$, se tiene:

In [44]:
from sympy import Matrix, factor, symbols, eye
In [45]:
A = Matrix([[2, 2], [3, 1]])

con polinomio característico:

In [46]:
A.charpoly().as_expr()
Out[46]:
$\displaystyle \lambda^{2} - 3 \lambda - 4$

Se computar fácilmente $A^{2} - 3 A - 4I_{2}$, en efecto:

In [47]:
A**2 - 3 * A - 4 * eye(2)
Out[47]:
$\displaystyle \left[\begin{matrix}0 & 0\\0 & 0\end{matrix}\right]$

Demostración. Si $A$ es diagonalizable, entonces $D = Q^{-1} A Q$ con $D$ diagonal, y sea $p(x)$ el polinomio característico de $A$. La diagonal de entradas de $D$ son los valores propios $\lambda_1,\dots, \lambda_n$ de $A$. por lo tanto son raíces del polinómio característico, es decir $p(\lambda_1)=\cdots=p(\lambda_n)=0$.

Se puede verificar fácilmente que:

\begin{equation} p(D)=p\left(\begin{bmatrix} \lambda_1 & & \\ &\ddots & \\ & & \lambda_n\end{bmatrix}\right) = \begin{bmatrix} p(\lambda_1) & & \\ &\ddots & \\ & & p(\lambda_n)\end{bmatrix} = \begin{bmatrix} 0 & & \\ &\ddots & \\ & & 0\end{bmatrix}=0. \end{equation}

Luego $p(A) = Q p(D) Q^{-1} = 0$ cómo se quería probar.

En el caso de una matriz $A$ no diagonalizable, la prueba del teorema de Cayley Hamilton es sustancialmente más dificil. Este caso se tratará en la sigueinte sección usando la forma canónica de Jordan.

Bibliografía

  1. Evan Dummit, 2020, Linear Algebra - part 4: Eingenvalues, Diagonalization, and the Jordan Form.
  2. SymPy Development Team. 2021. Sympy 1.8 documetation.

Contacto

  • Participa del canal de Nerve a través de Discord.
  • Se quieres conocer más acerca de este tema me puedes contactar a través de Classgap.

Si el post fue de tu agrado muestra tu apoyo compartiéndolo, suscribiéndote al blog, siguiéndome o realizando una donación.

26 feb 2021

Regresión Logística Multinomial

Posted on   by

Algunas veces es necesario hacer clasificación para más de dos clases. Quizas se quiere clasificar tres formas de sentimientos (positivo, neutral o negativo). Esto se podría hacer analizando el contenido del habla y asignado un etiquetado semático a cada una de las palabras para poder valores el sentimiento del habla, sin embargo en esta publicación no vamos a hablar de esto por ahora. Vamos a dedicar la atención a la regresión logística multinomial o softmax.

En estas situaciones en donde es necesario hacer una clasificación para más de dos clases, se puede hacer uso de la regresión logística multinomial, o tambien regresión softmax. En este tipo de regresión la variable objetivo tiene un rango que varia sobre un conjunto de más de dos clases; el objetivo aquí será determinar cuá es la probabilidad de $y$ de pertenecer a cada una de las clases potenciales $c\in C$, $P(y=c\;|\;x)$.

La regresión logística multinomial clasifica usando una generalización de la función sigmoide, conocida como la función softmax, para calcular la probabilidad $P(y=c\;|\;x)$. La función softmax toma un vector $z=[z_1, z_2, \dots, z_k]^{\top}$ de $k$ valores arbitrarios y los mapea en una distribucción de probalicada, con cada valore en el rango $(0, 1)$, y todos los valores sumando uno. Como la función sigmoide. es una función exponencial.

Para un vector $z$ de dimensionalidad $k$, la función softmax es definida como:

$$s(z_i)=\frac{e^{z_i}}{\sum_{j=1}^{k}e^{z_{j}}},\; 1\leq i\leq k.$$

Así, la función softmax de un vector $z=[z_1, z_2, \dots, z_k]^{\top}$ es por lo tanto una función vectorial:

$$s(z)=\left[\frac{e^{z_1}}{\sum_{j=1}^{k}e^{z_{1}}}, \frac{e^{z_2}}{\sum_{j=1}^{k}e^{z_{2}}},\dots, \frac{e^{z_k}}{\sum_{j=1}^{k}e^{z_{k}}}\right]$$

El denominador $\frac{e^{z_i}}{\sum_{j=1}^{k}e^{z_{j}}}$ es usado para normalizar todos los valores en probabilidades. Por ejemplo:

In [1]:
import numpy as np
from scipy.special import softmax
In [2]:
z = np.array([0.6, 1.1, -1,5, 1.2, 3.2, -1.1])
In [3]:
softmax(z)
Out[3]:
array([0.01002305, 0.01652522, 0.00202362, 0.81638616, 0.01826319,
       0.13494772, 0.00183105])

Otra vez como en la función sigmoide, la entrada de la función softmax puede ser el producto punto entre un vector de pesos $w=(w_0, \dots, w_n)$ y un vector $x=(1, x_1,\dots, x_n$. Pero ahora ese necesario separar el vector de pesos para cada una de las clases.

$$P(y=c\;| \;x)=\frac{e^{w_c^\top x}}{\sum_{j=1}^{k}e^{w_j^\top x}}$$

Como la función sigmoide, la función softmax tiene la propiedad de transformar los valores hacía $0$ o $1$. Pos lo tanto , si una de las entradas es más grande que los otros, tenderá a aumentar su probabilidad hacia $1$, y suprime las probabilidades de las entradas más pequeñas.

Aplicaciones de la regresión logística multinomial

Para la clasificación de los datos de entrada es necesario definir una función que depende de la observación $x$ y de la potencial clase $c$. Para esto se usará la notación $f_i(c, x)$, que indicará el atributo $i$ para una clases particular $c$ dado por la observación $x$.

En clasificación binaria, un peso positivo en una característica apunta hacia $y = 1$ y un peso negativo hacia $y = 0$, pero en la clasificación multiclase una característica podría ser evidencia a favor o en contra de una clase individual.

Veamos algunas características de muestra para algunas tareas de PNL para ayudar a comprender este uso quizás poco intuitivo de características que son funciones tanto de la observación $x$ como de la clase $c$.

Supongamos que estamos haciendo una clasificación de texto y, en lugar de una clasificación binaria, nuestra tarea es asignar una de las 3 clases A, B o C (neutral) a un documento. Ahora, una función relacionada con los signos de exclamación puede tener un peso negativo para C documentos y un peso positivo para documentos A o B:

$$f_1(C, x)=\begin{cases}1 & \mbox{ si } ! \notin doc \\ 0 & \mbox{ si } ! \in doc \end{cases},\;w_1 = -4.5$$
$$f_2(A, x)=\begin{cases}1 & \mbox{ si } ! \notin doc \\ 0 & \mbox{ si } ! \in doc \end{cases},\;w_1 = 2.6$$
$$f_3(B, x)=\begin{cases}1 & \mbox{ si } ! \notin doc \\ 0 & \mbox{ si } ! \in doc \end{cases},\;w_1 = 1.3$$

¿Cómo aprende las regresión multinomial logística?

La regresión logística multinomial tiene una función de pérdida ligeramente diferente a la regresión logística binaria porque utiliza el clasificador softmax en lugar del sigmoide. La función de pérdida para un solo ejemplo $x$ es la suma de los registros de las $k$ clases de salida:

$$L_{CE}(\hat{y}, y)=-\sum_{h=1}^{k}\mathbb{1}_{\{y=k\}}\log P(y=k\;|\;x)=-\sum_{k=1}^{k}\mathbb{1}_{\{y=k\}}\log \frac{e^{w_{k}\cdot x + b_{k}}}{\sum_{j=1}^{k}e^{w_j\cdot x + b_{j}}}$$

La expersión $\mathbb{1}_{\{y=k\}}$ toma el valor de uno cuando la condición en las llaves es verdadera y cero en cualquier otro caso.

El gradiente para una muestra es muy similar a el gradiente para la regresión logistica, aunque no se mostrará aquí la derivación. Es la diferencia entre el valor de la clase verdadera $k$ y la probabilidad que el clasificador genera para la clase $k$, ponderada por el valor de la entrada $x_{k}$:

$$\frac{\partial L_{CE}}{\partial w_{k}} = -(\mathbb{1}_{\{y=k\}}-P(y=k\;|\;x))x_{k}=-\left(\mathbb{1}_{\{y=k\}} - \frac{e^{w_{k}\cdot x + b_{k}}}{\sum_{j=1}^{k}e^{w_j\cdot x + b_{j}}}\right)x_k$$

Implementación con Tensorflow - MNIST

MNIST es un conjunto de datos de digitos escritos a mano que se en muchos ejemplos introductorios al machine learning. El conjunto de datos contiene 60000 ejemplos para entrenamiento y 10000 ejemplos para testeo. El tamaño de los digitos ha sido normalizado y la imagen centrada (28 x 28 pixeles) con valores de 0 a 1. Por simplicidad, cada imagen ha sido convertido es una matriz númerica 1-D de 784 características (28 x 28). Para más información http://yann.lecun.com/exdb/mnist/.

Para nuestro ejemplo de regresión logística multinomial usaremos TensorFlow V2 y se implementará a bajo nivel para entender los detalles que hay en el proceso de entrenamiento. Los detalles de este ejemplo se puede encontrar en TensorFlow Examples - GitHub

In [4]:
import tensorflow as tf
import numpy as np

A continuación se definen las características generales de los datos:

In [5]:
num_classes = 10
num_features = 784

También se definen los parámetros de entrenamiento:

In [6]:
learning_rate = 0.01
training_steps = 1000 
batch_size = 256

Lectura de los datos

Se cargan los datos y se identifican el conjunto de entrenamiento y el de testeo:

In [7]:
from tensorflow.keras.datasets import mnist
(x_train, y_train), (x_test, y_test) = mnist.load_data()

Para visualizar algunos ejemplos hacemos uso de matplotlib de la siguiente forma:

In [8]:
import matplotlib.pyplot as plt
In [9]:
plt.imshow(x_train[5], cmap='gray')
plt.show
Out[9]:
<function matplotlib.pyplot.show(close=None, block=None)>

Preparación de los datos

Estadarización del tipo de dato:

In [10]:
x_train, x_test = np.array(x_train, np.float32), np.array(x_test, np.float32)

Transformación de los datos a vectores de 784 características:

In [11]:
x_train, x_test = x_train.reshape([-1, num_features]), x_test.reshape([-1, num_features])

Normalización de los datos de [0, 255] a [0, 1]:

In [12]:
x_train, x_test = x_train / 255., x_test / 255.

A continuación particionamos los datos por lotes y los mezclamos:

In [13]:
train_data = tf.data.Dataset.from_tensor_slices((x_train, y_train))
train_data = train_data.repeat().shuffle(5000).batch(batch_size).prefetch(1)

Construcción del módelo:

In [14]:
W = tf.Variable(tf.ones([num_features, num_classes]), name="weight")
b = tf.Variable(tf.zeros([num_classes]), name="bias")

Regresión logistica de (Wx + b):

In [15]:
def logistic_regression(x):
    return tf.nn.softmax(tf.matmul(x, W) + b)

La función de costo en este caso sería:

In [16]:
def cross_entropy(y_pred, y_true):
    y_true = tf.one_hot(y_true, depth=num_classes)
    y_pred = tf.clip_by_value(y_pred, 1e-9, 0.9)
    return tf.reduce_mean(-tf.reduce_sum(y_true * tf.math.log(y_pred) + (1 - y_true) * tf.math.log(1 - y_pred),1))

La medida que se usará para determinar la calidad del modelo será:

In [17]:
def accuracy(y_pred, y_true):
    correct_prediction = tf.equal(tf.argmax(y_pred, 1), tf.cast(y_true, tf.int64))
    return tf.reduce_mean(tf.cast(correct_prediction, tf.float32))

Para entrenar el modelo, se utilizará el optimizador definido para el gradiente estocástico:

In [18]:
optimizer = tf.optimizers.SGD(learning_rate)
In [19]:
def run_optimization(x, y):
    with tf.GradientTape() as g:
        pred = logistic_regression(x)
        loss = cross_entropy(pred, y)
    
    gradients = g.gradient(loss, [W, b])
    
    optimizer.apply_gradients(zip(gradients, [W, b]))

A continuación, se ejecuta el proceso de entrenamiento:

In [20]:
display_step = 50
for step, (batch_x, batch_y) in enumerate(train_data.take(training_steps), 1):
    run_optimization(batch_x, batch_y)
    
    if step % display_step == 0:
        pred = logistic_regression(batch_x)
        loss = cross_entropy(pred, batch_y)
        acc = accuracy(pred, batch_y)
        print('step: %i, loss: %f, accuracy: %f' % (step, loss, acc))
step: 50, loss: 2.691798, accuracy: 0.707031
step: 100, loss: 2.201120, accuracy: 0.742188
step: 150, loss: 1.926627, accuracy: 0.789062

step: 250, loss: 1.502035, accuracy: 0.812500
step: 200, loss: 1.788280, accuracy: 0.773438
step: 300, loss: 1.421701, accuracy: 0.812500

step: 450, loss: 1.242893, accuracy: 0.847656
step: 350, loss: 1.371978, accuracy: 0.847656
step: 400, loss: 1.382541, accuracy: 0.789062
step: 500, loss: 1.199832, accuracy: 0.839844

step: 700, loss: 0.882333, accuracy: 0.914062
step: 550, loss: 1.111963, accuracy: 0.855469
step: 600, loss: 1.156131, accuracy: 0.828125
step: 650, loss: 1.010465, accuracy: 0.871094
step: 750, loss: 1.011202, accuracy: 0.863281

step: 1000, loss: 1.057235, accuracy: 0.820312
step: 800, loss: 0.971723, accuracy: 0.855469
step: 850, loss: 1.082722, accuracy: 0.832031
step: 900, loss: 0.912813, accuracy: 0.875000

step: 950, loss: 0.927843, accuracy: 0.863281

Finalmente se valida el modelo y se visualizan los resultados:

In [21]:
pred = logistic_regression(x_test)
print("Test Accuracy: %f" % accuracy(pred, y_test))
Test Accuracy: 0.877100
In [22]:
n_images = 2
test_images = x_test[:n_images]
predictions = logistic_regression(test_images)


for i in range(n_images):
    plt.imshow(np.reshape(test_images[i], [28, 28]), cmap='gray')
    plt.show()
    print("Model prediction: %i" % np.argmax(predictions.numpy()[i]))
Model prediction: 7

Model prediction: 2

Conclusiones

En esta ocasión se introduccido los aspectos generales de la regresión logistica multinomial como un modelo de clasificación:

  • La regresión logística multinomial se puede utilizar con dos clases (por ejemplo determinar si un sentimiento es positivo o negativo) o con múltiples clases (por ejemplo la clasificación de libros de acuerdo con un genero literario).
  • Se usa la función softmax para calcular probabilidades.

Bibliografía

Contacto

  • Participa de la canal de Nerve a través de Discord.
  • Se quieres conocer más acerca de este tema me puedes contactar a través de Classgap.
Suscribirse a: Entradas (Atom)