전체 글
-
(라이님 블로그 대회 알고리즘 따라잡기 28) 디닉 알고리즘(Dinic's Algorithm)PROGRAMMING/알고리즘 2024. 7. 23. 09:49
https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220812858041&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList\ 디닉 알고리즘(Dinic's Algorithm) (수정: 2016-09-19)안녕하세요. 예고한 대로 더 빠른 시간복잡도의 최대 유량 알고리즘을 소개하러 왔습니다. 그런데, 본래는 ...blog.naver.com 시간복잡도 O(V^2E) 알고리즘인 이 알고리즘은 에드몬드 카프 알고리즘이 O(VE^2)이였던 알고리즘에 비해 빠른 알고리즘이다! 설명은 라이님 블로그를 참고할 것! 코드는 크게 BFS를 이용해 레벨 그래프를 구축하는 과정과..
-
WGAN-GP 리뷰(Wasserstein GAN with gradient penalty)논문 리뷰/Generative Model 2024. 7. 22. 19:14
2017년 NeuIPS에 게재된 WGAN-GP 논문을 리뷰하고자 한다. 이 논문은 WGAN의 발전된 버전으로 WGAN과 주저자가 동일해 WGAN에 대한 설명은 많이 생략했다. 따라서 이 논문을 읽기 전에 WGAN에 대한 이해가 필요하다. (틈새 홍보) WGAN 논문 리뷰 ↓ ↓ ↓ ↓ ↓ https://jjo-mathstory.tistory.com/entry/WGAN-%EB%A6%AC%EB%B7%B0Wasserstein-GAN WGAN 리뷰(Wasserstein GAN)오늘은 WGAN 논문을 읽어보았다. 여러가지 수학적 개념들이 등장해서 개인적으로 좀 반가운 논문이였다ㅎㅎ 수학적 배경이 탄탄한 논문이라서 WGAN이 학습이 잘 되는 이유에 대한 증명이 많이 담jjo-mathstory.tistory.com ..
-
(라이님 블로그 대회 알고리즘 따라잡기 27) 최소 비용 최대 유량(Minimum Cost Maximum Flow)카테고리 없음 2024. 7. 22. 11:07
MCMF를 푸는 알고리즘을 배웠다.https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220810623254&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 최소 비용 최대 유량(Minimum Cost Maximum Flow) (수정: 2019-08-14)개강하고서 너무 피곤하네요. 하지만 제가 정말정말 쓰고 싶던 글이니까 빨리 씁시다. 이번에 다룰 내용은 ...blog.naver.com 그래프 관련된 알고리즘을 몇 개 보니 이제는 눈에 좀 익는거 같다. 이 알고리즘은 최단 경로(비용이 최소가 되는 거리)를 찾아 유량을 흘려주고, 더 이상의 최단 경로가 ..
-
(라이님 블로그 대회 알고리즘 따라잡기 26) 이분매칭(Bipartite Matching)PROGRAMMING/알고리즘 2024. 7. 22. 10:57
오늘은 네트워크 플로우의 특수한 케이스인 이분 매칭에 대해 배워보았다. 이론은 상당히 단순한데, 내용은 라이님 블로그에 자세히 설명되어 있다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220807541506&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 이분 매칭(Bipartite Matching)이번에 올릴 글은 네트워크 플로우 개념의 연장...은 아닌 것 같고, 유량 그래프의 아주 특수하면서 메이저...blog.naver.com 라이님이 알려준 코드를 살짝만 수정해서 사용하고자 한다.#include #include #include // m..
-
WGAN 리뷰(Wasserstein GAN)논문 리뷰/Generative Model 2024. 7. 19. 19:17
오늘은 WGAN 논문을 읽어보았다. 여러가지 수학적 개념들이 등장해서 개인적으로 좀 반가운 논문이였다ㅎㅎ 수학적 배경이 탄탄한 논문이라서 WGAN이 학습이 잘 되는 이유에 대한 증명이 많이 담겨있다. Introduction앞선 연구들은 real data distribution과 model distribution의 KL divergence를 최소화하는 방향으로 model distribution을 학습하고자 했다. 하지만 이러한 방법론은 상당한 문제점을 가지고 있는데, model manifold와 true distribution의 support는 잘 겹치지 않아서 이 둘 사이의 KL divergence를 계산하기 어렵다는 것이다. 이러한 문제를 극복하기 위해 simple한 distribution을 시작해 ..
-
DCGAN 논문 리뷰(Deep Convolutional Generative Adversarial Networks)논문 리뷰 2024. 7. 19. 12:47
오늘은 GAN 논문에 이어 DCGAN 논문 리뷰를 해보고자 한다. 논문의 이론보다는 테크니컬한 부분을 많이 다루고 있는 논문이라고 생각된다. GAN이 아무래도 학습하기 어려운 모델이라서 그런지 초기 세팅 등에 대한 팁을 많이 제공하고 있다.(누가 봐도 학습하느라 저자들이 엄청 고생한거 같은 논문이다..ㅋㅋㅋㅋ) 꽤나 오래된 논문이라서 과거 논문들과의 비교는 생략하고, 이 논문에서 도입한 3가지 CNN 구조에 대해 소개하겠다. 1. pooling 대신에 strided convolution을 사용하자. 2. convolutional feature의 가장 윗 부분에서 fully connected layers를 제거하자. 자세한 구조는 Fig. 1에서 제안하고 있다. DCGAN에서 제안한 구조에서는 4개의 ..
-
GAN을 어떻게 학습할 것인가(How to Train a GAN?)논문 리뷰/Generative Model 2024. 7. 18. 17:42
GitHub - soumith/ganhacks: starter from "How to Train a GAN?" at NIPS2016 GitHub - soumith/ganhacks: starter from "How to Train a GAN?" at NIPS2016starter from "How to Train a GAN?" at NIPS2016. Contribute to soumith/ganhacks development by creating an account on GitHub.github.com cs236을 듣다가 알게된 페이지인데 흥미로워서 한국어로 정리해보고자 한다.정확한 내용은 위에 페이지를 참고하면 된다! 1. Normalize the inputs : 입력값을 정규화하자-1에서 1사이의 값으로..
-
GAN 논문리뷰(Generative Adversarial Nets)논문 리뷰 2024. 7. 18. 16:22
GAN 논문에 대해 정리해볼 예정이다.이 논문은 14년도 NIPS에 Generative Adversarial Nets라는 이름으로 게재되었으며 Goodfellow, Bengio 등 개쩌는 사람들이 작성에 참여한 것을 알 수 있다. 이제는 너무나 많이 알려진 개념이라서 논문 자체가 어렵게 느껴지진 않지만 꼼꼼히 리뷰해보고자 한다. 또한 GAN 관련 강의는 cs236 9, 10장에서 자세히 다루고 있어서 한 번쯤 보는 걸 추천한다! Abstract 이 논문의 모든 것이 Abstract에 있다고 해도 과언이 아니다. 생성자 G는 data distribution을 학습하기 위해, 판별자 D는 training data와 G가 생성한 샘플을 구분하기 위해 존재하는 모델이다. 이 두 모델은 동시에 학습되며, 이상적..