Improving FMQA via Initial Training Data Design Considering Marginal Bit Coverage in One-Hot Encoding

This paper proposes enhancing the Factorization Machine with Quadratic-optimization Annealing (FMQA) algorithm by designing initial training data using Latin hypercube and Sobol' sampling methods to ensure complete marginal bit coverage in one-hot encoding, thereby improving optimization performance on integer and discretized continuous variable problems.

The Gist

Imagine you are trying to find the perfect shape for the wing of a human-powered airplane. You want it to fly as fast as possible, but the physics involved are so complex that you can't write down a simple formula to predict the speed. Instead, you have to build a virtual model, test it, see how fast it goes, and then try again. This is a "black-box" problem: you put a design in, and a speed comes out, but you don't know the secret recipe inside.

To solve this, researchers use a smart computer program called FMQA. Think of FMQA as a two-step detective team:

1. The Surrogate (The Student): A machine learning model that tries to guess the answer based on past tests.
2. The Searcher (The Hunter): A specialized computer (an "Ising machine") that uses the student's guesses to hunt for the best possible wing shape.

The Problem: The "Silent" Bits

To make the computer understand the wing shape, the researchers translate the continuous design variables (like "wing length") into a string of binary switches (0s and 1s) using a method called one-hot encoding.

Imagine you have 32 switches for "wing length." To say the length is "medium," you flip exactly one of those 32 switches to "ON" (1) and leave the other 31 "OFF" (0).

The paper identifies a flaw in how they usually start this process. They typically pick the starting wing shapes by rolling dice (random sampling).

• The Issue: If you roll the dice only 32 times to start, there's a high chance (about 36%) that some of those 32 switches will never get flipped to "ON" during the initial phase.
• The Consequence: The "Student" (the machine learning model) learns by looking at the switches that were ON. If a switch was never ON, the Student never learns how that specific setting affects the speed. It's like a teacher trying to grade a student who never raised their hand; the teacher has no data on that student's ability.
• The Result: The computer's "map" of the problem has blind spots. When the "Hunter" goes looking for the best solution, it might ignore good areas because the map says, "We have no idea what happens here."

The Solution: The "Fair Sampling" Strategy

The authors propose a new way to pick the starting wing shapes. Instead of just rolling dice, they use two mathematical tools called Latin Hypercube Sampling (LHS) and the Sobol' sequence.

Think of these tools as a fairness inspector.

• Instead of hoping luck will flip every switch, the inspector ensures that every single one of the 32 switches is flipped to "ON" at least once during the initial 32 tests.
• This guarantees that the "Student" gets a direct lesson on every single possible setting before the real search begins. No switch is left in the dark.

The Results: Better Wings, Faster

The researchers tested this on two versions of the airplane wing problem: one with 17 design variables and a harder one with 32 variables.

1. The "Old Way" (Random): Even after running 200 tests, about 36% of the switches had never been turned on in the starting data. The computer's performance was okay, but it had blind spots.
2. The "New Way" (LHS and Sobol'): Every switch was turned on at least once right from the start.
   • The Outcome: The new methods found wing shapes that flew faster than the old random method.
   • The Difference: The improvement was small for the simpler problem but became much more obvious for the harder, 32-variable problem. It's like the blind spots in the map mattered more when the terrain got more complex.

The Takeaway

The paper doesn't claim this makes the computer fly the plane itself, nor does it claim this solves all optimization problems. It simply shows that how you start matters.

By using a "fair sampling" strategy to ensure every possible option gets a chance to be seen in the initial training data, the computer learns a better map of the problem. This allows it to find better solutions faster, especially when the problem gets complicated. It's a reminder that in optimization, you don't just need a smart search engine; you need a smart way to start the journey.

Technical Summary

Technical Summary: Improving FMQA via Initial Training Data Design Considering Marginal Bit Coverage in One-Hot Encoding

Problem Statement
Factorization Machine with Quadratic-Optimization Annealing (FMQA) is a black-box optimization (BBO) method that combines a Factorization Machine (FM) surrogate model with an Ising machine for search. When FMQA is applied to integer or discretized continuous variables using one-hot encoding, a critical issue arises with uniform random initial sampling. In this scenario, many binary variables (bits) in the initial training dataset may never take the value "1." Since the gradient of the FM output with respect to parameters associated with a specific bit is proportional to the value of that bit, parameters corresponding to bits that remain "0" throughout the initial dataset receive no direct gradient updates from observed responses. Consequently, these parameters evolve solely based on initialization and weight decay, introducing bias into the estimated Quadratic Unconstrained Binary Optimization (QUBO) coefficients. This bias can degrade the quality of the solution search performed by the Ising machine, particularly in higher-dimensional problems.

Methodology
The authors propose a modification to the FMQA framework focused on the design of the initial training data. The core objective is to achieve complete marginal bit coverage, ensuring that every binary variable obtained via one-hot encoding takes the value "1" at least once in the initial dataset.

To realize this, the authors introduce two initial data generation methods based on space-filling sampling techniques:

1. LHS-FMQA: Utilizes Latin Hypercube Sampling (LHS).
2. Sobol'-FMQA: Utilizes the Sobol' sequence (a deterministic low-discrepancy sequence).

Both methods are configured such that the number of initial samples ($N_0$) equals the number of discrete values per variable ($M$). Under one-hot encoding, where each original variable is represented by $M$ binary bits, setting $N_0 = M$ allows these sampling strategies to guarantee that each discrete value is selected at least once. Through the decoding map, this ensures that every corresponding binary bit takes the value "1" at least once. This guarantees that all FM parameters receive direct dataset-derived gradient updates during the initial training phase, mitigating the bias caused by "never-active" bits.

Key Contributions

• Identification of a Bias Mechanism: The paper formally identifies that uniform random sampling in one-hot encoded FMQA leads to "never-active" bits, causing specific FM parameters to be uninformed by observed black-box responses.
• Proposed Initialization Strategy: The authors propose and implement initial training data designs using LHS and Sobol' sequences specifically to enforce marginal bit coverage ($N_0 = M$).
• Empirical Validation: The methods are evaluated on the Human-Powered Aircraft (HPA) wing-shape optimization benchmark (HPA103), a complex engineering problem with implicit constraints and no analytical gradient information. Experiments were conducted on two problem scales: 17 design variables (HPA103-1) and 32 design variables (HPA103-2).

Results
Numerical experiments comparing the proposed methods (LHS-FMQA and Sobol'-FMQA) against a baseline Conv-FMQA (uniform random initialization) and other optimizers (GP-BO, NSGA-II, Random Search) yielded the following:

• Performance Improvement: Both proposed methods achieved numerically higher mean final cruising speeds than the baseline Conv-FMQA.
• Dimensionality Dependence: The advantage of the proposed methods was more pronounced in the higher-dimensional problem (HPA103-2, 32 variables). The improvement in final cruising speed over the baseline increased from approximately +0.135 m/s (LHS) and +0.192 m/s (Sobol') on the 17-variable problem to +0.333 m/s and +0.352 m/s, respectively, on the 32-variable problem.
• Mechanism Confirmation: Analysis of bit usage distributions confirmed that while Conv-FMQA retained approximately 36% of "never-active" bits even after the full evaluation budget, the proposed methods achieved 0% "never-active" bits.
• Comparison with Other Optimizers: The proposed methods performed comparably to or better than GP-BO and NSGA-II. Notably, the improvement over Conv-FMQA was driven by the optimization process after the initial sampling phase (higher "gain"), rather than simply starting from better initial best values.

Significance and Claims
The paper claims that improving marginal bit coverage in the initial training data is a crucial factor for enhancing FMQA performance. By ensuring that every binary variable is active at least once, the proposed methods prevent the QUBO coefficients from being determined solely by initialization and weight decay in specific directions. This allows the Ising machine to perform an informed search across all design dimensions.

The authors modestly note that while their results support the hypothesis that marginal coverage reduces bias, the current study does not fully isolate the effect of marginal coverage from the space-filling properties of LHS and Sobol' sequences. They acknowledge that the proposed methods simultaneously achieve both properties. Furthermore, they note that the methods guarantee marginal coverage but not pairwise bit coverage (interactions between bits). The study concludes that these initialization strategies are particularly effective for higher-dimensional problems where the absolute number of potentially inactive bits in random sampling would otherwise be substantial. Future work is suggested to decouple marginal coverage from space-filling properties and to investigate pairwise coverage strategies.