-
Exploring Simulated Annealing for Derivative-free Optimization 2
Exploring Simulated Annealing for Derivative-free Optimization 2 이전 포스트 Exploring Simulated Annealing for Derivative-free Optimization 1에 이어서 기존 Simulated Annealing을 여러 방면으로 개선시킨 방법론들에 대해 이야기하겠습니다. Fast Simulated Annealing 기존의 온도 쿨링의 경우, 쿨링되는 과정이 너무 느려서 실제로 converge할 때까지 시간이 너무 오래걸린다는 단점이 있습니다. 이러한 문제를 해결하기 위해서 새롭게 제안된 방법이 바로 Fast Simulated annealing입니다. 기존의 SA의 경우, 새로운 상태를 채택할지에 대한 확률을 exponential function을 통해서 결정했습니다. 즉, exponential function을 사용하기 때문에, 새로운 상태의...
-
Deterministic Almost-Linear Time Edge Connectivity, with and without expander decomposition
Introduction 이곳에 글을 연재하기 시작할 즈음 두 개의 포스트에서 Minimum Cut 문제의 state-of-the-art라고 볼 수 있는 두 알고리즘을 소개했습니다. 하나는 적절한 random sampling을 통해 모든 min-cut을 sparse한 cut으로 근사한 Karger 2000에 대해 다루었고, 다른 하나는 almost-linear time complexity를 달성한 최초의 알고리즘인 Li 2021 에 대해 다루었습니다. 둘 다 “seminal work”이라는 표현이 아깝지 않을 만큼 좋은 논문이지만, 이 중 Li에 대해서는 Expander Decomposition에 대한 제 이해가 부족하여 논문의 outline만 짚고 넘어갔습니다. Li의 논문을 리뷰하며 스스로 느꼈던...
-
Geometric Deep Learning
Introduction 먼저, geometric deep learning에 대해 좀 더 알아보고 싶으신 분은 이 분야의 founder들이 작성한 놀라울 정도로 잘 쓰인 글이 있기 때문에 일독을 권합니다. 앞으로 이 글의 거의 대부분의 내용들은 위 자료를 따릅니다. 지난 10여년간 딥러닝은 엄청나게 빠르게 발전하며 컴퓨터 비전을 비롯하여 chatgpt에 이르기까지 다양한 산업에 수많은 변화를 가져왔습니다. 그리고 아직도 매일같이 수많은 논문이 쏟아져 나오고 있습니다. 각 논문들에서는 학습하는 데이터에 최적화된 각기 다른 neural network 구조를 사용하고 있고, 결국 우리는 성공적으로 동작하는 CNN, RNN,...
-
Introduction to Classical Shadow
Quantum state tomography 서론 양자컴퓨팅에는 다양한 양자 알고리즘이 존재한다. 하지만 양자컴퓨터의 결과를 해석하는 법은 computational basis를 기준으로 측정하는 것 뿐이다. Grover algorithm이나 Quantum Phase Estimation 알고리즘 등의 알고리즘은 결과 큐빗이 0인지 1인지 관측하는 것 만으로 충분하다. 하지만 임의의 n-qubit 양자상태는 $2^n \times 2^n$의 복소 행렬로 표현된다. 따라서 원래의 상태 행렬 자체를 알아내는 것 또한 활발하게 연구되었다. 이를 Quantum state tomography라고 한다. 하지만 n-qubit의 양자상태 $\rho$를 알아내는 것은 최소한 O($rank(\rho)2^n$)번의 측정이 필요한 것이 증명되어 있다. 10-qubit...
-
Federated Learning And Split Learning
들어가며.. 스마트폰이 나오고, 세월이 지나면서 누구나 스마트폰을 사용하는 시대가 되었습니다. 거기에, 스마트폰의 성능도 나날히 발전하면서 스마트폰에서 할 수 있는 일들도 점점 늘어났습니다. 기존에는 컴퓨터의 성능으로만 가능하던 인공지능의 학습 또한, 현재는 스마트폰으로도 가능해지는 시대가 되어가고 있습니다. 각자의 스마트폰으로 통신이 가능해지고, 인공지능의 학습이 가능해진 것은 큰 영향을 미쳤습니다. 기존에는 데이터를 전부 서버로 보낸 뒤, 서버에서 인공지능을 학습해야만 했습니다. 하지만 이제는 개인이 가진 스마트폰의 하드웨어를 이용하여 학습을 할 수 있게 되고, 언제 어디서나 통신을 할 수 있는 상황이...