-
Analysis of the Naive Bayes Classifier with Spam Filtering and MNIST datasets
Abstract Naive Bayes Classifier를 이용하여 MNIST dataset와 email dataset을 학습하고, k-fold cross validation을 이용하여 학습된 모델의 분류성능을 분석해본다. Keywords Naive Bayes Classifier, K-Fold Cross Validation, Spam Filtering, MNIST Introduction Bayes’ theorem 베이즈 정리는 사전 확률로부터 사후 확률을 계산하는 조건부 확률에 대한 정리이다. 사건 A와 B가 있고, 사건 A가 일어났을 때 사건 B가 일어날 조건부 확률과 A가 일어날 확률, B가 일어날 확률만을 계산할 수 있을 때, 사건 B가 일어났을 때 사건 A가 일어날 조건부 확률은 다음과...
-
알고리즘 문제 접근 과정 8
알고리즘 문제 접근 과정 8 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. 버스 노선 - KOI 2014 고등부 2번 풀이 이 문제를 해결하는데 큰 어려움이 되는 부분은 구간이 원형으로 되어있다는 점일 것입니다. 그렇다면 일단, 문제가 원형으로 생겨있지 않고 0번을 기준으로 일직선으로 생긴 형태라면 어떻게 해결할...
-
Recents Large Attacks on Decentralized Applications
서론 이 글에서는 rekt.news에 등재된 블록체인 해킹 사건 중 가장 규모가 큰 10개를 아주 간략하게 돌아봅니다. 각각의 기초적인 원리를 살펴보고, 이 10가지의 사건을 통해서 제가 블록체인 보안에 대해서 느낀 점을 정리했습니다. Lineup https://rekt.news/leaderboard/ 에 있습니다. 여기에도 옮기면, Poly Network : $611M Wormhole : $326M BitMart : $196M Compound : $147M Vulcan Forged : $140M Cream Finance : $130M Badger : $120M Qubit Finance : $80M Ascendex : $77M EasyFi : $59M 합치면 대략 2조 3천억...
-
Intel Intrinsics(SIMD) 가이드
1. Introduction 우리가 주로 사용하는 Intel(AMD) 아키텍쳐에서는 SIMD(Single Instruction Multiple Data)를 이용할 수 있습니다. SIMD는 말 뜻 그대로 하나의 명령을 통해 여러 값의 연산을 동시에 처리하는 명령어 셋으로, 단순 덧셈/비교/뺄셈과 같은 작업을 병렬화해서 실행 시간을 줄일 수 있습니다. 영상 처리, 머신러닝 분야에서 SIMD는 빼놓을 수 없는 존재이고, 암호 모듈 구현에서도 SIMD를 통해 성능을 극한으로 끌어올려 벤치마크를 확인합니다. 저는 처음 SIMD를 건드려본게 암호 모듈 구현체를 수정해야 할 일이 있어서였습니다. 아무래도 처음 쓰는거라 낯설다보니 이런저런 자료를 찾아가며...
-
Push Relabel Algorithm (1)
그래프의 최대 유량 (Maximum Flow) 를 찾는 문제는 웬만한 알고리즘 대회 입문서에는 다 소개되어 있는 중요한 문제이다. 일반적으로 최대 유량을 찾기 위해서는 Edmonds-Karp, Dinic과 같은 알고리즘을 사용한다. 이 알고리즘의 특징은 빈 그래프에서 시작해서 유량을 증가시키는 “증가 경로” 를 찾는 것을 반복하는 식으로 작동한다는 것이다. Dinic 알고리즘은 최악의 경우 $O(V^2E)$ 에 작동하지만 실제로는 이보다 훨씬 효율적으로 작동한다. 하지만 그럼에도 선형 시간에 가까울 정도로 빠르지는 않고, 한계가 분명히 있는 알고리즘이다. 이 글에서는 Push-relabel 이라고 하는 새로운 플로우...