Sparse Distributed Learning Based on Diffusion Adaptation

Paolo Di Lorenzo; Ali H. Sayed

Source-linked AI summary

Sparse Distributed Learning Based on Diffusion Adaptation

Paolo Di Lorenzo, Ali H. Sayed

arXiv:1206.3099v22012년 6월 14일cs.LGcs.DC

TL;DR

분산 추정에는 adaptive network에서 sparsity를 활용하는 온라인 방법이 필요하다. 이 논문은 convex-regularized diffusion LMS 전략을 개발하고, 수렴 및 mean-square 거동을 분석하며, 정규화하지 않은 diffusion보다 우수한 조건을 제시하는 동시에 파라미터를 실시간으로 조정하는 방법을 보인다.

문제
이 논문은 adaptive network에서 분산 추정의 sparsity를 활용하기 위한 adaptive online 기법의 필요성을 다룬다.
방법
이 논문은 두 가지 convex sparsifying penalty function으로 정규화한 diffusion LMS 전략을 개발하고 regularization parameter를 조정한다.
결과
수렴 및 mean-square 분석을 통해 제안된 sparse diffusion 방법이 정규화하지 않은 대응 방법보다 우수한 조건을 규명한다.
핵심 시사점 및 한계
adaptive regularization을 통해 system parameter를 실시간으로 조정하여 추정 성능을 향상할 수 있다.

Abstract

from arXiv · show

This article proposes diffusion LMS strategies for distributed estimation over adaptive networks that are able to exploit sparsity in the underlying system model. The approach relies on convex regularization, common in compressive sensing, to enhance the detection of sparsity via a diffusive process over the network. The resulting algorithms endow networks with learning abilities and allow them to learn the sparse structure from the incoming data in real-time, and also to track variations in the sparsity of the model. We provide convergence and mean-square performance analysis of the proposed method and show under what conditions it outperforms the unregularized diffusion version. We also show how to adaptively select the regularization parameter. Simulation results illustrate the advantage of the proposed filters for sparse data recovery.

I. 서론

이 논문은 희소 parameter vector의 완전 분산형 실시간 distributed estimation을 목표로 하며, batch sparsity recovery와 변화하는 sparsity pattern을 추적해야 하는 adaptive network 사이의 간극을 다룬다. 수렴 및 mean-square analysis, 성능 조건, online regularization adaptation을 포함하는 sparse diffusion 전략을 개발한다.

문제 설정: 이 논문은 네트워크 내부 처리만으로 잡음이 섞인 측정값에서 M × 1 parameter vector w_o를 distributed estimation하는 문제를 다룬다.N개의 노드로 구성된 ad-hoc network가 scalar measurement와 regression vector를 수집한 뒤 협력적으로 w_o를 추정한다.
동기와 연구 공백: cyclic path는 NP-hard하게 결정해야 하고 link 또는 node failure에 취약하므로 incremental strategy 대신 diffusion을 선택한다. diffusion은 central processor 없이 local cooperation을 가능하게 한다.정보는 online으로 처리되며 real-time diffusion mechanism을 통해 네트워크 전체에서 공유된다.
동기와 연구 공백: batch compressive-sensing recovery [27]-[29] 및 기존 distributed LASSO method [40], [41]와 달리, 제안 방식은 sparsity의 변화를 추적하면서 adaptive하고 recursive하며 완전 분산형인 recovery를 수행한다.고정된 measurement 집합을 처리하는 대신 incoming data에서 sparse structure를 real time으로 학습하는 것이 동기다.
기여: 이 논문은 예비 연구 를 확장하여 broader convex regularizer, 두 개의 combination-weight set을 통한 data와 weight estimate의 공유, 그리고 상세한 mean-square 및 stability analysis를 제시한다.확장 내용에는 uniform regularization 대신 w_o의 zero element에 sparsity를 선택적으로 촉진하는 방법과 closed-form regularization bias expression이 포함된다.
기여: 제안 method는 mean-square property를 제공하고 regularization parameter를 online으로 조정하여, sparse structure의 recursive learning과 변화하는 sparsity에서 향상된 tracking을 가능하게 한다.주요 기여는 adaptive network에서의 sparsity exploitation, sparse diffusion filter의 mean-square analysis, regularization-parameter adaptation이다.
기여: system model이 sufficiently sparse하면 하나의 regularization parameter를 조정하여 steady-state performance에서 sparse diffusion이 standard diffusion을 능가하게 할 수 있다.이 논문은 이러한 향상을 위한 조건을 유도하고, 이를 regularization parameter의 online selection을 정당화하는 근거로 사용한다.

II. 적응형 네트워크에서의 희소 분산 추정

이 절에서는 미지의 희소 벡터와 관련된 선형 모델 데이터에 기반해 적응형 네트워크에서 협력적 희소 추정을 정식화한다. 노드들이 국소적으로 통신하고 개별 노드 장애에도 네트워크가 계속 작동할 수 있는 분산 처리를 도입한다.

문제 정식화: 노드의 데이터는 회귀변수와 잡음에 대한 독립성 가정하에서 미지의 희소 벡터 w_o와 관련된 선형 관측으로 모델링된다.가정에는 모든 l과 j에 대해 v_k(i)가 u_l,j와 독립이고, l ≠ k 및 i ≠ j일 때 v_l(j)와도 독립이라는 조건이 포함된다.
문제 정식화: 협력적 희소 추정은 희소성을 강제하기 위해 γ > 0으로 가중된 convex regularizer를 비용 함수에 추가하고, 이를 최소화하여 완전 분산형 최적 추정기를 구하는 것을 목표로 한다.regularization function f(w)는 실숫값이며 convex하다.
분산 구현: 분산 해법이 선호되는 이유는 중앙집중형 구현이 전력과 대역폭을 소모하는 데이터 전송을 필요로 하며, 장애가 발생할 수 있는 fusion center에 의존하기 때문이다.중앙 프로세서가 고장 나면 중앙집중형 동작이 중단될 수 있다.
분산 구현: 분산 접근법에서는 각 노드가 인접 노드와 통신하고 네트워크 전체에서 처리를 분담하므로, 통신이 국소화되고 개별 노드 장애에도 동작의 복원력이 유지된다.개별 노드에 장애가 발생해도 네트워크는 계속 작동할 수 있다.

A. Adaptive Diffusion Strategy

이 절에서는 접근할 수 없는 전역 통계적 모멘트를 이웃 기반 반복 업데이트로 대체하여 분산 sparse diffusion 전략을 도출한다. 마지막으로 비음수 가중치 제약하에서 LMS-type adaptation과 이웃 diffusion을 결합한 ATC sparse diffusion algorithm을 제시한다.

Distributed cost construction: 도출 과정에서는 상호작용을 이웃으로 제한하고 covariance matrix를 diagonal identity-scaled weight로 대체하여 전역 cost를 locally implementable approximation으로 변환한다.이러한 대체를 통해 각 노드가 다른 모든 노드의 local estimate와 weighting matrix에 접근해야 하는 요구를 없애면서 convex regularization term을 유지한다.
Adaptive recursion: 도출된 recursion은 충분히 작은 step-size를 사용하는 sub-gradient steepest-descent update를 적용한 뒤, 접근할 수 없는 second-order moment를 local instantaneous LMS-type approximation으로 대체한다.이를 통해 {R_u,k, r_du,k}에 대한 사전 지식 없이 streaming data에서 직접 동작하는 adaptive implementation을 얻는다.
Weight constraints: diffusion weight는 real이고 nonnegative이며, 이웃에 대해 c_l,k > 0 및 a_l,k > 0을 만족하고 C1 = 1 및 A^T1 = 1도 만족한다.이러한 제약은 network recursion에서 허용되는 information-sharing 및 combination rule을 정의한다.
ATC sparse diffusion algorithm: ATC sparse diffusion algorithm은 먼저 neighborhood data를 사용해 각 노드를 adaptation한 다음, 계수 {a_l,k}를 통해 이웃 노드의 intermediate estimate를 결합한다.계수 {c_l,k}는 adaptation 중 어떤 이웃이 data를 공유할지를 결정하고, {a_l,k}는 diffusion 중 intermediate estimate를 어떻게 결합할지를 결정한다.
Algorithm variants and complexity: sparse diffusion scheme의 complexity는 O(3M)으로 standard stand-alone LMS adaptation과 같으며, update order를 뒤집으면 대안적인 CTA strategy가 된다.CTA는 adaptation 전에 data aggregation을 수행한다. 이후 분석은 ATC에 초점을 맞추며, 에서는 ATC가 일반적으로 CTA보다 우수하다고 주장했다.

B. 희소 정규화

이 절에서는 희소 diffusion learning을 위한 convex regularizer를 전개한다. ℓ1 surrogate로 시작해 ZA diffusion을 도출한 뒤, ℓ0-norm을 더 잘 근사하는 reweighted 대안인 RZA를 도입한다. ZA는 모든 계수를 균일하게 축소하는 반면, RZA는 작은 성분을 선택적으로 축소해 희소 복원을 향상한다.

희소 정규화: ℓ1-norm은 nonconvex한 ℓ0-norm의 convex surrogate를 제공하며 zero-attracting (ZA) diffusion algorithm으로 이어진다.ℓ0-norm은 영이 아닌 항목의 개수를 세지만, 비볼록성 때문에 직접 사용할 수 없다. 반면 ℓ1-norm은 벡터 항목의 절댓값을 합산한다.
희소 정규화: ZA는 모든 계수를 균일하게 축소하므로 시스템이 충분히 희소하지 않으면 성능이 저하된다.0 원소와 nonzero 원소를 동일하게 처리하기 때문에, 균일한 attraction은 sparsity가 제한적인 시스템에 부정적인 영향을 줄 수 있다.
희소 정규화: Reweighted approximation은 reweighted zero-attracting (RZA) diffusion algorithm을 도출하며, 작은 ε에 대해 ℓ1-norm보다 ℓ0-norm을 더 잘 근사한다.Reweighted ℓ1 regularization은 compressive sensing의 reweighting에서 동기를 얻는다,,.
희소 정규화: RZA는 크기가 ε에 가까운 계수를 선택적으로 축소하는 반면, |w_m| ≫ ε를 만족하는 성분에는 거의 영향을 주지 않는다.이러한 선택적 attraction은 큰 계수의 상당한 축소를 피함으로써 희소 복원을 향상하기 위한 것이다.

III. 평균제곱 성능 분석

이 절에서는 error-vector recursion과 network-level weighting quantity를 통해 sparse diffusion algorithm의 평균제곱 분석을 정식화한다. 도출되는 성능 표현을 단순화하기 위해 independent regressor와 충분히 작은 step-size를 가정한다.

분석에서는 추정값 w_k,i를 random process의 실현값으로 취급하고, sparse diffusion algorithm을 평균제곱 거동을 통해 평가한다.
저자들은 distributed recursion을 나타내기 위해 weight-error variable, network vector, block weighting matrix, random block quantity를 정의한다.
앞선 관계식을 결합하면 network weight-error vector가 시간에 따라 어떻게 변화하는지 나타내는 single recursion을 얻을 수 있으며, 이를 바탕으로 평균제곱 분석을 시작한다.
분석에서는 temporally white하고 spatially independent인 regressor와 충분히 작은 step-size를 가정하여 μ_k의 고차 거듭제곱을 무시할 수 있도록 한다.independent-regressor assumption은 분석적 단순화임을 인정하며, 선행 연구는 충분히 작은 step-size에서 양호한 일치가 나타남을 보여준다.

A. 평균에서의 수렴

이 절에서는 평균 오차 동역학을 유도하고 diffusion strategy의 평균에서의 점근적 수렴을 보장하는 조건을 제시한다. 또한 regularization으로 유도되는 정상상태 weight bias의 closed-form 표현을 제공한다.

평균에서의 수렴: 정리 1은 data model (1), Assumption 1 및 적절한 step-size하에서 diffusion strategy (21)가 평균에서 점근적으로 수렴함을 보장한다.이 결과는 (19)를 만족하는 임의의 초기 조건과 임의의 행렬 A 및 C에 대해 성립한다.
평균에서의 수렴: i → ∞일 때 모든 노드의 estimator bias는 regularization term으로 인해 발생하는 closed-form bias vector의 원소로 주어진다.분석에서는 기댓값을 취해 mean-error dynamics를 도입하고, µ_max, ∂f_max, δ = ρ(I − MD) < 1을 포함한 보조량을 정의한다.

B. 평균제곱 수렴

분석을 통해 sparse diffusion LMS의 평균제곱 안정성과 정상상태 성능식을 확립한다. 희소성 파라미터를 적절히 조정하면 충분히 희소한 모델이 standard diffusion보다 우수한 성능을 보일 수 있음을 보인다.

정상상태 성능: w_o가 충분히 희소하면 희소성 파라미터 γ를 조정하여 정상상태 성능에서 sparse diffusion이 regularization을 적용하지 않은 diffusion 알고리즘보다 우수해질 수 있다.분석을 통해 이러한 개선이 가능한 조건을 도출한다.
분산 관계식: [7], 의 energy-conservation framework에 따라, 분석에서는 임의로 선택한 Hermitian nonnegative-definite weighting matrix Σ를 사용하여 variance relation을 도출한다.Vectorization과 Kronecker-product identity를 적용하면 이 관계식은 선형 형식 σ′ = Fσ로 축약된다.
평균제곱 안정성: 조건 (40)이 성립하고 matrix F가 stable하면 충분히 작은 step-size가 평균 및 평균제곱 안정성을 보장한다.이 안정성 결과는 제시된 data model과 Assumption 1하에서 적용된다.
정상상태 성능 지표: 정상상태 극한이 존재하므로 weighting vector σ를 적절히 선택하여 성능 지표를 구할 수 있다.도출된 식은 (I − F)^−1을 포함하는 선택을 통해 node-level MSD와 average network MSD 식을 제공한다.

C. 비정규화 ATC Diffusion과의 비교

Sparse diffusion filter는 regularization-induced term이 음수인 경우 mean-square deviation에서 unregularized diffusion보다 우수할 수 있으며, 이는 충분한 sparsity와 관련된 조건이다. 적절한 γ를 선택하면 sparse model에서는 모든 node에서 더 나은 MSD를 얻지만, nonsparse model에서는 성능이 더 나쁠 수 있다.

C. 비정규화 ATC Diffusion과의 비교: MSD 식은 γ = 0에서의 standard diffusion MSD와 sparse diffusion의 성능 개선 여부를 결정하는 regularization-induced term으로 분리된다.첫 번째 항은 standard diffusion 결과와 일치하며, 두 번째 항이 음수이면 성능이 개선된다.
C. 비정규화 ATC Diffusion과의 비교: αΣk,∞ > 0이고 γ가 적절히 선택되면 Sparse diffusion이 standard diffusion보다 우수하며, nonsparse model에서는 일반적으로 이 비교가 반대로 나타난다.αΣk,∞ > 0 조건은 우위를 확보하기 위한 필요조건인 반면, nonsparse model은 관련 sparsity 조건을 대체로 만족하지 못해 성능이 더 나빠진다.

D. 정규화 파라미터의 적응적 조정

이 절에서는 sparse diffusion을 위해 iteration에 따라 변하는 정규화 파라미터 γ_i를 개발하여 네트워크가 모델의 sparsity를 추적할 수 있도록 한다. 또한 실용적인 local 근사를 유도하고, instantaneous MSD 개선 조건을 규명하며 O(4M) 복잡도를 유지한다.

적응적 파라미터 선택: 제안 방법은 iteration에 따라 변하는 정규화 파라미터 γ_i를 선택하여 system model의 sparsity를 적응적으로 활용하고 추적한다.최적 γ_i는 quadratic performance expression을 최소화하며, 실용적인 형태를 얻기 위해 small-step-size 근사를 사용한다.
성능 조건: Σ = I일 때 φΣ,i(γ_i) < 0이면 sparse diffusion이 instantaneous MSD에서 standard diffusion보다 우수하다.이 조건은 regularized strategy가 예측된 성능 이점을 갖는 시점을 결정한다.
실용적인 local 구현: 이상적인 update는 알려지지 않은 true vector와 network-wide data에 의존하므로, 논문은 정규화 파라미터의 local computation을 가능하게 하는 근사를 유도한다.이 구성에서는 A = I를 고려하고, ℓ1-norm upper bound와 같은 사전 sparsity 지식을 사용하며, network-wide rule을 node-local computation으로 대체한다.
알고리즘 요약: 적응적 sparse diffusion strategy의 복잡도는 O(4M)으로, standard stand-alone LMS adaptation과 같다.이 절에서는 adaptive regularization을 적용한 ATC sparse diffusion LMS strategy를 요약한다.
조건과 robustness: 우월성 보장은 triggering condition과 sparsity upper bound η가 얼마나 정확하게 지정되는지에 따라 달라진다.시뮬레이션에서는 practical rule을 사용한 성능과 잘못 지정된 η에 대한 robustness를 평가한다.

IV. 시뮬레이션 결과

시뮬레이션 결과, 미지 시스템이 sparse할 때 sparse diffusion이 distributed estimation을 개선하며, RZA-ATC가 일반적으로 ZA-ATC와 standard diffusion보다 우수한 성능을 보인다. Adaptive regularization은 변화하는 sparsity를 추적해 robustness를 높이는 반면, projection-based method는 더 높은 계산 비용으로 더 빠르게 수렴한다.

수치 예제 1: RZA-ATC는 sparse 및 partially sparse 시스템에서 diffusion 성능이 가장 우수하며, 시스템이 fully non-sparse일 때도 standard diffusion과 비슷한 성능을 유지한다.매우 sparse한 시스템에서는 ZA-ATC와 RZA-ATC가 모두 standard diffusion보다 우수하다. Sparsity가 감소하면 ZA-ATC의 성능은 저하되지만 RZA-ATC는 우위를 유지하며, 시스템이 non-sparse하면 모든 filter가 비슷한 성능으로 수렴한다.
수치 예제 1: 시스템이 충분히 sparse하지 않게 되면 ZA-ATC가 standard diffusion보다 갖는 이점은 사라지는 반면, reweighted regularization은 더 넓은 sparsity 범위에서 우수한 성능을 유지한다.ZA-ATC에 유리한 γ 값의 구간은 sparsity가 감소할수록 좁아지고 non-sparse 시스템에서는 0이 된다. ATC-RZA는 ZA-ATC보다 우수하며, 시스템이 완전히 non-sparse일 때만 standard diffusion보다 성능이 낮다.
수치 예제 2: γ의 adaptive selection은 변화하는 sparsity에 대응해 unregularized diffusion 대비 ATC-SD의 성능을 개선하고, γo를 differential-MSD 최적점 또는 non-sparse 시스템에서 0으로 유도한다.Adaptive parameter는 ZA-ATC와 RZA-ATC에서 minimum differential MSD 근처로 수렴하며, 시스템이 완전히 non-sparse일 때는 0으로 강제된다.
수치 예제 2: RZA-ATC는 trigger parameter η의 오차에 robust한 반면, ZA-ATC는 특히 η가 과소 추정될 때 매우 민감하다.ZA-ATC에서는 지나치게 sparse한 해가 bias를 증가시키고 성능을 크게 저하시킨다. RZA-ATC의 robustness는 parameter selection 요구 조건을 완화한다.

V. 결론

이 논문은 convex penalty를 사용해 distributed estimation을 수행하는 sparse diffusion LMS 전략을 제안하고, 그 수렴 및 mean-square 성능을 분석한다. 특정 조건에서 제안 방법은 unregularized diffusion보다 우수한 성능을 보이며, underlying sparsity에 맞춰 regularization을 실시간으로 조정할 수 있다.

V. 결론: 이 연구는 adaptive network에서 distributed estimation을 수행하기 위해 convex sparsifying penalty로 regularization한 diffusion LMS 전략을 도입한다.두 penalty를 사용한다. ℓ1-norm은 모든 원소를 균일하게 0을 향해 끌어당기는 반면, reweighted function은 작은 크기의 원소를 선택적으로 축소해 ℓ0-norm을 더 잘 근사한다.
V. 결론: 제안된 sparse adaptive diffusion filter는 확인된 조건에서 steady-state 성능 면에서 unregularized counterpart보다 우수하다.수렴 및 mean-square 분석을 통해 이러한 우위가 성립하는 조건을 확립한다.
V. 결론: regularization parameter의 update procedure는 unregularized filter에 대한 우위를 유지하면서 vector의 sparsity를 실시간으로 조정할 수 있게 한다.이 조정은 underlying system vector의 sparsity에 따라 estimation 성능을 향상시키기 위한 것이다.
V. 결론: 수치 결과는 제안된 sparse diffusion 전략을 사용할 때 얻을 수 있는 잠재적 이점을 보여준다.

부록 A 정리 1의 증명 · 부록 B 정리 2의 증명 · αΣ,∞의 존재

부록에서는 논문의 step-size 및 안정성 조건하에서 평균 오차 recursion, mean-square quantity, 그리고 α_Σ,∞를 정의하는 극한의 수렴을 확립한다. 증명에서는 bounded regularization term, block-norm contraction, comparison test, stable-matrix argument를 사용해 유한한 steady-state limit을 보인다.

부록 A 정리 1의 증명: 조건 (40)하에서 I − MD가 stable이고 분해를 구성하는 두 항이 모두 유한한 극한을 가지므로 평균 오차 recursion은 steady-state value로 수렴한다.첫 번째 항은 block-norm contraction을 통해 소멸하고, 두 번째 항은 comparison test에 의해 absolute convergence한다.
부록 B 정리 2의 증명: 정리 2에서는 조건 (40)이 평균 오차 sequence를 bounded and convergent하게 유지하며, 이에 따라 mean-square recursion을 구동하는 항들이 bounded해진다.따라서 증명은 recursion의 transient term과 accumulated term이 수렴함을 보이는 것으로 환원된다.
부록 B 정리 2의 증명: F가 stable이면 F^i는 0으로 수렴하고 mean-square recursion의 두 번째 항은 absolute convergence하므로 σ는 steady-state value로 수렴한다.이 논증에서는 comparison test와 F의 spectral radius에 맞춘 matrix norm을 사용한다.
부록 B 정리 2의 증명: 정리 2의 stability argument는 ρ(F) < 1, norm equivalence, submultiplicativity를 이용해 관련 series를 기하급수적으로 bound한다.이러한 bound는 mean-square proof에서 사용되는 series의 absolute convergence를 확립한다.
부록 C αΣ,∞의 존재: 부록 C에서는 조건 (40)이 transient term을 소멸시키고, random vector c_i의 boundedness가 나머지 항을 유한한 값으로 수렴시킨다.따라서 comparison-test argument를 통해 α_Σ,∞를 정의하는 극한의 존재를 확립한다.