Fast Differentiable Sorting and Ranking

잡담

옛날보다는 수식이 많은 식이 조금 더 잘 이해가 되는 것 같기도 하면서도 잘 안되는 것 같으면서도… 모든 걸 이해할 필요는 없는데, 자꾸 모든 부분을 이해하고 싶어진다. 많은 일들이 추상화가 잘 되어 있어서 윗단과 아랫단에 대해 잘 알고 있을 필요가 없다는 사실을 알고 있다. 예를 들어서, 컴퓨터 일 하면서 재료공학은 전혀 몰라도 상관이 없다. 전기공학도 전혀 상관 없을 것이다. CPU가 복잡한 전기회로로 이뤄지지 않고, 0과 1 계산을 빨리 하는(굳이 0과 1 계산일 필요도 없다) 미니언즈 1000만 마리쯤 모여 있다고 해도 내 일엔 그다지 상관이 없을 것 같다. 추천 시스템 일도 마찬가지일 텐데. 복잡한 수학적 정의와 성질과 증명을 잘 몰라도, 알아야 할 부분만 알면 괜찮을 것 같은데. 사실 이게 혼동스러운 이유는 어느 정도는 머신러닝 분야가 완전히 정립되지 않아서라고 생각된다. 몇년 지나면 수학 하나도 몰라도 개발 잘 할 수 있는 시기가 올 것 같다고 확신한다. 그럼 난 어떡하지;;

아무튼, 그래서, 복잡한 부분은 잘 몰라도 된다고 생각하고 논문을 이해한 대로만 설명하겠당.

Sorting as a Linear Optimization

정렬과 랭킹은 사실 같은 문제이다. $\theta=(5,8,3)$이 주어졌을 때, 랭킹은 $r=(2,1,3)$을 반환하는 문제이며 $\theta_r=(\theta_{r_1}, \theta_{r_2}, \theta_{r_3})=(8,5,3)$이며 정렬되어 있다.

$\rho=(3,2,1)$을 정의한다고 하면 정렬하는 문제에서의 ‘rank’를 다음과 같이 정의할 수 있다.

\[r = \text{argmin}_{y \in \mathcal{P}(\frac{1}{\epsilon}\rho)} y^T\theta\]

단, $\mathcal{P}(\rho)$는 $\rho$의 모든 permutation이 만드는 convex hull이며, 이 선형계획법의 feasible solution은 정수이다. 이 $\rho’=\rho/\epsilon$이라는 soft parameter를 넣어주고, 적절한 quadratic regularization term을 넣어 주면 그냥 사실 $\frac{1}{2} \vert \vert \rho + x\vert \vert^2$를 $x$에 대해 minimize하는 문제로 바뀔 수 있다. 논문에서는 Entropic Regularization을 대신 사용하는 경우도 유도되어 있다. Entropic Regularization은 $R(p)= p^T(\log_p-1)$로 정의된다.

성질

이 operation은 몇가지 이쁜 성질을 갖는다.

$\epsilon \rightarrow 0$일 때 실제 정렬/랭킹과 결과가 같아진다.
미분가능하다.
이게 만드는 정렬/랭킹은 (soft하더라도) order가 보존된다.

Computational Efficiency

뒷부분은 저 문제를 추가적으로, Fenchel Dual Form이라는 걸 써서 Regression 형태로 변환해서, gradient가 빠르게 계산되는 form을 보여줬는데, Fenchel Dual Form이라는게 도무지 이해가 가지 않았다. 요지는, 저 식(혹은 저 식과 동일한) 식의 계산/gradient 계산을 $O(n\log(n))$에 할 수 있다는 것인 것 같다.

느낀점

머신러닝 논문에서 필요한 수학 지식이 가면 갈 수록 올라가고 있는 것 같다. GAN이나 Attention같이, 수학적 지식이 깊게 필요하지 않아도 이해할 수 있는 (저 논문들도 물론 뒤에 깔린 어려운 수학이 있겠지만) 논문보다, 논문이 얘기하고자 하는 최소한의 요지만 이해하려고 해도 엄청엄청 복잡한 수학이 필요한 논문들이 늘고 있는 것 같다.

수학공부를 해야겠다.