Method of Steepest Descent
한 번에 계산하지 말고
여러 번 w를 업데이트 하면서 최적화를 해 보자
Continuously differentiable function of some unknown weight vector w
최적의 w의 cost는 항상 다른 곳의 cost보다 작거나 같아야 함\
cost가 가장 빠르게 증가하는 방향
cost의 minimum을 찾는 게 목적 -> 가장 빠르게 증가하는 방향의 반대 방향으로 업데이트
-gradient를 w에 더해줌
그런데 문제는, -gradient로 update하는 것은 좋지만,
무작정 크게 update하면 문제가 생길 수 있음
J에 대한 등고선을 가정해볼 때,
너무 크게 업데이트하는 건 적절하지 않음
업데이트 량을 조절해야 함
mu-> step size parameter
1/2은 ? -> 미분을 정의할 때 1/2을 곱하고 정의하는 경우가 많은데,
결과식에서 2가 없어지므로, 상대적인 값을 보정하기 위해 넣음
First-order Taylor series expansion
Stability of the Steepest-Descent Algorithm (1)
v(n)은 원래,
c가 2개의 weight로 이루어진 2tap 필터일 때,
어떤 평면을 이룰 때,
수직이 되는 J(cost)를 만들고 minimum point에서 타원형의 ball shape으로 만듦
토기를 만들어냄 -> 위에서 내려다 보면, w1,w2의 minimum point가 있고 등고선이 그려지는 형태가 됨
그 축에 맞게 align 한 게 v(n)
lambda는 항상 positive 이므로, 음수로 나누므로, 부등호가 바뀜
뮤가 작을 때는 타우 k를 근사화할 수 있음
Example (1)
원에 가까울 수록 모든 지점에서 미분한 값이 항상 minimum 방향을 가르키므로, 수렴하는데 무리가 없음
반대로 많이 찌그러지면, 그라디언트 방향이 미분 방향과 차이가 많이 나므로, step size를 적게 가져가야 수렴하게 됨
Example(2)
As the eigenvalue spread increases (and the input process becomes more correlated), the minimum MSE J_min for the prediction problem decreases
아이겐벨류 스프레드가 크면 스텝사이즈를 크게 가져갈 수가 없음 -> 수렴하는 시간이 걸림
반대로 수렴이 빠르게 됨
steep descent 는 모든 데이터에 대한 미분을 구해서 업데이트 해야하는데,
엄청나게 많은 계산을 한 iteration 에 해야하는데,
10번의 iteration 이 결코 작은 값이 아님
작게 가져가는 것 -> 업데이트 량이 작아짐(그 때 그때 그라디언트 방향을 따라가면 스무스한 무양)
=> 한 번 업데이트 양이 작으므로 Iteration 을 많이 하게 됨
The Steepest-Descent Algorithm as a Deterministic Search Method
• Steepest-descent algorithm depends on three quantities:
▫ The starting point
▫ The gradient vector
▫ The step-size parameter
하나의 path 가 정해지므로, ▫ Deterministic search method in weight space
구현이 매우 간단하므로 선호,
단점은 수렴이 매우 느림
현재에서 gradient 만 보고 따라가므로,
단점이 생기는 원인은?
first-order) approximation of the error-performance surface around the current point
이므로
order를 올려보자 ! -> next level
• Second-order Taylor series expansion of
훨씬 더 빠르게 수렴할 것인것은 알 수 있지만,
문제는 계산이 복잡해짐(H^(-1))=> 계산량이 커짐