선형 회귀 및 복구 방법

출처 : xkcd

선형 회귀는 데이터 분석과 관련된 여러 분야의 기본 알고리즘 중 하나입니다. 그 이유는 분명합니다. 이것은 수백 년은 아니더라도 수십 년 동안 널리 사용되는 데 기여한 매우 간단하고 이해하기 쉬운 알고리즘입니다. 아이디어는 한 변수가 다른 변수 집합에 대한 선형 의존성을 가정하고 이 의존성을 복원하려고 시도한다는 것입니다.

하지만 이 글은 실제 문제를 해결하기 위해 선형 회귀를 사용하는 것에 관한 것이 아닙니다. 여기에서는 복구를 위한 분산 알고리즘 구현의 흥미로운 기능을 고려할 것입니다. 아파치 이그나이트. 약간의 기본적인 수학, 기계 학습 및 분산 컴퓨팅은 데이터가 수천 개의 노드에 분산되어 있는 경우에도 선형 회귀를 수행하는 방법을 알아내는 데 도움이 될 수 있습니다.

우리가 무슨 소리하는거야?

우리는 선형적 의존성을 회복해야 하는 과제에 직면해 있습니다. 입력 데이터로는 독립 변수로 구성된 벡터 세트가 제공되며, 각 벡터는 종속 변수의 특정 값과 연관되어 있습니다. 이 데이터는 두 가지 행렬의 형태로 표현될 수 있습니다.

이제 종속성이 가정되고 더욱이 선형이므로 가정을 행렬 곱의 형태로 작성하겠습니다(기록을 단순화하기 위해 여기와 아래에서는 방정식의 자유 항이 뒤에 숨겨져 있다고 가정합니다). , 그리고 행렬의 마지막 열 단위 포함):

선형 방정식 시스템처럼 들리지 않나요? 그럴 것 같지만, 그러한 방정식 시스템에 대한 해결책은 없을 가능성이 높습니다. 그 이유는 거의 모든 실제 데이터에 존재하는 노이즈 때문입니다. 또 다른 이유는 원래 변수에 비선형적으로 의존하는 추가 변수를 도입하여 해결할 수 있는 선형 의존성이 부족하기 때문일 수 있습니다. 다음 예를 고려하십시오.

출처 : 위키 백과

이것은 축을 따라 하나의 변수의 관계를 보여주는 선형 회귀의 간단한 예입니다. ) 다른 변수에서 (축을 따라) ). 이 예에 해당하는 선형 방정식 시스템이 해를 얻으려면 모든 점이 정확히 동일한 직선 위에 있어야 합니다. 그러나 그것은 사실이 아닙니다. 그러나 그것들은 잡음 때문에(또는 선형 관계에 대한 가정이 잘못되었기 때문에) 정확하게 동일한 직선 위에 놓여 있지 않습니다. 따라서 실제 데이터로부터 선형 관계를 복원하려면 일반적으로 한 가지 가정을 더 도입해야 합니다. 즉, 입력 데이터에는 노이즈가 포함되어 있으며 이 노이즈는 정규 분포. 다른 유형의 노이즈 분포에 대해 가정할 수 있지만 대부분의 경우 고려되는 것은 정규 분포이며 이에 대해서는 나중에 설명합니다.

최대 가능성 방법

그래서 우리는 무작위로 정규 분포된 잡음이 있다고 가정했습니다. 이런 상황에서는 어떻게 해야 할까요? 이 경우 수학에는 널리 사용됩니다. 최대우도법. 즉, 그 본질은 선택에 있습니다 우도 함수 그리고 그 이후의 극대화.

정상적인 노이즈가 있는 데이터로부터 선형 관계를 복원하는 것으로 돌아갑니다. 가정된 선형 관계는 수학적 기대치입니다. 기존 정규분포. 동시에, 관찰 가능 항목의 존재 여부에 따라 하나의 값 또는 다른 값을 취합니다. 다음과 같이 보입니다.

이제 대신 대체해보자 и 우리에게 필요한 변수는 다음과 같습니다.

이제 남은 것은 벡터를 찾는 것뿐이다. , 이 확률이 최대입니다. 이러한 함수를 최대화하려면 먼저 로그를 취하는 것이 편리합니다(함수의 로그는 함수 자체와 동일한 지점에서 최대값에 도달합니다).

결과적으로 다음 기능이 최소화됩니다.

그런데 이것을 메소드라고 합니다. 최소제곱. 위의 고려 사항을 모두 생략하고 이 방법을 사용하는 경우가 많습니다.

QR 분해

위 함수의 최소값은 이 함수의 기울기가 XNUMX이 되는 점을 찾아 구할 수 있습니다. 그리고 그라데이션은 다음과 같이 작성됩니다.

QR 분해 최소제곱법에서 사용되는 최소화 문제를 해결하기 위한 행렬법이다. 이와 관련하여 방정식을 행렬 형식으로 다시 작성합니다.

그래서 우리는 행렬을 분해합니다 행렬에 и 일련의 변환을 수행합니다(여기에서는 QR 분해 알고리즘 자체는 고려하지 않고 현재 작업과 관련된 사용만 고려합니다).

매트릭스 직교합니다. 이를 통해 작업을 제거할 수 있습니다. :

그리고 교체하면 에 , 그러면 작동합니다 . 고려해 보면 상부 삼각 행렬은 다음과 같습니다.

이는 대체 방법을 사용하여 해결할 수 있습니다. 요소 다음과 같이 위치하고 있습니다 , 이전 요소 다음과 같이 위치하고 있습니다 등.

QR 분해를 사용하여 결과 알고리즘의 복잡성이 다음과 같다는 점은 여기서 주목할 가치가 있습니다. . 게다가 행렬 곱셈 연산이 병렬화되어 있다는 사실에도 불구하고 이 알고리즘의 효과적인 분산 버전을 작성하는 것은 불가능합니다.

경사하강법

함수 최소화에 대해 이야기할 때 항상 (확률적) 경사하강법을 기억하는 것이 좋습니다. 이는 한 점에서 함수의 기울기를 반복적으로 계산한 다음 이를 기울기의 반대 방향으로 이동시키는 간단하고 효과적인 최소화 방법입니다. 이러한 각 단계는 솔루션을 최소값에 더 가깝게 만듭니다. 그래디언트는 여전히 동일하게 보입니다.

이 방법은 또한 기울기 연산자의 선형 특성으로 인해 병렬화 및 분산이 잘됩니다. 위 공식에서 합계 기호 아래에는 독립된 항이 있다는 점에 유의하세요. 즉, 모든 인덱스에 대해 독립적으로 그래디언트를 계산할 수 있습니다. 처음부터 , 이와 병행하여 다음과 같은 인덱스에 대한 기울기를 계산합니다. 에 . 그런 다음 결과 그라디언트를 추가합니다. 덧셈의 ​​결과는 첫 번째부터 인덱스에 대한 기울기를 즉시 계산한 것과 동일합니다. . 따라서 데이터가 여러 데이터 조각에 분산되어 있는 경우 각 조각에 대해 독립적으로 기울기를 계산할 수 있으며 이러한 계산 결과를 합산하여 최종 결과를 얻을 수 있습니다.

구현 관점에서 볼 때 이는 패러다임에 적합합니다. MapReduce. 경사하강법의 각 단계에서는 각 데이터 노드에 작업을 보내 경사도를 계산하고, 계산된 경사도를 모아 합산한 결과를 사용하여 결과를 개선합니다.

MapReduce 패러다임의 구현 용이성과 실행 능력에도 불구하고 경사하강법에는 단점도 있습니다. 특히, 융합을 달성하는 데 필요한 단계 수가 다른 보다 전문적인 방법에 비해 훨씬 높습니다.

LSQR

LSQR 문제를 해결하기 위한 또 다른 방법으로, 선형 회귀를 복원하고 선형 방정식 시스템을 푸는 데 모두 적합합니다. 주요 특징은 행렬 방법과 반복적 접근 방식의 장점을 결합한 것입니다. 이 방법의 구현은 두 라이브러리 모두에서 찾을 수 있습니다. SciPy,에서 Matlab. 이 방법에 대한 설명은 여기서는 제공되지 않습니다(기사에서 찾을 수 있음). LSQR: 희소 선형 방정식 및 희소 최소 제곱을 위한 알고리즘). 대신 LSQR을 분산 환경에서 실행하도록 조정하는 접근 방식을 시연합니다.

LSQR 방법은 다음을 기반으로 합니다. 양측화 절차. 이는 반복 절차이며, 각 반복은 다음 단계로 구성됩니다.


하지만 행렬이 다음과 같다고 가정하면 수평으로 분할된 경우 각 반복은 두 개의 MapReduce 단계로 표시될 수 있습니다. 이러한 방식으로 각 반복 동안 데이터 전송을 최소화하는 것이 가능합니다(미지수 수와 길이가 같은 벡터만 해당).

선형 회귀를 구현할 때 사용되는 접근 방식입니다. 아파치 이그나이트 ML.

결론

선형 회귀 복구 알고리즘에는 여러 가지가 있지만 모든 조건에 모두 적용할 수는 없습니다. 따라서 QR 분해는 작은 데이터 세트에 대한 정확한 솔루션에 탁월합니다. 경사하강법은 구현이 간단하며 대략적인 솔루션을 빠르게 찾을 수 있습니다. 그리고 LSQR은 분산이 가능하고 경사하강법에 비해 빠르게 수렴하며 QR 분해와 달리 알고리즘을 조기에 중지하여 근사해를 찾을 수 있다는 점에서 이전 두 알고리즘의 가장 좋은 특성을 결합합니다.

출처 : habr.com