본문 바로가기

전체 글

 (6)
다변수 함수의 Chain Rule 이변수 함수 $z = f(x, y)$ 에 대해, $x = g(t), y = h(t)$ 이고 $f(x, y), g(t), h(t)$ 가 미분 가능한 함수이면 ${dz \over dt} = {\partial z \over \partial x}{dx \over dt} + {\partial z \over \partial y}{dy \over dt}$ 이라는 것이 이변수 함수의 chain rule 입니다. 따라서 위와 같은 신경망에서 z 에 대한 t의 편미분 값을 back propagation 알고리즘을 통해 얻을 수 있는 것입니다. 이를 확장하면 아무리 복잡한 신경망이라도 각 과정이 미분 가능한 함수들로 구성되어 있다면 back propagation 알고리즘이 잘 동작하는 것을 알 수 있습니다. Weight S..
Balkan Olympiad in Informatics 2018. Zalmoxis www.acmicpc.net/problem/16016 맨 처음에 길이 1인 배열 [30] 이 주어집니다. 여기에 다음 연산을 원하는 만큼 수행할 수 있습니다. "배열에 있는 양의 정수 x 를 x - 1 두 개로 만들 수 있다." 가령 [30] 을 [29, 29] 로 만들 수 있고, [29, 29] 에서 오른쪽 29 에 연산을 수행하여 [29, 28, 28] 과 같이 만들 수 있는 것. 연산을 적용하여 숫자를 나눈 뒤 순서를 바꾸면 안됩니다. 가령 [29, 29] 에서 오른쪽 29를 28, 28 로 나누어 위치를 바꾸어 삽입([28, 29, 28] 처럼)하면 안된다는 뜻입니다. 이 때, 우리가 만들 수 있는 배열을 "ZalSequence" 라고 합니다. 예) [30], [29, 29], [28, 28, 2..
Random Orthogonal Matrix 각 원소를 Standard Normal Distribution 에서 추출한 N x N Matrix 를 QR Decomposition 하면 Q가 Stiefel Manifold에서 uniform distribution 이 된다고 합니다. 또한, Q의 주대각 성분에 R의 주대각 성분의 부호를 곱해주면 Q가 Haar Distributed Matrix 가 된다고 합니다. arxiv.org/abs/2009.14794 Rethinking Attention with Performers We introduce Performers, Transformer architectures which can estimate regular (softmax) full-rank-attention Transformers with provab..
[Project Euler 252] 볼록 구멍 재미있어보이고 아무도 안 풀었길래 엄~청 오랜만에 문제를 풀어보았습니다. 오랜만에 c++로 코딩을 하니 어색하네요ㅋㅋ 힌트 더보기 O(N^3) 다이나믹프로그래밍으로 해결할 수 있습니다.
Neumann Series Predict then Propagate: Graph Neural Networks meet Personalized PageRank 라는 논문을 읽다가 흥미로운 technique 이 있어서 포스팅하게 되었습니다. 위의 논문에서는 graph 의 scaled down 된 normalized weighted adjacency matrix $A$ 에 대하여 $(I - A)^{-1}v$ 를 계산하는 phase 를 모델의 학습과정에서 포함하게 됩니다. $(I - A)^{-1}v$ 는 $(I - A)$ 의 inversion 을 계산한 뒤 $v$를 곱하는 naive 한 방법으로 구하게 되면 $O(N^3)$ ($N$ 은 그래프 정점의 개수) 시간이 걸립니다. 또한, matrix 의 inversion 을 구하는 과정에서 d..
An Optimal Deterministic Algorithm for Online b-Matching 최근에 온라인 광고 플랫폼에서 광고를 유저에게 최적으로 매칭시키는 문제에 대해 관심이 생겨서 관련된 논문들을 찾아보았는데 많은 논문들이 제목에 소개된 논문을 기반으로 하고 있었기 때문에 먼저 읽어보게 되었습니다. [논문 링크] An Optimal Deterministic Algorithm for Online b-Matching 위의 논문은 아래와 같은 특수한 경우의 online bipartite matching 문제를 합리적인 방법으로 해결하는 방법을 제시하는 것이 주요 목적이었습니다. 문제) support station 이 여러개 있고 각각은 최대 b명의 client 만을 support 할 수 있습니다. 또한 각 client 들은 support 받을 수 있는 station 들의 목록이 정해져 있습니다...

티스토리툴바