CLARITree: 해석 가능한 구간선형 트리를 이용한 회귀를 위한 숄레스키 및 룩어헤드 가속
CLARITree: Cholesky and Lookahead Accelerations for Regression with Interpretable Piecewise Linear Trees
한국어 초록
회귀 트리는 기계 학습에서 가장 해석 가능하면서도 표현력이 뛰어난 모델 클래스 중 하나입니다. 역사적으로 탐욕적 귀납(greedy induction)은 성능이 우수한 회귀 트리를 구성하는 데 주류 접근법이었습니다. 동적 프로그래밍(dynamic programming)과 분기 한정(branch-and-bound)에 기반한 최적 방법들이 존재하지만, 일반 선형 회귀 트리에 대해서는 탐욕적 접근법보다 훨씬 우수한 성능을 달성하는 경우가 많음에도 불구하고 계산 비용이 과도하게 큽니다. 최근 연구에서는 특화된 룩어헤드(lookahead) 전략이 주로 분류 환경에서 준최적 성능을 유지하면서 실행 시간을 극적으로 개선할 수 있음을 보였습니다. 본 연구에서는 룩어헤드 방식의 탐색 전략과 그람 행렬(Gram matrix)의 효율적인 랭크-1 숄레스키(Cholesky) 업데이트를 결합하여 준최적의 희소 구간선형 회귀 트리를 위한 새로운 알고리즘을 개발합니다. 본 방법이 계산 효율성, 예측 정확도, 희소성(sparsity) 간의 유리한 균형을 달성하며 현재 최신 기술 대비 확장성이 현저히 우수함을 이론적·실증적으로 모두 입증합니다.
원문 초록
Regression trees are among the most interpretable yet expressive model classes in machine learning. Historically, greedy induction has been the dominant approach for constructing well-performing regression trees. While optimal methods based on dynamic programming and branch-and-bound exist, they are computationally prohibitive for general linear regression trees, despite often achieving substantially better performance than greedy approaches. Recent work has shown that specialized lookahead strategies can dramatically improve runtime while maintaining near-optimal performance, primarily in classification settings. In this work, we develop a novel algorithm for near-optimal, sparse, piecewise linear regression trees that combines a lookahead-style search strategy with efficient rank-one Cholesky updates of the Gram matrix. We demonstrate, both theoretically and empirically, that our method achieves a favorable trade-off between computational efficiency, predictive accuracy, and sparsity, and scales significantly better than the current state of the art.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2606.12840v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
BLOKS: 스케치된 블록 전처리를 통한 커널 솔버의 스케일링
BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning
커널 리지 회귀(Kernel Ridge Regression, KRR)는 비매개변수적 학습(nonparametric learning)을 위한 이론적으로 타당한 알고리즘이며, 심층 학습(deep learning)의 특성을 연구하는 데에도 자주 사용된다. 그러나 정확한(exact) KRR 수식은 대규모 데이터셋(dataset)에 적용할 수 없을 정도의 시간 및 메모리 비용을 발생시키며, 이는 근사 솔버(approximate solver) 개발의 동기가 되었다. 이러한 알고리즘들은 (i) 직접적인 해법의 계산 부담을 피하기 위한 반복적 방법(iterative method), (ii) 문제 크기를 줄이기 위한 스케칭(sketching) 또는 배치화(batching), (iii) 수렴(convergence)을 가속화하기 위한 전처리(preconditioning)에 의존한다. 빠른 수렴을 위해 필수적이지만, 전처리는 메모리 비용을 발생시키며, 이는 모델(model)의 자유 매개변수 수를 줄임으로써 관리할 수 있으나 그 대가로 표현력, 나아가 정확도가 저하될 수 있다. 이러한 문제를 해결하기 위해, 우리는 블록 자코비(Jacobi) 근사와 스케칭을 결합한 새로운 프리컨디셔너(preconditioner)를 중심으로 구축된, Nyström 방식으로 스케치된 KRR을 위한 컨주게이트 그래디언트(Conjugate Gradient) 기반 솔버인 BLOKS를 제안한다. BLOKS의 프리컨디셔너는 데이터셋 크기와 매개변수 수 모두와 무관한 메모리 비용을 가지므로, 대규모 모델로의 스케일링(scaling)이 가능하다. 우리는 메모리 효율적이고 GPU로 가속화된 구현을 제공하며, BLOKS가 우수한 시간/메모리 복잡도를 유지하면서도 뛰어난 정확도를 달성함을 보인다. 실제로, 커널 솔버를 벤치마킹(benchmark)하는 데 사용되는 표준 대규모 데이터셋에서 BLOKS는 최신(state-of-the-art) 기법들과 비교할 만하거나 그보다 더 나은 성능을 달성한다.
희소 가우시안 프로세스 회귀에서의 기저 함수 선택
On Basis Function Selection for Sparse Gaussian Process Regression
희소 가우시안 프로세스는 입력 공간 상의 고정 기저 $\{\phi_j\}$로의 적절한 전개로 커널을 대체함으로써 $O(N)$ 추론을 달성한다. 계산 예산 $M \ll N$이 주어지면, 실무자들은 관례적으로 기저를 처음 $M$개 항으로 잘라(truncate) 사용한다. 그러나 형식적 프레임워크상 데이터에 실제로 중요한 $M$개의 기저 함수만 선택하는 것을 막을 수는 없다. 이렇게 하면 신호가 없는 기저 함수에 예산을 쓰는 것을 피할 수 있지만, 후보를 순위 매기기 위한 기준이 필요하다. 우리는 기저 함수 선택 문제에 대한 정보 이론적 관점에서 도출한 세 가지 기준을 제안한다. 각 기준은 선택 시점의 서로 다른 지식 상태에 대응한다: 무-데이터(no-data) 상태, 무-사전(no-prior) 상태, 그리고 그 중간(in-between) 상태. 그런 다음 세 가지 기저 계열—Hilbert 공간 가우시안 프로세스(HSGP), 변분 푸리에 특징(VFF), 변분 inducing 구면 조화(VISH)—에 대해 여섯 개의 UCI 회귀 벤치마크에서 절단(truncation) 대비 선택(selection) 전략의 성능을 연구한다. 우리는 무-데이터 기준이 안전한 기본값이며, HSGP, VFF, VISH에 대해 절단과 동등하거나 더 나은 성능을 보이고, VISH에서는 상당한 이득을, 해당 기저 계열에 대해 최근 개발된 선택 휴리스틱 대비 개선을 보인다고 관찰한다. 데이터를 고려한 무-사전 및 중간 기준은 세 계열 중 실무에서 가장 널리 쓰이는 HSGP에 대해 절단 대비 상당한 이득을 제공한다.
잔차 기반 적응형 GMsFEM을 위한 가우시안 프로세스 대리 지표
Gaussian-process surrogate indicators for residual-based adaptive GMsFEM
고대비(high-contrast) 타원형 문제에 대한 잔차 기반 적응형 GMsFEM은 모든 coarse 이웃에서 국소 가중 $H^{-1}$ 지표를 반복적으로 평가하므로, 반복 쿼리(repeated-query) 설정에서 지표 평가가 반복되는 비용이 된다. D\"orfler marking에 사용되는 지표 점수에 대해 비침투적(non-intrusive) 가우시안 프로세스(GP) 대리 모형을 도입한다. 운영 예측량은 GP 사후 평균이며, 명시된 규약 하에서 커널 릿지 회귀(KRR) 추정량과 대수적으로 동등하다; 다중스케일 해법, 국소 스펙트럼 구성, 또는 기저 enrichment를 바꾸지 않고 압축된 국소 해와 스펙트럼 특징을 사용한다. 비균일 perturbed-marking 결과는 점별 점수 오차가 대리 모형이 선택한 이웃이 포착하는 정확한 지표 질량(indicator mass)에 미치는 영향을 정량화하고, 조건부 bounded-discrepancy KRR 경로는 이러한 점수 경계에 대한 충분한 가정을 밝힌다. 통제된 held-out in-distribution 테스트에서, 대리 모형이 안내하는 방법은 고전적 $H^{-1}$-잔차 오프라인 적응성과 비교 가능한 오차 대 자유도(DoF) 추세를 보이며, 오프라인 데이터 생성 및 GP 학습을 제외하면 온라인 지표 구성 요소 평가가 2.0–2.1배 빠르다.
TinyUDE: 리-테일러 제트 매칭을 통한 마이크로컨트롤러 기반의 솔버 없는 범용 미분 방정식
TinyUDE: Solver-Free Universal Differential Equations on Microcontrollers via Lie-Taylor Jet Matching
범용 미분 방정식(UDE) 학습(training)은 전통적으로 수치적 ODE 솔버를 통한 역전파에 의존하므로, 엣지 마이크로컨트롤러의 성능을 크게 초과하는 메모리 사용량을 발생시킵니다. 본 논문에서는 관측된 시스템 상태의 1차 및 2차 시간 도함수(derivative)에 하이브리드 벡터장을 직접 피팅하는 솔버 없는(solver-free) 학습 프레임워크인 리-테일러 제트 매칭(Lie-Taylor jet matching)을 제시합니다. 절단된 리-테일러 제트(truncated Lie-Taylor jet)인 이러한 도함수는 사비츠키-골레이(Savitzky-Golay) 필터링을 통해 온디바이스에서 온라인으로 추정되며, 자동 미분 소프트웨어 없이도 완전한 해석적 그래디언트를 생성합니다. 본 연구는 동일한 동역학, 노이즈 모델, 네트워크 아키텍처 및 평가 지표를 공유하는 기존 기준선(baseline)(고정 스텝 RK4 적분, 다중 슈팅, 정확한 이산 수반 변수법, Adam)과 비교하여 솔버를 제거하는 것이 정확도를 저하시키는지 평가합니다. 단순한 도함수 매칭은 센서 노이즈 환경에서 성능이 저하되지만, 본 연구의 노이즈 적응형 메커니즘인 전비율 위상 천이 샘플링, 레저버 버퍼, 가중치(weight) 평균화를 적용한 코사인 어닐링 최적화(optimization), 온디바이스 노이즈 추정, 다항식 미스핏 품질 게이팅을 통해 이러한 격차를 해소하고 역전시킵니다. 감쇠 진자 및 혼돈 이중 진자 실험에서, 제안하는 방법은 동일한 데이터 윈도우에서 기준선 정확도와 일치하거나 이를 능가하며 모델링되지 않은 감쇠 계수를 복원합니다. 0%에서 5%까지의 노이즈 수준 전반에서, 수 메가바이트의 솔버 테이프와 비교해 108 kB의 정적 메모리 내에서 기준선의 0.65배에 해당하는 기하평균 상대 필드 오차를 달성합니다. ESP32 마이크로컨트롤러에서의 온디바이스 실행은 61.3 kB의 정적 메모리와 업데이트당 7.24 ms(25 Hz에서 18.1% 듀티 사이클) 내에서 0.0020의 필드 오차에 도달하고 감쇠 계수를 c = 0.400(실제값 0.400)으로 복원하여, 수치 솔버 없이도 실시간 온디바이스 학습이 실현 가능함을 입증합니다.
스크레이프오프 층(Scrape Off Layer) 플라즈마 시뮬레이션을 위한 확률적·기하 인지 신경망 대리 모델
Probabilistic and Geometry Aware Neural Surrogate of Scrape Off Layer Plasma Simulations
토카막 경계 플라즈마 시뮬레이션을 위한 고속 대리 모델(surrogate)은 일반적으로 전역 운전점(operating point)을 셀 값들의 평탄화된 벡터로 매핑하는 결정론적 회귀기이다. 디버터 탈부착(divertor detachment) 전이 근처에서는 정상 상태(steady state)가 단일 값으로 안정적으로 정해지지 않는다. 점 추정(point estimate)은 질적으로 서로 다른 플라즈마 상태들에 걸쳐 평균을 내야 하며, 신뢰도에 대한 어떠한 언급도 없이 결과를 내놓는다. 더욱이 평탄화된 벡터 표현은 SOLPS-ITER 메시의 기하학적 구조를 버린다. 본 연구는 이 두 가지 문제를 모두 다룬다. 우리는 곡선형(curvilinear) 메시를 셀 인접성을 보존하고 정확히 역변환되는 배치를 가진 세 개의 고정 크기 이미지 텐서로 펼쳐, 합성곱 신경망(convolutional network)이 정보 손실 없이 기하 구조 위에서 동작할 수 있도록 한다. 이후 민감도가 높은 시스템에 적합한 조건부 플로 매칭(conditional flow matching) 모델을 이 표현 위에서 학습한다. 그 결과 민감한 운전점에서도 여러 개의 그럴듯한 결과를 포착하는 효율적이고 확장 가능한 대리 모델을 얻는다. 가스 퍼프(gas-puff) 스캔을 따라, 예측 분포는 초기 레짐 전이(regime transition)를 지나면서 고온 모드와 저온 모드로 갈라진다. 크기가 알려진 분기(bifurcation)를 주입한 합성 데이터에 대한 추가 검증에서도, 모델이 두 분기의 평균이 아니라 두 분기를 각각 복원함을 확인한다.
매개변수 예산 하에서 루프 추정의 통계적 이득
Statistical Gains from Looped Estimation under Parameter Budgets
인공지능에서 메모리 수요가 증가함에 따라 더 적은 학습 가능 매개변수로 학습하려는 동기가 커지고 있다. 본 연구는 반복(iteration)마다 매개변수를 공유하며 하나의 적합된 연산자를 반복 적용하는 루프 추정기(looped estimator)가 동일한 매개변수 예산 하에서 통계적 정확도를 향상시킬 수 있는지 묻는다. 이에 대응하는 기존의 비공유(untied) 추정기는 각 반복마다 별도의 매개변수를 사용한다. 일반적인 가능도(likelihood) 모델에 대해, 루프 시브(sieve) 최대 가능도 추정에 대한 제곱 Hellinger 위험의 상한과, 튜닝된 비공유 모델군에 대한 미니맥스 하한을 확립한다. 이 경계들은 매개변수-반복-정확도 간의 트레이드오프를 드러낸다. 즉, 반복 계산은 매개변수를 추가하지 않고도 근사를 개선할 수 있으나, 계산 비용과 적합된 함수 클래스의 복잡도를 증가시킨다. 알려진 Hölder 매끄러움을 갖는 목표 함수에 대해, 루프 잔차 순방향 신경망(residual feedforward network)과 특정한 post-layer-normalized 트랜스포머(Transformer)는 유계 실수 매개변수의 개수를 고정한 채로 로그 인자를 제외하고 미니맥스 다항 수렴률을 달성한다. 충분히 큰 고정 예산에서는 표본 크기가 증가함에 따라 루프 방식의 최악 사례 위험이 0으로 수렴하는 반면, 최적의 비공유 방식의 최악 사례 위험은 0으로부터 일정 수준 이상 떨어진 채로 유지된다. 명시된 예산 증가 조건 하에서는 루프 대 비공유 위험 비율 또한 0으로 수렴한다. 가우시안 및 라플라스 회귀, 이진 응답, 에너지 기반 밀도 추정을 통해 이론을 예시한다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.