arXiv:2510.13210v2 cs.LG

볼츠만 머신 학습에서 이징 및 QUBO 변수 인코딩의 성능 평가

Performance Evaluation of Ising and QUBO Variable Encodings in Boltzmann Machine Learning

Yasushi Hasegawa, Masayuki Ohzeki

제출 2025-10-15

저자 비고

arXiv Comments

19pages, 10figures

한국어 초록

본 연구에서는 각 비교 내에서 샘플러, 옵티마이저(optimizer), 학습률 설계를 고정한 통제된 프로토콜 하에 볼츠만 머신 학습(Boltzmann machine learning)을 위한 이징(Ising, {-1, +1}) 및 QUBO({0, 1}) 인코딩을 비교합니다. 피셔 정보 행렬(Fisher Information Matrix, FIM)이 충분통계량의 공분산과 같다는 항등식을 활용하여, 모델 샘플로부터 도출된 경험적 모멘트를 시각화하고 표현에 따른 체계적인 차이를 밝혀냅니다. QUBO는 1차 및 2차 통계량 간에 더 큰 교차항(cross term)을 유발하여 FIM에서 더 많은 작은 고윳값 방향을 생성하고 스펙트럼 엔트로피를 낮춥니다. 이러한 불량 조건(ill-conditioning)은 확률적 경사하강법(SGD) 환경에서 수렴이 더 느려지는 원인을 설명합니다. 대조적으로, FIM 메트릭으로 업데이트 크기를 재조정하는 전체 FIM 자연 경사하강법(NGD)은 인코딩 전반에 걸쳐 유사한 수렴을 달성하는 반면, 대각 FIM 근사는 표현에 따른 차이를 다시 야기할 수 있습니다. 실질적으로 SGD 기반 학습의 경우 이징 인코딩이 더 등방성(isotropic)에 가까운 곡률과 더 빠른 수렴을 제공하며, QUBO의 경우 중심화/스케일링 또는 NGD 스타일의 사전조건화(preconditioning)가 곡률의 병리적 특성을 완화합니다. 이러한 결과는 표현 방식이 볼츠만 머신의 정보 기하학 및 유한 시간 학습 역학을 어떻게 형성하는지 명확히 보여주며, 변수 인코딩 및 전처리를 위한 실질적인 가이드라인을 제공합니다.

원문 초록

We compare Ising ({-1, +1}) and QUBO ({0, 1}) encodings for Boltzmann machine learning under controlled protocols that fix the sampler, optimizer, and learning-rate design within each comparison. Exploiting the identity that the Fisher information matrix (FIM) equals the covariance of sufficient statistics, we visualize empirical moments from model samples and reveal systematic, representation-dependent differences. QUBO induces larger cross terms between first- and second-order statistics, creating more small-eigenvalue directions in the FIM and lowering spectral entropy. This ill-conditioning explains slower convergence under stochastic gradient descent (SGD). In contrast, full-FIM natural gradient descent (NGD), which rescales updates by the FIM metric, achieves similar convergence across encodings, whereas diagonal-FIM approximation can reintroduce representation-dependent differences. Practically, for SGD-based training, the Ising encoding provides more isotropic curvature and faster convergence; for QUBO, centering/scaling or NGD-style preconditioning mitigates curvature pathologies. These results clarify how representation shapes information geometry and finite-time learning dynamics in Boltzmann machines and yield actionable guidelines for variable encoding and preprocessing.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2510.13210v2

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2609.26978v1stat.ML공통 태그 Stochastic Optimization, Combinatorial Optimization

다중 스케일 행렬 가중치를 통한 온라인 역 선형 최적화의 정밀 후회 상한

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

고정된 알려지지 않은 선형 효용(utility)을 갖는 온라인 역 선형 최적화를 연구한다. 각 라운드에서 환경(environment)은 컴팩트 행동 집합을 제시하고, 학습자(learner)는 그 집합에서 행동(action)을 추천하며, 환경은 동일한 집합 위에서 효용을 최대화하는 행동을 반환한다. 효용 벡터와 행동이 $d$차원 유클리드 단위 구(unit ball) 안에 있을 때, 시간 지평(time horizon)을 알 필요 없이 모든 시간 지평에 대해 기대 후회(regret)---최적 행동 대비 누적 효용 부족분---가 $O(\sqrt d)$인 무작위 알고리즘을 제시한다. $d$에 대한 의존성은 $T\ge d$인 지평에 대한 알려진 $\Omega(\sqrt d)$ 하한에 의해 상수 배수까지 최적이다. 우리 알고리즘은 기하학적으로 간격을 둔 스케일에서 다항식 특징(feature) 공간上的 행렬 곱셈 가중(matrix multiplicative weights)을 유지한다. 선형 프로그램(linear program)을 풀어 추천 분포를 선택하고, 이용 가능한 행동과 피드백 행동을 비교하여 점수 행렬을 갱신한다. 유리수 oracle 출력과 피드백 행동 하에서, 선형 최적화 oracle에 상대적으로 계산 가능한 구현이 $O(\sqrt d)$ 후회 상한을 유지한다. 차원, 지평, 입력 길이에 대해 다항 시간 실행 복잡도로 동일한 rate를 달성할 수 있는지는 열려 있다.

arXiv:2609.28263v1cs.LG공통 태그 Stochastic Optimization, Combinatorial Optimization

재해결 없이 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법

Resource-Adaptive Stochastic Gradient Descent for Online Linear Programming without Re-solving

대규모 언어 모델(LLM) 추론과 검색 서비스의 확대는 온라인 선형 계획 문제의 규모를 키우며, 계산적으로 효율적인 알고리즘을 요구한다. 본 연구는 확률적 온라인 선형 계획을 위한 자원 적응형 확률적 경사하강법(RASGD)을 제안한다. 이 알고리즘은 요청 하나와 현재 재고(inventory)만으로 자원 가격을 갱신하며, 자원 m개에 대해 도착(arrival)마다 O(m) 연산과 메모리만 필요하고 LP나 표본 평균 최적화(sample-average optimization)는 사용하지 않는다. 핵심은 재해결(re-solving)에서 쓰이는 현재 자원 가격 책정 로직을 1차 SGD 갱신으로 표현하는 것이다. 각 도착마다 이중 목적(dual objective)의 잔여 재고 허용량(allowance)을 갱신하고, 스텝 크기(stepsize)는 초기에는 학습을 위해 작아지다가 이후에는 재고 조정 속도에 맞추어 커진다. 표준 비퇴화(non-degeneracy) 조건 하에서 알고리즘은 모든 표본 경로(sample path)에서 실행 가능(feasible)하며, 실현된 분수적 후견 최적(realized fractional hindsight optimum) 대비 O(\log T) 기대 후회(expected regret)를 달성한다. 이는 분포를 알고 계산 제약이 없는 정책에 대한 하한과 일치한다. 분석은 변화하는 자원 수준에서 최적 가격을 추적하지 않고, 고정 참조 가격 주변의 곡률(curvature)을 재고 안정성(inventory stability)으로 전환한다. 수치 실험에서 RASGD는 도착마다 LP 재해결과 견줄 만한 후회를 달성하고, 시험한 1차 기준선(first-order baselines)보다 나으면서 1차 방법의 계산 효율은 유지한다. 이 결과는 RASGD가 대규모 OLP에서 높은 할당 품질을 계산 효율적으로 달성하는 접근임을 보여준다.

arXiv:2609.23180v1quant-ph공통 태그 Stochastic Optimization, Combinatorial Optimization

잡음이 있는 QAOA 최적화를 위한 적응형 차분 진화 및 다중 시작 탐색

Adaptive Differential Evolution and Multistart Search for Noisy QAOA Optimization

우리는 $N=12$, $p=3$, $D=6$ 조건에서 네 가지 비용 해밀토니안(cost-Hamiltonian) 계열에 걸쳐 고정된 저심도(low-depth) 양자 근사 최적화 알고리즘(Quantum Approximate Optimization Algorithm, QAOA) 앤자츠(ansatz)에 대한 고전적 최적화를 벤치마크한다. 10개의 옵티마이저를 10,000회 및 30,000회의 함수 평가(function evaluations, FEs)라는 공통 상한 하에서 25회의 독립 실행에 걸쳐 비교하며, 먼저 정확한 상태벡터(statevector) 목적함수로, 이후 두 가지 수준의 가산 관측 잡음(observation noise)을 적용하여 비교한다. 정확한 목적함수에서는 다중 시작(multistart) BFGS와 다중 시작 CMA-ES가 우세하다. 잡음이 있는 피드백 하에서는 적응형 개체군(population) 기반 방법들이 더 경쟁력을 갖게 되지만, 그 순위는 성능을 방문한 최적의 정확한 지점으로 측정하는지 아니면 잡음이 있는 관측값으로부터 선택된 지점으로 측정하는지에 따라 달라진다. 각 계열별로 사전 선별된 세 가지 인스턴스 전체에 대한 표적 확장 실험은 이러한 국면 전환(regime change)을 확인해주는 동시에, 명명된 적응형 차분 진화(adaptive-DE) 우승자들이 인스턴스에 따라 달라짐을 보여준다: 동일 인스턴스 요약에서 jSO-lite는 저잡음 오라클 탐색을, iL-SHADE는 고잡음 오라클 탐색을, L-SRTDE는 고잡음 선택 해(solution)를 각각 주도한다. 부트스트랩(bootstrap) 분석은 무시할 수 없는 수준의 고잡음 탐색-선택 격차(search-selection gap)를 정량화하며, 소급적 고정 예산 검증 프록시(retrospective fixed-budget verification proxy)는 최종 재평가를 위해 소량의 측정 예산을 남겨두는 것이 30,000 FEs에서 열 가지 방법 모두에 걸쳐 선택된 해의 품질을 향상시킴을 보여준다. 추가적인 구조 인식(structure-aware) 연구는 나아가 이러한 조건에서 QAOA의 교차 심도 제한(cross-depth restriction)과 연속적 분지 정제(continuous basin refinement)가 단독 몬테카를로 트리 탐색(Monte Carlo tree-search) 선택보다 더 유용함을 보여준다. 전반적으로 옵티마이저 선택은 지형 구조(landscape structure), 관측 잡음, 그리고 최종 지점 식별(final-point identification)에 공동으로 의존한다.

arXiv:2607.22550v1math.OC공통 태그 Stochastic Optimization, Combinatorial Optimization

대규모 최적화 학습: 확률적 조합 최적화를 위한 Benders 분해-TransfORmer 프레임워크

Learning to Optimize at Scale: A Benders Decomposition-TransfORmers Framework for Stochastic Combinatorial Optimization

우리는 대규모 2단계 확률적 혼합정수 프로그램을 풀기 위한 학습 보강 Benders 분해 프레임워크를 제안한다. 우리는 수요 불확실성 하의 2단계 확률적 용량 제약 lot-sizing 문제(TSSCLSP)에 초점을 맞춘다. 우리의 방법은 시나리오 하위 문제(subproblem)에 대한 고품질 근사해를 신속하게 생성하기 위해 사전학습된 TransfORmer 모델을 사용하여 분해의 수렴을 가속화한다. 이 하이브리드 전략은 TransfORmer 예측을 활용해 강력한 최적성 및 실행 가능성 컷(cut)을 생성하여 Benders 마스터 문제를 효과적으로 안내한다. 우리의 프레임워크에는 새로운 확장 가능 생성 메커니즘이 포함되어, 고정된 시간 구간(horizon)에서 학습된 모델이 임의 길이의 인스턴스를 풀 수 있게 한다. 검토한 테스트 세트에서 우리의 방법은 T = 270까지의 인스턴스를 풀며, 이는 기존 접근법으로는 다루기 어려웠던 규모이며, 생성된 하위 문제 해에서 실행 불가능성(infeasibility)을 0으로 유지한다. 이는 고전적 분해 알고리즘 내에 내장된 강력한 대리(surrogate) 솔버로서 TransfORmer의 잠재력을 보여준다.

arXiv:2607.22539v1math.OC공통 태그 Stochastic Optimization, Combinatorial Optimization

방사선 치료 스케줄링을 위한 최적화 모델 비교

Comparing Optimization Models for Radiotherapy Scheduling

방사선 치료 스케줄링 문제(Radiotherapy Scheduling Problem, RTSP)는 방사선 치료를 받는 환자들에 대한 최적 일정을 결정하는 문제로, 방사선 치료가 암 치료에서 핵심적인 역할을 하므로 임상 결과에 큰 영향을 미치는 과업이다. 하루가 끝날 때 새로 도착한 모든 환자를 함께 스케줄링하는 일일 배치 접근법은 정수 선형 계획(Integer Linear Programming)으로 모델링되며, 현재 RTSP에 대한 가장 효과적인 방법 중 하나이다. 그러나 이러한 형식화는 시간과 메모리 측면에서 상당한 계산 자원을 필요로 한다. 본 연구에서는 RTSP First Fit과 RTSP Best Fit이라는 두 가지 새로운 탐욕적 휴리스틱(greedy heuristics)을 개발하고, 이를 시뮬레이티드 어닐링(Simulated Annealing, SA) 접근법의 구성적 휴리스틱(constructive heuristics)으로 사용하여 스케줄링을 최적화함으로써 이러한 한계를 해결한다. 제안된 방법——휴리스틱 단독 및 SA와의 결합——은 공개 데이터셋에서 두 가지 서로 다른 최신 정확 솔버(exact solvers)로 풀린 정수 선형 프로그램(integer linear program) 형식화와 비교하여 평가된다. 평가 지표에는 환자 대기 시간, 선호도 충족, 선형 가속기(linear accelerator) 배정 변경(네 가지 서로 다른 가중치 구성으로 집계)을 포착하는 여섯 가지 스케줄링 목표, 풀이 시간, 메모리 소비가 포함된다. 결과는 새로운 휴리스틱이 정확한 방법들의 해에 근접한 해를 달성하면서 실행 시간과 메모리 사용량을 극적으로 줄인다는 것을 보여준다. 또한 SA와 결합하면 실행 시간과 메모리 사용량을 낮게 유지하면서 해의 품질을 더욱 향상시킨다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.