네트워크 플로우 관련 알고리즘 중 가장 기초적인 Max-Flow 중, Ford-Fulkerson알고리즘에 대해 알아보도록 하겠습니다.
이 알고리즘은 Max-Flow 뿐만 아니라 네트워프 플로우 관련 알고리즘 중 가장 먼저 고안된 알고리즘입니다.
동작 원리는 매우 간단합니다. 유량 네트워크에 있는 모든 간선의 유량을 0으로 초기화 시킨 뒤, 소스에서 source에서 sink로 유량을 더 보낼 수 있는 경로를 찾아 흘리는 동작만 반복하면 됩니다.
이전까지 다룬 그래프 알고리즘에서는 간선에 거리, 가중치 등을 나타내는 cost라는 값이 있었습니다. 네트워크 플로우에는 capacity라는 개념이 추가됩니다.
네트워크 플로우는 네트워크 유량이라고 부르기도 합니다. 핵심이 되는 아이디어는 (u, v)를 연결하는 간선이 있을 때, u에서 v로 용량 이하의 유량을 보낼 수 있다는 것입니다.
네트워크 플로우 관련 알고리즘은 위에서 말한 핵심 아이디어를 기반으로 해서, 시작점(source)에서 도착점(sink)까지 시작점에서 유량을 흘려보내 도착점까지 보내는 것이 목표입니다. 최대한 많이 흘려보내 Max-Flow, 최소한의 비용을 들여서 최대한 많이 흘려보내는 Min-Cost Max-Flow 등 여러 알고리즘이 있고, 몇 개의 글을 통해 하나씩 소개하려고 합니다.
이번 글에서는 입력 데이터를 학습한 뒤, 데이터를 두 가지로 분류하는 방법을 다룹니다.
이 글에서 사용할 예제는 다음과 같습니다.
| 보고서 제출 여부(x1) | 쪽지 시험 점수(x2) | 출석 수(x3) | 합격 여부(y) |
|---|---|---|---|
| 1 | 2 | 1 | 0 |
| 0 | 3 | 2 | 0 |
| 1 | 3 | 3 | 0 |
| 1 | 5 | 5 | 1 |
| 1 | 7 | 5 | 1 |
| 1 | 2 | 5 | 1 |
Linear Regression에서는 가설 함수를 y = w1x1 + w2x2 + w3x3 형태로 작성을 하였습니다. 그러나 Logistic Regression에서는 결과를 0 또는 1로 만드는 것이 목표이기 때문에 가설 함수의 값을 0과 1 사이로 조정할 필요가 있습니다.
가설 함수를 다음과 같이 작성합시다.
아래줄에 있는 식은 시그모이드(sigmoid)함수라고 불리며, 입력 데이터를 0부터 1사이의 값으로 적절히 변환하여 반환해줍니다. 그래프는 아래 사진과 같습니다.
입력 값이 작아지면 0으로 수렴하고, 커지면 1로 수렴하는 함수입니다.
지금까지 해왔던 것과 달리, 이번 글에서는 행렬을 이용해 Linear Regression을 해보도록 하겠습니다.
첫 번째 글과 두 번째 글에서 다룬 데이터들은 변수와 가중치가 각각 1개씩 있었습니다. 이번 글에서는 변수와 가중치가 각각 n개씩 있는 데이터를 학습시켜봅니다.
이전 글에서는 오차에 learning rate를 곱한 값을 이용해 학습을 진행하였습니다. 이번 글에서는 미분을 이용해 학습을 시켜보도록 하겠습니다.
이 카테고리는 파이썬을 싫어하고, 라이브러리 사용보다 직접 구현하는 변태같은 필자의 특성에 맞게 머신러닝을 C++로 바닥부터 구현하는 방법을 다루는 흥미로운 글들이 올라올 것입니다.
Linear Regression, Classification 등 기초적인 것을 먼저 알아보고 신경망의 원리를 알아가며 구현한 뒤, 최종적으로 CNN 구현을 목표로 하고 있습니다.
이제 시작합니다!