¿Qué técnica estadística sería adecuada para optimizar las ponderaciones?

Question

Antecedentes:

Tengo los siguientes datos (un ejemplo):

headings = { 
         :heading1 => { :weight => 25, :views => 0, :conversions => 0}
         :heading2 => { :weight => 25, :views => 0, :conversions => 0}
         :heading3 => { :weight => 25, :views => 0, :conversions => 0}
         :heading4 => { :weight => 25, :views => 0, :conversions => 0}
       }
total_views = 0

Tengo que servir estas rúbricas en función de su peso. Cada vez que se sirve un encabezado su views se incrementa en uno y total_views también se incrementa. Y cada vez que un usuario hace clic en un encabezado servido su conversions se incrementa en uno. He escrito un programa (en Ruby) que realiza esto bien.

Pregunta:

Necesito Auto Optimize rúbrica que mejor se convierte. Considere las siguientes vistas y conversiones para todos los encabezados:

heading1: views => 50, conversions => 30
heading2: views => 50, conversions => 10
heading3: views => 50, conversions => 15
heading4: views => 50, conversions => 5

Necesito aumentar automáticamente los pesos de la(s) rúbrica(s) que más convierte(n) y viceversa. La suma de pesos será siempre 100.

¿Existe algún algoritmo/fórmula/técnica estándar para hacerlo? Es posible que haya otros parámetros que deban predefinirse antes de realizar estos cálculos. Pero no lo estoy consiguiendo.

Answer 1

Su problema es un problema estándar en el área del aprendizaje por refuerzo y puede ser reformulado como problema del bandido n-armado donde hay que encontrar los mejores brazos de los que tirar para optimizar la ganancia global. En este caso un brazo = un cabezal y la ganancia es equivalente a 1 (si hay conversión), si no 0.

Realmente recomiendo leer el libro de Sutton y Barto especialmente capítulo 2 donde se explica en detalle la técnica básica para resolver el problema del bandido n-armado (cómo seleccionar, cómo aumentar los pesos, cómo hacer frente a las ganancias que cambian con el tiempo, etc.). Es realmente una lectura estupenda (y no innecesariamente complicada).

Editar: Aquí hay algunas explicaciones detalladas a modo de resumen de cómo funciona la RL en el caso de la OP. Algunas partes son bastante similares a la respuesta de Matt, pero no todas.

En el aprendizaje por refuerzo (RL) diferenciamos entre "exploración" y "explotación". Durante la exploración buscamos en el espacio de acciones disponibles (también conocidas como rúbricas a mostrar) para encontrar una mejor o la mejor, mientras que en la explotación sólo utilizamos las acciones/rúbricas para las que ya sabemos que son buenas. Para medir lo buena que es una acción, calculamos la recompensa que obtuvo una acción cuando se utilizó y, por lo tanto, utilizamos este valor para estimar la recompensa del uso posterior de esta acción. En nuestro caso, la recompensa media esperada de una acción/rúbrica es simplemente la tasa de conversión.

Algunas definiciones:

$h_i$ = Rúbrica i

$Q(h_i)$ = Función de recompensa esperada de la partida i = $conversion_i / views_i$

¿Cómo se selecciona una acción o rúbrica? Una opción es seleccionar con avidez la acción con la mayor estimación de recompensa/tasa de conversión. Sin embargo, de este modo no podemos encontrar soluciones nuevas o mejores (no hay exploración en absoluto). Lo que queremos es un equilibrio entre la exploración y la explotación. Por ello, utilizamos un procedimiento denominado "selección máxima suave".

$weight(h_i)=\frac{exp(Q(h_i)/\tau)}{\sum_j exp(Q(h_j)/\tau)}$ (ver la selección de softmax en el libro de sutton )

Calcule estos pesos y luego seleccione una acción al azar con respecto a estos pesos (véase, por ejemplo, la función sample() en R)

Ajustando el parámetro tau, se puede controlar el equilibrio entre la exploración y la explotación. Si $\tau$ = 0, entonces volvemos a la selección de acción codiciosa pura, si $\tau$ llega al infinito (o es lo suficientemente grande), todos los pesos se vuelven iguales y nos limitamos a un muestreo aleatorio puro (sin explotación).

¿Cómo se actualizan las recompensas? Se puede utilizar esta fórmula ...

$Q_{k+1}(h)=Q_k(h) + \alpha*(r_{k+1}-Q_k(h))$ (ver ver la fórmula en el libro de Sutton )

donde k - indica la k-ésima vez que se ha mostrado la rúbrica h y $r_k$ = 1 (si durante la k-ésima vez que se mostró la cabecera h se produjo una conversión) o $r_k$ = 0 (si no) Para el tamaño del paso $\alpha$ puedes, por ejemplo, elegir:

• $1/k$ lo que en su caso debería conducir a la convergencia (las recompensas/conversiones más recientes se ponderan menos)
• una constante, lo que hará que no haya convergencia (todas las recompensas se ponderan igual), pero permitirá que el sistema se adapte a los cambios. Por ejemplo, imagina que el concepto de cuál es la mejor cabecera cambia con el tiempo.

Observación final Cómo configurar los parámetros $\tau$ y $\alpha$ depende del problema. Te sugiero que hagas algunas simulaciones para ver cuáles son las mejores para ti. Para esto y en general, sólo puedo recomendar la lectura del capítulo 2 del libro enlazado. Vale la pena.

Otra observación derivada de la experiencia práctica con esta fórmula (si las cabeceras a mostrar cambian constantemente) es no utilizar siempre la fórmula de selección softmax. Sugiero más bien elegir la mejor cabecera p% de las veces que se mostrará una cabecera y seleccionar otra cabecera en (100-p)% de las veces para encontrar otra posiblemente mejor. Por otro lado, si su objetivo es encontrar la mejor cabecera entre un número fijo de cabeceras, es mejor utilizar siempre la selección softmax y establecer $\alpha=1/k$ y $\tau$ cerca de cero.

Answer 2

Así que, si lo he entendido bien, está intentando llegar a un esquema de ponderación que maximice la cantidad de conversiones totales. Supongo que va a restablecer los valores de conversión para cada rúbrica después de cada cambio de peso.

Una solución sencilla entonces podría ser algo así:

(No estoy familiarizado con su sintaxis así que espero que entienda este pseudocódigo)

heading1: {ConvPView = conversions / views}   
heading2: {ConvPView = conversions / views} 
heading3: {ConvPView = conversions / views}
heading4: {ConvPView = conversions / views}

AvgeConvPView = (h1.cpv + h2.cpv +h3.cpv +h4.cpv) / 4

heading1: {weight = weight + ((ConvPView - AvgeConvPView) * weightChangeConstant)}
heading2: {etc..}

Así que, básicamente, se toman las conversiones por vista de una rúbrica (conversiones / vistas) y luego se resta la media de conversiones por vista de todas las rúbricas. Luego se multiplica por una constante de cambio de peso y se añade el resultado al peso anterior. O, en resumen:

Weight = weight + (((conversions / views) - (mean of (conversions / views)) * constant)

Esto dará un número negativo si está por debajo de la media y un número positivo si está por encima. Una constante más grande le dará una modificación más rápida de los pesos, pero también será más volátil y menos capaz de establecer una distribución óptima de pesos.