일기/수업 필기 노트 (11) 썸네일형 리스트형 NP hard 문제에 대한 접근법 대부분의 discrete optimization problem 은 NP-hard 이다. 만일 P!=NP 일 경우에 우리는 NP-hard 문제를 (1) 다항 시간 내에 (2) 모든 인스턴스(예제 문제)에 대해서 (3) 최적값을 구할 수 있는 알고리즘을 찾아낼 수 없을 것이다. 그래서 연구자들이 택하는 접근법은 종종 세가지 조건중 하나를 완화하여 접근한다. 첫째로 다항 시간 조건을 완화한다면 어떻게 최적해를 더 효율적으로 탐색해나갈지 고민하는것에 집중해볼 수 있다. 하지만 이 경우 어떤 인스에 대해 수 분에서 수십 시간 안에 최적해를 구해내는데 성공했다 할지라도 바로 다음 예제의 최적해를 합리적 시간안에 구해낼 것이라 장점할 수 없는 것이 가장 큰 문제이다. 두번째로 모든 instance 에 대해 일반적으로.. Palm Khintchine Theorem - 포아송 분포 시간대별 공공자전거 대여소의 대여/반납 이용 수요를 포아송 분포로 가정할 수 있는 이유 아래와 같은 reasoning 을 따라가보자. Palm Khintchine Theorem 의 핵심 아이디어를 따른다. n 명의 사람들이 각기 독립적으로 행동하는 상황을 생각해보자. 시간을 한 유닛 단위 (델타) 로 나눴다고 생각해보자 -이를 보통 영어로는 time slot이라 표현한다-. 어떤 이벤트의 발생 확률은 람다 라고 가정해보자. 각 사람이 한 time slot 안에 특정 이벤트를 발생시킬 확률은 다음과 같이 표현한다. $$p_n = \lambda \delta/n$$ 이제 한 time slot안에 어떤 이벤트의 총 발생 횟수는 이항 확률 분포를 따른다고 할 수 있다. $$Bionomial(n, p_n)$$ n이.. 공공자전거 최적화 문제로 포뮬레이션하기 보통 공공자전거 문제를 최적화 문제로 풀면 목적 함수가 maximize customer satisfaction/revenue 혹은 minimize outages (자전거를 대여하고자 할때 재고 없는 상황/반납하고자 할때 반납가능한 거치대 (dock/rack) 이 없는 상황) 될 것이라고 쉽게 생각할 수 있다. 한가지 중요한것은 사람들이 대여/반납할 때 실패하는 상황은 데이터에 드러나지 않는다는 것이다. 이 현상을 censoring 이라 한다. 최적화 문제에서의 결정 변수(decision variables)를 다음과 같이 설정할 수 있다. Station locations: (every year)Station capacity: (every 6 months)Number of bikes at each stati.. Unconstrained optimization, Gradient Descent [읽기 전에.. ] 1. 용어정리 minimum, minimizer : 최소값, 최소점 2. 선수학습 Taylor series expansion 관련 내용이 종종 나오므로 간단한 개념을 알아야 잘 이해할 수 있다. 3. 관련 포스팅 예전 글에서 gradient descent 에 대해 정리한 적 있다. 그때 글은 gradient descent 를 한번에 이해할 수 있도록 돕기 위해 우리가 한번쯤 접해봤을 법 한 _선형회귀 함수를 fitting 하는 과정_을 gradient descent 를 이용해서 어떻게 하는지를 단적인 예시로 보여주었다면, 이번 글은 조금 더 큰 맥락에서의 설명이 될 것이다. youngseokim.tistory.com/81?category=911369 Stochastic Gradient.. 이전 1 2 3 다음
