https://atcoder.jp/contests/abc368/tasks/abc368_d D - Minimum Steiner TreeAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp 1부터 n까지 번호를 가진 정점을 가진 트리에서 어떤 정점들을 제거할때, 특정한 정점 v1,v2,...,vk를 반드시 포함하게 하는 트리를 만들고 싶다면, 그러한 트리의 최소 정점 수는? 예를 들어 왼쪽 트리에서 1,3,5를 반드시 포함하는 트리를 만들고 싶을때, 4번, 6번, 7번을 제거하면 된다 사실 테크닉에 감탄해서 복기하는거긴 한..
1. terminology kernel, filter, matrix, tensor 전부 비슷하면서 약간 달라? kernel을 channel로 쌓으면 filter라고 부른다는데 딱히 찾아봐도 뭐가 없네 matrix가 2차원으로 원소를 모아놓은거면 tensor는 3차원 이상으로 원소를 모아놓은거 decomposition과 factorization은 사실상 동일해서 혼용해서 사용 그래서 tensor decomposition을 tensor factorization이라고 부르기도함 low rank approximation은 decomposition들을 전부 통틀어서 이르는 느낌이랄까 convolution layer를 decomposition하는 경우 convolution filter를 decomposition..
1. background ensemble이란 단일 알고리즘보다 적당히 여러개 알고리즘을 조합해서 성능이 향상되길 기대하는 것 모든 데이터셋에 대한 우수한 알고리즘이 존재하는가? 위 그림에서 x축은 데이터셋이고 y축은 알고리즘의 상대적인 에러이고 각 line은 알고리즘에 따른 그래프 그림을 보면 모든 알고리즘 각각이 모든 데이터셋에 우수하진 않다 neural network도 Diabetes라는 데이터에는 에러율이 높다 특정 알고리즘이 모든 데이터셋에 대해 항상 열등한가? 우월한가? 그것은 아니다 따라서 하나의 알고리즘을 쓰는 것보다 여러 알고리즘을 모두 쓰는 것이 좋은 인사이트를 얻을 수 있다 2. ensemble learning 여러 개의 분류기를 생성하고 그 예측을 결합함으로써 보다 정확한..
1. motivation 모든 network는 기본적으로 graph로 나타낼 수 있다. C가 작성만 하면 컴퓨터가 이해하는 것이 아니고 compile 과정을 거쳐서 기계어로 최종 번역되어야 이해할 수 있다. network도 마찬가지로 그냥 GPU에서 돌아가는 것이 아니라 graph lowering 과정을 거쳐야 hardware에서 이해할 수 있다. 이러한 역할을 해주는 것이 deep learning compiler 지금까지 software측면에서 network만 주로 공부했지만 실제로 network가 CPU,GPU 같은 hardware 환경에서 돌아가기까지 생각보다 많은 일이 있다. high level단의 pytorch 같은 것으로 만든 모델은 edge device인 edge TPU나 Jetson ..
두 직사각형의 왼쪽 하단 좌표, 오른쪽 상단 좌표 (x1,y1), (x2,y2), (x3,y3), (x4,y4)가 각각 주어질때, 이 두 직사각형이 서로 겹쳐서 생기는 영역의 좌표를 구해본다면? E의 좌표가 (x5,y5), F의 좌표가 (x6,y6)라고 한다면... 놀랍게도 이를 구하는 공식이 있다 x5 = max(x1,x3)y5 = max(y1,y3) x6 = min(x2,x4)y6 = min(y2,y4) 만약 x5 > x6이거나 y5 > y6이면 두 직사각형이 겹치지 않는다 근데 몇개 해보니까 진짜 맞는듯? 왼쪽 하단은 max, 오른쪽 상단은 min 조건 하나하나 생각해서 할려고 하면 거의 무조건 틀리더라 그냥 공식 써버리는게 제일 편함 #직사각형1 (x1,y1), (x2,y2)#직사각형2..
1. Bernoulli distribution coin flip, head and tail 확률변수 값이 0 또는 1로 나타나는 분포 X ~ Ber(p)라고 표시 베르누이 분포는 p라는 모수 하나만 있으면 표현이 가능하다. P(X=1) = p라 하면 자동적으로 P(X=0) = 1-p이 결정되니까 2. Categorical distribution m-sided dice Bernoulli distribution의 확장판 확률변수 값이 1,2,3,...,m중 하나를 가질 수 있는 분포 Y~ Cat(p1,p2,...,pm)으로 표시 이 분포를 표현하기 위해 필요한 parameter의 수는 m-1개이다. 왜냐하면 각 카테고리별로 확률을 부여하면 이렇게 쓸 수 있어 필요한 모수의 수가 m개같이 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
