Hands-on ML : 4. 선형 회귀 및 계산 복잡도 (시간복잡도, 공간복잡도)

4.1 선형 회귀 (Linear regression)

4.1.1 정규방정식 (normal equation)

통계에서 일반 최소 제곱은 선형 회귀 모델에서 알려지지 않은 매개변수를 추정하기 위한 선형 최소제곱 방법의 한 유형

 

이를 파이썬으로 나타내보자.

X=2*np.random.rand(100,1)
y=4+3*X+np.random.randn(100,1)

정규방정식으로 Theta 구하기.

X_b=np.c_[np.ones((100,1)),X]
theta_best = np.linalg.inv(X_b.T.dot(X_b)).dot(X_b.T).dot(y)

theta0 , theta1

X_new=np.array([[0],[2]])
X_new_b=np.c_[np.ones((2,1)),X_new]
y_predict=X_new_b.dot(theta_best)

plt.plot(X_new,y_predict,'r-')
plt.plot(X,y,'b.')

선형 회귀 모델의 예측

유사역행렬

np.linalg.pinv(X_b).dot(y)

특잇값 분해 (Singular Value Decomposition)를 사용해 계산된다.

훈련 세트 행렬 X를 3개읭 행렬 곱셈으로 분해.

4.1.2 계산 복잡도 (Computational complexity)

정규방정식은 (n+1)x(n+1) 크기가 되는 XTX의 역행렬을 계산

https://joshuajangblog.files.wordpress.com/2016/09/1.jpg?w=638

시간 복잡도 (time complexity)

일반적으로 O(n)의 시간복잡도를 가지면 좋은 알고리즘으로 취급.

n의 값이 커지면 커질수록, 시간복잡도가 복잡한 알고리즘은 수행시간이 급격하게 길어진다.

그러므로 시간복잡도가 단순하도록 알고리즘을 짜는 것이 중요.

 

공간 복잡도 (space complexity)

알고리즘이 수행되는데 필요한 메모리의 총량으로, 주로 시간 복잡도를 해결 후 공간 복잡도를 해결하는 경우가 많다.

동적 계획법의 경우, 메모리 사용이 많이 필요하므로 임베디드, 펌웨어 등의 하드웨어 환경이 한정되있는 경우 공간복잡도가 상당히 중요하다는 것을 알 수 있다.

 

​빅오표기법

www.tutorialspoint.com/asymptotic-complexity

Best Case - 여기에서 실행 시간의 하한이 계산된다. 최적의 조건에서 알고리즘의 동작을 설명한다.

Average Case - 이 경우 알고리즘 실행 시간의 상한과 하한 사이의 영역을 계산한다. 이 경우 실행된 작업의 수는 최소가 아니며 최대가 아니다.

Worst Case - 이 경우 알고리즘 실행 시간의 상한을 계산한다. 이 경우 최대 작업 수가 실행된다.

 

참고 문헌 :

https://book.naver.com/bookdb/book_detail.nhn?bid=16328592

핸즈온 머신러닝