Stage-dependent integer-binary encoding in factorization-machine black-box optimization

Resumen Técnico: Codificación entero-binaria dependiente de la etapa en la optimización de caja negra mediante máquinas de factorización

Planteamiento del problema
La optimización de caja negra (BBO, por sus siglas en inglés) aborda problemas donde las funciones objetivo carecen de formas analíticas explícitas y son costosas de evaluar. La Máquina de Factorización con Recocido de Optimización Cuadrática (FMQA) es un enfoque prominente de BBO que construye un modelo sustituto utilizando una Máquina de Factorización (FM) y lo optimiza mediante una máquina de Ising. Un componente crítico de la FMQA es la conversión de variables enteras o continuas en variables binarias mediante codificación entero-binaria (por ejemplo, one-hot, domain-wall o codificación binaria) para formular el problema como un modelo de Optimización Binaria No Restringida Cuadrática (QUBO).

La FMQA convencional emplea un único método de codificación entero-binaria durante ambas etapas: la etapa de aprendizaje automático (construcción del modelo sustituto) y la etapa de búsqueda de soluciones (optimización de la máquina de Ising). Sin embargo, investigaciones previas sugieren un compromiso (trade-off): la codificación domain-wall suele ofrecer un rendimiento de búsqueda de soluciones superior en las máquinas de Ising, mientras que se ha observado que la codificación one-hot produce valores de función objetivo más bajos en el proceso de optimización global de la FMQA. Esta discrepancia implica que la codificación óptima para aprender el paisaje del sustituto puede diferir de la codificación óptima para buscar en dicho paisaje. Los métodos convencionales, al fijar una única codificación, pueden no aprovechar plenamente las capacidades distintas de la FM y de la máquina de Ising.

Metodología
Los autores proponen un marco de trabajo FMQA dependiente de la etapa que utiliza diferentes métodos de codificación entero-binaria para las etapas de aprendizaje automático y de búsqueda de soluciones. El núcleo de este enfoque consiste en:

1. Estrategia de doble codificación: El marco entrena el modelo sustituto FM utilizando una codificación adecuada para el aprendizaje (específicamente la codificación one-hot en la variante propuesta "OhDw") y luego convierte el modelo sustituto resultante en una codificación diferente adecuada para la búsqueda (específicamente la codificación domain-wall) antes de la optimización por la máquina de Ising.
2. Conversión de la matriz QUBO: Para permitir este cambio, los autores derivaron fórmulas de conversión matemática entre las matrices QUBO de las codificaciones one-hot y domain-wall. Estas fórmulas aseguran que el paisaje de la función objetivo del sustituto se preserve sobre los estados enteros factibles hasta una constante aditiva.
   • La conversión de one-hot a domain-wall implica transformar los términos diagonales y fuera de la diagonal de la matriz QUBO $Q^{(oh)}$ a $Q^{(dw)}$ utilizando relaciones de sumatoria específicas (Ecs. 18–20).
   • La conversión inversa (domain-wall a one-hot) también es derivada (Ecs. 22–24).
   • Se establece que la complejidad computacional para estas conversiones mutuas es $O(N^2q^2)$, donde $N$ es la dimensión de entrada y $q$ es el número de niveles de discretización.
3. Flujo de trabajo algorítmico:
   • Etapa de aprendizaje: Se entrena una FM sobre datos de entrada-salida codificados mediante codificación one-hot.
   • Conversión: El modelo sustituto entrenado (representado como una matriz QUBO) se convierte de codificación one-hot a domain-wall.
   • Etapa de búsqueda: El QUBO convertido, aumentado con restricciones de codificación domain-wall, se optimiza utilizando una máquina de Ising (Fixstars Amplify Annealing Engine) para encontrar soluciones candidatas.
   • Evaluación: Las soluciones se decodifican, se evalúan frente a la verdadera función de caja negra y se añaden al conjunto de datos de entrenamiento para la siguiente iteración.

Contribuciones clave

1. Propuesta de marco de trabajo: Introducción de un marco de trabajo FMQA que desacopla la elección de la codificación entre las etapas de aprendizaje y de búsqueda de soluciones, en lugar de fijar una única codificación durante todo el proceso.
2. Derivación teórica: Derivación de fórmulas de conversión mutua entre matrices QUBO one-hot y domain-wall que preservan el paisaje de la función objetivo del sustituto sobre los estados factibles, permitiendo el cambio de codificaciones sin perder la fidelidad del modelo aprendido.
3. Descomposición empírica: Una descomposición numérica de los efectos de la codificación entero-binaria en las contribuciones de la etapa de aprendizaje y la etapa de búsqueda de soluciones, evaluándolas por separado para comprender sus distintos impactos en el rendimiento.

Resultados experimentales
El método propuesto fue evaluado con la función Rastrigin, un problema de referencia multimodal, con dimensiones de entrada $N \in \{2, 5\}$ y niveles de discretación $q \in \{61, 301\}$. El rendimiento del método "OhDw" propuesto (una one-hot para el aprendizaje, domain-wall para la búsqueda) se comparó con las variantes convencionales de codificación única (Oh, Dw, Bi) y la Optimización Bayesiana (BO).

• Dominancia de la codificación de la etapa de aprendizaje: En todas las condiciones, la codificación utilizada en la etapa de aprendizaje fue el factor dominante que rigió el rendimiento de la optimización. Los métodos que emplean codificación one-hot para el aprendizaje (Oh y OhDw) lograron consistentemente errores residuales más bajos que aquellos que utilizan codificación domain-wall o binaria para el aprendizaje.
• Beneficios dependientes de la etapa: El beneficio de cambiar a la codificación domain-wall para la etapa de búsqueda dependió de la condición:
  • Para $N=5$ y $q=301$ (discretización más fina, espacio de búsqueda más grande), el método OhDw logró errores residuales más bajos y soluciones más cercanas al óptimo global en comparación con el método Oh (solo one-hot).
  • Para $N=5$ y $q=61$, el método Oh superó ligeramente al OhDw.
  • Para $N=2$, no se observó una diferencia de rendimiento significativa entre Oh y OhDw.
• Estabilidad de la búsqueda: El análisis de la etapa de búsqueda de soluciones indicó que la codificación domain-wall permite transiciones más estables entre estados factibles en la máquina de Ising, mientras que la codificación one-hot requiere pasar por estados que violan las restricciones, lo que potencialmente reduce la estabilidad de la búsqueda.

Significado y afirmaciones
El artículo afirma que la elección de la codificación entero-binaria no es meramente una elección de representación, sino un elemento de diseño que cumple funciones distintas en las etapas de aprendizaje y de búsqueda de soluciones de la FMQA. El hallazgo principal es que la codificación one-hot en la etapa de aprendizaje es el motor principal del rendimiento de la optimización, debido probablemente a su capacidad superior para construir un modelo sustituto preciso. Sin embargo, el estudio demuestra que emplear codificaciones dependientes de la etapa —específicamente combinando one-hot para el aprendizaje con domain-wall para la búsqueda— puede proporcionar mejoras adicionales, particularmente en escenarios con mayores dimensiones de entrada y una discretización más fina donde el espacio de búsqueda es más complejo.

Los autores concluyen que, si bien el método OhDw es prometedor, su generalidad requiere una validación adicional en una variedad más amplia de funciones de referencia y problemas de optimación de diseño del mundo real. Además, el análisis sistemático de la sensibilidad a los coeficientes de penalización y las diferencias de densidad de las matrices QUBO sigue siendo una dirección para trabajos futuros.