비선형모델 신경망

• 신경망 모델은 기본적으로 비선형 모델이지만, 보통 선형 모델과 비선형 모델의 결합으로 이루어져 있다.

• 소프트맥스(softmax) 연산

  • 모델의 출력을 확률로 해석할 수 있게 변환해주는 연산임.

  • 분류 문제를 풀 때 선형모델과 소프트맥스 함수를 결합하여 예측한다.

  • def softmax(vec):
        denumerator = np.exp(vec = np.max(vec, axis=-1, keepdims=True))
        numerator = np.sum(denumerator, axis=-1, keepdims=True)
        val = denumerator / numerator
        return val
    

• 신경망은 선형모델과 활성함수(activation function)을 합성한 함수이다.

• Multi-layer Perceptron(MLP)은 신경망이 여러층 합성된 함수이다.

활성함수

• 활성함수는 비선형함수이다.
• 활성함수를 쓰지 않으면 딥러닝은 선형모형과 차이가 없다.
• 시그모이드 함수나 tanh 함수는 전통적으로 많이 쓰이던 활성함수지만 딥러닝에선 ReLU 함수를 많이 쓰고 있다.

층을 여러 개 쌓는 이유

• 이론적으로는 2층 신경망으로도 임의의 연속함수를 근사할 수 있다.
• 층이 깊을수록 목적함수를 근사하는데 필요한 뉴런(노드)의 숫자가 훨씬 빨리 줄어들어 좀 더 효율적으로 학습이 가능하다.
  • 층이 얇으면 필요한 뉴런의 숫자가 기하급수적으로 늘어나서 넓은(wide) 신경망이 되어야 한다.

딥러닝 학습원리: 역전파 알고리즘

• 딥러닝은 역전파(backpropagation) 알고리즘을 이용하여 각 층에 사용된 파라미터를 학습한다.
• 역전파 알고리즘은 합성함수 미분법인 ‘연쇄법칙(chain-rule)’ 기반 자동미분(auto-differentiation)을 사용한다.

미분

• 미분은 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구로 최적화에서 가장 많이 사용하는 기법이다.
• 미분은 함수 f의 주어진 점 (x, f(x))에서의 접선의 기울기를 구한다.
• 미분값을 더하면 경사상승법(gradient ascent)이라 하며, 함수의 극대값의 위치를 구할 때 사용한다.
• 미분값을 빼면 경사하강법(gradient descent)이라 하며, 함수의 극소값의 위치를 구할 때 사용한다.
• 경사상승/경사하강법은 극값에 도달하면 움직임을 멈춘다.

1
2
3
4
5
6
7
8

# gradient: 미분 계산 함수
# init: 시작점, lr: 학습률, eps: 알고리즘 종료조건

var = init
grad = gradient(var)
while(abs(grad) > eps):
	var = var - lr * grad
	grad = gradient(var)

• 미분은 변수의 움직임에 따른 함수값의 변화를 측정하기 위한 도구로서, 최적화에서 제일 많이 사용하는 기법이다.
• 벡터가 입력인 다변수 함수의 경우 편미분(partial differentiation)을 사용한다.
• 각 변수 별로 편미분을 계산한 그래디언트 벡터(gradient vector)를 이용하여 경사하강/상승법에 사용할 수 있다.
  • Nabla(역삼각형) 기호로 표기

역행렬을 이용한 선형회귀분석

• np.linalg.pinv 를 이용하면 데이터를 선형모델로 해석하는 선형회귀식을 찾을 수 있다.

• 행렬 X(n, m)에서 n >= m인 경우,

  • XB = y_hat ~= y

    -> B = X^+ * y (L2-노름을 최소화)

    -> = (X^T X)^-1 X^T * y

• 선형모델의 경우 역행렬을 이용하여 회귀분석이 가능하다.

경사하강법을 이용한 선형회귀분석

• 선형회귀의 목적식은 ||y - XB||2 이고, 이를 최소화하는 B를 찾아야 하므로 아래와 같은 그래디언트 벡터를 구해야 한다.

  • 

  • 

  • 

• # norm: L2-노름을 계산하는 함수
  # lr: 학습률, T: 학습횟수
  
  for t in range(T):
      error = y - X @ beta
      grad = - transpose(X) @ error
      beta = beta - lr * grad
  

• 이론적으로 경사하강법은 미분가능하고 볼록(convex)한 함수에 대해선 적절한 학습률과 학습횟수를 선택했을 때 수렴이 보장되어 있다. (볼록한 함수는 그래디언트 벡터가 항상 최소점을 향하기 때문)

확률적 경사하강법(SGD, Stochastic Gradient Descent)

• 확률적 경사하강법은 모든 데이터가 아닌 데이터 한 개 또는 일부(mini batch)를 활용하여 업데이트한다.
• 볼록함수가 아닌(non-convex) 목적식은 SGD를 통해 최적화할 수 있다.
• SGD는 데이터의 일부를 가지고 파라미터를 업데이트하기 때문에 연산자원을 좀 더 효율적으로 활용하는데 도움이 된다.
  • 전체 데이터(X, y)를 쓰지 않고 미니배치(X(b), y(b))를 사용하여 업데이트하므로 연산량이 b / n 으로 감소한다.

행렬이란?

• 행렬은 벡터를 원소로 가지는 2차원 배열
• 행렬은 행과 열이라는 인덱스를 가진다.
• 행렬의 특정 행(열)을 고정하면 행(열)벡터라고 부른다.
• 전치행렬(transpose matrix)은 행과 열의 인덱스가 바뀐 행렬이다.
• 벡터가 공간에서 한 점이었다면, 행렬은 여러 점을 나타낸다.
• 행렬끼리 같은 모양을 가지면 덧셈, 뺄셈, 성분곱을 계산할 수 있다.
• 행렬곱은 i번째 행벡터와 j번째 열벡터 사이의 내적을 성분으로 가지는 행렬을 계산한다.
• 행렬은 벡터공간에서 사용되는 연산자(operator)로 이해한다.
• 행렬곱을 통해 벡터를 다른 차원의 공간으로 보낼 수 있다.
• 행렬곱을 통해 패턴을 추출할 수 있고, 데이터를 압축할 수도 있다.
• 모든 선형변환(linear transform)은 행렬곱으로 계산할 수 있다.

역행렬

• 어떤 행렬 A의 연산을 거꾸로 되돌린 행렬을 역행렬이라 한다.
• 역행렬은 행과 열 숫자가 같고 행렬식(determinant)이 0이 아닌 경우에만 계산할 수 있다.
• 역행렬을 계산할 수 없다면 유사역행렬(pseudo-inverse) 또는 무어-펜로즈(Moore-Penrose)역행렬을 이용한다.
  • 
• 유사역행렬을 이용하면 데이터를 선형모델로 해석하는 선형회귀식을 찾을 수 있다.

벡터란?

• 벡터는 공간에서 한 점 을 나타낸다.
• 벡터는 원점으로부터의 상대적인 위치 를 표현한다.

• 벡터에 숫자를 곱해주면(스칼라곱) 길이가 변하지만, 스칼라가 0보다 작다면 반대 방향 이 된다.

  • 

• 벡터는 숫자를 원소로 가지는 리스트 혹은 배열이다.

• 벡터끼리 같은 모양을 가지면 덧셈, 뺄셈, 성분곱을 계산할 수 있다.
• 두 벡터의 덧셈은 다른 벡터로부터 상대적인 위치 이동 을 표현한다. (뺄셈은 방향을 뒤집은 덧셈)
  • 벡터 x에 대하여, $x = 0 + x$ 가 성립한다. 즉 x라는 벡터는 원점벡터에서부터의 상대적인 위치를 나타낸다.

벡터의 노름

• 벡터의 노름(norm)은 원점에서부터의 거리 이다.

  • 

• L1-노름은 각 성분의 변화량의 절대값을 모두 더한 값이다.

• L2-노름은 피타고라스 정리를 이용하여 유클리드 거리 를 계산한다.
• 노름의 종류에 따라 기하학적 성질이 달라진다.
  • L1-노름 상의 원은 마름모꼴 (Robust 학습, Lasso 회귀)
  • L2-노름 상의 원은 흔히 알고 있는 원이다. (Laplace 근사, Ridge 회귀)
• 두 벡터 사이의 거리를 계산할 때는 벡터의 뺄셈을 이용한다.
  • 
  • 뺄셈을 거꾸로 해도 거리는 같다.
• L2-노름에서 두 벡터 사이의 거리를 이용하여, 제2 코사인 법칙에 의해 두 벡터 사이의 각도를 계산할 수 있다.
  • 내적(inner product)을 통해 분자를 쉽게 계산할 수 있다.

벡터의 내적

• 내적은 두 성분곱의 총합이다.
• 내적은 정사영(orthogonal projection)된 벡터의 길이와 관련이 있다.
• Pros(x)는 벡터 y로 정사영된 벡터 x의 그림자 를 의미한다.
• Proj(x) = ||x||2cos(theta)
• 내적은 정사영의 길이를 벡터 y의 길이 ||y||만큼 조정한 값이다.
• = Proj(x) * ||y||2 = ||x||2||y||2cos(theta)

1. 소켓 이해하기

전화를 걸기 위해서는 ‘단연코’ 전화기가 필요하다. 전화기는 멀리 떨어져 있는 두 사람이 대화할 수 있도록 만들어주는 매개체이다. 소켓은 전화기처럼 멀리 떨어져 있는 두 개의 호스트(host)를 연결해주는 매개체 역할을 한다.

1
2
3
4

#include <sys/types.h>
#include <sys/socket.h>

int socket(int domain, int type, int protocol);

우리는 누군가에게 걸려오는 전화를 받게 된다. 그리고 전화를 받으면 ‘여보세요’라는 응답을 주게 된다. 그렇다면, 전화기(소켓)을 만든 이후에 무엇이 더 필요할까? 당연히 전화번호가 필요하다. 그래야 누가 나한테 전화를 할 수 있기 때문이다. 그렇다면, 전화번호를 우리의 전화기에 할당시켜야 하는 것처럼, 소켓에도 일종의 ‘전화번호’가 필요하다. 소켓에서 전화번호의 역할을 하는 것은 바로 IP 주소이며, bind 함수를 이용하여 소켓에 주소를 할당할 수 있다.

1
2
3

#include <sys/socket.h>

int bind(int sockfd, struct sockaddr *myaddr, int addrlen);

이제 전화를 받을 준비가 끝났다. 하지만, 전화가 케이블에 연결되어 있지 않으면 소용이 없다. 즉, 전화선을 연결시키고 전화를 받을 상태를 만들어주어야 한다. 마찬가지로 소켓도 연결 가능한 상태가 되도록 대기를 시켜주어야 하는데, listen 함수를 이용하여 연결 요청이 가능하도록 만들어줄 수 있다.

1
2
3

#include <sys/socket.h>

int listen(int sockfd, int backlog);

자, 이제 전화벨이 울린다. 통화를 하기 위해서는 통화버튼을 눌러야 한다. 즉 누군가 대화를 요청했을 때 이것을 수락해야 한다는 뜻인데 소켓 역시 누군가가 데이터를 주고받기 위해 대화(연결)를 요청했을 때 그 요청을 수락할 수 있어야 한다. 이것을 accept 함수가 수행하게 된다.

1
2
3

#include <sys/socket.h>

int accept(int sockfd, struct sockaddr *addr, int *addrlen);

https://namu.wiki/w/%EC%8B%9D%EC%82%AC%ED%95%98%EB%8A%94%20%EC%B2%A0%ED%95%99%EC%9E%90%20%EB%AC%B8%EC%A0%9C

n명의 철학자가 스파게티를 먹고 있다고 가정한다.

철학자들은 잠자기, 먹기, 생각하기 셋 중 한 번에 하나만 할 수 있고 모든 철학자가 스파게티를 먹어야 한다.

식사하는 중에는 무조건 두 개의 포크를 사용해야 한다.

포크의 개수는 철학자의 인원수와 같으며, 포크는 각각의 철학자 사이에 놓이게 된다.

이 때 만약에 모든 철학자들이 동시에 자신의 왼쪽 포크를 잡게 된다면, 자기 오른쪽의 포크가 사용 가능해질 때까지 기다려야 하는데,

모든 철학자들이 기다리는 상태에 놓이게 된다.

이렇게 아무것도 진행할 수 없는 상태를 교착(deadlock)상태라고 한다.

멀티태스킹이 가능한 멀티쓰레드 환경일 때

사용자 레벨에서 Semaphore나 Mutex를 이용하여 한 쓰레드가 동작중일 때 다른 쓰레드가 CPU를 잡지 못하게 만들면 교착상태를 방지할 수 있다.

CPython에서는 흥미로운 사실이 발견된다.

변수에 값을 대입하는 흔한 식 a = 1 에서 = 연산자는 1이라는 값을 a에다가 할당하겠다는 뜻이다.

이것은 1이라는 값을 가진 a라는 객체를 생성하겠다는 뜻과 같다.

1
2
3
4
5
6
7
8
9
10

>>> id(5)
10914624

>>> a = 5
>>> id(a)
10914624

>>> b = 3 + 2
>>> id(b)
10914624

위의 코드에서 5라는 정수는 10914624 라는 객체 id를 가지고 있다.

하지만 a와 b 변수에 5라는 값을 할당했는데도 새로운 객체가 생성된 것이 아닌 같은 id를 가지게 된다.

https://docs.python.org/3/c-api/long.html#c.PyLong_FromLong

브루트 포스 알고리즘 - Brute Force Search

암호학에서의 Brute force attack이 아닌 알고리즘으로서의 브루트포스이다.

이 알고리즘의 핵심은 완전탐색, 가능한 모든 경우의 수를 탐색하면서 요구에 부합하는 결과를 가져오는 것이다.

장점은 모든 경우를 검사하므로 100%의 확률을 가졌지만,

모든 경우를 검사하는 만큼 효율성이 떨어질 수 있다.

문제해결 방법

1. 주어진 문제를 선형구조로 구조화함.
2. 구조화된 공간안에서 적절한 방법으로 해를 구성할 때까지 탐색한다.
3. 구성된 해를 정리한다.

예제 및 알고리즘

백준 블랙잭

네트워크

효율적인 데이터 전송을 위한 장비와 장비간의 연결을 칭함
프로토콜

데이터 전송시 필요한 규칙 및 약속을 미리 정의한 도구
외부와 통신 시 IP 프로토콜을 사용하면 Encapsulation과 Decapsulation을 통해 데이터 전송 가능.
Encapsulation, Decapsulation

데이터(PDU-Protocol Date Unit)를 패키지화, 해제하는 과정.
OSI(Open System Interconnection) 참조 모델

컴퓨터 응용프로그램 정보가 다른 컴퓨터 응용프로그램으로 어떻게 이동하는지 설명.
네트워크 설계를 위한 프레임워크 제공(호환성)
네트워크 장애 발생 시 (트러블슈팅) 해결방법에 접근하기 위해 필요.
Upper Layer

데이터 생성을 담당
Lower Layer

데이터 전송을 담당

IP Address - 네트워크 계층에서 사용되는 주소. IP 헤더에 포함된 데이터 주소.

• IPv4: 32bit(2^32), 8bit씩 4개의 octet
• IPv6: 128bit(2^128), 16bit씩 8개의 field

Subnet Mask - IP주소에 대한 네트워크 아이디와 호스트 아이디를 구분하기 위해 사용.

Unitcast Address

• A Class: 첫번째 필드의 2진수 값 중 맨 앞이 0이라는 공통비트라면 A Class로 정의. (00000000 ~ 01111111)
• B Class: 첫번째 필드의 2진수 값 중 맨 앞이 10이라는 공통비트라면 B Class로 정의.
• C Class: 첫번째 필드의 2진수 값 중 맨 앞이 110이라는 공통비트라면 C Class로 정의.
• D Class: 첫번째 필드의 2진수 값 중 맨 앞이 1110이라는 공통비트라면 D Class로 정의.
• E Class: 첫번째 필드의 2진수 값 중 맨 앞이 1111이라는 공통비트라면 E Class로 정의.

Network Name: 호스트 아이디 전체가 0인 주소

ex) 192.168.1.1/24 -> 192.168.1.0

Subnet Broadcast Address: 호스트 아이디 전체가 1인 주소

ex) 192.168.1.1/24 -> 192.168.1.255