• Saltar al contenido principal
  • Skip to secondary menu
  • Saltar a la barra lateral principal
  • Saltar al pie de página
  • Inicio
  • Secciones
    • Ciencia de datos
    • Criptografía
    • Herramientas
    • Machine Learning
    • Noticias
    • Opinión
    • Productividad
    • Programación
      • JavaScript
      • Julia
      • Matlab
      • Python
      • R
  • Programación
    • JavaScript
    • Julia
    • Matlab
    • Python
    • R
  • Noticias
  • Boletín
  • Contacto
  • Tienda
    • Libros
    • Equipamiento de oficina
    • Equipamiento en movilidad
    • Tiendas afiliadas
      • AliExpress
      • Amazon
      • Banggood
      • GeekBuying
      • Lenovo

Analytics Lane

Ciencia e ingeniería de datos aplicada

  • Ciencia de datos
  • Machine Learning
  • Python
  • Pandas
  • NumPy
  • Matlab
  • Julia
  • JavaScript
  • Excel

UCB1-Tuned para un problema Bandido Multibrazo (Multi-Armed Bandit)

abril 16, 2021 Por Daniel Rodríguez Deja un comentario
Tiempo de lectura: 4 minutos

La semana pasada hemos visto UCB2, un algoritmo que ha ofrecido mejores rendimientos que UCB1 para nuestros bandidos basados en una distribución binomial. En esta ocasión vamos a ver UCB1-Tuned (también conocido como UCB-Tuned), una mejora de UCB1 en el que se modifica la fórmula con la que se calcula el límite de confianza superior.

UCB1-Tuned

El método UCB1-Tuned propone una mejora estricta de la expresión usada en UCB1 para determinar el límite de confianza superior para cada uno de los bandidos. Modificando de esta manera la regla de selección. En concreto, lo que se hace es modificar la formula para el cálculo de

\varepsilon_j = \sqrt{\frac{2 \log N}{n_j}},

donde N es el número total de veces que se ha jugado con un bandido y n_j las que se ha jugado con el bandido j. Reemplazandola por la expresión

\varepsilon_j = \sqrt{\frac{\log N}{n_j} \min(1/4, V_j(n_j))},

donde V_j es una estimación de límite confianza superior que se puede obtener mediante

V_j(n_j) = \bar{X_j^2} - \bar{X_j}^2 + \sqrt{\frac{2 \log N}{n_j}},

en donde \bar{X_j^2} es la media de los cuadrados de las recompensas y \bar{X_j} es la media de las recompensas.

Publicidad


El algoritmo UCB1-Tuned suele superar empíricamente a UCB1 en cuanto a la veces que selecciona el mejor bandido. Además de ser un método menos sensible a la variabilidad de las recompensas.

Implementación de UCB1-Tuned en Python

Al igual que en las entradas anteriores vamos a realizar una implementación de UCB1-Tuned en Python. Para lo que nos basaremos en la clase Epsilon implementada para al hablar de Epsilon-Greedy. Siendo necesario en esta ocasión modificar los método run(), select() y reset(), además de agregar la propiedad privada _mean2. Cambios que se muestran en el siguiente código.

class UCB1Tuned(Epsilon):
    def __init__(self, bandits):
        self.bandits = bandits
        
        self.reset()
    
    
    def run(self, episodes=1):
        for i in range(episodes):
            # Selección del bandido
            bandit = self.select()
            
            # Obtención de una nueva recompensa
            reward = bandits[bandit].pull()
            
            # Agregación de la recompensa al listado
            self._rewards.append(reward)
            
            # Actualización de la media
            self._plays[bandit] += 1
            self._mean[bandit] = (1 - 1.0/self._plays[bandit]) * self._mean[bandit] \
                                 + 1.0/self._plays[bandit] * reward
            
            # Actualización de la media de los cuadrados
            self._mean2[bandit] = (1 - 1.0/self._plays[bandit]) * self._mean2[bandit] \
                                 + 1.0/self._plays[bandit] * reward ** 2
        
        return self.average_reward()
    
    
    def select(self):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        if total == 0:
            bandit = np.random.choice(len(bandits))
        else:
            ucb = [0] * num_bandits
            
            for i in range(num_bandits):
                if self._plays[i] == 0:
                    v = self._mean2[i] - self._mean[i] ** 2 + np.sqrt(2 * np.log(total))
                else:
                    v = self._mean2[i] - self._mean[i] ** 2 + np.sqrt(2 * np.log(total) / self._plays[i])
        
                ucb[i] = self._mean[i] + np.sqrt(np.log(total) * np.min([1/4, v]))
            
            max_bandits = np.where(ucb == np.max(ucb))[0]
            bandit = np.random.choice(max_bandits)
            
        return bandit
    
    
    def reset(self, initial=None):
        self._rewards = []
        self._plays = [0] * len(self.bandits)
        self._mean = [0] * len(self.bandits)
        self._mean2 = [0] * len(self.bandits)

La propiedad privada _mean2 es necesaria ya que es necesario disponer de la media de los cuadrados de cada uno de los bandidos. Una propiedad que se puede calcular como _mean reemplazando la recompensa por la recompensa al cuadrado. Propiedad que se tiene que reiniciar mediante el método reset().

Para actualizar el valor de _mean2 es necesario incluir el cálculo de esta propiedad en el método run(). Lo que se ha hecho utilizando la misma expresión para actualizar el valor que la media. Siendo este el único cambio implementado en run().

Finalmente, el método select() se tiene que actualizar con la nueva fórmula para seleccionar el límite de confianza superior y, en consecuencia, la selección del bandido con el que jugar en cada momento.

Publicidad


Resultados de UCB1-Tuned en Python

Al igual que en las entradas anteriores se puede ver el rendimiento de este método. Para ello se pueden utilizar la clase Bandit creada en la entrada de valores iniciales optimistas. Una clase que implementa unos bandidos basados en la distribución binomial. Así para probar el algoritmo y compararlos con UCB1 solamente se tienen que escribir el siguiente código.

np.random.seed(0)

bandits = [Bandit(0.02), Bandit(0.06), Bandit(0.10)]

ucb_tuned = UCB1Tuned(bandits)
ucb_1 = UCB1(bandits)

ucb_tuned.run(200000)
ucb_1.run(200000)

ucb_tuned.plot(True, label='UCB-Tuned')
ucb_1.plot(True, True, label='UCB-1')
plt.legend()

Lo que genera la siguiente gráfica.

Evolución de la recompensa promedio con el numero de tiradas para el algoritmo UCB1 y UCB1-Tuned con tres bandidos basados en una distribución binomial
Evolución de la recompensa promedio con el numero de tiradas para el algoritmo UCB1 y UCB1-Tuned con tres bandidos basados en una distribución binomial

Lo que se puede ver en este ejemplo es que el rendimiento de ambos métodos es similar a largo plazo, convergiendo ambos hacia valores muy próximos al teórico del mejor bandido. Aunque el método UCB1-Tuned ha detectado el bandido óptimo más rápido que UCB1. Por lo que demuestra ser un método más adecuado cuando el número de tiradas disponibles es reducido.

Conclusiones

En esta entrada hemos visto un tercer método de la familia UCB (Límite de Confianza Superior, del inglés Upper Confidence Bounds) para resolver un problema tipo Bandido Multibrazo. Concretamente el método UCB1-Tuned. Siendo este una mejora de UCB1 que, en el ejemplo que hemos visto, reconoce más rápidamente el bandido óptimo. Aunque quedan por ver más métodos UCB cómo pude ser el que veremos la semana que viene: UCB-Normal.

Imagen de Giani Pralea en Pixabay

¿Te ha parecido de utilidad el contenido?

¡Puntúalo entre una y cinco estrellas!

Puntuación promedio 0 / 5. Votos emitidos: 0

Ya que has encontrado útil este contenido...

¡Síguenos en redes sociales!

¡Siento que este contenido no te haya sido útil!

Publicidad


¡Déjame mejorar este contenido!

Dime, ¿cómo puedo mejorar este contenido?

Publicaciones relacionadas

  • Comparación de refuerzo (reinforcement comparison) para un problema Bandido Multibrazo (Multi-Armed Bandit)
    Comparación de refuerzo (reinforcement comparison) para un…
  • EXP3 para un problema Bandido Multibrazo (Multi-Armed Bandit)
    EXP3 para un problema Bandido Multibrazo (Multi-Armed…
  • Epsilon-Greedy con decaimiento para un problema Bandido Multibrazo (Multi-Armed Bandit)
    Epsilon-Greedy con decaimiento para un problema Bandido…
  • Librería Python para resolver el Bandido Multibrazo (Multi-Armed Bandit)
    Librería Python para resolver el Bandido Multibrazo…
  • Epsilon-Greedy para el Bandido Multibrazo (Multi-Armed Bandit)
    Epsilon-Greedy para el Bandido Multibrazo (Multi-Armed…
  • CP-UCB para un problema Bandido Multibrazo (Multi-Armed Bandit)
    CP-UCB para un problema Bandido Multibrazo (Multi-Armed…

Publicado en: Ciencia de datos Etiquetado como: Aprendizaje por refuerzo, Machine learning

Interacciones con los lectores

Deja una respuesta Cancelar la respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

I accept the Terms and Conditions and the Privacy Policy

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.

Publicidad




Barra lateral principal

Suscríbete a nuestro boletín

Suscríbete al boletín semanal para estar al día de todas las publicaciones.

Política de Privacidad

Analytics Lane en redes sociales

  • Amazon
  • Facebook
  • GitHub
  • Instagram
  • Pinterest
  • RSS
  • Twitter
  • Tumblr
  • YouTube

Publicidad

Entradas recientes

El método de Hare-Niemeyer y su implementación en Python

septiembre 29, 2023 Por Daniel Rodríguez

Redimensionar una partición de disco LVM con espacio no asignado en Linux

septiembre 27, 2023 Por Daniel Rodríguez

¿Cómo saber la versión de Pandas o cualquier otra librería en Python?

septiembre 25, 2023 Por Daniel Rodríguez

Publicidad

Es tendencia

  • Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas publicado el mayo 10, 2019 | en Python
  • ¿Cómo eliminar columnas y filas en un dataframe pandas? publicado el marzo 25, 2019 | en Python
  • pandas Pandas: Cómo crear un DataFrame vacío y agregar datos publicado el noviembre 16, 2020 | en Python
  • Sistema de ecuaciones Sistemas de ecuaciones lineales con numpy publicado el octubre 29, 2018 | en Python
  • Seleccionar filas y columnas en Pandas con iloc y loc publicado el junio 21, 2019 | en Python

Publicidad

Lo mejor valorado

4.9 (22)

Seleccionar filas y columnas en Pandas con iloc y loc

4.7 (12)

Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas

4.6 (15)

Archivos JSON con Python: lectura y escritura

4.5 (10)

Diferencias entre var y let en JavaScript

4.3 (12)

Ordenación de diccionarios en Python mediante clave o valor

Publicidad

Comentarios recientes

  • Daniel Rodríguez en ¿Cómo eliminar columnas y filas en un dataframe pandas?
  • Miguel en ¿Cómo eliminar columnas y filas en un dataframe pandas?
  • alberto en Resolver problema de credenciales en Bitbucket
  • Pablo en Aplicar el método D’Hondt en Excel
  • Agapito en Creación de un EXE desde un archivo Python en Windows

Publicidad

Footer

Analytics Lane

  • Acerca de Analytics Lane
  • Boletín de noticias
  • Contacto
  • Libros
  • Lo más popular
  • Noticias
  • Tienda
  • Tiendas afiliadas

Secciones

  • Ciencia de datos
  • Criptografía
  • Herramientas
  • Machine Learning
  • Opinión
  • Productividad
  • Programación
  • Reseñas

Sobre de Analytics Lane

En Analytics Lane tratamos de explicar los principales conceptos de la ciencia e ingeniería de datos con un enfoque práctico. Los principales temas tratados son ciencia de datos, ingeniería de datos, inteligencia artificial, machine learning, deep learning y criptografía. Además, también se habla de los principales lenguajes de programación y herramientas utilizadas por los científicos e ingenieros de datos.

Copyright © 2018-2023 Analytics Lane ·Términos y condiciones ·Política de Cookies ·Política de Privacidad ·Herramientas de privacidad ·Contacto