최적화(Optimization) with Scipy, 확률(Probability) with Pgmpy

1. 변분법

1.1 범함수

• 함수를 입력받아 실수를 출력하는 것

1.2 변분법

• 입력인 함수가 변할때 범함수의 출력이 어떻게 달라지는지 계산하는 학문

2. 최적화 기초

2.1 최적화 문제

• 함수 f의 값을 최대화 혹은 최소화 하는 변수 x값 x*를 찾는 것
• 해 : x*의 최적화 문제
• 목적함수 : 최소화하려는 함수 f(x) (비용함수, 손실함수, 오차함수)

2.2 그리드 서치와 수치적 최적화

• 그리드 서치 : 가능한 x의 값을 여러개 넣어보고 그중 가장 작은 값을 선택하는 방법으로 함수 위치가 최적점이 될 때까지 가능한 한 적은 횟수만큼 x위치를 옮기는 방법
• 단점 : 모든 트레이닝 데이터 집합에 대해 예측값과 타깃값의 차이를 구해야 함으로 계산량이 큼

2.3 수치적 최적화

• 반복적 시행 착오에 의해 최적화 필요조건을 만족하는 값 x*를 찾는 방법
• 현재위치 가 최저점인지 판단하는 알고리즘
• 어떤위치 를 시도한뒤, 다음 번에 시도할 위치 을 찾는 알고리즘

2.4 기울기 필요조건

• 독립변수값 x*가 최소점이라면 함수의 기울기와 도함수 값이 0이어야함
• 단일 변수에 대한 함수인 경우 미분값이 0이어야 한다
• 다변수함수인 경우 모든 변수에 대한 편미분값이 0이어야한다
• 

2.5 최대 경사법

• 현재 위치 에서의 기울기만을 이용하여 다음 위치 를 결정하는 방법
• 
• 스텝사이즈 : 위치를 옮기는 거리를 결정하는 비례상수
• 최대 경사법에는 스텝사이즈를 적절히 조정하는 것이 중요함
• 진동현상 : 그레디언트벡터가 최저점을 가르키지 않고 있을때 발생하는 현상
  • 헤시안 행렬과 모멘텀 방법을 사용하여 삭제

2.6 2차 도함수를 사용한 뉴턴방법

• 목적 함수가 2차 함수라는 가정하에 한 번에 최저점을 찾으며, 그레디언트 벡터에 헤시안 행렬을 곱해서 방향과 거리가 변형된 그레디언트 벡터를 사용
• 
• 장점 : 스텝사이즈가 필요없으며 목적함수가 실제로 2차 함수와 비슷한 모양이면 빠르게 수렴이 가능함
• 단점 : 1차 도함수(그레디언트벡터)뿐 아니라 2차 도함수(헤시안행렬)도 필요함

2.7 사이파이를 이용한 최적화

1
2
3
4
5
6
7

# 목적함수 재정의
def f1(x):
    return (x - 2) ** 2 + 2

x0 = 0  # 초깃값
result = sp.optimize.minimize(f1, x0)
print(result)

1
2
3
4
5
6
7
8
9
10

fun: 2.0
hess_inv: array([[0.5]])
jac: array([0.])
message: 'Optimization terminated successfully.'
nfev: 9
nit: 2
njev: 3
status: 0
success: True
x: array([1.99999999])

• scipy의 optimize 서브패키지 minimize()를 사용
• result = minimize(func, x0, jac = jac)
  • func : 목적 함수
  • x0 : 초깃값 벡터
  • jac : (옵션) 그레디언트 벡터를 출력하는 함수
    • 계산량을 줄이려면 직접 그레디언트 벡터값을 반환하는 함수를 만듬
• minimize 명령의 결과
  • x : 최적화 해
  • success : 최적화에 성공하면 True 반환
  • status : 종료상태, 최적화에 성공하면 0
  • message : 메세지 문자열
  • fun : x 위치에서 함수의 값
  • jac : x 위치에서 자코비안(그레디언트) 벡터의 값
  • hess_inv : x 위치에서 헤시안 행렬의 역행렬 값
  • nfev : 목적함수 호출 횟수
  • njev : 자코비안 계산 횟수
  • nhev : 헤시안 계산 횟수
  • nit : 이동 횟수

2.8 전역 최적화 문제

• 최적화 하려는 함수가 복수의 국소 최저점을 가지고 있는 경우에는 수치적 최적화 방법으로 전역 최저점에 도달한다는 보장이 없음

2.9 컨벤스 문제

• 목적함수의 2차 도함수의 값이 항상 0 이상이되는 영역에서만 정의된 최적화 문제

3. 제한조건이 있는 최적화 문제

3.1 등식 제한조건이 있는 최적화 문제

• 여러 제한조건이 있는 최적화 문제중 연립방정식 제한조건이 있는 경우

3.2 라그랑주 승수법

• 원래의 목적함수 f(x)대신에 제한조건 등식에 라는 새로운 변수를 곱해서 더한 함수를 목적함수로 간주하여 최적화

3.3 사이파이(Scipy)를 사용하여 등식 제한조건이 있는 최적화 문제 계산하기

1
2
3
4
5
6
7

def f1array(x):
    return x[0] ** 2 + x[1] ** 2

def eq_constraint(x):
    return x[0] + x[1] - 1

sp.optimize.fmin_slsqp(f1array, np.array([1, 1]), eqcons=[eq_constraint])

1

array([0.5, 0.5])

• scipy의 optimize 서브패키지의 fmin_slsqp()명령어로 계산
• 항상 eqcons 인수를 명시 해야함

3.4 라그랑주 승수의 의미

• 만일 최적화 문제에서 등식 제한 조건 이 있는 가없는가에 따라 해의 값이 달라진다면 이 등식 제한조건에 대응하는 라그랑주 승수는 0이 아닌 값이어야 한다.

3.5 부등식 제한조건이 있는 최적화 문제

• 
• KKT (karush-kuhn-tucker) 조건 : 최적화 해의 필요조건
  • 모든 독립변수에 대한 미분값이 0이다
  • 모든 라그랑주 승수와 제한조건 부등식의 곲이 0이다
  • 라그랑주 승수는 음수가 아니여야 한다.

3.6 Scipy를 사용하여 부등식 제한조건이 있는 최적화 문제 계산하기

1
2
3
4
5
6
7
8
9

def f2(x):
    return np.sqrt((x[0] - 4) ** 2 + (x[1] - 2) ** 2)

# 제한 조건 상수
k = 1
def ieq_constraint(x):
    return np.atleast_1d(k - np.sum(np.abs(x)))
    
sp.optimize.fmin_slsqp(f2, np.array([0, 0]), ieqcons=[ieq_constraint])

1
2
3
4
5
6

Optimization terminated successfully.    (Exit mode 0)
            Current function value: 3.6055512804550336
            Iterations: 11
            Function evaluations: 77
            Gradient evaluations: 11
array([9.99999982e-01, 1.79954011e-08])

• fmin_slsqp() 명령은 등식 제한조건과 부등식 제한조건을 동시에 사용할 수 있다.
• fmin_slsqp()를 사용하며 ieqcons 인수조건을 넣어준다

4 선형계획법 문제와 이차계획법 문제

4.1 선형계획법 문제

• 방정식이나 부등식 제한 조건을 가지는 선형모형의 값을 최소화 하는 문제
• 목적함수는 이다

4.2 Scipy를 이용한 선형계획법 문제 계산

1
2
3
4
5
6
7
8

import scipy.optimize

A = np.array([[-1, 0], [0, -1], [1, 2], [4, 5]])
b = np.array([-100, -100, 500, 9800])
c = np.array([-3, -5])

result = sp.optimize.linprog(c, A, b)
result

1
2
3
4
5
6
7
8
9
10

con: array([], dtype=float64)
fun: -1400.0
message: 'Optimization terminated successfully.'
nit: 3
slack: array([ 200.,    0.,    0., 8100.])
status: 0
success: True
x: array([300., 100.])

# 제품 A를 300개, 제품 B를 100개 생산할 때 이익이 1400으로 최대가 됨을 알 수 있다.

• scipy의 optimize 패키지의 linprog() 명령을 사용
  • linprog(c, A, b)
  • c : 목적 함수의 계수 벡터
  • A : 등식 제한조건의 계수 행렬
  • b : 등식 제한조건의 상수 벡터

4.3 CVXPY를 이용한 선형계획법 문제 계산

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

import cvxpy as cp
conda install cvxpy

# 변수의 정의
a = cp.Variable()  # A의 생산량
b = cp.Variable()  # B의 생산량

# 조건의 정의
constraints = [
    a >= 100,  # A를 100개 이상 생산해야 한다.
    b >= 100,  # B를 100개 이상 생산해야 한다. 
    a + 2 * b <= 500, # 500시간 내에 생산해야 한다.
    4 * a + 5 * b <= 9800,  # 부품이 9800개 밖에 없다.
]

# 문제의 정의
obj = cp.Maximize(3 * a + 5 * b)
prob = cp.Problem(obj, constraints)

# 계산
prob.solve() 

# 결과
print("상태:", prob.status)
print("최적값:", a.value, b.value)

1
2

상태: optimal
최적값: 299.99999999999983 100.00000000000001  

• linprog와 달리 계수행렬 a b c를 직접 정의하지 않고, 심볼로 정의하여 사용
• 다만 변수나 조건의 수가 많다면 속도가 느림

4.4 이차계획법 문제

• 방정식이나 부등식 제한 조건을 가지는 일반화된 이차형식의 값을 최소화하는 문제
• 목적 함수는 이다

4.5 CVXOTP를 이용한 이차계획법 문제 계산

1
2
3
4
5
6
7
8
9
10

conda install cvxopt
from cvxopt import matrix, solvers

Q = matrix(np.diag([2.0, 2.0]))
c = matrix(np.array([0.0, 0.0]))
A = matrix(np.array([[1.0, 1.0]]))
b = matrix(np.array([[1.0]]))

sol = solvers.qp(Q, c, A=A, b=b)
np.array(sol['x'])

1
2

array([[0.5],
       [0.5]])

• CVXOPT를 이용허여 이차계획법 문제를 풀수 있다.
• ndarray 배열을 matrix 자료형으로 바꿔야하여, 정수대신 실수를 사용하여야한다

5. 집합(Set)

5.1 집합과 원소

• 집합(set) : 구별 가능한 객체의 모임
• 원소(element) : 집합에 포함된 구별 가능한 객체
• set : 내용을 변경할 수 있는 뮤터블 자료형
• frozenset : 내용을 변경할 수 없는 임뮤터블 자료형

5.2합집합과 교집합

• 합집합 : 각 집합의 원소를 모두 포함하는 집합
• 교집합 : 두 집합 모두에 속하는 원소로만 이루어진 집합

• uninon : 합집합을 만드는 파이썬 메서드 (

  )

• intersection : 교집합을 만드는 파이썬 메서드(&)

5.3 전체집합, 부분집합, 진부분집합

• 부분집합 : 어떤 집합의 원소 중 일부만을 포함하는 집합
• 전체집합 : 원래의 집합
• 진부분집합 : 원소의 크기가 더 작은 부분집합

5.4 차집합과 여집합

• 차집합 : 어떤 집합 A에 속하면서 다른 집합 B에는 속하지 않는 원소로 이루어진 A의 부분집합을 A에서 B를 뺀 차집합이라 함
• 여집합 : 전체 집합중에서 부분집합에 속하지 않은 원소로만 이루어진 부분집합

5.5 공집합

• 아무 원소도 포함하지 않는 집합
• 모든 집합의 부분집합이 됨

5.6 부분집합의 수

• N개의 원소를 가진 집합의 부분집합의 수는 개

5.7 합집합과 교집합의 분배 법칙

• 곱셈과 덧셈의 분배 법칙처럼 교집합과 합집합도 괄호를 풀어내는 분배법칙이 성립함