예산 제약 서브모듈러 최대화를 위한 데이터 의존적 평가
Data-dependent Evaluations for Budgeted Submodular Maximization
한국어 초록
서브모듈러 최대화(submodular maximization)는 기계학습(machine learning) 및 데이터 마이닝(data mining) 등 다양한 분야의 알고리즘 개발에 중요한 기반 요소이다. 이 문제의 NP-난해성으로 인해, 서브모듈러 최대화 알고리즘의 분석은 일반적으로 비관적인 최악의 경우(worst-case) 근사 인수만을 제공한다. 주어진 문제 인스턴스에 대해 산출된 해가 최적 해에 얼마나 근접한지를 평가하는 것은 쉽지 않다. 본 논문에서는 배낭 제약(knapsack constraint)이 있는 서브모듈러 최대화에 대한 새로운 데이터 의존적 상한(data-dependent upper bounds)을 개발한다. 이 상한이 최적 해를 지배함을 이론적으로 증명하고, 실세계 데이터셋을 이용한 실험을 통해 해가 최적에 얼마나 근접한지 인증하는 데 있어 그 이점을 실증적으로 보인다.
원문 초록
Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.
요약
배낭 제약(knapsack constraint)이 있는 단조 서브모듈러 최대화(MSMK) 문제에서 기존의 비관적 최악의 경우 근사 인수 대신, 특정 문제 인스턴스에 대해 최적 해를 지배함이 이론적으로 증명된 새로운 데이터 의존적 상한(data-dependent upper bounds)을 슬라이싱·제거 전략 및 선형 프로그램 형태로 제안한다. 최대 커버리지, 수익 최대화, 피처 선택 등 실세계 데이터셋 실험에서 기존 상한보다 더 타이트하게 해의 최적성을 인증함을 실증적으로 보인다.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2607.05759v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
그래프 신경망을 통한 균일 시설 입지 문제 근사 학습
Learning to Approximate Uniform Facility Location via Graph Neural Networks
신경망, 특히 메시지 전달 신경망(MPNN)은 어려운 조합 최적화(combinatorial optimization) 문제를 해결하기 위한 휴리스틱으로 점차 널리 활용되고 있습니다. 그러나 많은 학습(training) 기반 방법론들은 지도 학습, 강화학습(reinforcement learning), 또는 그래디언트(gradient) 추정기에 의존하여 높은 계산 비용, 불안정한 학습, 또는 제한적인 이론적 보장만을 제공하는 한계가 있습니다. 전통적인 근사 알고리즘은 최악 조건 보장을 제공하지만 미분 불가능하며 자연적인 입력 분포의 구조에 적응할 수 없습니다. 본 연구에서는 클러스터링, 요약, 물류, 공급망 등에 응용되는 문제인 균일 시설 입지(Uniform Facility Location, UniFL) 문제를 통해 이러한 상충 관계를 조사합니다. 솔버의 지도 신호나 이산 완화(discrete relaxation) 없이도 근사 알고리즘 원리를 통합하는 완전 미분 가능한 MPNN을 제안합니다. 제안된 모델(model)은 증명 가능한 근사 보장을 지니며, 경험적으로 표준 근사 알고리즘보다 향상된 성능을 보여 정수 선형 계획법(integer linear programming)과의 격차를 좁힙니다.
계층적 $\mathcal{F}$-클러스터링: 트리 및 유계 직경 그래프로의 클러스터링의 근사와 난해성
Hierarchical $\mathcal{F}$-Clustering: Approximation and Hardness of Clustering into Trees and Bounded Diameter Graphs
계층적 클러스터링(Hierarchical Clustering) 문제의 다음과 같은 변형을 고려한다. 일반적으로 계층적 클러스터링을 구축할 때는 각 클러스터가 단일 원소(singleton)가 될 때까지 데이터를 재귀적으로 분할한다. 우리는 재귀 과정의 중단 조건을 완화하여, 남은 클러스터가 클래스 $\mathcal{F}$에 속하는 그래프가 되는 시점에 멈추도록 한다. 이 문제를 계층적 $\mathcal{F}$-클러스터링이라 하며, 임의의 해법의 품질은 수정된 Dasgupta의 클러스터링 목적 함수로 측정한다. $\mathcal{F}$의 두 가지 자연스러운 선택인 트리와 유계 직경(bounded diameter) 그래프를 연구한다. 트리로의 클러스터링과 유계 직경 그래프로의 클러스터링에 대해 각각 최초의 다항 시간 $\mathcal{O}(\log n\cdot\log\log n)$ 및 $\mathcal{O}(\log n)$ 근사 알고리즘을 제시한다. 주요 기술적 기여는 선형 계획법(linear programming)에 기반한 이러한 문제의 근사를 위한 프레임워크이다. 실제로 우리의 접근법을 적용할 수 있는 그래프 클래스 $\mathcal{F}$를 특성화하고, 이 클래스가 트리와 유계 직경 그래프를 모두 포함함을 보인다. 그러나 우리의 아이디어는 이들에 국한되지 않으며 다른 구조에도 유용할 수 있다. 넓게 말하면, 우리의 프레임워크는 대응하는 평면(flat) 클러스터링 문제—$p_{\mathcal{F}}$-Partitioning이라 부르는—가 자연스러운 ILP 정식화와 증명 가능한 근사 보장을 갖는 라운딩(rounding) 절차를 함께 허용할 때 적용된다. 직관적으로, 터미널(terminal)이라 불리는 정점 집합이 주어졌을 때 문제는 각 터미널에 대해 정점 의존적 구조적 술어(predicate)를 만족하도록 하는 간선 집합을 제거하는 것이다. 그런 다음 이러한 요소들을 사용하여 앞서 언급한 근사 보장을 갖는 클러스터링 트리를 구축한다. 이 결과를 보완하기 위해, 트리로의 계층적 클러스터링과 유계 직경 그래프로의 계층적 클러스터링 모두 소규모 집합 확장 가설(Small Set Expansion Hypothesis) 하에서 임의의 상수 배수 이내로 근사될 수 없음을 보인다.
MMAO: 연속 및 이산 최적화를 위한 내인성 자원 할당 기반 대사적 다중 에이전트 옵티마이저
MMAO: A Metabolic Multi-Agent Optimizer with Endogenous Resource Allocation for Continuous and Discrete Optimization
Minimal MMAO: 적응형 메타휴리스틱 탐색을 위한 자원 폐쇄 루프 프레임워크
Minimal MMAO: A Resource-Closed-Loop Framework for Adaptive Metaheuristic Search
공정 예산 연속 및 이산 벤치마크에서 MMAO의 대규모 실증 평가
A Large-Scale Empirical Evaluation of MMAO Under Fair-Budget Continuous and Discrete Benchmarks
MMAO: Mechanism and Stability Analysis of Metabolic Closed-Loop Metaheuristics
토론
이 논문과 연결된 포럼 글이 아직 없습니다.