cho.sh

선형 회귀는 너무 쉬워 2

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

유림이는 선형 회귀에 자신이 있다. 그래서 MatKor 동아리에서 선형 회귀에 관한 수업을 할 때 집중하지 않았다. 당시 강사였던 동우는 이를 못마땅하게 여겨 유림이에게 다른 문제 선형 회귀는 너무 쉬워 1을 내주었고, 유림이는 문제를 쉽게 풀었다.

동우는 이제 기존의 선형 회귀 문제를 내주었다. 데이터 (x_1,y_1),(x_2,y_2),⋯ ,(x_n,y_n)(x\_1, y\_1), (x\_2, y\_2), \cdots , (x\_n, y\_n)이 주어졌을 때, 이를 가장 잘 설명하는 일차함수 y=ax+by=ax+b를 찾는 문제이다. 여기서 주어진 점들 (x_i,y_i)(x\_i, y\_i)에 대해 x_ix\_i를 통해 얻는 추정치 y_i^=ax_i+b\hat{y\_i} = ax\_i+b로 정의하고, 실제 y_iy\_i에서 예측치인 y_i^\hat{y\_i}를 뺀 값 y_i−y_i^y\_i-\hat{y\_i}를 잔차 ϵ_i\epsilon\_i로 정의한다.

선형 회귀 문제는 이 잔차 제곱의 합이 00에 가장 가깝도록, 즉 ∑_i=1nϵ_i2=∑_i=1n(y_i−ax_i−b)2\displaystyle\sum\_{i=1}^n \epsilon\_i^2 = \displaystyle\sum\_{i=1}^n (y\_i-ax\_i-b)^2이 최소가 되도록 하는 실수 aa와 bb를 찾는 문제이다. 이 값이 최소가 되도록 하는 aa와 bb를 a_2a\_2, b_2b\_2라고 한다. 여기서 ∑_i=1nϵ_i2\displaystyle\sum\_{i=1}^n \epsilon\_i^2은 ϵ_12+ϵ_22+⋯+ϵ_n2\epsilon\_1^2+\epsilon\_2^2+\cdots+\epsilon\_n^2를, ∑_i=1n(y_i−ax_i−b)2\displaystyle\sum\_{i=1}^n (y\_i-ax\_i-b)^2은 (y_1−ax_1−b)2+(y_2−ax_2−b)2+⋯+(y_n−ax_n−b)2(y\_1-ax\_1-b)^2+(y\_2-ax\_2-b)^2+\cdots+(y\_n-ax\_n-b)^2를 나타낸다.

동우는 유림이에게 주어진 점들에 대해 잔차 제곱의 합이 최소가 되도록 하는 실수 a_2a\_2와 b_2b\_2를 구해보라는 문제를 내주었다.

그러나 유림이는 이미 답을 알고 있고, 바로 코딩하기로 했다. 답은 다음과 같다.

  • 먼저 x_ix\_i의 합을 S_xS\_x, y_iy\_i의 합을 S_yS\_y, x_i2x\_i^2의 합을 S_xxS\_{xx}, x_iy_ix\_iy\_i의 합을 S_xyS\_{xy}라 하고, 이를 구하자. 그렇다면 a_2a\_2와 b_2b\_2는 경우에 따라 다음과 같다.

    • 만약 S_x2≠nS_xxS\_x^2\ne nS\_{xx}라면 아래와 같이 답을 구할 수 있다. \[\begin{align*}a_2&=\frac{nS_{xy}-S_xS_y}{nS_{xx}-S_x^2}\\ b_2&=\frac{S_y-a_2S_x}{n}\end{align*}\]
      • 계산 중 분자와 분모에 대해 2×10182\times 10^{18}의 큰 수가 등장할 수 있음에 유의해 적절한 자료형을 사용하도록 하자.
    • 만약 S_x2=nS_xxS\_x^2=nS\_{xx}이라면 가능한 a_2a\_2와 b_2b\_2 쌍이 유일하지 않고 여러 개 존재한다.

위의 결과에 대한 구체적인 증명 과정은 아래 노트에 있으므로, 관심이 있다면 나중에 읽어보자.

입력

첫 줄에 데이터의 개수를 의미하는 정수 n(2≤n≤106)n(2 \le n \le 10^6)이 주어진다.

두 번째 줄부터 nn개의 줄에 걸쳐 한 줄에 하나씩 점의 좌표를 나타내는 정수 x_ix\_i와 y_iy\_i(−103≤x_i,y_i≤103-10^3 \le x\_i, y\_i \le 10^3)의 값이 주어진다.

이때, 서로 같은 점이 여러 번 주어질 수 있음에 유의한다.

출력

첫 번째 줄에 ∑_i=1n(a_2x_i+b_2−y_i)2\displaystyle\sum\_{i=1}^n (a\_2x\_i+b\_2-y\_i)^2의 값이 00에 가장 가깝도록 하는 a_2a\_2와 b_2b\_2가 유일하게 존재한다면, 이를 공백으로 구분하여 출력한다

만약 답으로 가능한 a_2a\_2와 b_2b\_2 쌍이 여러 개 존재한다면, 첫 줄에 EZPZ를 출력한다.

정답과의 절대 혹은 상대 오차가 10−610^{-6} 이하라면 정답으로 간주한다.

힌트

선형 회귀식을 구하는 방식은 행렬을 이용하는 법, 미분을 이용하는 법 등 다양하지만 다음과 같은 방식을 소개하겠다.

<과정>

선형 회귀를 하기 위해 f(a,b)=∑_i=1n(ax_i+b−y_i)2f(a,b)= \displaystyle\sum\_{i=1}^n (ax\_i+b-y\_i)^2을 0과 가장 가깝게 만들라는 것은, 각 오차의 제곱들의 합이므로 각 항이 0보다 커, 해당 식을 최소로 만드는 aa와 bb를 찾으면 된다. 이때, 해당 값이 a_2a\_2와 b_2b\_2가 될 것인데 그 말은, ∀(a,b)∈R2,f˜(a_2,b_2)≤f(a,b)\forall (a,b)\in \mathbb{R}^2,\~f(a\_2, b\_2) \le f(a,b)를 만족해야 한다는 것이다. 즉, b=b_2b = b\_2일 때, f(a,b_2)f(a,b\_2)의 최솟값일 때 aa의 값이 결국 a_2a\_2가 될 것이고, 반대로 a=a_2a=a\_2일 때로 고정하면 b_2b\_2도 최솟값이다. 즉, 서로 다른 변수에 대해 고정하고 미분했을 때 0이 나오는 aa와 bb를 찾으면 된다. 즉, ∂f∂a=0\frac{\partial f}{\partial a}=0, ∂f∂b=0\frac{\partial f}{\partial b}=0을 만족시키는 aa와 bb를 찾으면 된다. 즉, 이를 Gradient 벡터라고 정의하고 ∇f=(∂f∂a,∂f∂b)=0\nabla f = \left(\frac{\partial f}{\partial a}, \frac{\partial f}{\partial b}\right) = \mathbf{0}을 구하면 된다.

여기서 S_xS\_x를 x_ix\_i들의 합, S_yS\_y를 y_iy\_i들의 합, S_xyS\_{xy}를 x_iy_ix\_iy\_i들의 합, S_xxS\_{xx}를 x_i2x\_i^2들의 합으로 정의하자. 수식으로 나타내면 S_x=∑_i=1nx_iS\_x = \displaystyle\sum\_{i=1}^n{x\_i}, S_y=∑_i=1nx_iS\_y = \displaystyle\sum\_{i=1}^n{x\_i}, S_xy=∑_i=1nx_iy_iS\_{xy} = \displaystyle\sum\_{i=1}^n{x\_iy\_i}, S_xx=∑_i=1nx_i2S\_{xx} = \displaystyle\sum\_{i=1}^n{x\_i^2}가 된다. 우선 이 값들을 먼저 구해 놓은 뒤, Gradient 벡터를 보면 다음과 같다.

\frac{\partial f}{\partial a} $$= \frac{\partial}{\partial a}\displaystyle\sum\_{i=1}^n (ax\_i+b-y\_i)^2 $$= \displaystyle\sum\_{i=1}^n{\frac{\partial}{\partial a}\left( (ax\_i+b-y\_i)^2\right)}$$= 2\displaystyle\sum\_{i=1}^n{x\_i(ax\_i+b-y\_i)}$$=2\left(a\displaystyle\sum\_{i=1}^n{x\_i^2}+b\displaystyle\sum\_{i=1}^n{x\_i}-\displaystyle\sum\_{i=1}^n{x\_iy\_i}\right)이고, 이 값이 00일 때 최적이므로, S_xxa_2+S_xb_2=S_xyS\_{xx}a\_2+S\_xb\_2=S\_{xy}을 만족한다. 이 식을 ①①이라 하자.

마찬가지로 \frac{\partial f}{\partial b} $$= \frac{\partial}{\partial b}\displaystyle\sum\_{i=1}^n (ax\_i+b-y\_i)^2 $$= \displaystyle\sum\_{i=1}^n{\frac{\partial}{\partial b} \left((ax\_i+b-y\_i)^2\right)}$$= 2\displaystyle\sum\_{i=1}^n{(ax\_i+b-y\_i)}$$=2\left(a\displaystyle\sum\_{i=1}^n{x\_i}+b\displaystyle\sum\_{i=1}^n{1}-\displaystyle\sum\_{i=1}^n{y\_i}\right)이고, 이 값이 00일 때 최적이므로, S_xa_2+nb_2=S_yS\_xa\_2+nb\_2=S\_y을 만족한다. 이 식을 ②②라 하자.

(①×n−②×S_x)\left(①\times n - ②\times S\_x\right)의 식을 변변 계산하면, (nS_xx−S_x2)a_2=nS_xy−S_xS_y\left(nS\_{xx} - S\_x^2\right)a\_2=nS\_{xy}-S\_xS\_y가 된다.

여기서 n=∑_i=1n1n = \displaystyle\sum\_{i=1}^n{1}으로 생각하면, S_x2≤nS_xxS\_x^2\le nS\_{xx}라는 것은 코시-슈바르츠 부등식을 통해 쉽게 알 수 있다.(혹은 분산이 0보다 크며, 제곱의 평균에서 평균의 제곱을 뺀 값이라는 성질을 통해 알 수 있다) 또한, 등호는 모든 xx좌표가 같을 때라는 것 역시 등호 성립 조건에서 알 수 있다.

<결론>

  • 만약 S_x2≠nS_xxS\_x^2\ne nS\_{xx}라면, a_2=nS_xy−S_xS_ynS_xx−S_x2a\_2=\frac{nS\_{xy}-S\_xS\_y}{nS\_{xx}-S\_x^2}을 만족한다. 여기서 구한 a_2a\_2를 ②②의 S_xa_2+nb_2=S_yS\_xa\_2+nb\_2=S\_y에 대입하면, b_2=S_y−a_2S_xnb\_2=\frac{S\_y-a\_2S\_x}{n}가 된다. 즉, 이 식에 값을 넣고 계산하여 최적해를 구할 수 있다.
  • 만약 S_x2=nS_xxS\_x^2=nS\_{xx}이라면, 코시-슈바르츠 부등식 혹은 분산과 0의 등호 조건과 같으므로, 모든 x_ix\_i의 좌표가 같다는 것을 의미하고, 그 값을 xx라 하자. f(a,b)f(a,b)가 a=a_2a=a\_2이고 b=b_2b=b\_2일 때, 최솟값을 가진다면, a=a_2+1a=a\_2+1이고 b=b_2−xb=b\_2-x일 때도 f(a,b)=∑_i=1n((a_2+1)x+(b_2−x)−y_i)2=∑_i=1n(a_2x+b_2−y_i)2=f(a_2,b_2)f(a,b) =\displaystyle\sum\_{i=1}^n ((a\_2+1) x+(b\_2-x) -y\_i)^2=\displaystyle\sum\_{i=1}^n (a\_2x+b\_2-y\_i)^2=f(a\_2,b\_2)이므로, 마찬가지로 최솟값을 가진다. 즉, 가능한 a_2a\_2와 b_2b\_2 쌍이 여러 개 존재한다.

<추가 증명>

추가로, Gradient 벡터(변수가 여러 개일 경우는 Jacobian Matrix)를 한 번 더 편미분해 구한 것을 Hessian Matrix라고 부른다. 이는 H(f)=(∂2∂a2∂2∂a∂b ∂2∂b∂a∂2∂b2 )fH(f) = \left( \begin{matrix} \frac{\partial^2}{\partial a^2} & \frac{\partial^2}{\partial a\partial b} \\\ \frac{\partial^2}{\partial b\partial a} & \frac{\partial^2}{\partial b^2} \\\ \end{matrix} \right)f로 표현할 수 있다.

이 경우 Hessian Matrix를 보면, ∂2∂a2f=2S_xx\frac{\partial^2}{\partial a^2}f = 2S\_{xx}, ∂2∂a∂bf=∂2∂b∂af=2S_x\frac{\partial^2}{\partial a\partial b}f =\frac{\partial^2}{\partial b\partial a}f =2S\_x, ∂2∂b2f=2n\frac{\partial^2}{\partial b^2}f =2n이다. 즉, ∣H(f)∣=4(nS_xx−S_x2)≥0\left|H(f)\right| = 4 \left(nS\_{xx} - S\_x^2\right) \ge 0이 변수 및 조건과 관계없이 성립한다는 사실을 알 수 있고, 이는 결국 점의 좌표 관계없이 aa와 bb 두 축에 대해 convex 함을 의미하며, local minimum 즉, 위에서 구한 a_2a\_2와 b_2b\_2가 global minimum도 된다는 것을 알 수 있다.