1. idea 군집을 찾는 대표적인 하향식 알고리즘으로 전체 그래프에서 시작하여 군집들이 서로 분리되도록 link를 순차적으로 제거함 서로 다른 군집을 연결하는 다리 역할을 하는 link를 먼저 제거해나가야 군집들이 분리 될 것이다. 2. betweenness centrality 그래프의 임의의 두 node의 최단 경로 위에 특정 link가 몇번이나 놓이는지 계산 link A-B는 양 옆 4개의 node중 하나를 선택하여 만든 최단 경로에 모두 존재해야하므로 4*4=16가지가 있다. 따라서 그림을 보면 직관적으로 betweenness centrality가 높은 link는 두 군집을 연결하는 다리 역할을 할 가능성이 높다. 3. algorithm 주어진 그래프에서 모든 link의 매개 중심성을..
1. 1보다 큰 10진수를 다른 진수로 변환하는 방법 주어진 수를 변환하고자하는 진수의 base로 계속 나누고 나머지를 써둔다 마지막에 저장해둔 나머지 뒤에서부터 가지고옴 예를 들어 133은 3진법으로 변환하면 $11221_{(3)}$이다. 2. 10진수 소수를 진수 바꾸는 방법 반면 소수는 방법이 조금 다른데 base를 계속 곱해나간 뒤 소수점을 넘은 정수는 옆에 따로 저장해두고 정수를 뺀 나머지를 다음 단계로 보낸 뒤 base를 계속 곱해 다음 단계로 보낸 나머지 부분이 0이 될때까지 반복함 정수 변환은 맨 뒤에서부터 앞으로 가지고 왔지만 맨 처음부터 따로 저장한 수를 맨 뒤까지 가지고 오면 끝 예를 들어 0.375는 8진수로 변환하면 $0.3_{(8)}$이고 0.1을 2진수로 변환하면 $0.00..
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 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
