홈
퍼뮤테이션 엔트로피
https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.88.174102 http://materias.df.uba.ar/dnla2019c1/files/2019/03/permutation_entropy.pdf
오토마타
- 폰 노이만 네이버후드
유전 알고리즘
MEP
https://arxiv.org/pdf/2110.00367
DBscan
최적화이론에서의 타부 탐색
ISTA: 반복 소프트 쓰레숄딩 알고리즘
알고리즘
$$ \argmin_{\beta} \left( {{ 1 } \over { 2 }} \left\| Y - X \beta \right\|_{2}^{2} + \lambda \left\| \beta \right\|_{1} \right) $$
위와 같은 BPDN, 혹은 라쏘 회귀 문제를 푸는 방법으로써, 다음의 업데이트 룰을 ISTAIterative Soft Thresholding Algorithm라 한다. $$ \beta^{(k+1)} = S_{\lambda} \left( \beta^{(k)} - \alpha X^{T} \left( X \beta^{(k)} - Y \right) \right) $$ 여기서 $\alpha$ 는 스텝 사이즈step size고, 벡터화된vectorized 소프트 쓰레숄딩 $S_{\lambda} : \mathbb{R}^{n} \to \mathbb{R}^{n}$ 는 벡터의 각 성분별로 소프트 쓰레숄딩 $\eta_{S} \left( x ; \lambda \right)$ 을 적용하는 함수다.
설명
ISTA는 프락시멀 그래디언트 메서드의 일종으로, 행렬대수적으로 쉽게 풀리는 최소제곱법과 달리 해를 영벡터 근처에서 찾고 싶을 때 쓰일 수 있다.
$\lambda$ 가 상수로 주어져 있을 때, 라쏘 회귀의 목적 함수 $L$ 을 위와 같이 나타내자. 일반적으로 라쏘 회귀의 최적해는 클로즈드 폼closed form이 없지만, $X$ 의 모든 칼럼이 서로 직교한다고 가정하면 $\hat{\beta} = \argmin_{\beta} L \left( \beta \right)$ 의 $k$ 번째 성분 $\left( \hat{\beta} \right)_{k}$ 는 다음과 같다. $$ \begin{align*} \left( \hat{\beta} \right)_{k} =& {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \eta_{\lambda} \left( X^{T} Y \right)_{k} \\ = & {{ 1 } \over { \left( X^{T} X \right)_{kk} }} \begin{cases} \left( X^{T} Y \right)_{k} + \lambda & , \text{if } \left( X^{T} Y \right)_{k} < - \lambda \\ 0 & , \text{if } \left( X^{T} Y \right)_{k} \in [-\lambda, \lambda] \\ \left( X^{T} Y \right)_{k} - \lambda & , \text{if } \left( X^{T} Y \right)_{k} > \lambda \end{cases} \end{align*} $$
실제로 BPDN에서 계획행렬이 풀랭크일 때, 라쏘 회귀의 최적해는 위와 같이 나타낼 수 있고, 그렇지 않더라도 라쏘 회귀를 수행하는 메서드가 바로 ISTA다. 이러한 이론적 배경을 수식적으로 이해하는 것은 굉장히 중요한데, 이것이 발전시킨 FISTA를 알기 위해 피할 수 없는 내용이기 때문이다.
유도
$S_{\lambda}$ 는 그 자체로 해를 영벡터 근처로 이동시키는 함수고, 프락시멀 오퍼레이터를 반영한다고 보면 되니까, BPDN에서는 제곱항인 $L = \left\| Y - X \beta \right\|_{2}^{2} / 2$ 신경쓰면 된다.
잔차제곱합의 그래디언트: $$ f \left( \mathbf{s} \right) := \left( \mathbf{y} - X \mathbf{s} \right)^{T} R \left( \mathbf{y} - X \mathbf{s} \right) $$ $\mathbf{s}$ 에 종속되지 않은 벡터 $\mathbf{y} \in \mathbb{R}^{n}$ 과 행렬 $X \in \mathbb{R}^{n \times p}$, $R \in \mathbb{R}^{n \times n}$ 에 대해 다음이 성립한다. $$ {{ \partial f \left( \mathbf{s} \right) } \over { \partial \mathbf{s} }} = - X^{T} \left( R + R^{T} \right) \left( \mathbf{y} - X \mathbf{s} \right) $$
$R = I$ 인 경우에 대해 위 공식들을 적용하면 $$ \begin{align*} & {{ \partial } \over { \partial \beta }} L \\ =& {{ 1 } \over { 2 }} {{ \partial } \over { \partial \beta }} \left\| Y - X \beta \right\|_{2}^{2} \\ =& {{ \partial } \over { \partial \beta }} {{ 1 } \over { 2 }} \left( Y - X \beta \right)^{T} \left( Y - X \beta \right) \\ =& - {{ 1 } \over { 2 }} X^{T} \left( I + I^{T} \right) \left( Y - X \beta \right) \\ =& X^{T} \left( X \beta - Y \right) \end{align*} $$ 이고, 이 자체로 그래디언트이므로 경사하강법으로 치자면 $$ \beta^{(k+1)} = \beta^{(k)} - \alpha \nabla L $$ 이고, 여기에 벡터화된 소프트 쓰레숄딩을 취하면 ISTA의 업데이트 룰이 된다.
■
코드
다음은 줄리아로 구현한 ISTA의 예시 코드다.
function soft_thresholding(x, λ)
return sign(x) * max(abs(x) - λ, 0.0)
end
function ista(A, b, λ, α=1.0, max_iter=1000)
x = zeros(size(A, 2))
for i in 1:max_iter
grad = A' * (A * x - b)
x = soft_thresholding.(x - α * grad, α * λ)
end
return x
end