Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learning
원문 초록
Integer Linear Programs (ILPs) are powerful tools for modeling and solving a large number of combinatorial optimization problems. Recently, it has been shown that Large Neighborhood Search (LNS), as a heuristic algorithm, can find high quality solutions to ILPs faster than Branch and Bound. However, how to find the right heuristics to maximize the performance of LNS remains an open problem. In this paper, we propose a novel approach, CL-LNS, that delivers state-of-the-art anytime performance on several ILP benchmarks measured by metrics including the primal gap, the primal integral, survival rates and the best performing rate. Specifically, CL-LNS collects positive and negative solution samples from an expert heuristic that is slow to compute and learns a new one with a contrastive loss. We use graph attention networks and a richer set of features to further improve its performance.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
지지 비지배점에 의한 다목적 네트워크 문제의 비지배 집합 표현
Representing the Non-dominated Set of Multi-objective Network Problems by Supported Non-dominated Points
다목적 조합 최적화에서 비지지 비지배점(unsupported non-dominated point)은 통상 지지점(supported point)보다 수가 많으며, 계산하기도 훨씬 어려운 경우가 많다. 최근 연구에 따르면 극단 지지 비지배점(extreme supported non-dominated point)은 특정 이진 문제의 비지배 집합에 대해 고품질 표현을 제공한다. 본 논문에서는 이 관찰이 용량 제한 네트워크 최적화 문제로 일반화되지 않음을 보인다. 즉, 호(arc) 용량이 증가할수록 표현 품질이 저하되는 반면, 지지 비지배점은 여러 품질 지표에서 지속적으로 고품질 표현을 제공한다. 그러나 지지점 집합도 실용적인 응용에서는 지나치게 클 수 있으며, 일반적으로 소수의 고정된 대안만이 요구된다. 비지배 집합에서 고정 크기 표현을 선택하려면 계산 비용이 높은 전체 집합 생성이 필요하므로, 표현이 제공하려는 계산 상의 이점이 감소한다. 따라서 본 논문은 부분집합 선택 문제에서 (극단) 지지점을 대안적 후보 집합으로 제안한다. 수치 실험 결과, 후보 집합을 지지 비지배점으로 제한하더라도 완전한 비지배 집합에서 선택한 것과 거의 동일한 품질의 고정 크기 표현을 얻을 수 있음을 보인다. 종합하면, 지지 비지배점은 고품질 표현이자 부분집합 선택을 위한 합리적인 후보 집합으로 모두 활용될 수 있다.
Read It Back: 사전학습된 MLLM은 텍스트-이미지 생성을 위한 제로샷 보상 모델이다
Read It Back: Pretrained MLLMs Are Zero-Shot Reward Models for Text-to-Image Generation
본 논문에서 우리는 SpectraReward를 제안한다. SpectraReward는 사전학습된 다중모달 대규모 언어 모델(MLLM)을 이미지 생성 강화학습을 위한 즉시 사용 가능한 보상 모델로 전환하는 추가 학습이 불필요한 보상 함수이다. SpectraReward는 MLLM에게 생성된 이미지를 판단하거나 분해된 검증 질문에 답하도록 요청하는 대신, 단일 이미지 조건부 교사 강제(teacher-forced) 순전파를 통해 원본 프롬프트가 생성된 이미지로부터 얼마나 잘 복원될 수 있는지를 측정한다. 이미지 조건부 프롬프트 로그-가능도의 평균을 보상으로 사용함으로써, 선호도 레이블이나 보상 모델 미세조정 없이 MLLM의 사전학습된 이미지-텍스트 정렬 능력을 직접 재활용한다. 나아가 우리는 Self-SpectraReward를 소개한다. Self-SpectraReward는 통합 다중모달 모델을 위한 특수 사례로, 정책 자체의 이해 브랜치가 생성 브랜치를 위한 보상 모델로 기능하여 외부 보상 모델이나 외부 지식 없이 폐쇄 루프 자기 개선 프레임워크를 형성한다. 광범위한 실험을 통해 SpectraReward를 검증하였으며, 이 연구는 두 가지 확산 모델, 세 가지 강화학습 알고리즘, 4B에서 235B 파라미터에 걸친 네 가지 MLLM 계열의 아홉 가지 보상 MLLM 백본, 다섯 가지 분포 외(out-of-distribution) 텍스트-이미지 벤치마크를 포괄한다. 실험 결과, SpectraReward와 Self-SpectraReward 모두 생성 성능을 유의미하고 일관되게 향상시키며 기존 MLLM 기반 보상 학습 방법을 능가하였다. 추가 분석에 따르면 더 큰 보상 MLLM이 항상 더 우수한 것은 아니며, Self-SpectraReward는 훨씬 더 큰 외부 보상 모델과 동등하거나 이를 능가할 수 있어, 보상-정책 정렬(reward-policy alignment)이 효과적인 이미지 생성 강화학습의 핵심 요인임을 시사한다. 프로젝트 페이지: https://huangrh99.github.io/SpectraReward/
3D 수어 생성을 위한 확산 기반 운동학 및 동역학 모델
A Diffusion-Based Kinematics and Dynamics Model for 3D Sign Language Production
수어 생성(SLP)은 언어적 입력으로부터 연속적인 수어 동작을 생성하며 수어 아바타와 같은 접근성 기술을 구동한다. 확산 모델을 포함한 현재의 생성기는 관절 좌표를 구조 없는 벡터로 회귀하므로, 생성된 신체가 해부학이나 운동의 역학을 따르도록 보장하는 요소가 없다. 물리학은 기하학적 손실 항을 통해서만 SLP에 도입되었으며 그 이점이 이해도에 미치는 영향은 검증되지 않았고, 수어를 하는 신체의 동역학은 모델링되지 않았다. 본 논문은 두 수준에서 물리 정보를 활용하는 확산 모델 PIDiffSign을 제안한다. 운동학 측면에서는 순기구학 헤드가 뼈의 방향과 길이를 출력하고 이를 조합하여 해부학적으로 정확한 골격을 구성한다. 동역학 측면에서는 인체측정학적 매개변수를 갖는 상체 강체 모델이 두 가지 학습 사전분포를 뒷받침한다. 운동 제어의 두 법칙을 포함하는 물리적 타당성 평가 모음이 생성된 수어를 평가한다. 통제된 프로토콜에서 이 헤드는 PHOENIX14T와 CSL-Daily에서 역번역 단어 오류율을 약 5포인트 낮추는 반면 기하학적 페널티는 측정 가능한 효과가 없으며, 대조 실험은 이득이 뼈 길이 보존이 아니라 운동학적 사슬 표현에서 비롯됨을 추적한다. 동역학 사전분포는 PHOENIX14T에서 물리적이지 않은 대응 대조군보다 약 1포인트 추가 이득을 주지만 CSL-Daily에서는 그렇지 않다. 생성된 수어는 운동 제어 법칙을 실제 수어만큼 근접하게 따르지만 운동 에너지는 현저히 적다. 정확한 골격은 리깅된 아바타를 직접 구동할 수 있으며, 이 평가 모음은 향후 SLP 시스템을 위한 물리적 벤치마크를 제공한다.
공정한 자기지도 학습을 위한 편향 없는 Open World 정규화
Unbiased Open World Regularization for Fair Self-Supervised Learning
최근의 발전에도 불구하고 자기지도 학습(SSL) 모델과 결합 임베딩 예측 아키텍처(JEPA)는 여전히 허위 상관관계에 취약하다. 많은 붕괴 방지 정규화 기법은 전역 표현 분포가 다변량 가우시안이나 구면 위의 균등분포와 같이 미리 정해진 목표 분포와 일치하도록 제약한다. 그러나 전역 분포 일치는 편향 속성으로 정의되는 집단들이 표현 공간의 서로 다른 영역을 차지하는 것을 막지 못한다. 본 논문은 EnD와 FSCL을 포함한 기존의 인코더 기반 편향 제거 정규화 기법이 조건부 분포 일치의 제한된 형태로 해석될 수 있음을 보인다. 이러한 해석을 바탕으로, 관측된 각 편향 집단 내부의 표현 분포를 공통의 목표 분포에 일치시키는 Unbiased Open World(UOW)를 제안한다. 모집단 최적해에서 판별적 조건부 불일치도를 사용하면 표현과 대상 속성 사이의 독립성이 보장된다. 우리는 UOW를 가우시안 공간과 구면 공간에서 구현하고, 통제된 합성 환경과 실제 공정성 벤치마크에서 평가한다. Synthetic Engraving, Colored MNIST, CelebA, Waterbirds 전반에서 조건부 일치는 유용한 하위 작업용 표현을 보존하면서도 전역 정규화에 비해 편향을 크게 줄인다. 여러 편향 속성을 함께 조건화하면 개별 주변 제약으로는 놓치는 교차적 격차도 추가로 줄어든다. 마지막으로 CelebA 실험은 공정성을 고려한 검증 기준에 따라 체크포인트를 선택한다면 UOW를 사전학습 목적함수로 사용하여 무작위 초기화에서부터 모델을 학습할 수 있음을 보여준다.
HierFlow: 자동 에이전트 워크플로 생성을 위한 계층적 결합 이중 공간 탐색
HierFlow: Hierarchical Coupled Dual-Space Search for Automatic Agentic Workflow Generation
구조화된 워크플로우는 대규모 언어 모델(LLM)이 복잡한 문제를 해결할 수 있게 해주지만, 이를 자동으로 생성하는 것은 방대한 조합적 탐색 공간으로 인해 심각하게 저해되며, 이는 종종 유연하지 않고 자원을 많이 소모하는 오프라인 학습 의존성을 초래한다. 이를 해결하기 위해, 우리는 워크플로우 생성을 상위 토폴로지 층이 하위 작업 경계를 규정하고 하위 수준의 실행 결과가 토폴로지 자체를 능동적으로 재형성하는, 토폴로지와 실행이 맞물린 탐색 패러다임으로 개념화한다. 이 기반 위에서, 우리는 피드백 기반 토폴로지 조정과 하위 워크플로우 최적화를 위한 빠른 MCTS(Monte Carlo Tree Search) 기반 트리 탐색을 결합하여 에이전트형 워크플로우 설계를 자동화하는, 학습 불필요·테스트 시점 계층적 탐색 아키텍처인 HierFlow를 제안한다. HierFlow는 맥락적 필요에 따라 실행 수준 탐색을 선택적으로 트리거하는 지능형 게이팅 모듈을 통해 효율성을 극대화하며, 우리는 작업 간 결합 정도가 계층적 분할의 효과에 미치는 영향을 상세히 분석함으로써 이 메커니즘을 추가로 뒷받침한다. 질의응답, 수학적 추론, 코드 생성 벤치마크에 걸친 종합적인 테스트는 HierFlow가 강력한 베이스라인을 지속적으로 능가하며, 추가 학습 부담 없이 고품질 결과와 계산 효율성의 최적 균형을 제공함을 확인한다.
학생 학습 자원 배분을 위한 유전 알고리즘
A genetic algorithm for student academic resource allocation
개별 학생에게 학습 자원을 최적으로 배분하는 것은 학습자 다양성을 다루고 공평한 교육 성과를 촉진하는 데 필수적이다. Erasmus+ KA220-SCH 프로젝트의 틀 안에서, 본 논문은 고등학교 수학 학생을 위한 교육 자료 선택을 엄격한 학습 시간 제약을 따르는 0-1 이진 조합 최적화(optimization) 문제로 모델링한다. 이 공식화의 NP-hard 복잡도를 고려할 때, 자원 카탈로그가 확대될수록 정확한 해법은 계산적으로 다루기 어려워진다. 이 과제를 해결하기 위해, 우리는 이진 결정 공간을 효과적으로 탐색하기 위해 특화된 제약 복구 메커니즘과 통합된 유전 알고리즘(Genetic Algorithm)을 제안한다. 10회의 독립 실행에 걸친 실험적 평가는 빠른 수렴, 높은 해 품질, 그리고 서로 다른 기본 시드에 걸친 강한 알고리즘적 안정성을 보여준다. 이 결과는 중등 교육에서 실시간 의사결정 지원 시스템을 위한 메타휴리스틱(metaheuristic) 접근법의 실용적 유용성을 확인한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.