Imputation of Time-varying Edge Flows in Graphs by Multilinear Kernel Regression and Manifold Learning
원문 초록
This paper extends the recently developed framework of multilinear kernel regression and imputation via manifold learning (MultiL-KRIM) to impute time-varying edge flows in a graph. MultiL-KRIM uses simplicial-complex arguments and Hodge Laplacians to incorporate the graph topology, and exploits manifold-learning arguments to identify latent geometries within features which are modeled as a point-cloud around a smooth manifold embedded in a reproducing kernel Hilbert space (RKHS). Following the concept of tangent spaces to smooth manifolds, linear approximating patches are used to add a collaborative-filtering flavor to the point-cloud approximations. Together with matrix factorizations, MultiL-KRIM effects dimensionality reduction, and enables efficient computations, without any training data or additional information. Numerical tests on real-network time-varying edge flows demonstrate noticeable improvements of MultiL-KRIM over several state-of-the-art schemes.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
조건부 텐서 확산: 분포적 반사실 학습 및 추론
Conditional Tensor Diffusion: Distributional Counterfactual Learning and Inference
인과 추론은 운영 및 관리 의사결정을 이끌지만, 고차원 패널 또는 텐서 설정에서는 여전히 어렵고, 이때 의사결정은 누락된 통제(control) 결과의 결합 조건부 분포에 의존할 수 있다. 본 연구는 처리(treatment) 마스크와 잠재 Tucker 구조를 조건부 확산에 통합하여, 관측된 통제 결과가 주어졌을 때 저차원 코어에서의 효율적인 비선형 score 학습을 통해 이 분포를 복구하는 Counterfactual Tucker Diffusion(CFTDiff)를 제안한다. 마스킹된 Tucker score는 텐서 모드 간 의존성을 유지하면서, 비선형 score 학습의 차원을 모드 차원의 곱에서 Tucker rank의 곱이라는 훨씬 작은 규모로 줄인다. Tucker rank, 최대 모드 차원, 요인 강도(factor-strength)로 조정된 누락 결과 수에 의존하는 조건부 score 추정의 고확률(high-probability) 오차 상계를 확립하고, 이 상계가 누락된 통제 결과의 조건부 분포 복구 보장으로 어떻게 이어지는지 보인다. 다양한 누락률에서의 시뮬레이션은 일반적인 인과 패널 및 행렬/텐서 completion 방법보다 더 정확한 점(point) 복구를 보여 주며, 중첩 확산 명세와의 비교는 마스킹 조건화와 Tucker 차원 축소의 이득을 추가로 뒷받침한다. 노르웨이 iFlex 실험에서 CFTDiff는 경쟁 방법보다 누락 결과를 더 정확하게 복구한다. 인과 분석에 적용하면 추정된 조건부 분포로부터 반사실(counterfactual) 예측 구간과 목표 달성 확률을 얻을 수 있어, 가격 개입을 수요 감소 규모와 신뢰성(reliability) 측면에서 평가할 수 있다.
다양체 가설 하의 결측 데이터 대체
Missing Data Imputation under Manifold Hypothesis
다양체 가설(manifold hypothesis)은 고차원 데이터가 저차원 내재 다양체 근방에 집중되어 있다고 가정한다. 혼합 변분 오토인코더(VAE)의 최근 발전은 이러한 내재 구조를 충실하게 추출하는 강력한 도구를 제공한다. 이로부터 얻어지는 기하학적 구조는 변수들 간의 지역적 및 전역적 관계를 자연스럽게 도입하며, 결측 데이터를 체계적으로 대체할 수 있는 방법을 제공한다. 우리는 샘플링-중요도-재샘플링(SIR) 절차를 통해 \( p(\bm{x}_{\mathrm{mis}} \mid \bm{x}_{\mathrm{obs}}) \)로부터 샘플링할 수 있는 모델 기반 대체 방법을 제안하며, 이는 잠재 공간에서의 결합 확산 모델(diffusion model)로 더욱 보강될 수 있다. 우리의 방법은 내재 기하학적 구조를 존중하면서 결측 데이터를 대체하고, 최신 방법들과 경쟁력 있는 성능을 달성하며, 대체값의 불확실성을 정량화하고, 모델 기반이므로 전체 절차를 재실행하지 않고도 즉석 대체(on-the-fly imputation)가 가능하다.
재학습 없는 추천을 위한 가변 저랭크 스케치
Mutable Low-Rank Sketches for Retrain-Free Recommendation
2단계 추천에서 흔한 병목은 임베딩 노후화(staleness)입니다. 사용자가 새 항목을 평가하면, 다음 재학습 주기까지 그들의 임베딩은 고정된 채로 남습니다. 우리는 mutable sketch를 제안합니다. 이는 각 사용자의 선호도를 KP-tree(합 집계를 갖는 희소 세그먼트 트리)에 저장하고, 저랭크 투영을 한 번 적합한 뒤, 평가가 도착할 때마다 임베딩을 즉석에서 재계산합니다. 각 새 관측이 예측 오차 범위를 단조적으로 좁힌다는 것을 증명합니다(Theorem 1). 이는 FunkSVD와 eALS에는 없는 보장입니다. KuaiRec에서 mutable sketch는 데이터 읽기 1.8%로 RMSE 0.810을 달성한 반면, ALS는 100%에서 0.822를 기록했으며, 배치당 업데이트는 8배 더 빠릅니다. 새 사용자는 첫 평가 이후 1 ms 미만 만에 개인화된 추천을 받을 수 있으며, 모델 재학습은 필요하지 않습니다. 밀도 구간별 샘플링 전략 비교에 따르면, KP-tree의 노름 비례(norm-proportional) 샘플링은 희소 데이터(밀도 <1%)에서 항목 커버리지를 40–130% 더 높이는 반면, 밀집 행렬에서는 균등 샘플링으로 충분합니다.
부분 관측 행동을 갖는 확률적 선형 밴딧
Stochastic Linear Bandits with Partially Observed Actions
확률적 선형 밴딧(stochastic linear bandit)은 행동을 벡터로 표현하고 보상이 선형인 순차적 의사결정의 핵심 패러다임이다. 본 연구에서는 학습 에이전트가 각 행동에 대해 좌표의 무작위 부분집합만을 관측하는 부분 관측(partially observed) 변형 문제를 다룬다. 이러한 부분 관측 가능성은 추천 및 의료와 같이 전체 행동 기술(description)을 얻는 것이 비용이 많이 들거나 불가능한 환경에서 자연스럽게 발생한다. 일반적으로 이는 준선형 후회(sublinear regret)를 정보이론적으로 불가능하게 만든다. 그러나 행동 벡터의 내재적 차원(intrinsic dimension)이 낮을 경우 이 장벽을 극복할 수 있음을 보인다. 우리는 마스킹된 행동으로부터 잠재 행동 부분공간(latent action subspace)을 추정하고, 에포크 단위로 고정된 표현을 이용해 현재 행동을 대체(impute)하며, 그 결과 얻어진 저차원 좌표에서 OFUL을 실행하는 알고리즘 TOFU-POV를 제안한다. 이론적으로 TOFU-POV는 주변 차원(ambient dimension)이 아닌 내재적 행동 부분공간 차원에 비례하는 $\sqrt{T}$ 후회를 달성하며, 이들 수량과 결측률, 결정 집합 크기, 부분공간 조건화(subspace conditioning) 간의 상호작용을 정량화한다. 또한 내재적 차원에 대한 사전 지식 없이도 동작하는 랭크 적응형(rank-adaptive) 알고리즘도 고안한다. 이러한 보장을 보완하기 위해, 통상적인 보상 학습 불확실성과 부분 관측에 내재된 결측 의존적 비용을 분리하는 새로운 곱 구성(product construction)에 기반한 하한을 제시한다. 합성 및 실제 데이터 실험을 통해 이론을 뒷받침하고, TOFU-POV가 이 어려운 문제에서 자연스러운 베이스라인에 비해 상당한 성능 향상을 달성할 수 있음을 보인다.
ImputeViz: 결측 데이터 진단 및 대체 방법 비교를 위한 시각적 분석 대시보드
ImputeViz: A Visual Analytics Dashboard for Diagnosing Missing Data and Comparing Imputation Methods
결측 데이터는 과학, 사회과학, 공중보건 연구에서 지속적인 장애물로, 분석에 편향을 초래하고 결측값 처리 방식에 대한 책임을 분석가에게 부여한다. 우리는 결측성 진단, 대체 모델 구성, 결과 평가를 지원하는 통합 시각적 분석 대시보드인 ImputeViz를 소개한다. 이 시스템은 MICE, Random Forest, XGBoost, kNN을 포함한 널리 사용되는 방법들을 결측성 패턴을 명시적으로 드러내는 인터랙티브 환경 내에 통합한다. 지리공간적 추론을 지원하기 위해, 사회경제적 거리와 공간적 거리를 혼합하고 기증자 기여를 노출하는 지리적으로 정보화된 kNN 변형인 gKNN을 도입하여, 각 추정치를 어느 지역이 주도하는지 보여주는 출처 기반 시각적 책임성을 가능하게 한다. 우리의 주요 기여는 교차 방법 비교를 일급 시각적 과제로 만들고 표준 방법과 함께 gKNN을 통합하는 방법 불가지론적 시각적 분석 환경이다. 조율된 뷰는 히트맵, 공동 결측성 요약, 분포 진단을 통해 결측성 구조를 드러내며, 분석가가 결측성 패턴(MCAR/MAR)과 결측이 비무작위일 수 있는 경우(MNAR)를 추론하는 데 도움을 준다. 사용자는 모델을 비교하고 조정할 수 있으며, 분포 오버레이, 현재 대상 및 마스크에 대한 각 알고리즘의 MAE, RMSE, Delta RMSE, 실행 시간을 보고하는 방법 비교 요약, 변수 수준 불일치 뷰를 통해 결과를 심층 분석할 수 있다. 방법별 캐시된 결과와 고정된 축 스케일은 방법 전환 시 범위 변화로 인한 인지 부하를 줄인다. 이러한 비교는 방법들이 불일치하는 지점, 민감한 변수, 그리고 대체 선택이 하류 요약에 미치는 영향을 부각시킨다. 사례 연구는 ImputeViz가 분석가들이 효과적인 전략을 선택하고, 민감한 변수를 발견하며, 모델 견고성을 평가하는 데 어떻게 도움을 주는지 보여준다.
Low-Cost High-Order Singular Value Decomposition for Tensor-Based Reconstruction from Sparse Sensor Measurements: Urban Flow and Air-Quality Applications
토론
이 논문과 연결된 포럼 글이 아직 없습니다.