• 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

UCB-V para un problema Bandido Multibrazo (Multi-Armed Bandit)

mayo 28, 2021 Por Daniel Rodríguez Deja un comentario
Tiempo de lectura: 3 minutos

El algoritmo UCB-V es una variante de la familia UCB que utiliza la varianza para seleccionar el bandido en problemas tipo Bandido Multibrazo (Multi-Armed Bandit). Un algoritmo genérico que puede ser utilizado en cualquier tipo de bandido.

UCB-V

En el algoritmo UCB-V se tiene que seleccionar en cada tirada aquel bandido que maximice la siguiente expresión.

X_{UCB1-V} = \bar{X_j} + \sqrt{ \frac{2 \sigma^2_j \log(N)}{n_j}} + \frac{b \log(N)}{N}

Donde \sigma^2_j es la varianza empírica del bandido j, n_j es el número de veces que se ha jugado con el bandido j, N el número de veces que se ha jugado con todos los bandidos y b es un hiper-parámetro en el que generalmente se utiliza el valor 3.

Implementación de UCB-V en Python

Al igual que en otras entradas anteriores, para implementar el algoritmo UCB-V en Python se puede usar la clase Epsilon que se había implementado para el algoritmo de valores iniciales optimistas. Dato que en este algoritmo es necesario la varianza, además de los valores que se guardan en la clase original, es necesario crear una nueva propiedad en la que se guarde el cuadrado de las recompensas. Valor con el que se puede obtener la varianza empírica usando la expresión

\sigma^2_j = \sum\frac{X_j(t)^2}{n_j} - \bar{X_j}^2

Así, una posible implementación de UCB-V es la que se muestra en la siguiente clase.

Publicidad


class UCBV(Epsilon):
    def __init__(self, bandits, b=3):
        self.bandits = bandits
        self.b = b
        
        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
            self._mean2[bandit] += reward**2
        
        return self.average_reward()
    
    
    def select(self):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        if total < num_bandits:
            bandit = total
        else:
            ucb = [0] * num_bandits
                
            for i in range(num_bandits):
                var = self._mean2[i] / self._plays[i] - self._mean[i]**2
                ucb[i] = self._mean[i]
                ucb[i] += np.sqrt(2 * var * np.log(total) / self._plays[i])
                ucb[i] += self.b * np.log(total) / self._plays[i]             
            
            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)

Nótese que en este caso, además del método select(), ha sido necesario modificar los métodos run() para que guarde la suma de las recompensas al cuadrado y reset() para crear esta propiedad.

Resultados de UCB-V

Para evaluar el rendimiento de este algoritmo se puede comparar el rendimiento frente al que se obtienen con UCB1. De forma análoga a como se ha realizado en entradas anteriores. Para ello se puede emplear el siguiente código en el que se crean tres bandidos cuya recompensa se obtienen mediante una distribución binomial con diferente media. En el que posteriormente se compara el resultado que se obtiene después de 200.000 tiradas con UCB-V y UCB1.

np.random.seed(0)

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

ucbv = UCBV(bandits)
ucb1 = UCB1(bandits)

ucbv.run(200000)
ucb1.run(200000)

ucbv.plot(True, label='UCB-V')
ucb1.plot(True, True, label='UCB1')
plt.legend()

print(ucbv._plays)
print(ucb1._plays)

Al ejecutar el código se obtiene la siguiente figura.

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

En la que se puede ver como UCB-V obtiene mejores resultados a corto plazo que UCB1 para estos bandidos. Aunque a largo plazo, como sería de esperar, ambos tienen obtienen una recompensa promedio cercana a teórica del mejor bandido. La diferencia a corto plazo se debe a que UCB-V solamente selecciona el bandido optimo 196.844 veces frente a las 187.605. Lo que indica que ha necesitado menos tiradas para decantarse por este.

Conclusiones

En esta entrada hemos visto otro algoritmo de la familia UCB con el que se puede abordar un problema tipo Bandido Multibrazo (Multi-Armed Bandit). Un algoritmo que se basa en el uso de la varianza para seleccionar el bandido con el que jugar en cada ocasión. Por lo que se puede utilizar con cualquier tipo de bandido, independientemente de la distribución usada para generar la recompensa. Ofreciendo, en el caso analizado, mejores resultados que UCB1.

Publicidad


Imagen de Mier Chen 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!

¡Déjame mejorar este contenido!

Dime, ¿cómo puedo mejorar este contenido?

Publicaciones relacionadas

  • EXP3 para un problema Bandido Multibrazo (Multi-Armed Bandit)
    EXP3 para un problema Bandido Multibrazo (Multi-Armed…
  • UCB2 para un problema Bandido Multibrazo (Multi-Armed Bandit)
    UCB2 para un problema Bandido Multibrazo (Multi-Armed…
  • Epsilon-Greedy para el Bandido Multibrazo (Multi-Armed Bandit)
    Epsilon-Greedy para el Bandido Multibrazo (Multi-Armed…
  • Valores iniciales optimistas para un problema Bandido Multibrazo (Multi-Armed Bandit)
    Valores iniciales optimistas para un problema Bandido…
  • Softmax para un problema Bandido Multibrazo (Multi-Armed Bandit)
    Softmax para un problema Bandido Multibrazo (Multi-Armed…
  • Algoritmos de seguimiento (pursuit) para un problema Bandido Multibrazo (Multi-Armed Bandit)
    Algoritmos de seguimiento (pursuit) para un problema Bandido…

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

  • ¿Cómo eliminar columnas y filas en un dataframe pandas? publicado el marzo 25, 2019 | en Python
  • Operaciones de filtrado de DataFrame con Pandas en base a los valores de las columnas publicado el mayo 10, 2019 | 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
  • pandas Pandas: Cómo crear un DataFrame vacío y agregar datos publicado el noviembre 16, 2020 | 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