Lote vs pendiente gradiente incremental

Question

Estoy estudiando el Aprendizaje de Máquina, pero creo que ustedes deben ser capaces de ayudarme con esto!

Básicamente, hemos dado un conjunto de datos de entrenamiento $\{(x_1,y_1), x(x_2,y_2), ..., (x_n, y_n)\}$, y tenemos que entrenar a un tipo perceptrón para ajustar los datos de la mejor forma posible. Un tipo perceptrón aquí, es un modelo simple que consiste en un vector de peso $w$, y el tipo perceptrón salidas $w^Tx$, para una entrada $x$.

Definimos una función de error $ E(w) = \frac{1}{2N} \sum_{i=1}^{N}(t_d - o_d)^2$ donde $t_d - o_d$ es simplemente la diferencia entre el ideal de valor de la meta, y nuestra salida, $w^Tx$.

Una manera de minimizar el error para el cálculo del gradiente, y obtenemos

$\frac{\partial E}{\partial w_i} = \frac{1}{N} \sum_{i=1}^{N}(t_d - o_d)(-x_{id})$

Ahora, en un algoritmo de computadora, puedo, en cada iteración, la actualización de cada una de las $w_i$ a $w_i + \eta \frac{\partial E}{\partial w_i}$, pero el problema es que la computación que es lento, ya que se extiende sobre el conjunto de entrenamiento conjunto de datos.

Así, lo que se ha inventado, es el LMS (Least Mean Squares) de la regla, que afirma que

$\frac{1}{N} \sum_{i=1}^{N}(t_d - o_d)(-x_{id}) \approx (t_d - o_d)(-x_{id}) $

lo que significa que puedo usar el de la formación actual de ejemplo para realizar mi gradiente de la pendiente.

Ahora, después de esta introducción, me gustaría pedir un poco más de la intuición y de la formalidad detrás de este LMS de la regla, y por qué es una buena aproximación. Supongo que me gustaría un poco más de explicación sobre el $\approx$ parte de la ecuación anterior, y cuándo, y cuánto tiene. Gracias por la ayuda.

Answer 1

Una cosa que le falta es que normalmente perceptrones son formulados como clasificadores binarios. Normalmente, existe un umbral en $w^Tx$, por ejemplo,$\mathrm{sign}(w^Tx)$, el cual $t_d$, $o_d$ son 1 o -1 (o, equivalentemente, 0 o 1 si se utiliza $\mathbb{I}(w^Tx > 0)$; efectivamente funciona de la misma).

La respuesta corta es que no es una gran aproximación, en un sentido absoluto. Se garantiza la convergencia a algunos de peso vector que produce cero error de clasificación, si cualquier vector existe. No hay garantías acerca de cuánto tiempo le tomará para llegar allí (y no hay ninguna garantía de que cualquier paso siempre será hacer que su tasa de error de ir hacia abajo), y en general de tales métodos (esto es un ejemplo de una aplicación más general método conocido como "estocástico de gradiente de la pendiente") han terrible asintótico de las propiedades de convergencia (pero todavía son utilizados por otras razones).

Las notas de Geoff Hinton del curso de pregrado tienen alguna información útil sobre el tema (con la necesaria SVM-bashing). Si desea una prueba formal en Google para "tipo perceptrón convergencia" de la "prueba". De ello se desprende del hecho de que si las clases son linealmente separables, entonces el conjunto de vectores de peso que cero error en el entrenamiento (normalmente habrá una infinidad de) forma una región convexa en peso de espacio.

Answer 2

Me enteré de que el tipo perceptrón sólo funciona en un ejemplo en un momento y la actualización no se realiza basado en el gradiente decente, pero simplemente por error. Básicamente, si usted adivinar el ejemplo de la etiqueta correctamente usted no hace nada, si adivina incorrectamente actualizar el peso de los parámetros vinculados con la etiqueta equivocada hacia abajo una y la correcta etiqueta hacia arriba, donde uno es su tamaño de paso.

Lo que usted acaba de describir suena como lo que he aprendido como la regresión logística.

Aquí está la literatura que he aprendido de.

http://www.cc.gatech.edu/~jeisenst/clases/cs7650_sp12/lec2.pdf

Tengo el código para el tipo perceptrón en python si que sería útil, pero es bastante feo e indocumentados. Hay probablemente el mejor de código abierto alrededor.

Sin embargo, todo esto podría depender de la semántica de su clase, para tomar con un grano de sal.

PS. por una razón formal por qué de su no es tan malo para suponer que la suma es aproximadamente igual a cualquier muestra dada, probablemente debería mirar a las estadísticas y a la ley de grandes muestras. Más muestras de la distribución de la mayor es la probabilidad de que las muestras se representan la distribución original. Si esta ruta te interesa me pueden enviar un documento donde bayes modelos son entrenados con montey carlo técnicas.

Answer 3

Aquí está mi conjetura acerca de lo que está pasando. Nos gustaría elegir a $w$ a minimizar \begin{equation} C(w) = \frac12 \mathbb E \left[(w^T x - y)^2 \right]. \end{equation} Para minimizar $C$ por gradiente de la pendiente, tenemos que ser capaces de evaluar \begin{equation} \nabla C(w) = \mathbb E \left[(w^T x - y)x \right]. \end{equation} Por desgracia, no sabemos $\mathbb E \left[(w^T x - y)x \right] \, \,$ , pero podemos aproximar utilizando nuestros datos de entrenamiento $\{(x_i,y_i) | 1 \leq i \leq N\}$.

La más obvia aproximación a usar es \begin{equation} \mathbb E \left[(w^T x - y)x \right] \approx \frac{1}{N} \sum_{i=1}^N (w^T x_i - y_i) x_i. \end{equation} Sin embargo, esa aproximación es caro si $N$ es enorme, y nos gustaría actualización de $w$ inmediatamente tan pronto como los nuevos datos de entrenamiento llega, sin tener que rehacer el cálculo completo. Así, una aproximación es más barato \begin{equation} \mathbb E \left[(w^T x - y)x \right] \approx (w^T x_i - y_i) x_i \end{equation} donde $(x_i,y_i)$ es una formación particular de vectores (y etiqueta), quizá la que llegaron más recientemente.

Esta aproximación no es tan buena, pero es menos costoso.