Abstract

시계열 예측 문제는 기후학 및 수요 예측과 같은 현대 응용 분야에서 점점 더 고차원이 되고 있습니다. 예를 들어, 후자의 경우 수요를 예측해야 하는 항목 수는 5만 개에 달할 수 있습니다. 또한, 데이터는 일반적으로 노이즈가 많고 누락된 값들로 가득합니다. 따라서 현대 응용 분야에서는 고도로 확장 가능하고, 노이즈 데이터에 대해 손상 또는 누락된 값으로 처리할 수 있는 방법이 필요합니다. 그러나 고전적인 시계열 방법은 이러한 문제를 처리하는 데 한계가 있습니다. 이 논문에서는 데이터 기반의 시계열 학습과 예측을 지원하는 시간적으로 규제된 행렬 분해 (TRMF) 프레임워크를 제안합니다. 새로운 규제 방법을 개발하고 많은 누락된 값이 있는 고차원 시계열 데이터에 적합한 확장 가능한 행렬 분해 방법을 사용합니다. 제안한 TRMF는 매우 일반적이며, 시계열 분석을 위한 기존 접근 방식을 포괄합니다. 또한 자기회귀적인 프레임워크에서 종속성을 학습하는 그래프 규제 방법과 흥미로운 연결을 만듭니다. 실험 결과는 확장성과 예측 품질 측면에서 TRMF의 우수성을 보여줍니다. 특히, 5만 차원의 문제에서 TRMF는 다른 방법보다 두 배 이상 빠르며 Wal-mart 전자 상거래 데이터셋과 같은 실제 데이터셋에서 더 좋은 예측을 생성합니다.

Introduction

시계열 분석은 수요 예측과 기후학과 같은 다양한 응용 분야에서 중요한 문제입니다. 이러한 응용 분야에서는 종종 매우 큰 수(n)의 상호 의존적인 일차원 시계열과/또는 큰 시간 범위(T)를 처리하기 위해 고도로 확장 가능한 방법이 필요합니다.
따라서 현대 시계열 모델은 사람들에게 두 가지 도전을 제시합니다: 대규모 n과 T를 처리할 수 있는 확장성 및 누락된 값 처리에 대한 유연성.

자기회귀 (AR) 모델이나 동적 선형 모델 (DLM)과 같은 전통적인 시계열 문헌의 대부분의 접근 방식은 저차원 시계열 데이터에 초점을 맞추고 두 가지 문제를 처리하는 데 한계가 있습니다. 예를 들어, L차원의 AR 모델은 O(TL^2n^4 + L^3n^6) 시간이 소요되어 O(Ln^2) 개의 파라미터를 추정합니다.
이는 큰 n 값에 메모리 효율성이 떨어집니다.
마찬가지로, 칼만 필터 기반의 DLM 접근 방식은 k가 잠재 공간의 차원으로, 많은 상황에서 n보다 크게 선택되는 경우가 많아서 O(kn^2T + k^3T) 계산 비용이 필요합니다. 특정 예로, 일반 최적화 솔버에 의존하는 널리 사용되는 R-DLM 패키지의 최대 우도 추정기 구현은 n이 수십 개를 초과하는 경우에도 확장할 수 없습니다. 면에 AR과 같은 모델의 경우, 누락된 값을 처리하는 유연성은 일차원 시계열에서도 어려울 수 있으며, 특히 고차원 시계열을 처리하는 것은 더 어렵습니다.

고차원 시계열 데이터를 모델링하는 자연스러운 방법은 행렬 형태로 표현하는 것으로, 각 일차원 시계열에 해당하는 행들과 시간 지점에 해당하는 열들로 구성됩니다. n 개의 시계열은 일반적으로 서로 상관 관계가 높으므로, 높은 차원의 시계열을 분석하기 위해 저차원 행렬 분해 (MF) 또는 행렬 완성 (MC) 기법을 적용하는 시도가 있었습니다.
이러한 시도들은 최근 기술적인 MF 방법들은 n에 대해 선형적으로 확장 가능하므로 큰 데이터셋을 처리할 수 있습니다. 옵저브된 n 차원 시계열을 나타내는 행렬을 Y ∈ R^(n×T)라고 하면, Yit는 i번째 시계열의 t번째 시간점에서의 관측값을 나타냅니다.
표준 MF 접근 방식에서는 Y_it는 i번째 시계열에 대한 k차원 잠재 임베딩인 fi ∈ R^k와 t번째 시간점에 대한 k차원 잠재 시간 임베딩인 xt ∈ R^k의 내적으로 추정됩니다. 우리는 xt를 행렬 X ∈ R^(k×T)의 열로, fi를 행렬 F ∈ R^(n×k)의 행으로 쌓아서 Y ≈ F X를 얻을 수 있습니다. 이후 Y ≈ F X를 해결할 수 있습니다.

여기서 Ω은 관측된 항목의 집합을 나타냅니다. Rf (F)와 Rx(X)는 F와 X에 대한 정규화항으로, 일반적으로 과적합을 피하거나 특정 시간 구조를 임베딩들 사이에 유도하기 위해 사용됩니다. 일반적인 선택인 Rx(X) = kXkF는 시계열 응용 분야에는 적합하지 않습니다. 왜냐하면 이는 시간적 임베딩 {xt}들 사이의 순서를 고려하지 않기 때문입니다. 기존의 대부분의 MF 접근 방식은 그래프 기반 접근 방식을 채택하여 시간적 의존성을 처리합니다. 특히, 의존성은 가중 유사도 그래프로 설명되며, 라플라시안 정규화로 통합됩니다. 그러나 이러한 그래프 기반 정규화는 두 시점 간에 음의 상관 관계가 있는 경우에 실패합니다. 또한 데이터와 함께 명시적 그래프 정보가 사용 가능한 경우 (예: 추천 시스템을 위한 소셜 네트워크 또는 제품 공동 구매 그래프), 명시적 시간 의존 구조는 보통 사용 가능하지 않으며 추정하거나 근사해야 하는데, 이는 실행자들이 의존성을 추정하기 위해 별도의 절차를 수행하거나 간단한 고정 가중치로 매우 단기적 의존성을 고려하게 될 수 있습니다. 또한, 기존의 MF 접근 방식은 과거 시점의 누락된 값을 잘 추정하면서도, 시계열 분석에서 관심 대상인 미래 값 예측 측면에서는 성능이 저조합니다.

이 논문에서는 고차원 시계열 분석을 위한 새로운 시간적 규제 행렬 분해 프레임워크 (TRMF)를 제안합니다. TRMF에서는 잠재적 시간 임베딩 {xt}들 사이의 시간적 의존성 구조를 설명하는 원리적 접근 방식을 고려하고, 이 시간 구조를 표준 MF 수식에 통합하기 위해 시간적 정규화항을 설계합니다. 기존의 대부분의 MF 접근 방식과 달리, TRMF 방법은 데이터 기반의 시간 의존성 학습을 지원하며, 또한 행렬 분해 접근 방식에서 미래 값 예측 능력을 가져옵니다. 또한, MF 접근 방식의 특성에서 상속 받아서 TRMF는 많은 누락된 값이 존재하는 고차원 시계열 데이터도 쉽게 처리할 수 있습니다. 특정 예로, TRMF에서는 임베딩 {xt}들 사이에 AR(자기회귀) 구조를 유도하는 새로운 시간적 규제 항을 시연합니다. 또한, 우리의 프레임워크에서 적용되는 의존성 구조에 대한 이러한 연결을 만듭니다. 이러한 연결은 우리의 프레임워크에서 적용되는 의존성 구조에 대한 이해를 높여주며, GRALS과 같은 효율적인 솔버를 사용하는 이점을 제공합니다. 이를 통해 TRMF를 직접 해결할 수 있습니다.

Motivation

2.1 고전적인 시계열 모델

AR 및 DLM과 같은 모델들은 내재적인 계산 비효율성 때문에 현대의 다중 고차원 시계열 데이터 (즉, n과 T가 모두 큰 경우)에 적합하지 않습니다 (1절 참조). AR 모델에서 오버피팅을 피하기 위해 저차원 및 희소 행렬과 같은 다양한 구조화된 전이 행렬에 대한 연구가 있었습니다. 이 연구의 초점은 더 나은 통계적 보장을 얻는 데에 있었습니다. AR 모델의 확장성 문제는 여전히 해결되지 않았습니다. 반면에, 많은 고전적인 시계열 모델들은 많은 누락된 값을 처리하는 것도 어렵습니다. 모델 파라미터가 기존에 주어지거나 전문가에 의해 설계된 경우, 예측을 수행하기 위해 Kalman 필터 접근 방식을 사용하고, 누락된 항목을 보완하기 위해 Kalman 스무딩 접근 방식을 사용합니다. 모델 파라미터가 알려지지 않은 경우, DLM을 위해 EM 알고리즘을 사용하여 모델 파라미터와 잠재 임베딩을 추정합니다. 대부분의 DLM을 위한 EM 접근 방식은 Kalman 필터를 구성 요소로 포함하므로 매우 고차원 시계열 데이터에 확장되지 않습니다.

2.2 시간적 의존성을 갖는 데이터를 위한 기존 행렬 분해 접근 방식
표준 MF (1)에서는 일반적으로
이 X에 대한 선택적인 정규화항입니다. 이러한 제곱 프로베니우스 노름은 {xt}들 사이에 의존성이 없다고 가정하며, 표준 MF 수식은 열 순열에 무관하고 시간적 의존성이 있는 데이터에 적용되지 않습니다. 따라서 대부분의 기존 시간적 MF 접근 방식은 시간적으로 의존적인 {xt}들을 위해 그래프 기반 정규화 프레임워크로 전환합니다. 여기에는 시간적 의존성을 인코딩하는 그래프가 포함됩니다.

2.3. 시간적 의존성을 위한 그래프 정규화:
그래프 기반 정규화의 프레임워크는 변수들 간의 일반적인 의존성을 설명하고 통합하는 접근 방식입니다. G가 {xt}들에 대한 그래프이고 Gts가 t번째 노드와 s번째 노드 사이의 엣지 가중치이면, 목적 함수의 일부로 포함할 수 있는 인기 있는 정규화 방법은 다음과 같습니다:

여기서 t는 1부터 T까지, s는 1부터 T까지 실행됩니다. 이 정규화 방법은 시간적 의존성을 나타내는 그래프를 통합합니다. 그러나 이러한 그래프 기반 정규화는 두 시점 간에 음의 상관 관계가 있는 경우에 실패할 수 있습니다. 또한, 그래프 정보가 데이터와 함께 명시적으로 제공되지 않는 경우 (예: 시간 의존성 추정을 위한 별도의 절차 수행 또는 간단한 고정 가중치를 가진 매우 단기적 의존성 고려) 시간적 의존성을 처리하는 것이 어려울 수 있습니다.

Temporal Regularized Matrix Factorization

언급된 한계를 해결하기 위해, 시간적 의존성을 행렬 분해 모델에 통합하는 혁신적인 접근 방식인 Temporal Regularized Matrix Factorization (TRMF) 프레임워크를 제안합니다. 앞서 언급한 그래프 기반 접근 방식과 달리, 우리는 시간적 의존성을 {xt}들 사이에서 명시적으로 설명하기 위해 잘 연구된 시계열 모델들을 사용하도록 제안합니다. 이러한 모델들은 다음과 같은 형태를 가집니다:

여기서 ε_t는 가우시안 노이즈 벡터이고, MΘ는 L과 Θ로 매개변수화된 시계열 모델입니다. L은 라그 지수 l을 포함하는 세트이며, t번째와 (t - l)번째 시간 지점 간의 의존성을 나타냅니다. Θ는 시간적 의존성의 가중치 정보를 포함합니다.

표준 MF 수식에 시간적 의존성을 통합하기 위해, 우리는 MΘ에 의해 유도된 구조를 유도하는 새로운 정규화항 TM(X | Θ)를 설계하기로 제안합니다. 시계열을 모델링하는 표준적인 방법을 적용하여, TM(X | Θ)을 주어진 모델 MΘ에 대한 {xt}의 특정 실현을 관찰할 때의 음의 로그 가능도로 설정합니다.

최종은 아래와 같습니다.

.... 7

TRMF에서 데이터 기반 시간 의존성 학습

시간 의존성을 포함하기 위해 그래프 기반 정규화항을 직접 사용하면 가중치에 대해 트리비얼한 해가 나타나는 것을 보였습니다. TRMF는 이 문제를 우회합니다. F와 X가 고정될 때 위의 식은 다음과 같이 단순화됩니다:

이는 베이지안 관점에서 Θ가 주어진 {xt}에 대해 MΘ 모델 아래에서 최적의 Θ을 추정하는 최대사후(MAP) 추정 문제입니다. 이러한 문제를 해결하고 비트리비얼한 Θ을 얻기 위해 잘 개발된 알고리즘이 있습니다. 따라서 시간적 행렬 분해 접근 방식의 대부분과 달리 TRMF에서는 의존성의 강도가 고정되어 있지 않고, Θ을 데이터로부터 자동으로 학습할 수 있습니다.

• Time Series Analysis with TRMF:We can see that TRMF (7) lends itself seamlessly to handle a variety of commonly encountered tasks in analyzing data with temporal dependency:

• Time-series Forecasting: Once we have MΘ for latent embeddings {xt : 1, . . . , T}, we can
use it to predict future latent embeddings {xt : t > T} and have the ability to obtain non-trivial
forecasting results for yt = Fxt for t > T.

• Missing-value Imputation: In some time-series applications, some entries in Y might be unobserved, for example, due to faulty sensors in electricity usage monitoring or occlusions in the
case of motion recognition in video. We can use f^T * xt to impute these missing entries, much like standard matrix completion, that is used in recommender systems and sensor networks.

A Novel Autoregressive Temporal Regularizer

RMF 프레임워크를 매우 일반적인 관점에서 설명하며, 시계열 모델 MΘ로 지정된 의존성을 포함하는 정규화항 TM(X | Θ)을 다루었습니다. 이 섹션에서는 이를 AR 모델에 특화시키는데, 이 모델은 래그 집합 L과 가중치 xt =
로 매개변수화됩니다. 여기서 xt는 이전 시점의 일부 포인트들의 잡음이 섞인 선형 조합이라고 가정합니다. 즉,

기서 t는 가우시안 잡음 벡터입니다. 간단히 하기 위해 t ∼ N(0, σ2Ik)로 가정합니다. 여기서 Ik는 k × k 항등 행렬입니다. 이 AR 모델에 해당하는 시간적 정규화항 TM(X | Θ)은 다음과 같이 쓸 수 있습니다:

TRMF는 가중치 W(l)이 알려지지 않은 경우에 해당 가중치를 학습할 수 있게 해줍니다. 각 W(l) ∈ R (k×k) 매트릭스에는 |L|k² 개의 변수가 있을 수 있으며, 이는 과적합으로 이어질 수 있습니다. 이를 방지하고 해석 가능한 결과를 얻기 위해 우리는 대각 성분으로 구성된 W(l)을 고려하며, 이로 인해 매개변수 수가 |L|k로 감소합니다. 표기를 간단히 하기 위해, W를 k × L 매트릭스로 표기합니다. 여기서 l번째 열은 W(l)의 대각 성분으로 구성됩니다. L에 속하지 않는 l에 대해서는 W의 l번째 열이 모두 0인 벡터입니다. X의 r번째 행을 x¯r = [· · · , Xrt, · · · ]로, W의 r번째 행을 w¯r = [· · · , Wrl, · · · ]로 정의하면 (9)는 다음과 같이 쓸 수 있습니다:

여러 시계열 간의 상관관계:

Wl이 대각선 형태라고 하더라도, TRMF는 요인들 {fi}을 통해 여러 시계열 간의 상관관계를 캡처할 수 있습니다. 대각선 형태의 Wl은 latent embeddings {xt}의 구조에만 영향을 미치기 때문입니다. 실제로 {yt}의 i번째 차원은 (7)에서 fi X로 모델링되므로, 저차원의 F는 여러 시계열 간의 k 차원 latent embedding입니다. 이러한 embedding은 여러 시계열 간의 상관관계를 포착합니다. 또한 {fi}는 시계열 특징으로 작용하여, 결측값이 있는 경우에도 분류/클러스터링을 수행하는 데 사용될 수 있습니다.

Lag 인덱스 집합 L의 선택:

TRMF에서는 L의 선택이 더 유연합니다. 따라서 TRMF는 중요한 이점을 제공합니다. 첫째로, 가중치 매개변수 W를 지정할 필요가 없으므로 L을 더 크게 선택하여 먼 거리의 종속성을 고려할 수 있습니다. 이는 더 정확하고 견고한 예측을 제공합니다. 둘째로, L의 인덱스가 연속적이지 않아도 됩니다. 따라서 주기성이나 계절성에 대한 도메인 지식을 쉽게 포함시킬 수 있습니다. 예를 들어, 일년 주기의 주간 데이터에 대해 L = {1, 2, 3, 51, 52, 53}과 같이 선택할 수 있습니다.

그래프 정규화와의 관계:

TAR(x¯ |L, w¯, η)와 그래프 정규화(2) 간의 관계를 설명합니다. L¯ := L ∪ {0}, w0 = −1로 두면 식은 다음과 같이 됩니다.

Experiment

Conclusion

해당 논문은 높은 차원의 시계열 문제와 결측값을 가진 데이터에 대해 새로운 시간적으로 규제된 행렬 인수분해 프레임워크(TRMF)를 제안합니다. TRMF는 데이터 포인트 간의 시간적 종속성을 모델링하는데 그치지 않고 데이터 기반 종속성 학습을 지원합니다. TRMF는 몇 가지 잘 알려진 방법을 일반화하며, 실제 데이터셋에서 다른 최첨단 방법과 비교했을 때 우수한 성능을 제공합니다.