일기/수업 필기 노트 (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.. Simplex method 에서 basis 를 나간 basic variable은 바로 다음 pivot 에 들어올 수 있을까? Q1. Simplex method 에서 특정 pivot 에서 basis 를 나간 어떤 basic variable x_j는 그 바로 다음 pivot 에서 들어올 수 있을까? 없다. 기하학적으로 생각해보자. 특정 pivot 과 그 다음 pivot 의 basis 는 adjacent basic feasible solution 이다. 즉, 하나만 빼고 모두 같은 basic variable 을 공유한다. extreme points 들이 다면체의 꼭지점들이라고 본다면 한 꼭지점에서 (BFS) iteration 이 끝나면 다른 인접한 꼭지점으로 edge를 따라 이동해서 다른 꼭지점 (adjacent BFS)에 도달하는 셈이다. 이러한 관점에서 봤을때 특정 basis 를 나간 어떤 basic variable x가 바로 .. 튜링머신에 대한 완벽한 이해 (1편) 요약과거에는 어떤것이 "computable" 한지 혹은 아닌지에 대한 수학적인 정의가 없었다. 엘런튜링 이 개발한 Turing machine 은 어떤것이 연산가능한지/아닌지를 판단할 수 있는 수학적 정의를 제공해주어 computability(계산 가능함) 에 대한 거대 담론의 시발점이 되었고, 또한 이는 현대의 컴퓨터의 전신이 되었다. Motivation"튜링 머신이 등장하게 된 배경은 무엇일까?"20세기 초반, 독일의 수학자 힐버르트는 정의와 공리를 입력하면 모든 수학적 명제를 도출해 줄 수 있는 만능 기계를 만들자는 제안을 한다. 쉽게 말해 우리가 알고있는 수학적 명제와 정의들을 때려 넣으면 자동으로 증명을 해주는 컴퓨터를, 즉 수학자를 대체할 인공지능을 개발하자는 것이다. 앨런 튜링은 힐버르트 프로.. decision problem 과 optimization problem 의 관계 (feat. np) optimization problem 에 대해 배우는 최적화 수업과 decision problem 의 다양한 구분들 (p, np)에 대해 배우는 알고리즘 수업을 동시에 듣다가 optimization 문제를 decision problem 으로 바꿀 수 있다는 사실을 알게되었다. 예를들어 traveling salesperson problem (TSP) 문제를 최적화 문제로 말한다면 우리는 모든 도시를 방문하는 최소 경로를 구하고 싶다고 할 수 있다. 이걸 decision problem 으로 바꾸면 어떨까? 참고로 decision problem 은 YES/NO로 답을 내릴 수 있는 문제를 의미한다. 모든 도시를 방문하면서 최대 k거리를 갖는 경로가 있을까? 로 바꿀 수 있다. 만약 decision proble.. Duality 변환 공식 암기하지말고 이해하기 Duality 변환 공식 선형계획법에서 Duality 에 대해 배우다보면 아래와 같은 dual 변환 공식을 종종 접한다. 다음과 같이 규칙 기반으로 표를 외우는 방법도 있다. 한쪽 문제의 equality constraints는 다른쪽 문제의 free variables 과 대응된다. minimize 문제의 constrainst 와 그의 dual 인 maximize 문제의 variables 의 부호는 같다. minimize 문제의 variables 과 그의 dual 인 maximize 문제의 contraints 부호는 다르다. 하지만 왜 꼭 이렇게 되어야만 하는것인지 규칙에 숨겨진 원리를 당위적으로 이해하고 싶은 사람이라면 아래 예제를 살펴보자. 다음 LP 예제를 살펴보자 minx1+3x2\min x_1+.. 이전 1 2 다음
