Introducción a las RNN.

Es ampliamente conocido que las Redes Neuronales Recurrentes (Recurrent Neural Networks RNN) son la mejor elección a la hora de procesar datos secuenciales. ¿Qué tipo de datos son secuenciales? Podemos considerar para este caso texto, voz, DNA, moléculas, lineas de tiempo, etc. Como vemos este tipo de redes son muy útiles. Dos tareas comunes para trabajar con estos datos son: segmentar los datos de entrada y asignar anotación a los datos. Cada una de estas tareas se suele realizar mediante una red neuronal distinga. En la siguiente imagen vemos cómo por cada entrada xt se obtiene una salida yt donde xtX  y ytY.  

Bidirectional RNN. Fuente

Cada estado hes una unidad RNN, donde las más comunes son LSTMs o GRUs. Para capturar la mayor cantidad de contexto se suele usar dos capas de RNN. Una que lee la secuencia desde el inicio hasta el final (de x0 hasta xn, donde n es el tamaño de la secuencia) y otro desde el final hasta el inicio. Los estados de las dos RNN se concatenan y se calcula la probailidad de salida mediante una función de activación, que en la mayoría de los casos es una función tangente hiperbólica tanh. Evidentemente, el error de estas redes es calculado por una función de error y son corregidas por algún algoritmo de optimización, cómo puede ser el Algoritmo de la Gradiente Descendiente. 

Redes Neuronales Recurrentes Segmentacionales (SRNN)

Ahora que tenemos la base de las redes neuronales veamos de qué se tratan las SRNN. Aquí se combina el aprendizaje de representación y el aprendizaje de estructuras. En general se trata de lo siguiente: una RNN bidireccional hace el embedding de segmentos convenientes de la entrada a un espacio continuo, y estos embeddings son usados para calcular la compatibilidad de cada segmento candidato con una etiqueta de anotación. Al realizar esto, las SRNN son una variante de los CRFs de semi-Markov, dado que definen a una distribución de probabilidad condicional sobre un espacio de salida dada la entrada.  Esto permite modelar específicamente dependencias estadísticas como son los tamaños de los segmentos y las etiquetas adjacentes. Lo interesante de este modelo es que dado los valores de probabilidad se pueden descomponer en potenciales de estructuras de cadena, es posible usar algoritmos de programación dinámica para estimar los parámetros y realizar las predicciones. 

Los parámetros pueden ser aprendidos, ya sea con objetivos completamente supervisados (con delimitaciones de segmentación y etiquetas) y semi-supervisado, donde las delimitaciones de segmento están latentes. A continuación veremos el modelo en fórmulas, además de mostrar el código necesario que implementa cada parte que se va a explicar. Para ello vamos a utilizar PyTorch.

El modelo

A continuación describiremos el modelo SRNN según lo plantea Chung, et. all. (2016). Una SRNN define una distribución conjunta de p(y,z|x) sobre una secuencia de segmentos etiquetados. Cada segmento  es caracterizado por una duración zi Z+  y la etiqueta yi ∈ Y. La secuencia de entrada observada es =〈x1,x2,...,x|x|〉. La duración de cada segmento de acota tal que 

\[ \sum^{|z|}_{i=1}z_i=|x| \]

El tamaño de la secuencia de salida |y| = |z| es una variable aleatoria y |y| <= |x| con probabilidad de 1. Veamos ahora qué se busca en el modelo con el problema de predicción:

 

\[ y^*=\arg\max_y p(y|x) = \arg\max_y \sum_z p(y,x|x) \approx \arg \max_y \max_z P(y,z|x) (1)\]

 Para el caso de aprendizaje semi-supervisado donde la duración z de los segmentos no es visible a la hora de entrenar, estos serán inferidos como una variable latente. Para ellos se necesita usar una esperanza marginal en el criterio de entrenamiento, tal que:

\[\mathcal{L}=-\log p(y|x) = -\log \sum_z p(y,z|x). (2)\]

Para las pasadas ecuaciones la probabilidad condicional de la secuencia de segmentos etiquetados es:

\[ p(y,z|x)=\frac{1}{Z(x)}\prod^{|y|}_{i=1}\exp{f(y_{i-k:i},z_i,x)}\]

donde Z(x) es apropiada para normalizar la función. Para asegurar que f sea expresiva y asegurar que  sea eficiente computacionalmente para los problemas de marginalización y maximización de las ecuaciones 1 y 2 se usa la siguiente definición de f:

\[ f(y_{i-k:i}, z_i, x_{s_i:s_i+z_i-1})= \mathbf{w}^T \phi(\mathbf{V}[\mathbf{g}_y(y_{i-k});\dots;\mathbf{g}_y(y_i);\mathbf{g}_z(z_i); \overrightarrow{\mathbf{RNN}}(\mathbf{c}_{s_i:s_i+z_i-1});\overleftarrow{\mathbf{RNN}}(\mathbf{c}_{s_i:s_i+z_i-1})]+\mathbf{a})+b. (3)\]

Como ya lo podrán imaginar, las dos RNN que se especifican en la formula son dos redes neuronales recurrentes, donde la primer hace el embedding de la secuencia en dirección hacia adelante, y la segundo lo realiza hacia atrás. Tal cuál se explicó en la introducción de este artículo. Las funciones gy y gz mapean el la etiqueta canidata y la duración de segmento z a un vector que lo representa. La notación a, b, c denotan concatenación de vector. Finalmente, la duración concatenada de segmento, la etiqueta candiata y el embedding del segmento se pasan por una capa de transformación parametrizada por V y una función de activación no lineal φ, que puede ser, por ejemplo una tanh. Con todo esto, se realiza un producto punto con w y adicionado por un escalar b. Este modelo equivale a un semi-Markov CRF computado con una red neuronal.  Para la implementación de la RNN, se puede usar una LSTM. 

La estructura general descrita por la anterior formulación del modelo, es la siguiente:

Ahora veremos cómo se define esta red neuronal en código. Usaremos para ejemplificar el modelo con Python y PyTorch. Las partes de la fórmula de describen dentro del código. 

Primero comenzaremos por definir nuestros tensores de entrada y se les asignará un valor aleatorio. Estas entradas serán las encargadas de contener la variable xi

self.forward_initial = (nn.Parameter(torch.randn(LAYERS_2, 1, SEG_DIM)), nn.Parameter(torch.randn(LAYERS_2, 1, SEG_DIM)))
self.backward_initial = (nn.Parameter(torch.randn(LAYERS_2, 1, SEG_DIM)), nn.Parameter(torch.randn(LAYERS_2, 1, SEG_DIM)))

También necesitaremos definir los tensores donde se guardaran los encodings de los valores de salida y y z.

self.Y_encoding = [nn.Parameter(torch.randn(1, 1, TAG_DIM)) for i in range(len(LABELS))]
self.Z_encoding = [nn.Parameter(torch.randn(1, 1, DURATION_DIM)) for i in range(1, DATA_MAX_SEG_LEN + 1)]

Y se registrarán los parámetros en nuestra red general. 

self.register_parameter("forward_initial_0", self.forward_initial[0])
self.register_parameter("forward_initial_1", self.forward_initial[1])
self.register_parameter("backward_initial_0", self.backward_initial[0])
self.register_parameter("backward_initial_1", self.backward_initial[1])
for idx, encoding in enumerate(self.Y_encoding):
  self.register_parameter("Y_encoding_" + str(idx), encoding)
for idx, encoding in enumerate(self.Z_encoding):
  self.register_parameter("Z_encoding_" + str(idx), encoding)

Después se define el tensor de contexto tal cual aparece en la lustración pasada. Este contendrá los valos de c1, c2, ... c|x|, dado que para todo xi de entrada, contamos con un contexto ci. Estos tensores de contexto se utilizan en vez de usar los embeddings directamente de xi . Cada token ci es representado por la concatenación hacia adelante y hacia atrás sobre la secuencia de entras raw. Esto permite que los token sean sensibles al contexto. 

self.forward_context_initial = (nn.Parameter(torch.randn(LAYERS_1, 1, XCRIBE_DIM)), nn.Parameter(torch.randn(LAYERS_1, 1, XCRIBE_DIM)))
self.backward_context_initial = (nn.Parameter(torch.randn(LAYERS_1, 1, XCRIBE_DIM)), nn.Parameter(torch.randn(LAYERS_1, 1, XCRIBE_DIM)))

Ahora vamos a definir las dos redes neuronales que van a hacer el embedding de estas concatenaciones:

self.forward_context_lstm = nn.LSTM(INPUT_DIM, XCRIBE_DIM, LAYERS_1, dropout=DROPOUT)
self.backward_context_lstm = nn.LSTM(INPUT_DIM, XCRIBE_DIM, LAYERS_1, dropout=DROPOUT)

Y registramos los parámetros:

self.register_parameter("forward_context_initial_0", self.forward_context_initial[0])
self.register_parameter("forward_context_initial_1", self.forward_context_initial[1])
self.register_parameter("backward_context_initial_0", self.backward_context_initial[0])
self.register_parameter("backward_context_initial_1", self.backward_context_initial[1])

 Y Finalmente computaremos todo junto en la ecuación 3, caluclando las RNN's definidas ahí y realizando las operaciones con V, W y phi (definido como tangente hyperbólica).

self.forward_lstm = nn.LSTM(2 * XCRIBE_DIM, SEG_DIM, LAYERS_2)
self.backward_lstm = nn.LSTM(2 * XCRIBE_DIM, SEG_DIM, LAYERS_2)
self.V = nn.Linear(SEG_DIM + SEG_DIM + TAG_DIM + DURATION_DIM, SEG_DIM)
self.W = nn.Linear(SEG_DIM, 1)
self.Phi = nn.Tanh()


Inferencia

Para realizar la inferencia de los parámetros del problema descrito anteriormente se debe resolver: encontrar el segmentación y etiquetado más probable para un modelo dado de a una secuencia x; evaluar la función de partición Z(x) y computar los marginales posteriores Z(x,y), que suman sobre todas las segmentaciones compatibles con una secuencia referencia y. Para resolver esto se usará programación dinámica. Como los algoritmos usados para ellos necesitan los embeddings de segmento para adelante y hacia atrás se discutirán primero cómo generarlos.

Sean los estados hi,j desginados por las RNN de la entrada (i,j) en ambas direcciones. Habrá entonces O(|x|2) vectores que tienen que ser computados. Todos del tamaño O(|x|). Esto podría ser computado de manera ingenua en O(|x|3), pero con el siguiente programa dinámico, será posible resolverlo en O(|x|2).

\[ \begin{align} \overrightarrow{\mathbf{h}}_{i,i} &= \overrightarrow{RNN}(\overrightarrow{\mathbf{h}}_0,\mathbf{c}_i) \\ \overrightarrow{\mathbf{h}}_{i,j} &= \overrightarrow{RNN}(\overrightarrow{\mathbf{h}}_{i,j-1},\mathbf{c}_j) \\ \overleftarrow{\mathbf{h}}_{i,i} &= \overleftarrow{RNN}(\overleftarrow{\mathbf{h}}_0,\mathbf{c}_i) \\ \overleftarrow{\mathbf{h}}_{i,j} &= \overleftarrow{RNN}(\overleftarrow{\mathbf{h}}_{i+1,j},\mathbf{c}_i) \end{align} \]

Este algoritmo es ejecutado inicializando los valores en la diagonal que representan los segmentos de tamaño uno y posteriormente va llenando el resto de la matriz. En la práctica se puede poner una cota superior para el tamaño del segmento elegible reduciendo la complejidad de computación a O(|x|).  Esta restricción es especialmente útil para secuencias muy largas como lo son reconocimiento de voz.  

Ahora se va a calcular la segmentación/etiquetado más probable y Z(x). Para una secuencia de entrada x hay 2|x|-1 posibles segmentaciones y O(|Y||x|) diferentes etiquetas para esos segmentos. Una computación exhaustiva se hace imposible. Pero la función de partición Z(x) puede ser computada en tiempo polinomial con el siguiente programa dinámico: 

 

\[ \begin{align} \alpha_0 &= 1 \\ \alpha_j &= \sum_{i<j}\alpha_i \times \sum_{y\in Y}(\exp \mathbf{w}^T \phi(\mathbf{V}[\mathbf{g}_y(y_{i-k});\dots;\mathbf{g}_y(y_i);\mathbf{g}_z(z_i); \overrightarrow{\mathbf{RNN}}(\mathbf{c}_{s_i:s_i+z_i-1});\overleftarrow{\mathbf{RNN}}(\mathbf{c}_{s_i:s_i+z_i-1})]+\mathbf{a})+b) \end{align} \]

 Después de computar estos valores. Z(x)=α|x|. Cambiando la suma por el operador max y almacenando los correspondientes argmax, el máximo a posteriori para segmento/etiqueta puede ser calculado. Tanto el cálculo de la función de partición Z(x) cómo la búsqueda por las salidas mapeadas corren en tiempo O(|x|2 |Y|).

Veamos ahora cómo se realiza el aprendizaje del modelo. La primer forma de hacerlo es completamente supervisado, eso quiere decir que se contarán con los datos de z e y al momento de entrenar. 

 

\[ \begin{align} \mathcal{L} &= \sum_{(\mathcal{x},\mathbf{y},\mathbf{z})\in \mathcal{D}} -\log p(\mathbf{y}, \mathbf{z} | \mathbf{x}) \\ &= \sum_{(\mathcal{x},\mathbf{y},\mathbf{z})\in \mathcal{D}} \log Z(\mathbf{x}) -\log Z(\mathbf{y}, \mathbf{z} | \mathbf{x}) \\ \end{align} \]

La probabilidad condicional no normalizada de la referencia segmentación/etiquetado dada una entrada x es escrita como Z(x,y,z). 

Hora bien, para un entrenamiento parcialmente supervisado, donde no se verá a la hora de entrenar el valor de z, esta será tomada como variable latente. 

 

\[ \begin{align} \mathcal{L} &= \sum_{(\mathcal{x},\mathbf{y})\in \mathcal{D}} -\log p(\mathbf{y} | \mathbf{x}) \\ &= \sum_{(\mathcal{x},\mathbf{y})\in \mathcal{D}} \sum_{\mathbf{z}\in Z(\mathcal{x},\mathbf{y})\in \mathcal{D}} -\log p(\mathbf{y}, \mathbf{z} | \mathbf{x}) \\ &= \sum_{(\mathcal{x},\mathbf{y})\in \mathcal{D}} -\log Z(\mathbf{x}) - log Z(\mathbf{x}, \mathbf{y}) \end{align} \]

 

Apuntes finales.

Ahora que ya se tiene una presentación formal del modelo de Redes Neuronales Recurrentes Segmentacionales (SRNN) y se conoce su uso, invitamos a los lectores a implementar su propio sistema a todas las tareas que así crean convenientes. Para tener una mejor idea acerca del modelo también compartimos implementaciones un Python y C++.

Esperamos esta breve introducción les haya servido para su trabajo. 

Referencias

Chung, J., Ahn, S., & Bengio, Y. (2016). Hierarchical multiscale recurrent neural networks. arXiv preprint arXiv:1609.01704.

 

 

 

Share This