• 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

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

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

Continuando con el repaso a los principales algoritmos existentes para abordar los problemas tipo Bandido Multibrazo (Multi-Armed Bandit) vamos a ver en esta ocasión KL-UCB. Una versión del UCB donde se utiliza la divergencia de Kullback-Leibler para seleccionar el mejor bandido óptimo en cada jugada.

La divergencia de Kullback-Leibler

Una de las medidas más populares para medir la diferencia entre dos distribuciones de probabilidad sobre la misma variable es la divergencia de Kullback-Leibler (KL). Una medida no simétrica estrechamente relacionada con la entropía relativa, la divergencia de la información y la ganancia de la información. En concreto, la divergencia KL de para dos distribuciones p(x) y q(x) es una media de la información pedida cuando se emplea q(x) para aproximar p(x). Un valor que, en el caso de una distribución de variable discreta se puede obtener mediante la expresión:

d_{KL} \left(p(x)|q(x)\right) = \sum_x p(x) \log \left|\frac{p(x)}{q(x)}\right|

Mientras que en el caso de distribuciones de una variable continua se emplearía

d_{KL} \left(p(x)|q(x)\right) = \int_{-\infty}^{\infty} p(x) \log \left|\frac{p(x)}{q(x)}\right| dx

KL-UCB

KL-UCB es un enfoque UCB (Upper Confidence Bound) para resolver el problema del bandido multibrazo donde la función para seleccionar al bandido se deriva de la divergencia KL. Un algoritmo en el que se considera la distancia entre las distribuciones estimadas para cada uno de los bandidos. En el caso de bandidos basados en la distribución de Bernoulli la divergencia KL se puede obtener mediante la expresión

d_{KL}(p,q) = p \log\frac{p}{q} + (1 - p) \log\frac{1-p}{1-q}

Algo que se puede extender fácilmente al caso de distribuciones binomiales como las que usan los bandidos implementados en entrada anteriores, para lo que simplemente se debe multiplicar el valor anterior por el número de intentos

Publicidad


d_{KL}(p,q,n) = n \left( p \log\frac{p}{q} + (1 - p) \log\frac{1-p}{1-q} \right)

Ahora para seleccionar un bandido en cada una de las jugadas se busca el valor que maximice la siguiente expresión

j = \arg \max_j (n_j d_{KL}(\bar{X_j}, M \le \log N + c \log\log N)

Donde n_j es el número de veces que se ha jugado con el bandido j, N es el número total de veces que se ha jugado y c es un parámetro.

Implementación de KL-UCB en Python

Para facilitar la implementación de KL-UCB en Python se puede partir de la clase Epsilon implementada previamente en Epsilon-Greedy con decaimiento. A partir de la cual se puede crear una clase hija en la que se sobreescriba el método select() con KL-UCB. Pudiéndose agregar dos nuevas propiedades para configurar el número de pruebas de la distribución binomial (n) y el hiperparámetro c. Además de esto, en este caso también es necesario definir una función en la que se implemente la divergencia KL. Lo que se muestra en el siguiente código.

def klBin(p, q, n=1, eps=1e-15):
    p = min(max(p, eps), 1 - eps)
    q = min(max(q, eps), 1 - eps)
    
    return n * (p * np.log(p / q) + (1 - p) * np.log((1 - p) / (1 - q)))

class KLUCB(Epsilon):
    def __init__(self, bandits, n=1, c=0):
        self.bandits = bandits
        self.n = 1
        self.c = 1
        
        self.reset()
        
    
    def select(self):
        num_bandits = len(self.bandits)
        total = len(self._rewards)
        
        if total < num_bandits:
            bandit = total
        else:
            ucb = [0] * num_bandits
            d = np.log(total) + self.c * np.log((total + 1))
                
            for i in range(num_bandits):
                ucb[i] = klBin(self._mean[i], d / self._plays[i], self.n)
        
            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)

Antes de poder aplicar el algoritmo para seleccionar el bandido es necesario que, por lo menos, exista una tirada con cada uno de los bandidos. Debido a esto en el método select() las primeras jugadas son con cada uno de los bandidos definidos. A partir de ese punto, el bandido se selecciona usando la divergencia KL. Para lo que primero se calcula el valor de d que posteriormente se divide por el número de veces que se ha jugado con cada uno de los bandidos.

En el caso de la función klBin se evita explícitamente usar 0 o 1 en los valores de p y q para evitar logaritmos y divisiones por cero. Motivo por el que se ha definido el parámetro eps.

Publicidad


Resultados

Una vez implementado el algoritmo se puede comparar el rendimiento de KL-UCB con UCB1 empleando para ello los bandidos basados en una distribución binomial. Para lo que se puede utilizar el siguiente código.

np.random.seed(0)

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

ucb_kl = KLUCB(bandits)
ucb_1 = UCB1(bandits)

ucb_kl.run(200000)
ucb_1.run(200000)

ucb_kl.plot(True, label='KL-UCB')
ucb_1.plot(True, True, label='UCB1')
plt.legend()

Con el que se obtiene la siguiente gráfica como resultado.

Evolución de la recompensa promedio con el número de tiradas para KL-UCB y UCB1 con tres bandidos basados en una distribución binomial
Evolución de la recompensa promedio con el número de tiradas para KL-UCB y UCB1 con tres bandidos basados en una distribución binomial

En este ejemplo se puede ver que el resultado de KL-UCB converge más rápidamente que UCB-1. Aunque la implementación de KL-UCB puede presentar problemas de estabilidad en el caso de que en las primeras tiradas se obtenga muy buenos resultados en bandidos que no sea el óptimo. Lo que puede llevar a que el valor de la divergencia KL sea cero para ellos, algo que se puede evitar aumentando el número de jugadas fijas con cada uno de los bandidos.

Conclusiones

En esta ocasión hemos visto un nuevo algoritmo para solucionar un problema tipo Bandido Multibrazo, el método KL-UCB. Un método que viene a completar los ya vistos como Epsilon-Greedy, UCB1, UCB2, UCB1-Tuned, UCB1-Normal y BayesUCB.

Imagen de max_gloin en Pixabay

¿Te ha parecido de utilidad el contenido?

¡Puntúalo entre una y cinco estrellas!

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

Publicidad


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

  • UCB1-Normal para un problema Bandido Multibrazo (Multi-Armed Bandit)
    UCB1-Normal para un problema Bandido Multibrazo (Multi-Armed…
  • Comparación de refuerzo (reinforcement comparison) para un problema Bandido Multibrazo (Multi-Armed Bandit)
    Comparación de refuerzo (reinforcement comparison) para un…
  • UCB-V para un problema Bandido Multibrazo (Multi-Armed Bandit)
    UCB-V para un problema Bandido Multibrazo (Multi-Armed…
  • MOSS para un problema Bandido Multibrazo (Multi-Armed Bandit)
    MOSS para un problema Bandido Multibrazo (Multi-Armed…
  • UCB1 para un problema Bandido Multibrazo (Multi-Armed Bandit)
    UCB1 para un problema Bandido Multibrazo (Multi-Armed…
  • EXP3 para un problema Bandido Multibrazo (Multi-Armed Bandit)
    EXP3 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

  • ¿Cómo eliminar columnas y filas en un dataframe pandas? publicado el marzo 25, 2019 | en Python
  • Seleccionar filas y columnas en Pandas con iloc y loc publicado el junio 21, 2019 | en Python
  • Sistema de ecuaciones Sistemas de ecuaciones lineales con numpy publicado el octubre 29, 2018 | en Python
  • La aplicación Auto Py to Exe Creación de un EXE desde un archivo Python en Windows publicado el mayo 16, 2022 | en Python
  • ¿Cómo cambiar el nombre de las columnas en Pandas? publicado el mayo 6, 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