arXiv:1910.08018

A Unified Framework for Tuning Hyperparameters in Clustering Problems

Xinjie Fan, Yuguang Yue, Purnamrita Sarkar, Y. X. Rachel Wang

제출 2019-10-17

원문 초록

Selecting hyperparameters for unsupervised learning problems is challenging in general due to the lack of ground truth for validation. Despite the prevalence of this issue in statistics and machine learning, especially in clustering problems, there are not many methods for tuning these hyperparameters with theoretical guarantees. In this paper, we provide a framework with provable guarantees for selecting hyperparameters in a number of distinct models. We consider both the subgaussian mixture model and network models to serve as examples of i.i.d. and non-i.i.d. data. We demonstrate that the same framework can be used to choose the Lagrange multipliers of penalty terms in semi-definite programming (SDP) relaxations for community detection, and the bandwidth parameter for constructing kernel similarity matrices for spectral clustering. By incorporating a cross-validation procedure, we show the framework can also do consistent model selection for network models. Using a variety of simulated and real data examples, we show that our framework outperforms other widely used tuning procedures in a broad range of parameter settings.

함께 살펴볼 논문

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

arXiv:2609.30277v2cs.LG공통 태그 Clustering, Community Detection

고정된 확산 없는 고정점: 수렴하는 테스트 시점 연산을 위한 암시적 신경 층

Fixed Points Without Fixed Diffusion: Implicit Neural Sheaves for Convergent Test-Time Computation

암시적 그래프 신경망(IGNN)은 노드 표현을 그래프 신경 연산자의 고정점(fixed point)으로 정의하여 실질적으로 무한한 깊이의 전파, 반복(iteration) 독립적인 매개변수화, 유연한 테스트 시점 연산(test-time computation)을 가능하게 합니다. 그러나 이러한 이점은 평형점이 유일하며 고정점 반복을 통해 도달할 수 있는지 여부에 달려 있습니다. 기존의 구조들은 이러한 보장을 얻기 위해 순환 업데이트에 제약을 가하는 경우가 많아 평형 상태에서 사용 가능한 변환을 제한했습니다. 이는 핵심적인 질문을 제기합니다: IGNN이 평형 정식화의 고유한 강점을 유지하면서 더 풍부한 엣지 의존적 변환을 통해 표현력을 얻을 수 있을까요? 본 논문에서는 적응형 신경 층(neural-sheaf) 전파를 갖춘 준동차(subhomogeneous) 심층 평형 아키텍처인 SheafDEQ를 소개합니다. 학습된 행렬 값 층 제한 사상(sheaf restriction map)은 이웃한 표현들을 정렬, 혼합 또는 반전시킬 수 있습니다. 완만한 정칙성 조건 하에서, SheafDEQ가 임의의 양의 초기 상태로부터 고정점 반복을 통해 전역적으로 도달 가능한 유일한 평형점을 가짐을 증명합니다. 나아가 축약성(contractivity)은 유계된 통신 지연(staleness) 하에서도 수렴을 보장합니다. 본 연구는 반복적인 비국소적 집계가 필요한 분산 추론(inference) 태스크와 연결 재구성이 점차 커뮤니티 간 상호작용을 선호하게 되는 커뮤니티 탐지 태스크에서 SheafDEQ를 평가합니다. SheafDEQ는 Sums, MNIST Terrain, Coordinates 태스크 및 연결성이 점차 이종친화적(heterophilic)으로 변하는 커뮤니티 탐지에서 암시적 베이스라인보다 향상된 성능을 보입니다. 또한 SheafDEQ는 평형 보장이 없는 순환 모델들과 비교해도 경쟁력을 유지합니다. 연속 반복 진단 결과 유한 구간(finite-horizon) 대조군과 달리 100회 반복까지 잔차가 감소하고 테스트 정확도가 유지됨을 확인하였으며, 지연 업데이트 실험에서는 유계된 통신 지연에 대해 낮은 민감도를 나타냈습니다.

arXiv:2609.26748v1stat.ME공통 태그 Clustering, Model Selection

$\beta$-통합 지역 깊이와 적응형 그룹화를 통한 자동 깊이 기반 로컬 중심 클러스터링

Automatic depth-based local center clustering via $\beta$-integrated local depth and adaptive grouping

클러스터링은 레이블이 없는 데이터를 여러 그룹으로 분할하는 비지도 학습 기법이다. 기존 대부분의 방법은 클러스터 수나 이웃 크기와 같이 사용자가 지정해야 하는 매개변수를 요구한다. 반면 우리는 수치적 매개변수 조정을 없애는 완전히 데이터 주도적인 방법인 automatic depth-based local center clustering(A-DLCC)을 제안한다. A-DLCC는 $\beta$-integrated local depth를 사용하여 여러 지역성 수준에서 일관되게 중심에 있는 점, 즉 안정적 exemplar인 local center를 식별하고, 이들을 대표성(representativeness)에 따라 순위화한다. 각 local center는 유사한 점들의 그룹을 유도하며, 그룹 수준 유사도는 제안한 비모수적 지표인 group-level local similarity로 측정한다. 병합을 안내하기 위해 그래프 이론의 bottleneck path 개념을 통합하며, 이는 우리의 적응형 병합 기준의 기반이 된다. 이 기준에 따라 그룹이 자기 자신보다 더 잘 도달하는 이웃에 흡수되거나, 양쪽 모두가 각자의 배경보다 더 도달 가능하다고 보는 이웃과 결합되는 단일 점진적 병합(agglomeration) 규칙을 설계한다. 모든 병합은 추가로 configuration-model null이 기대하는 것보다 강한 접촉(contact)에 의해 이루어져야 한다. 이 규칙은 클러스터 수를 자동으로 추정하고 병합을 중단할 시점을 결정한다. 합성 데이터와 실제 데이터에 대한 실험은 A-DLCC가 매개변수 조정 없이 해석 가능한 클러스터링 결과를 생성함을 보여준다.

arXiv:2607.22641v1cs.DL공통 태그 Clustering, Model Selection

AutoCluster, AutoTopicModeling, AutoTrendAnalysis: 신흥 트렌드 예측을 위한 완전한 AutoML 파이프라인

AutoCluster, AutoTopicModeling, AutoTrendAnalysis: A Complete AutoML Pipeline for Predicting Emerging Trends

신흥 트렌드 예측은 기업, 연구자, 정책 입안자에게 필수적이지만, 기존 접근법은 종종 확장성과 적응성이 부족하다. 본 논문은 시간 속성을 갖는 텍스트 데이터셋에서 통찰을 추출하도록 설계된 자동 머신러닝(AutoML) 기반 트렌드 예측 프레임워크를 제시한다. 시스템은 날짜 필드가 동반된 주제별 텍스트 항목을 입력으로 받는다. 파이프라인은 전처리와 임베딩으로 시작하며, 이어서 메타학습(meta-learning)을 사용해 최적의 클러스터링 알고리즘을 선택하는 AutoClustering이 수행된다. AutoTopicModeling은 successive halving을 적용하여 각 클러스터의 coherence score를 기준으로 Latent Dirichlet Allocation (LDA), Latent Semantic Analysis (LSA), BERTopic, 또는 Non-negative Matrix Factorization (NMF) 중 최적의 토픽 모델링 방법을 식별한다. 트렌드 예측을 위해 AutoTrendAnalysis는 Facebook Prophet, 자기회귀 통합 이동평균(AutoRegressive Integrated Moving Average, ARIMA), Loess를 이용한 계절-트렌드 분해(Seasonal-Trend decomposition using Loess, STL), 장단기 메모리(Long Short-Term Memory, LSTM) 등 여러 모델을 평가하며, successive halving 또는 전수 비교를 통해 평균 제곱근 오차(Root Mean Square Error, RMSE)를 기준으로 가장 정확한 모델을 선택한다. 토픽은 예측 결과에 따라 강한 신호, 약한 신호, 또는 노이즈로 분류되어 신흥 트렌드를 식별할 수 있다. 클러스터링, 토픽 모델링, 시계열 예측을 자동화함으로써 본 연구는 수작업을 줄이면서 트렌드 예측 정확도를 향상시킨다. 제안 시스템은 실시간 응용과 머신러닝 전문성이 제한된 이해관계자에게 적합한 확장 가능하고 사용하기 쉬운 솔루션을 제공한다. 실험 결과, 제안 시스템의 최적 시행은 최종 RMSE 7.099를 달성하여 높은 예측 정확도를 보여준다.

arXiv:2607.21039v1cs.LG공통 태그 Clustering, Community Detection

Grassmann 다양체 상의 정규화 최적화: 이론, 알고리즘 및 응용

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

스펙트럴 방법은 커뮤니티 탐지, 클러스터링, 그래프 학습에서 가장 널리 사용되는 기법 중 하나이다. 그러나 그 성능은 근본적인 스펙트럴 부분공간의 정확한 추정에 크게 의존하며, 노이즈, 이상치, 또는 모델 교란이 존재할 경우 상당히 악화될 수 있다. 이 한계를 해결하기 위해, 우리는 rank-$K$ 투영 행렬의 강건한 추정을 위한 정규화 투영 행렬 근사(Regularized Projection Matrix Approximation, RPMA) 프레임워크를 제안한다. RPMA는 정규화 항을 통합하여 고전적인 스펙트럴 투영을 확장하며, 더 강건하고 희소하며 해석 가능한 투영 추정치를 생성한다. 우리는 제안된 모델을 rank-$K$ 투영 행렬의 다양체 상의 최적화 문제로 공식화하고, Grassmann 다양체와의 기하학적 동등성을 활용한다. 이 다양체 특성화를 바탕으로, 1차 및 2차 최적성 조건을 유도하고, 정규화된 선행 고유공간의 국소 안정성을 확립하며, 충분히 작은 정규화 하에서 임계점 경관의 안정성을 특성화한다. 결과적인 비볼록 최적화 문제를 효율적으로 풀기 위해, 역추적 선 탐색(backtracking line search)을 갖춘 Riemann 그래디언트 투영 알고리즘과, 반복적인 고유값 분해를 피하는 보다 효율적인 Cayley--Sherman--Morrison--Woodbury(Cayley--SMW) 그래디언트 방법을 개발한다. 합성 및 실제 데이터셋에 대한 광범위한 실험은 RPMA가 투영 행렬의 복원 정확도를 크게 향상시키며, 노이즈가 있는 환경에서 커뮤니티 탐지 및 클러스터링을 위한 기존 스펙트럴 투영 방법보다 일관되게 우수한 성능을 보임을 입증한다.

arXiv:2607.14297v1stat.ME공통 태그 Clustering, Model Selection

비대칭 쌍선형 요인 분석기의 절약적 혼합 모형

Parsimonious Mixtures of Skewed Bilinear Factor Analyzers

비대칭 무작위 행렬을 군집화하는 혼합 모형은 차원 축소를 수행하지 않을 경우 과매개변수화 문제를 자주 겪을 수 있다. 쌍선형 요인 분석기를 사용하더라도, 군집 간 매개변수에 제약을 가함으로써 추가적인 매개변수 축소를 달성할 수 있다. 본 원고에서는 비대칭 행렬 변량 쌍선형 요인 분석기 혼합 모형에 대한 256개 모형으로 구성된 절약적 모형군을 제안하며, 특히 skew-t 분포의 경우를 다룬다. 매개변수 추정을 위한 AECM 알고리즘이 상세히 논의된다. 또한 광범위한 시뮬레이션이 수행되었으며, 본 방법은 MNIST 데이터셋과 Olivetti faces 데이터셋에 적용된다.

arXiv:2607.09441v1math.ST공통 태그 Clustering, Community Detection

다항 시간 내 준최적 노드-프라이빗 커뮤니티 추정

Near-optimal node-private community estimation in polynomial-time

이 논문에서 우리는 Klopp & Zadik (2026)의 미해결 문제를 해결하여, 확률적 블록 모델(stochastic block model)에서의 정확 복원(exact recovery)에 대해 그들의 지수 시간 노드-프라이빗 알고리즘의 성능에 근접하는, 높은 확률을 보장하는 다항 시간 노드-프라이빗 알고리즘을 제시한다. 우리의 결과는 페널티 가능도 함수에 대해 명시적으로 구성된 립시츠 대리 함수(Lipschitz surrogate)와, 다항 시간 내에 지수 메커니즘(exponential mechanism)으로부터 커뮤니티 레이블을 샘플링하는 신중하게 고안된 수용-기각 알고리즘(accept-reject algorithm)을 포함한다. 우리는 제안 알고리즘의 프라이버시, 실행 시간, 유용성을 엄밀하게 분석하며, 커뮤니티 수 K가 노드 수 n에 대해 로그 수준으로 증가하는 경우에도 프라이버시 매개변수 epsilon이 log(n)으로 증가할 때 정확 복원에 대한 미니맥스 수렴률을 달성할 수 있음을 보임으로써, 이 설정에서 프라이버시 비용에 관해 알려진 하한과 일치함을 증명한다.

토론

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