Método de actualización de peso multiplicativo

Dado un juego secuencial entre un adversario y un agregador asesorado por N expertos, el objetivo es que el agregador cometa la menor cantidad de errores posible. Supongamos que entre los N expertos hay un experto que siempre da la predicción correcta. En el algoritmo de reducción a la mitad, solo se conservan los expertos consistentes. Los expertos que cometen errores son descartados. Para cada decisión, el agregador decide mediante votación mayoritaria entre los expertos restantes. Por lo tanto, cada vez que el agregador comete un error, al menos la mitad de los expertos restantes son descartados. El agregador comete como máximo log ₂ ( N ) errores. ^{[ 2 ]}

Fuente: ^{[ 1 ] [ 7 ]}

A diferencia del algoritmo de reducción a la mitad, que descarta a los expertos que han cometido errores, el algoritmo de mayoría ponderada desestima sus consejos. Dado el mismo escenario de "consejo de expertos", supongamos que tenemos n decisiones y necesitamos seleccionar una decisión en cada iteración. En cada iteración, cada decisión conlleva un coste. Todos los costes se revelarán después de tomar la decisión. El coste es 0 si el experto acierta y 1 en caso contrario. El objetivo de este algoritmo es limitar sus pérdidas acumuladas a un valor similar al del mejor de los expertos. El primer algoritmo que toma decisiones basándose en el voto mayoritario en cada iteración no funciona, ya que la mayoría de los expertos pueden equivocarse sistemáticamente. El algoritmo de mayoría ponderada corrige el algoritmo anterior al mantener un peso para los expertos en lugar de fijar el coste en 1 o 0. ^{[ 1 ]} Esto generaría menos errores en comparación con el algoritmo de reducción a la mitad.

Inicialización : Reparar un${\displaystyle \eta \leq 1/2}$. Para cada experto, asocie el peso${\displaystyle {w_{i}}^{1}}$≔1. Para${\displaystyle t}$=${\displaystyle {\mathit {1}}}$,${\displaystyle {\mathit {2}}}$,...,${\displaystyle T}$1. Realizar la predicción dada por la mayoría ponderada de las predicciones de los expertos en función de sus ponderaciones.${\displaystyle \mathbb {w_{1}} ^{t},...,\mathbb {w_{n}} ^{t}}$. Es decir, elige 0 o 1 dependiendo de qué predicción tenga un mayor peso total de expertos que la avalan (resolviendo los empates arbitrariamente). 2 . Por cada experto i que haya predicho erróneamente, disminuye su peso para la siguiente ronda multiplicándolo por un factor de (1-η): ${\displaystyle w_{i}^{t+1}}$=${\displaystyle (1-\eta )w_{i}^{t}}$(actualizar regla)

Si${\displaystyle \eta =0}$, el peso del consejo del experto seguirá siendo el mismo. Cuando${\displaystyle \eta }$A medida que aumenta, el peso del consejo del experto disminuirá. Tenga en cuenta que algunos investigadores fijan${\displaystyle \eta =1/2}$en el algoritmo de mayoría ponderada.

Después${\displaystyle T}$pasos, dejar${\displaystyle m_{i}^{T}}$sea ​​el número de errores del experto i y${\displaystyle M^{T}}$sea ​​el número de errores que ha cometido nuestro algoritmo. Entonces tenemos la siguiente cota para cada${\displaystyle i}$:

${\displaystyle M^{T}\leq 2(1+\eta )m_{i}^{T}+{\frac {2\ln(n)}{\eta }}}$.

En particular, esto se aplica a i, que es el mejor experto. Dado que el mejor experto tendrá el menor${\displaystyle m_{i}^{T}}$Esto proporcionará el mejor límite posible sobre el número de errores cometidos por el algoritmo en su conjunto.

Este algoritmo puede entenderse de la siguiente manera: ^{[ 2 ] [ 8 ]}

Supongamos la misma configuración con N expertos. Consideremos la situación especial en la que las proporciones de expertos que predicen resultados positivos y negativos, contando los pesos, son cercanas al 50%. En ese caso, podría haber un empate. Siguiendo la regla de actualización de pesos del algoritmo de mayoría ponderada, las predicciones del algoritmo serían aleatorias. El algoritmo calcula las probabilidades de que los expertos predigan resultados positivos o negativos y, a continuación, toma una decisión aleatoria basada en la fracción calculada.

predecir

${\displaystyle f(x)={\begin{cases}1&{\text{con probabilidad}}{\frac {q_{1}}{W}}\\0&{\text{en otro caso}}\end{cases}}}$

dónde

${\displaystyle W=\sum _{i}{w_{i}}=q_{0}+q_{1}}$.

El número de errores cometidos por el algoritmo de mayoría ponderada aleatoria está acotado de la siguiente manera:

${\displaystyle E\left[\#{\text{errores del aprendiz}}\right]\leq \alpha _{\beta }\left(\#{\text{errores del mejor experto}}\right)+c_{\beta }\ln(N)}$

dónde ${\displaystyle \alpha _{\beta }={\frac {\ln({\frac {1}{\beta }})}{1-\beta }}}$y ${\displaystyle c_{\beta }={\frac {1}{1-\beta }}}$.

Nótese que solo el algoritmo de aprendizaje es aleatorio. La suposición subyacente es que los ejemplos y las predicciones de los expertos no son aleatorios. La única aleatoriedad es la aleatoriedad donde el aprendiz hace su propia predicción. En este algoritmo aleatorio ,${\displaystyle \alpha _{\beta }\rightarrow 1}$si${\displaystyle \beta \rightarrow 1}$En comparación con el algoritmo ponderado, esta aleatoriedad redujo a la mitad la cantidad de errores que el algoritmo va a cometer. ^{[ 9 ]} Sin embargo, es importante señalar que en algunas investigaciones, las personas definen${\displaystyle \eta =1/2}$en el algoritmo de mayoría ponderada y permitir${\displaystyle 0\leq \eta \leq 1}$en el algoritmo de mayoría ponderada aleatoria . ^{[ 2 ]}

Fuente: ^{[ 1 ] [ 9 ]}

Supongamos que nos dieron la distribución${\displaystyle P}$sobre expertos. Deje${\displaystyle A}$= matriz de pagos de un juego finito de suma cero para dos jugadores, con${\displaystyle n}$filas.

Cuando el jugador de fila${\displaystyle p_{r}}$plan de usos${\displaystyle i}$y el jugador de columna${\displaystyle p_{c}}$plan de usos${\displaystyle j}$, la recompensa del jugador${\displaystyle p_{c}}$es${\displaystyle A\left(i,j\right)}$≔${\displaystyle A_{ij}}$, suponiendo${\displaystyle A\left(i,j\right)\in \left[0,1\right]}$.

Si el jugador${\displaystyle p_{r}}$elige acción${\displaystyle i}$de una distribución${\displaystyle P}$sobre las filas, luego el resultado esperado para el jugador${\displaystyle p_{c}}$seleccionar acción${\displaystyle j}$es${\displaystyle A\left(P,j\right)=E_{i\in P}\left[A\left(i,j\right)\right]}$.

Para maximizar${\displaystyle A\left(P,j\right)}$, jugador${\displaystyle p_{c}}$debería elegir plan${\displaystyle j}$. De manera similar, la recompensa esperada para el jugador${\displaystyle p_{l}}$es${\displaystyle A\left(i,P\right)=E_{j\in P}\left[A\left(i,j\right)\right]}$. Elegir plan${\displaystyle i}$minimizaría esta recompensa. Según el teorema Min-Max de John Von Neumann , obtenemos:

${\displaystyle \min _{P}\max _{j}A\left(P,j\right)=\max _{Q}\min _{i}A\left(i,Q\right)}$

donde P e i cambian sobre las distribuciones sobre las filas, Q y j cambian sobre las columnas.

Entonces, deja${\displaystyle \lambda ^{*}}$denotemos el valor común de las cantidades anteriores, también llamado "valor del juego". Sea${\displaystyle \delta >0}$sea ​​un parámetro de error. Para resolver el juego de suma cero limitado por el error aditivo de${\displaystyle \delta }$,

${\displaystyle \lambda ^{*}-\delta \leq \min _{i}A\left(i,q\right)}$${\displaystyle \max _{j}A\left(p,j\right)\leq \lambda ^{*}+\delta }$

Entonces hay un algoritmo que resuelve el juego de suma cero hasta un factor aditivo de δ usando O( log ₂ ( n ) /${\displaystyle \delta ^{2}}$) llamadas a ORACLE, con un tiempo de procesamiento adicional de O(n) por llamada ^{[ 9 ]}

Bailey y Piliouras demostraron que, si bien el comportamiento promedio en el tiempo de la actualización de pesos multiplicativos converge a equilibrios de Nash en juegos de suma cero, el comportamiento diario (última iteración) diverge de él. ^{[ 10 ]}

En aprendizaje automático, Littlestone y Warmuth generalizaron el algoritmo Winnow al algoritmo de mayoría ponderada. ^{[ 11 ]} Posteriormente, Freund y Schapire lo generalizaron en forma de algoritmo Hedge. ^{[ 12 ]} El algoritmo AdaBoost, formulado por Yoav Freund y Robert Schapire, también empleó el método de actualización de pesos multiplicativa. ^{[ 1 ]}

${\displaystyle \forall j=1,2,{\text{…}},m:a_{j}x\geq 0}$, ${\displaystyle 1*x=1}$, ${\displaystyle \forall i:x_{i}\geq 0}$.

${\displaystyle \sum _{t\leq T}p^{t}m^{t}\leq \sum _{t\leq T}m_{i}^{t}+{\frac {\ln(N)}{\eta }}+\eta T}$

 1. Elija la distribución${\displaystyle p_{i}^{t}={\frac {w_{i}^{t}}{\Phi t}}}$dónde${\displaystyle \Phi t=\sum _{i}w_{i}^{t}}$. 2. Observar el costo de la decisión${\displaystyle m^{t}}$. 3. Conjunto ${\displaystyle w_{i}^{t+1}=w_{i}^{t}\exp(-\eta m_{i}^{t}}$).

Aporte : Secuencia de${\displaystyle N}$ejemplos etiquetados (${\displaystyle x_{1}}$,${\displaystyle y_{1}}$),...,(${\displaystyle x_{N}}$,${\displaystyle y_{N}}$) Distribución${\displaystyle D}$sobre el${\displaystyle N}$ejemplos Algoritmo de aprendizaje débil "'WeakLearn'" Entero${\displaystyle T}$Especificar el número de iteraciones Inicializar el vector de pesos:${\displaystyle w_{i}^{1}=D(i)}$para${\displaystyle i=1,2,...,N}$. Hacer por${\displaystyle t=1,2,...,T}$1. Conjunto${\displaystyle p^{t}={\frac {w^{t}}{\sum _{i=1}^{N}w_{i}^{t}}}}$2. Llama a WeakLearn y proporciónale la distribución .${\displaystyle p^{t}}$; obtener una hipótesis${\displaystyle h_{t}:X\rightarrow }$[0,1]. 3 . Calcular el error de${\displaystyle h_{t}:\epsilon _{t}=\sum _{i=1}^{N}p_{i}^{t}|h_{t}(x_{i})-y_{i}|}$. 4 . Conjunto${\displaystyle \beta _{t}={\frac {\epsilon _{t}}{1-\epsilon _{t}}}}$. 5 . Establezca el nuevo vector de pesos como${\displaystyle w_{i}^{t+1}=w_{i}^{t}\beta _{t}^{1-|h_{t}(x_{i})-y_{i}|}}$. Enunciar la hipótesis:

${\displaystyle f(x)=h_{f}(x)={\begin{cases}1&{\text{if}}\sum _{t=1}^{T}(\log(1/\beta _{t}))h_{t}(x)\geq {\frac {1}{2}}\sum _{t=1}^{T}\log(1/\beta _{t})\\0&{\text{otherwise}}\end{cases}}}$

Fuente: ^{[ 14 ]}

${\displaystyle \exists ?x:Ax\geq b}$ (1)

${\displaystyle \exists ?x:p^{\textsf {T}}\!\!Ax\geq p^{\textsf {T}}\!b}$ (2)

Teoría de juegos evolutiva

La actualización de pesos multiplicativos es la variante en tiempo discreto de la ecuación del replicador (dinámica del replicador), un modelo comúnmente utilizado en la teoría de juegos evolutivos . Converge al equilibrio de Nash cuando se aplica a un juego de congestión . ^{[ 15 ]}

Investigación operativa y toma de decisiones estadísticas en línea

En el campo de la investigación operativa y la toma de decisiones estadísticas en línea, el algoritmo de mayoría ponderada y sus versiones más complejas se han encontrado de forma independiente. ^{[ 1 ]}

Geometría computacional

El algoritmo de pesos multiplicativos también se aplica ampliamente en geometría computacional , ^{[ 1 ]} como el algoritmo de Clarkson para programación lineal (PL) con un número limitado de variables en tiempo lineal. ^{[ 4 ] [ 5 ]} Posteriormente, Bronnimann y Goodrich emplearon métodos análogos para encontrar cubiertas de conjuntos para hipergrafos con una dimensión VC pequeña . ^{[ 6 ]}

Método de descenso de gradiente ^{[ 1 ]}

Actualización de pesos multiplicativos de matriz ^{[ 1 ]}

Marco de Plotkin, Shmoys, Tardos para empaquetar / cubrir LP ^{[ 1 ]}

Aproximación de problemas de flujo de múltiples productos básicos ^{[ 1 ]}

Aproximación O(logn) para muchos problemas NP-difíciles ^{[ 1 ]}

Teoría del aprendizaje y potenciación ^{[ 1 ]}

Conjuntos de núcleo duro y el lema XOR ^{[ 1 ]}

El algoritmo de Hannan y los pesos multiplicativos ^{[ 1 ]}

Optimización convexa en línea ^{[ 1 ]}