131023 summary chapter 5
cholonge edited this page Oct 30, 2013
·
5 revisions
- singleheart: 무난하게 따라가면서 읽으면 될거 같아요. 시각화는 좀 뜬금 없지 않았나.. 해도 최적화는 하니까요.
- cholonge: singleheart형이 정리를 너무 잘하셨다는 느낌을 받았습니다. 책 내용은 역시 좀 난잡하지만 그래도 이게 딴데보다는 겉을 잘 핥고 있는거 같아요.
- dgoon: singleheart형을 믿으며 믿음의 공부를 하겠습니다.
- jsryu: 재밌었고요, 학생 기숙사 최적화 문제만 좀 이해가 안되었던거 같아요.
- bbasy: 저도 역시 믿음의 시간을..
- shurain: 평이했던거 같아요. 다른 부분은 제가 독학을 했던 부분들이니까 다 안다고 못하는데 이 부분은 좀 더 잘 알아서(전공이니까) 어떤 이야기를 했는지 안했는지 더 잘 보였어요.
- wookayin: SA, GA를 다루긴 하지만, 현실은 녹록치 않다는 느낌이 있어요. 수많은 구현 이슈와 디테일이 책에 없어서 다행인거 같습니다.
- stania: 책에 생략된 디테일들이 교류되는 시간이면 좋을거 같습니다.
-
간단히는 선형 결합. 엔지니어링 문제.
-
cost function 이 deterministic 하지 않아도 됨. 내재적으로 깔린 분포에서 나온다면 OK
-
function evaluation 이 빠를 수록 좋음.
-
나온 결과값이 total order 를 이루고 있어야 한다.
-
문제공간: cost function 의 공간이 어떻게 생겼나
-
Mathematical optimization
-
무엇을 최적화 할 것인가 - cost function, 문제의 표현, 탐색 방법
- 랜덤 서치가 비교 대상으로 쓰이고 있음.
- 단, 세상의 모든 문제를 다 놓고 봤을 때 이 방법이 가장 나쁜 방법인 것은 아니다.
- 이후에 기술할 방법들은 보통 어떠한 가정을 안고 들어가기 때문에, 어떤 문제는 빨리 풀겠지만, 어떤 문제는 랜덤보다 나쁜 결과를 낼 수도 있음.
- 정리하면 모든 최적화 방법은 우열을 가릴 수 없다는 것이 수학적으로 증명되어 있다고 함.
-
어딘가에 던져놓고, 낮은 방향으로 멈출때까지 내려가기. (보통은 '좋은' 걸 찾으러 가기 때문에 climbing 입니다)
-
일종의 Local search 기법. 굉장히 연구 많이 되는 주제. '주변' 을 결정하는 것 또한 어려운 문제이다.
-
주변을 결정하는 방법에 따라 탐색 순서등이 영향을 받게 됨.
-
책에서는 '바로 앞/뒤 비행편' 을 '주변' 으로 설정
-
한계점: 로컬 미니멈만을 찾을 수 있다는 한계가 있습니다.
-
discrete 하면 한 번에 한 칸씩, continuous 하고 이쁘면 미분이 짱
로컬 옵티멈에 빠져들어가 헤어나오지 못하는 상황을 극복하기 위한 방법
- 일정 확률로 더 나븐 해를 채택하는 것을 허용한다. 나쁜 해를 채택할 확률을 온도에 따라 점점 줄인다.
- 점프를 할 때 더 안 좋은 로컬 옵티마가 있는 곳으로 갈 확률이 있음.
- SA 루프를 끝내는 방법: 시간에 따라 온도값을 줄여나감.
- adaptive SA: 알고리즘이 상황에 따라 T 를 다시 높이기도 함.
- global optima 로 간다는 보장은 없음.
- cholonge 발표자료 https://dl.dropboxusercontent.com/u/97911179/%EC%84%B8%EB%AF%B8%EB%82%98%EC%9E%90%EB%A3%8C/ML/%EC%B5%9C%EC%A0%81%ED%99%94.pptx
- selection : 해집단에서 어떠한 해(최소 2개)가 crossover/duplicate 될지 선택한다.
- crossover : 두 해의 부분적 특성을 결합하여 새로운 해를 만든다.
- mutation : 만들어진 해의 일부분을 변이시켜 두 부모해의 특성과 관계없는 돌연변이 해를 만든다.
- replacement : 만들어진 해를 원래의 해와 대치한다. 대치하는 방법에 따라 수렴 속도에 큰 차이가 나게 된다.
- 장점: easy to implement, 안정적으로 나쁘지 않은 결과가 나옴
- 단점: 느림. 파라메터에 영향을 많이 받음
- mutation 이 SA 에서 나쁜 해를 선택하는 정도의 역할을 해줌.(순수 GA에서, 새로운 문제 공간의 탐색은 전적으로 mutation에 의존하게 된다)
- Hybrid GA: GA + Local: 다른 해로 점프한 뒤에 그 해 부근의 local optimum 을 찾으러 가야
- 쓰기 좋은 경우: 조합 최적화와 같이 공간이 매우 크면서, 해의 일부가 좋은 특성을 가질 수 있고, 그 특성을 넘겨주는 것이 가능한 경우
- exploitation 과 exploration 을 조화롭게 행하고 싶으면 복잡한 방법이 된다. 해집합의 다양성을 유지하기 위한 스킬들이 따로 있음.
- cost function evaluation 이 오래 걸리는 경우엔 GA가 더 나을거임. cost를 estimation 하는 꼼수등이 있음.
- singleheart: 새로운 내용이 없었어요 (...) 다음시간을 기대해봅니다.
- cholonge: 준비한다고 했는데 도움이 되셨는지 모르겠네요.
- kindone: 점점 재밌어지고 있는거 같아요
- dgoon: 책을 아슬아슬하게 읽은 분량이 적당해서 다행이네요. 박사님 감사합니다. 재밌었어요.
- xenosoz: 개인적으로 shurain가 지난번보다 좀 더 조용히 있을 수 있었던거 같네요
- zooty38: 전문가분들 짱..
- jsryu: 저도 어려운 이야기 할 수 있으면 좋겠어요
- bbasy: 공부는 지난번보다 더 못했지만 cholonge형 설명을 들으니 궁금한것들이 많이 생기고 공부하고 싶네요
- ipkn: 신기한 거에 폭 빠져서 노느라 늦었어요
- shurain: 오늘 평소보다 말을 훨씬 덜 했는데, 아 내가 GA 공부 하나도 안했지만 많이 알겠다는 걸 느꼈어요. 평소와 달리 아는 이야기를 다 했다는 느낌이 안들어요.
- wookayin: 이번 챕터 적당히 쉬우면서도 어려우면서도 재밌었고, 많은 전문가들의 이야기들을 들을 수 있어서 재밌었습니다.
- stania: 어.. GA 궁금증 속에 살고있었는데 어느정도 해결이 된것 같고 실무까지 활용은 못하더라도 그림이 머리속에 들어온것만으로도 의미있었다고 생각합니다
다음 시간은 naive bayes 입니다.