무기력한 제이미

요즘 Blender를 사용해서 모델링을 하고 있는데, 좌표계 개념이 헷갈려서 글을 작성하여 정리하고자 한다. 

좌표계는 크게 두가지로 나눌 수 있다.

• Left Handed Coordinate System 왼손 좌표계
• Right Handed Coordinate System 오른손 좌표계

Blender는 이 중 오른손 좌표계에 속하는 프로그램이다. 보통 OpenGL을 기반으로 하는 프로그램이 주로 속한다.

(Direct X를 기반으로 하면 왼손 좌표계를 주로 사용한다. - Ex. 언리얼엔진)

Coordinate System

위의 그림처럼, 좌표계의 이름은 손에서 엄지와 검지, 중지의 방향과 손가락이 말린 방향으로 좌표축을 구분하기 위해 명칭을 '왼손'과 '오른손'으로 한 것이다. (예전에 배웠던 물리 이론 중 오른손 법칙 등과 같다)

검지(Y축)를 중심으로 중지(Z축)의 방향이 내 쪽(right)을 보는지, 바깥 쪽(left)을 보는지를 보면 된다. 

Left-handed Coordinate System Vs. Right-handed Coordinate System 

손 모양을 직접 해보면 알 수 있는데, 손가락이 말아지는 방향이 축을 따라 회전하는 방향이 된다.

위 그림처럼 왼손 좌표계는 시계방향(clockwise)으로, 오른손 좌표계는 반시계방향(counterclockwise)으로 돌게 되는 것을 확인할 수 있을 것이다.

블렌더의 경우 위의 모양과 같은 방향이므로 거꾸로 뒤집은 형태의 회전축을 따라 회전하게 된다. (이 부분을 신경쓰지 않고 무작정 회전하다가 거꾸로 회전하게 되는 실수가 발생하고는 했다.)

Example

다음은 블렌더를 통해 만든 간단한 예시이다. (이러한 형태의 원뿔이 있다고 했을 때, 각각을 x,y축에 대해 rotation)

한번 숙지하고 나면 어렵지 않지만, 가끔 헷갈리는 부분이라 정리해두었다. 

What is K-D Tree?

K-D tree는 공간을 기반으로 partitioning하는 binary tree인데, 점들을 k-차원 공간에서 정리한다. 

 위의 그림은 3차원 k-d 트리의 예시인데, 

1) 빨간색의 수직 plane으로 split하여, 하얀색 선으로 표시된 cell을 두개의 subcell로 나눈다. 

2) 각자의 subcell은 초록색의 수평 plane으로 split되어, 또 두 개의 subcell들로 나뉜다.

3) 네 개의 cell은 파란색의 수직 plane들로 각각 split되어, 두 개의 subcell들로 나뉜다.

이렇게, splitting이 끝난 후의 마지막 8개의 cell들을 leaf cell이라고 한다. 

이러한 k-d tree는 보통 다차원 공간에서의 search 등에 많이 사용되는 기법이며, range search, nearest neighbor 등의 문제에 적용된다.

• range search : 2차원, 3차원 물체가 서로 겹치는지 확인하여, 겹치는 물체들을 모두 search하는 것.

• neareast neighbor : 주어진 point와 가장 가까운 (주어진 set안의) 점을 찾는 것.

K-D Tree는 

Implementation

from collections import namedtuple
from operator import itemgetter
from pprint import pformat

class Node(namedtuple("Node", "location left_child right_child")):
    def __repr__(self):
        return pformat(tuple(self))

def kdtree(point_list, depth: int = 0):
    if not point_list:
        return None

    k = len(point_list[0])  # assumes all points have the same dimension
    # Select axis based on depth so that axis cycles through all valid values
    axis = depth % k

    # Sort point list by axis and choose median as pivot element
    point_list.sort(key=itemgetter(axis))
    median = len(point_list) // 2

    # Create node and construct subtrees
    return Node(
        location=point_list[median],
        left_child=kdtree(point_list[:median], depth + 1),
        right_child=kdtree(point_list[median + 1 :], depth + 1),
    )

def main():
    """Example usage"""
    point_list = [(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)]
    tree = kdtree(point_list)
    print(tree)

if __name__ == "__main__":
    main()

위의 코드는 https://en.wikipedia.org/wiki/K-d_tree 에 기재된 python 구현 코드이다.

(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)의 6개의 코드를 K-D Tree를 사용하면, 아래와 같이 출력된다. 

간단하게 설명하자면, 위의 예제에서 각 좌표는 2차원이므로, x축(depth = 0)과 y축(depth = 1)을 기준으로 번갈아가면서 모든 point를 노드에 넣을 때까지 partitioning하는 것이다. 각 축의 순서대로 정렬된 후 median 값을 기준으로 왼쪽과 오른쪽 subtree로 나누는 과정을 재귀적으로 진행한다. 

Nearest neighbour search with K-D Tree

Nearest Neighbour search 알고리즘은, tree안의 point들 중 주어진 point와 가장 가까운 것을 찾아내는 것이다. 

K-D Tree안의 nearest neighbour를 찾는 순서는 아래와 같다.

1. 루트 노드부터 시작해서 tree를 recursively하게 아래로 내려가면서, search point가 이 tree에 insert된다면 들어가야 할 자리를 찾음. 
2. 만약 리프 노드에 도착하면, 노드 point를 체크한 후, distance가 더 가까우면 이 노드 point를 "current best"로 저장.
3. tree의 recursion을 거슬러올라가면서, 각 노드마다 아래의 과정을 거친다.  

        (1) 만약 현재 node가 current best 노드보다 더 가까이 있다면, current best를 업데이트함.

        (2) 반대 splitting plane을 넘어서, search point와 더 가까운 점이 있을지 확인함. 

           - search point 중심으로, current nearest distance거리를 반지름으로 한 hypersphere를 그린 후, 이와 교차하는              점이 있는지 확인하면 된다.

             (a) 만약, hypersphere가 plane을 교차할 때, 반대 side에 nearer point가 있을 수도 있으므로, 알고리즘은 현재

              노드에서 다른 branch로 이동하여 똑같은 recursive process를 거쳐야 한다. 

             (b) 만약, hypersphere가 splitting plane과 교차하지 않는다면, 알고리즘은 반대 side의 경우를 전부 제거하고                마저 진행해도 됨. 

   4. 알고리즘이 루트 노드에 대해 위와 같은 process를 끝마치면, search가 끝난다. 

위의 경우, 새로운 점 (7,4)와 가장 가까운 점을 찾는 예시이다.  (7,4)는 KD-tree를 따라가다보면, 오른쪽 그림에서 파란색으로 칠해져있는 bounding box안에 속하게 된다. (leaf node) 가장 아래의 노드인 (7,2)와 (9,6)과의 distance를 구하고, 제일 작은 distance를 "current best" distance로 설정한다. 이후, 그 distance를 radius로 한 hypersphere를 그렸을 때, 반대 편에 속하는 점이 이 sphere안에 있기 때문에, 다른 branch도 체크하여야 한다. 

What is Plug in?

3ds Max에서 추가적인 features나 functionality를 사용하기 위해서는 plug-in이라는 c++ 코드가 필요하다.

이런 Plug-in을 통해, 추가적으로 geometric objects를 처리하거나 texture map, animation 등의 다른 여러 그래픽적인 요소들을 구현할 수 있다. (대표적인 유명한 rendering plug-in에는 Chaos Group에서 개발한 VRay가 있다! )

개발자들은 plug-in을 DLL(Dynamic Link Libraries)을 통해 구현할 수가 있는데, 이 DLL들은 Max SDK 안에 이미 정의되어있는 base class들을 기반으로 확장된 여러 class들을 가지고 있게 된다. (override 등의 member function을 사용하여 원하는 함수를 구현함) 3ds Max를 시작하면 plug-in을 포함한 경로에 있는 모든 DLL 파일들 중에, 아래 조건을 만족하는 DLL function을 export해야지만 load될 것이다. 이 function들은 DLL 파일 안에 몇 개의 plug-in이 있는지를 알려주고, 이 plug-in에 대한 정보들을 return한다. 

3ds Max에서 요구하는 plug-in의 조건

DLL function

• DLL entry point function(DLLMain()으로 named)이 있어야 함.
• 3ds Max를 위한 4가지의 function이 있어야 함. ((+2) : initializing, un-initializing) 

1. DLL 안에 class의 개수 return
2. 3ds Max SDK의 버전 return
3. user에게 plug-in에 대한 정보를 주는 짧은 string return
4. 실제 plug-in이 가지고 있는 mechanism 

Class descriptors

• 모든 plug-in 프로젝트는 'class descriptor'라는 class를 가지고 있음. 
• class descriptor는 plug-in의 정보를 3ds Max에 전달하기 위한 여러 member function을 가지고 있음.
• 정보 : class ID, category, name
• class descriptor는 주로 ClassDesc2(혹은 ClassDesc)를 통해 나온다. 
• Create() function을 구현하여, 3ds Max에 plug-in object에 대한 pointer를 제공하는 것이 중요하다. 

Class ID

• 3ds Max는 plug-in을 이름이 아니라 ID에 의해 인식함.
  (2가지의 서로 다른 plug-in이 같은 이름을 가지고 있어도 ID가 다르면 공존 가능)
• 만약 같은 ID를 가지는 두 plug-in이 존재할 경우, 3ds Max는 그 중 하나만 load한다.

DEF Files

• .DEF file을 DLL project에 추가하여, name이나 function의 순서 등에 대해 자세히 설명할 수 있다.
• 6개의 필수적인 plug-in function을 .DEF 파일 안에 나열함으로써, 3ds Max에게 이 function들이 구현되었고, call될 준비가 되어있다는 것을 알려줄 수 있다!
• .DEF 파일이 없어도 plug-in들을 load하는 것이 가능하긴 하지만, howto / samples sub folders 안의 plug-in과 상응가능하게 하기 위해 보통 추가한다. 

하나의 독립된 application과는 달리, plug-in은 3ds Max가 호출할 수 있는 여러 member function을 구현하는 것이다.

각 plug-in들은 기존에 정의된 base class를 기반으로 확장된 것이고, 원하는 기능들을 이를 통해 구현할 수 있다!

Plug-in Wizard (AppWizard)

3ds Max Plug-in Wizard(AppWizard)는 3ds Max에서 사용하는 plug-in의 skeleton code를 제공해주는 visual studio 전용 add-in이다. visual studio에서 프로젝트를 새로 생성할 때, 이 wizard를 사용한다면 원하는 plug-in type을 입력하면 필요한 기본 틀을 제공해준다.

3ds Max에 max sdk를 설치하면, Autodesk 폴더 안에 3ds Max 20xx SDK라는 폴더가 생기는데, 이 아래의 maxsdk\howto\3dsmaxPluginWizard 폴더의

• 3dsmaxPluginWizard.ico
• 3dsmaxPluginWizard.vsdir
• 3dsmaxPluginWizard.vsz

를 Visual studio 안의 vcprojects 폴더 안에 붙여넣기 하면 자동으로 add-in이 설치된다. 나의 경우 C:\Program Files (x86)\Microsoft Visual Studio\2019\Community\Common7\IDE\VC\vcprojects\Extensibility 안에다 붙여넣었더니 제대로 실행이 잘 되었다. 처음에 visual studio 2019를 설치한 후 vcprojects 폴더가 없었는데, visual studio installer에서 확장프로그램을 추가로 설치한 이후 vcprojects 폴더가 생겼다. 

그 후, 붙여넣은 파일 중 3dsmaxPluginWizard.vsz을 편집하는데, 검색해본 결과 Visual studio 2019를 사용하기 위해서는, Wizard=VsWizard.VsWizardEngine.16.0 으로 수정해야 한다고 하여 그대로 진행하였다. ABSOLUTE_PATH로 되어있는 부분도 Param="ABSOLUTE_PATH = [Absolute Path Location of 3dsmaxPluginWizard Root Directory]" 로 변경해준다. 변경한 후 visual studio를 실행하면 3ds max plugin으로 프로젝트를 실행할 수 있다. 

Sample plug-in 예제

3ds max plugin 프로젝트를 만들면, 여러 템플릿이 있고 이 중에 원하는 것을 고를 수 있다. 

진행하다보면, 3가지 path를 입력하는 부분이 있는데 maxsdk의 위치, plugin의 위치, 3ds Max의 위치 등 요구하는 경로를 지정해주면 된다. 전부 입력 후 진행하면 아래의 파일들이 자동으로 생기게 된다. (아래는 간단한 설명)

• <yourprojectname>.def

DLL의 various attributes에 대한 설명. (위에서 더 자세히 설명함) 6개의 plug-in 파일들을 나열함. 

• DllEntry.cpp

DLL functions + DLL entry point function을 가지고 있음. DLL이 loaded될 때 Windows에 의해 call되거나, rendering할 때마다 call될 수도 있음. 이 부분은 항상 똑같아야 한다!

• <yourprojectname>.rc

plug-in에 필요한 windows resource들. plug-in name/category/description string.  UI panel.  이 부분을 수정할 수 있지만, 3ds max에서 필수로 요구하는 부분이 아니다. 

• 3dsmaxsdk_preinclude.h

compile-time-to-do 메세지를 위한 매크로. plug-in을 수동으로 만들 때는 필요하지 않다.

• resource.h

constant value들을 위한 헤더. plug-in을 수동으로 만들 때는 필요하지 않다.

• <yourprojectname>.h

내 plug-in class를 위한 헤더. 해당 예제에서는 Utility 종류의 프로젝트로 시작했기 때문에 utilapi.h를 포함함.

- hInstance : OS memory 공간 안에 있는 plug-in DLL module을 위한 Handle
- GetString() : name/category/description을 위한 string call.

• <yourprojectname>.cpp

이 예제는 utility plug-in이기 때문에, UtilityObj class로부터 확장되었다. 이 안의 기본 뼈대 코드는 전부 제공되고, 내가 필요한 부분을 채워나가야 원하는 plug-in을 완성시킬 수 있다. 

이 중 <yourprojectname>.cpp을 수정하면 원하는 plug-in을 대부분 작성할 수 있다.

** 솔루션을 빌드하는 데, .h파일이나 .dlu파일을 열 수 없다는 오류가 나서 이에 대해 써보자면

    1. visual studio에서 MFC, SDK 관련 extension들을 설치해야 한다. 

    2. 빌드 환경은 Hybrid 로 설정한 후 진행해야 한다.

    3. visual studio를 관리자 권한으로 실행해야 한다.

이를 실행한 후, 솔루션이 제대로 빌드되는 것을 확인할 수 있었다.

What is Voronoi diagram?

위키피디아에 의하면, Voronoi Diagram은 평면을 특정 점까지의 거리가 가장 가까운 점의 집합으로 분할한 것이다. 

평면들에 있는 점(seed point)들 중 가장 가까운 점 2개를 모두 연결하고, 그 선들의 수직이등분선을 그어서 분할되는 것들이 보로노이 다각형(서로 다른 색으로 칠해져있는 다각형들)이다. 과정은 아래와 같은데, 여기서 점들을 연결하는 방법을 Delaunay triangulation(들로네 삼각분할)을 사용한다. 이에 대해서는 아래 section에서 설명하도록 하겠다. 

보르노이 다이어그램은, proximity information을 담고 있다. 예를 들어, 각 seed point를 도시 하나에 분포하고 있는 가게(shop)라고 하면, 이 다이어그램을 통해 "주어진 point X와 가장 가까운 가게는 어디인가?"와 같은 문제를 풀 수 있다.

What is Delaunay triangulation?

Delaunay triangulation(들로네 삼각분할)은, 다음의 조건을 만족하는 삼각형들의 집합을 만드는 분할이다.

• 평면위의 점들을 삼각형(simplex. 2D에서 그냥 triangle로 지칭함)으로 연결하여 공간을 분할할 때, 이 삼각형들의 내각의 최소값이 최대가 되도록 하는 분할을 말한다.

즉, (a)와 같이 점들이 있을 때, 이 점들을 연결하여 삼각형을 만드는 방법들이 (b), (c)와 같이 다양한데, (b)와 같이 최대한 정삼각형에 가깝도록 분할하는 기법이다. 

• 삼각형으로 이루어지는 circumsphere(외접원)의 내부에 삼각형을 이루는 세 point 외의 다른 point가 존재하지 않아야 한다. 

Voronoi diagram and Delaunay triangulation

보로노이 다이어그램과 들로네 삼각분할은 서로 dual image 관계에 있다. (= 하나를 알면 다른 하나도 바로 알 수 있음)

• Voronoi diagram -> Delaunay triangulation

     서로 인접한 보로노이 다이어그램의 seed point들을 연결하면 들로네 삼각분할들이 얻어진다. 

• Delaunay triangulation -> Voronoi diagram

     들로네 삼각분할로 구한 삼각형들의 외접원들의 중심을 연결해보면 보로노이 다이어그램이 나온다. 

https://darkpgmr.tistory.com/96 참고

Applications

• Convex Hull 구하기

Convex Hull이란 2차원 평면상에 점이 여러 개가 있을 때, 이 점들 중 일부를 골라서 나머지 점들을 모두 포함하는 볼록 다각형을 만드는 것을 말한다. 

Delaunay triangulation을 이용하여 convex hull을 구하기 위해서는, 원래의 input들의 집합에 외부의 점 3개를 추가하여 Delaunay triangulation을 구한 후 어떤 점들이 새로 추가된 외부의 점과 삼각형을 이루었는지를 조사하면 된다. 그 후, 새로 추가한 외부의 점과 삼각형을 형성한 점들을 연결하면 원래 점들에 대한 convex hell을 구할 수 있다. 

• 로봇 내비게이션

로봇이 길을 찾아 목적지까지 이동할 때, 주변 장애물과 부딪히지 않고 안전한 길을 찾아야 한다. 보로노이 다이어그램을 통해 이동경로를 생성하면, 공간의 가장 빈 곳을 따라 이동하기 때문에 안정성을 확보할 수 있다.

• OpenCV와 함께 사용한 프로젝트

위의 그림은 미국 전 대통령 오바마의 사진을 openCV library(Dlib)를 통해 얼굴의 특징점(Facial landmarks)이 되는 점을 찾은 것이다. 순서대로, 가운데 이미지는 이 점들을 seed point로 두고 Delauny triangulation을 구한 것이다. 오른쪽 이미지는 이에 상응하는 보로노이 다이어그램이다. Subdiv2D를 통해 Delauny triangulation이나 보로노이 다이어그램은 쉽게 구할 수 있다.

Bayes' Rule(베이즈 정리)은 machine learning의 중요한 개념 중 하나이다. 그 이유는, Bayes' Rule을 통해 상황에 대해 명시적으로 표현할 수 있기 때문이다. 

Frequentist and Bayesian Probability

통계학에는 크게 두 가지 학파가 있는데, 하나는 Frequentist(빈도주의자)이고 다른 하나는 Bayesian이다. 이 둘은, 가장 기본적 개념인 확률을 정의하는 방식에서 차이를 보인다.

[Frequentist Approach]

이들은 어떤 특정 measurement나 observation을 불신한다. 이들은 이미 정해진 true answer가 있다고 생각하며, 이를 찾는 것이 우리의 목적이라고 생각한다. 이 true value를 찾기 위해, frequentist는 굉장히 많은 observation을 결합하여 가장 frequently하게 나타나는 값을 most probable값으로 정의한다. 

[Bayesian Approach]

Bayesian은, 각각의 observation을 무언가에 대한 정확한 측정값으로 신뢰한다. 이들의 입장은, process의 마지막에 "true" value가 정해져 있지 않을 것이라는 것이다. 예를 들면, 산의 높이의 각 측정값은 땅의 어떤 점으로부터 산의 꼭대기의 어떤 점까지의 길이를 측정한 것이고, 이는 절대 매번 다르게 측정될 것이다. 따라서, 각 측정값은 accurate한 것이라고 여겨지며, 진정한 "true" 값이라는 개념은 여기서 크게 의미가 없다. 

[Discussion]

각각의 approach는 서로 다른 상황에 적용시켜 유용한 결과를 낼 수 있다.

ex. 지우개를 조금 사용한 흔적이 있는 연필의 길이를 측정한다고 가정하자. 이 길이를 측정하기 위해 정확한 ruler로 여러 번 측정하여 아주 조금은 다르지만 비슷한 여러 값들을 측정해낼 것이다. 

(1) frequentist : 이 연필에는 한 개의 true 값이 존재하고, 이를 찾아내야 한다. 각 측정값은 전부 믿을 수 없는 값들이다. 이 측정값들을 전부 결합하여, error값을 제거하여 정확한 답을 찾아낼 수 있다. 이 중 가장 빈번하게 나타나는 값이 맞는 답이다.

(2) bayesian : 연필의 길이에 대한 오직 한 개의 true값은 존재하지 않는다. 각 측정값은 전부 믿을만한 값들이며, 여러 개의 가능한 확률이 존재한다. 

이러한 관점의 차이는, 각기 다른 data와 information을 도출해낸다. 

Coin Flipping

확률 문제에 관한 예시에서 동전 뒤집기 문제는 굉장히 많이 사용된다.

보통 fair coin을, 던졌을 때 앞면 뒷면이 나올 확률이 같은 coin이라고 한다. 

반대로, 앞면과 뒷면이 나올 확률이 같지 않은 coin을 rigged/ unfair/ cheater's coin이라고 한다.

(bias 0.1 coin : 앞면이 나올 확률이 10%)

위의 그림은, 순서대로 bias가 0.2, 0.5, 0.8인 경우 결과를 나타낸다. 

Is this a Fair Coin?

  똑같이 생긴 두 동전 묶음과, marked board가 있다고 가정하자. 이 동전 pair 중 하나만 fair coin이고, 나머지는 앞면이 나올 확률이 2/3인 biased coin이다. (bias = 2/3) 게임을 통해, player는 어떤 coin이 biased coin인지를 추정한다. 그 후, 동전을 실제로 돌려서(spin), 이를 확인할 것이다. (무게가 다르기 때문에 biased coin이 fair coin보다 먼저 떨어짐)

  이 게임을 제대로 수행하기 위해, coin의 true identity를 구분하려고 한다. 우리는 "Fair", "UnFair" 봉투에다가 각각의 동전을 구분하여 넣을 것이다. 이 동전들을 구분하기 위해, 다음과 같은 과정을 거친다.

만약, 두 가지의 coin 중 한개를 고른다면, 각 확률은 50%이다. 

각 fair, biased 부분을 head/tail로 나누면 위와 같다. fair 부분은 1/2, 1/2로 나뉘어지며, biased부분은 2/3, 1/3으로 나뉨.

여기서, 우리의 질문은 "fair coin을 뽑을 확률은 무엇인가?"라는 것을 잊지 말자. 우리는 이미 동전을 던져서 앞면임을 확인했다고 가정하자. 이 때, 질문을 다시 정리하면, "앞면임을 확인했을 때, fair coin일 확률은 무엇인가?"라고 말할 수 있다.

위의 그림처럼, "앞면이 나올 확률을 가진" 모든 확률 중에, "fair coin"일 확률을 계산하면 되는 것이다.

probability term을 사용하여 이를 재정비하면, 위의 그림처럼 표현할 수 있다. 

Head가 나왔을 때, fair coin일 확률(P(F|H))은, head이면서 fair coin일 확률과 head이면서 rigged(Biased) coin일 확률을 더한 것 중에, head이면서 fair coin인 확률을 구하면 된다.

위의 그림을 보면, A와 B의 joint probability를 P(A|B)와 P(B)의 곱으로 표현할 수 있음을 확인할 수 있다. 이를 수식으로 정리하면, 아래와 같다.

우리는 P(H, F)의 값을 모르기 때문에, P(H|F) x P(F)로 대체하여 이를 대신 계산할 수 있다. 

이제, 모든 값들이 다 아는 값들의 곱과 합으로 이루어져있으므로, 계산하면 된다.

P(F) : fair coin을 고를 확률 = 1/2

P(H|F) : fair coin이면서 앞면이 나올 확률 = fair coin의 bias = 1/2

P(H|R) : rigged coin이면서 앞면이 나올 확률 = rigged coin의 bias = 2/3

P(R) : rigged coin을 고를 확률 = 1/2

다 계산하면 약 0.43의 결과를 얻게 된다. 이를 통해, 우리는 coin을 한 개 뒤집었을 뿐인데 fair coin일 확률이 43%라는 것을 알 수 있다 ! 

반대로, 첫 flip이 뒷면이 나왔을 경우를 계산해보면 위와 같은 결과가 나온다. 이처럼, 앞면일 때와 뒷면일 때의 확률은 서로 다르게 나온다. 아직 한 번의 flip만을 계산하였기 때문에 결과를 확신할 수는 없다.

Bayes' Rule

앞에서 말한 내용을 수식 하나로 표현하면 위와 같다. 이를, Bayes' Rule, 베이즈 정리라고 한다.

우리가 구하려고 하는 것은 P(F|H), 즉 Head일 때 fair coin일 확률이다. 이를 구하기 위해서는 3가지의 정보가 필요하다.

(1) P(H|F) : fair coin일 때 head가 나올 확률

(2) P(F) : fair coin을 얻게 될 확률. P(H, F) 값을 구하기 편하게 만들어 놓은 수식이다. 

(3) P(H) : fair / rigged 두 경우 head가 나올 확률을 모두 더한 것.

"B가 true임이 주어졌을 때, A가 true일 확률은 무엇인가?"

베이즈 정리는 위와 같은 형태의 질문에 사용하기 위해 만들어진 term이다. 

베이즈 정리를 쉽고 빠르게 도출해내기 위한 예제이다.

첫번째 줄에서, P(F, H)와 P(H, F)은 joint probability이기 때문에 같다. 이를 두번째 줄에서, 다른 형태로 변형한다.

세번째 줄에서, P(H)로 양쪽을 나누면 우리가 구하려는 베이즈 정리의 식이 나오게 된다.

식의 각 부분은, 다음과 같이 나타낸다. 

P(A) : prior probability / prior. P(A)는 동전을 던지기 전에, 동전이 fair/rigged coin인지 상관없이 fair coin을 고를 확률.

-> 사건 B가 발생하기 전에, 이미 알고 있던 정보.

P(B) : evidence / normalizing constant. B사건이 발생할 "모든" 확률. 

P(B|A) : likelihood. fair coin을 가졌다고 했을 때 앞면이 나올 확률.

-> 사건 A가 발생한 경우 사건 B의 확률.

P(A|B) : posterior probability / posterior. 베이즈 정리에 의해, 앞면이 나왔다는 observation을 토대로 fair coin을 고를 확률을 얻게 되는 것이므로, 계산을 다 했을 때 얻게 되는 값이다. 따라서, 사후 확률이라고 한다.

-> 사건 B가 발생한 후 갱신된 사후 확률.

위의 예시에서는 prior값을 구하는 게 쉬웠지만, 더 복잡한 상황에서는, "good prior"를 고르는 것이 어려울 것이다.

prior를 주관적이고 개인적인 견해로 고르는 것을 subjective Bayes라고도 한다.

반대로, prior를 고를 때 어떠한 법칙이나 알고리즘을 사용한다면, automatic Bayes라고 한다.

* Bayesian approach에서 추구하는 것은, 앞서 말했듯이 우리의 preconception과 expectation을 명시적으로 표현하는 것이다. 우리가 prior를 어떻게 고르는 지에 따라 달라진다고 할 수 있다.

Finding Life Out There

  이전 chapter에서는, test의 결과값을 이해하기 위해 confusion matrix를 사용했었다. 이번에는, Bayes' Rule을 사용해서 이해해보도록 하자.

Ex. 만약 우리가 우주선의 선장이고, 사람이 살지 않는 행성으로부터 원료를 얻는 것이 목표라고 가정해보자. 어떤 행성을 발견해서 채광을 하려하지만, 우리는 "행성에 생명체가 있으면 채광을 절대 하면 안된다"라는 명령을 받았다.

이 때, 우리가 질문할 것은 "이 행성에 생명체가 있는가?" 에 대한 것이다.

우리는 행성들의 10%는 생명체가 있다는 경험적 근거가 있다. 이 때, 우리는 probe(조사단)를 행성에 내려보내고, "생명체가 없다"라는 결과를 보고받는다. 여기서 우리가 질문해야 하는 것은 "probe가 생명체를 발견하지 못했을 때, planet이 생명체를 가질 확률은 무엇인가?"이다. 이 결과를 얻기 위해 Bayes' Rule을 사용한다. 

"life is present" 조건을 L이라 표현하고, "detected life"조건을 D라고 표현한다. L이 positive라면 planet에 life가 있는 것이고, negative라면 없는 것이다. 마찬가지로, D가 positive라면 probe가 life를 detect했다는 것이고, negative라면 probe가 생명체를 탐지하지 못했다는 것이다.

-> 우리가 가장 피하고 싶은 상황은, "생명체가 있는 planet을 채광하는 것이다. 즉, False-negative 상황이다.

(probe가 탐지하지 못했는데, 사실은 생명체가 있는 경우)

-> false positive 경우는 조금 괜찮을 것이다. 생명체가 없지만 생명체가 있다고 하여 mining을 하지 않으면 큰 피해 X

probe를 구현해낸 과학자들은 이러한 주의사항을 숙지하고, 최대한 false negative 상황을 피하려고 노력했을 것이다.

위의 figure는 총 1000개의 test planet에 대한 probe의 performance를 나타낸다. 이 중 101개의 planet은 생명체가 존재한다. probe는 1000 중에 100번의 경우 생명체를 찾았다고 제대로 report하였다. (true-positive. 101개 중 100개 correct)

899개의 빈 행성들에 대해서, probe는 그 중 869개의 planet에 대해 생명체가 없다고 report하였다. (true-negative)

probe는 1개의 planet을 false negative, 30개의 planet은 false positive로 report하였다. 

위와 같이 confusion matrix로 나타내면, 확률 값들이 무엇인지 구할 수 있다.

P(D)의 경우 "detected life"의 확률이므로 130/1000, P(L)의 경우 "life is present"의 확률이므로 101/1000이다.

P(D|L)은, 생명체가 있을 때 probe가 제대로 detect할 확률이므로, TP/(TP+FN) = 100/101이다.

우리가 구하고자 하는 것은, probe가 생명체를 탐지하지 못했을 때 생명체가 있을 확률이다. P(L|not-D)

이 값을 베이즈 정리로 나타내면 위와 같다. 확률은 약 0.001이므로, 1000번의 수행 중 약 한 번만 잘못된 결과가 나온다는 뜻이다. 반대로, probe가 생명체를 탐지해냈을 때, 생명체가 있을 확률을 구해보면 아래와 같다.

Repeating Bayes' Rule

위의 예시에서, 우리는 probe를 한 개가 아니라 여러 개를 보내서 결과값에 대한 confidence(신뢰도)를 높일 수도 있다.

다시 두 개의 동전 예시로 돌아와서 생각해보자. 아까는 동전을 한 번만 던져서 이에 대한 결과값을 구했다. 하지만, 만약 동전을 계속 던진다면 어떻게 될까?

새로운 data는 새로운 posterior 값을 줄 것이고, 이 값을 새로운 observation에 대한 prior값으로 사용할 수 있다. 

위의 term(prior/posterior)과는 달리, 베이즈 정리를 위와 같이 표현할 수도 있다. 

A를 원인/가정이라고 생각하고, B를 관측값으로 생각한 것이다. 

동전 예시에서, hypothesis는 "우리는 fair coin을 선택했다"가 될 것이고, observation은 "동전은 앞면이 나왔다"가 되는 것이다. 여기서 사후 확률(posterior)은 observation이 일어났을 때 hypothesis가 true일 확률을 말한다. 그러나, 우리는 "observation이 발생했다"는 사실을 이미 알고 있기 때문에(그게 우리가 posterior를 계산한 이유니까), posterior는 hypothesis의 확률이 되는 것이다.

따라서, posterior는 우리가 관찰한 observation을 기반으로 한, prior의 improved version이라고 할 수 있다. 

이때, 만약 또 다른 관측값이 들어온다고 해보자. (동전 또 던짐) 

우리의 원래 prior값을 hypothesis의 확률로 사용하는 대신에, 방금 구한 posterior값을 사용한다. 

매번 observation을 새로 input으로 받아올 때마다, 우리는 이를 그 observation의 likelihood나 evidence, prior값과 결합하고, 새로운 posterior값을 계산한다. 이 posterior값은 다음 observation의 prior값으로 사용된다. 

ex. fair coin 한 개와, 각자의 bias를 theta값으로 스티커로 표시해둔 여러 개의 rigged coin들이 있다고 가정해보자.

이 rigged coin들 중 한개를 고르고, 해당 bias값을 적어놓은 후, 스티커를 없앨 것이다. 스티커를 제거한 coin을 가방에 넣고, 똑같이 생긴 fair coin을 또 넣는다. 우리는 이제 bias값을 알고 있고, 똑같이 생긴 coin이 가방 안에 두 개 있다!

우리는 여기서 coin을 한 개 고르고, 그 coin이 fair coin인지 아닌지를 알고 싶다. Bayes' Rule의 형태로 30번의 동전을 던질 것이고, 각각 head인지 tail인지를 기록한다. 동전을 30번만 던졌기 때문에, 결과가 이상하게 나올 수도 있다.

예를 들면, fair coin인데 6개의 head와 24개의 tail이 나올 수도 있다. 또한, rigged coin인데 똑같은 수의 head와 tail이 나올 수도 있다. 이러한 경우, 베이즈 정리가 observation을 어떻게 처리할까?

위의 경우는, bias가 0.2인 rigged coin과 fair coin 중 한 개를 골라서 30번 던진 결과이다. 우리의 가정에서, fair coin의 경우 15개의 head가 나올 것으로 예측되고, rigged coin의 경우 6개의 head가 나올 것으로 예측된다. 위의 결과는 총 24개의 head가 나왔으므로 Rigged coin이라고 예측하게 된다.

왼쪽으로부터 보면, 처음에는 각 확률이 0.5이다. 아직 동전을 던져본 적이 없으므로 어떠한 data도 얻지 못한 상태이다. 

그 다음은, 처음에 T를 관측한 다음의 결과이다. fair coin에서 tail을 관측할 확률은 0.5지만, rigged coin에서 관측할 확률은 0.8이기 때문에, rigged coin일 확률이 높아진다. 

오른쪽으로 쭉 이동할 때, 이 중 80%의 관측값이 T이다. 이는 rigged coin으로부터의 예측값과 비슷하기 때문에, probability는 빠르게 1과 가까워진다. 

지금까지는, rigged coin의 data와 굉장히 비슷한 data였다. 만약, 이 이후에는 head가 더 적게 나온다고 가정해보자.

4개의 flip만으로도, 90%의 confidence를 가지게 되는 것을 확인할 수 있다.

그 후, 30개의 flip을 또 던졌을 때, 24개의 head가 나왔다고 해보자. 이 경우, fair coin은 15개의 head가 나온다고 예측하지만 rigged coin은 6개의 coin이 나온다고 예측할 것이다. 양쪽 다 맞지 않지만, fair coin이 더 높은 확률을 가진다.

위에서 3개의 head-tail pattern을 다뤘다. 이를 다시 하되, 10개의 서로 다른 bias를 가진 coin에 10개의 pattern을 사용할 것이다. 이 결과는 위와 같다. 맨 왼쪽 아래를 보면, x축의 값이 약 0.05인 것을 확인할 수 있다. 이는, coin이 20개 중 1번은 head가 나온다는 것이다. y축을 보면, 마찬가지로 0.05정도인데, 마찬가지로 20개 중 1개가 head가 나오도록 하는 artificial sequence of observations를 우리가 만들 것이라는 뜻이다. 위 표에서, rigged coin에서 우리가 예상하는 패턴과 비슷하므로 coinfidence가 빠르게 증가함을 확인할 수 있다. 

* 해당 정리 및 요약본은 Andrew Glassner의 "Deep Learning : From Basics to Practice Volume 1,2"를

기반으로 제작된 것을 밝힙니다. *

Basic Probability Concepts

[Simple Probability]

다트를 던지면 무조건 벽에 꽂힌다고 가정하고, 확률은 모두 동일하다고 하자.

이 때, 다트가 붉은색 영역에 꽂히는 사건을 'A'라고 하면, A의 확률 P(A)는 붉은 영역과 전체 영역의 넓이의 비로 나타난다. 이렇게, 사건 하나가 일어날 확률 P(A)를 A의 simple probability / marginal probability라고 한다.

[Marginal Probability 주변 확률]

어떤 하나의 사건이 일어날 단순한 확률. 아무 조건이 붙지 않는 확률을 말한다. 

[Conditional Probability 조건부 확률]

벽에 그림이 추가되어 초록색 영역이 생겼다고 가정하자. 이제 사건은 한 개가 아니라, 두 개이다. (시행은 한 번)

다트가 초록색 영역에 꽂히는 사건을 'B'라고 할 때, 조건부 확률 P(A|B)는 다트가 꽂힌 곳이 B의 영역 안일 때, 이 영역이 A 안에 있을 확률을 말한다. 

-> 조건부 확률 P(A|B)는, 다시 말해 어떤 사건 'B'가 일어난 게 알려져 있을 때 다른 사건 'A'가 일어날 확률을 나타낸다.

-> A, B를 input으로 받고, probability를 return하는 algorithm이라고도 표현할 수 있다.

[Joint Probability]

P(A, B)의 경우는, 두 개의 서로 다른 사건 A와 B가 동시에 일어날 확률을 나타낸다.

위의 그림의 경우 전체 영역 중,  A영역과 B영역이 intersect하는 부분에 다트가 꽂힐 확률을 말한다. 

* Conditional Probability와 Joint Probability

Confusion matrix

[Simple Classifier]

왼쪽 그림은 2D data sample을 나타낸다.

Classifier는, data sample을 input으로 받아 어떤 카테고리에 속하는지 output으로 출력한다. 

Classifier를 build한다는 것은, 오른쪽 그림과 같이 data sample들을 동일한 것끼리 묶는 boundary curve를 찾는 것이다.

이 챕터에서는 output이 positive / negative인 경우만 고려한다.

현재 2D data sample은 모두 빨간색 / 초록색이므로 초록색인 경우를 Positive라고 가정한다. 

위 그림처럼, dataset에서 20개의 sample을 사용한다고 가정하자. 실제 classifier는 이전 그림과 달리, curve의 양쪽(위아래)에 positive, negative가 섞여있게 된다. 왼쪽 그림의 화살표는 "positive" 방향을 가리키며, 각 sample들의 position을 무시한 채, count하기 편리하게 재배치한 그림이 오른쪽의 schematic version이다.

(실제 확률을 계산하는 데 관여하는 것은 sample의 수이기 때문에 두 diagram은 같다!)

이 sample들 중 어떤 sample은 맞는 결과가 나왔고, 어떤 sample은 틀린 결과가 나왔다. 이를 제대로 잘 분류하기 위해서, classifier를 수정하거나 새로 만드는 등의 작업을 거쳐야 한다. 따라서, 이러한 error들을  효율적으로 characterizing하는 것이 중요하다!

[Confusion Matrix 혼동행렬]

classifier의 정확성을 알아보기 위해, 점들을 4가지의 category로 분류한다.

- True Positive : 제대로 분류된 positive 경우

- False Positive : negative인데 positive로 분류된 경우

- False Negative : positive인데 negative로 분류된 경우

- True Negative : 제대로 분류된 negative 경우

Confusion matrix는 위에 언급된 4개의 값들로 만들어진 2 by 2 matrix이다. 

(Confusion matrix를 작성할 때, 형식에 대한 universal agreement가 없기 때문에, 늘 label을 주의깊게 확인해야 한다!)

[Interpreting the Confusion Matrix]

ex. medical diagnosis의 경우를 예시로 들어, positive는 어떤 사람이 병에 대해 증상이 있는 것이고, negative는 그 사람이 건강하다는 것을 나타낸다고 하자. 또한, 우리는 보건 관련 직원이고, morbus pollicus, 줄여서 MP라는 상상 속 병이 있다고 가정하자. MP에 걸린 모든 사람은 그들의 엄지손가락을 제거해야 하고, 그러지 않으면 몇시간 내에 죽는다!

따라서, 우리가 사람들이 MP에 걸렸는지 아닌지를 진단하는 것이 여기서 매우 중요한 문제가 될 것이다.

(병에 걸렸는데 손가락을 자르지 않으면 그 사람이 죽고, 병에 걸리지 않았는데 굳이 손가락을 자르게 될 수 있는 것임)

이 병의 진단을 confusion matrix로 표현하면 위의 그림과 같다. 각 matrix의 cell에 numbers를 부여하고, 이 값들을 사용하여 population과 test에 질문을 할 수 있다. 이 때 "어떤 질문"을 하느냐가 굉장히 중요하다.

예를 들면, "MP를 가진 사람 중에 몇 명이나 정확하게 분류되었는가?"라는 질문은 겉보기엔 유용해보이지만, 잘못된 결과를 나타낼 수도 있다. 만약 우리의 test가 항상 True를 return했다고 가정하면, 위의 질문에 대한 대답은 "100%"가 될 것이다. 다시 말해, test는 위 질문에 대한 수행을 완벽하게 해냈지만, MP를 가지지 않았는데도 positive한 결과가 나온 (False Positive) 모든 사람들의 수많은 경우들을 전부 무시한 게 되는 것이다. 

이 질문 외에, "우리가 제대로 진단한 건강한 사람은 몇명이었는가?"라는 질문을 생각해보자. 마찬가지로, 우리는 지금 한 경우의 진단만을 확인하고 있다. 만약 우리가 모든 사람에게 False 진단을 내린다면, 단순히 우리의 test는 "100%" 정확하다는 결과를 내보낼 것이다. 모든 건강한 사람은 "건강하다는 진단"을 받겠지만, MP를 가진 사람들은 전부 죽게 될 것이다. 

"제대로 된 질문"을 하는 것은 굉장히 어렵고, 이러한 실수를 하기 쉽다. 이러한 wrong question problem을 해결하기 위해, 여러 해결 방법이 있다. 

Measuring Correctness

어떤 measure를 사용하느냐에 따라 classifier의 정확도가 99%가 되기도 하고, random guess보다 못한 수준이 되기도 한다. 다음은 classifier의 quality를 characterize하는 개념들이다. 

[Accuracy]

Accuracy는 전체 sample data 중 제대로 정답을 맞춘 경우(True positive / True negative)의 비율을 나타낸다.

즉, 이 classifier가 얼마나 정확한지를 알려준다. 하지만, false negative와 false positive 중 어디서 prediction이 잘못되었는지를 나타내지 못한다는 단점이 있다. 

[Precision (positive predictive value) / PPV]

Precison은 positive로 예측한 sample값들 중 실제로 positive인 sample들의 비율을 말한다.

만약 precision이 1보다 작다면, positive가 아닌 값들을 positive로 labeling했다는 것이 된다. (unnecessary operations)

Precision의 단점은, 모든 ground truth positive값들 중에 classifier가 얼마나 이들을 찾아냈는지 알 수 없다는 것이다.

(Ground truth : 사람이 수작업을 통해서 만들어낸 original data. 직접 수집하고 정제한 후 labeling한 data를 말함)

[Recall (Sensitivity, hit rate, true positive rate)]

Recall은 실제로 positive인 sample들 중에서, positive로 제대로 예측된 sample들의 비율을 말한다. 

recall이 1.0이라는 것은, 모든 positive event를 다 찾아냈다는 것을 의미한다. recall 값이 떨어질수록 positive event를 더 많이 놓쳤다는 것이 된다. 위의 MP예제에 적용해본다면, recall이 1.0이하면 MP에 걸린 어떤 사람을 제대로 진단해내지 못했다는 것이 된다. 

Recall은 실제로 negative한 값들이 어떻게 예측됐는지 무시해버린다는 단점이 있다.

[Precision and Recall]

500page의 wiki에 "dog training"이라는 phrase를 검색한다고 가정하자.

만약 우리의 search engine의 page가 dog training에 대해 return한다면 positive, return하지 않는다면 negative라 한다.

accuracy의 경우, 전체 비율 중 제대로 labeled된 비율이기 때문에 위와 같다. 

precision의 경우, 

[Perfect Precision]

Precision과 recall은, machine learning에서 많이 쓰이는 measure 중 하나이다. 

하지만, 만약 precision만 쓸 경우에는 perfect precision이라는 문제가 발생할 수 있다.

만약 Classifier가 수많은 sample들 중 가장 positive일 확률이 높은 하나의 sample만 positive로 분류하고, 나머지 sample들을 모조리 negative로 분류한다고 가정하면, precision은 100%가 될 것이다.

-> 이는 precision이 positive로 분류된 sample만을 고려하기 때문에 발생하는 문제이다.

[Perfect Recall]

[F1 score]

precision과 recall을 합쳐, 둘의 조화평균으로 나타낸 것을 F1 score라고 부른다. 위의 그래프를 보면, F1 score는 한 쪽의 점수가 아무리 높더라도 다른 한 쪽의 점수가 0에 가까워지면 급격하게 감소함을 확인할 수가 있다.

Applying the Confusion Matrix

실제 예시를 들어 위의 개념들을 적용해보자. 위의 MP 병에 대해 우리가 가진 classifier인 진단 test를 시행해보았다고 하고, 이 마을에서 약 1%의 사람만 MP를 가지고 있음이 이미 확인되었다고 가정한다.

(1) MP를 가진 사람들의 경우

99%의 확률로 MP는 제대로 진단되어 TP rate는 0.99이고, 따라서 MP를 가졌지만 제대로 진단되지 않은 사람의 비율 FN rate는 1%(0.01)라고 하자.

(2) MP에 걸리지 않은 사람들의 경우

실제로 걸리지 않아서 건강하다고 진단받은 사람의 경우인 TN rate는 0.98, 실제로 걸리지 않았는데 걸렸다고 진단받은 사람의 경우인 FP rate는 0.02라고 하자. 

어떤 사람이 양성(positive) 판정을 받았을 때, 이 사람이 정말로 MP에 걸렸는지 아닌지를 알고 싶다면, confusion matrix를 build하여 알아볼 수 있을 것이다. 하지만, 위 그림처럼 matrix를 만드는 것은 잘못된 결과를 도출해낼 것이다.

-> 위의 matrix에서는 MP에 걸릴 확률과 걸리지 않을 확률을 동일하게 가정하고 있다. 이 마을에서는 실제로 오직 1%의 사람들만 MP가 발병하였다. 실제 positive와 negative의 비율을 고려해야 한다!

진짜 confusion matrix를 구현하기 위해서는, 전체 인구 10,000명을 100명의 감염자(1%)와 9900명의 비감염자로 나누고, 다시 진단 test의 결과에 따라서 이를 나눠야 한다. 이렇게 해서 나뉜 값들이 진짜 confusion matrix의 원소가 된다.

이제 제대로 된 chart가 생성되었으니, 아까의 질문에 대답을 얻어낼 수 있다.

Q. test에서 양성의 결과가 나왔을 때, 그 사람이 MP에 실제로 걸려있을 조건부 확률은 무엇인가?

A. TP / TP + FP이므로, 98 / 99+198 = 약 33%의 결과가 나온다.

-> 이 결과를 보면, 약 300명 중 200명은 잘못된 결과를 도출한다는 뜻이므로, 우리의 test가 거의 잘못 진단을 내린다는 것을 알 수 있다 ! 이는 10,000명의 사람들 중 건강한 사람의 비율이 높았기 때문에 발생한 결과이다.

-> 이보다 더 비싸고 정확한 test를 해야 한다는 것으로 이해하면 됨.

오른쪽 그림을 보면, MP를 가진 사람들을 대부분 positive라고 제대로 진단해내지만, MP에 걸리지 않은 198명의 사람들을 positive라고 잘못 진단해낸 걸 볼 수 있다. 

* 해당 정리 및 요약본은 Andrew Glassner의 "Deep Learning : From Basics to Practice Volume 1,2"를

기반으로 제작된 것을 밝힙니다. *

 Random Variables

Machine learning에서는, 임의의 number를 그냥 뽑지 않고, Random numbers를 통해 data에서 sample을 뽑아낸다.

[용어 및 개념 정리]

- mean : average. 평균

- mode : list에서 가장 많이 나타나는 value. 

- median : list의 정중앙에 있는 number. (정렬될 경우)

- probability distribution : value의 확률 분포. normalized되었기 때문에 value의 합은 1이 된다.

- Expected value : probability distribution으로부터 추출된 long list values의 mean

ex. 만약 1, 3, 5, 7이 각각 동일한 확률을 가지고 있을 때, expected value는 (1+3+5+7)/4 = 4가 된다. (list안에 꼭 포함x)

- Random variable : 변수의 의미가 아닌, 단순한 Function이다! (확률변수 X)

-> input : probability distribution (확률분포)

-> output : specific value를 output으로 함.

- probability distribution(density) function : pdf. 확률분포함수. X가 [r1, r2] 안에 포함될 확률.

- probability mass function : pmf. 확률질량함수. X에 대한 확률을 나타내는 함수. (ex. 주사위 한 번 굴림 = 1/6)

- discrete probability distribution : 이항확률분포. 

- continuous probability distribution : cpd. probability density function. 연속확률분포. 연속된 그래프이다.

해당 그래프 아래의 넓이의 합은 1이 되어야 한다. 

- drawing a value : value를 만들어내는 것

random한 variable을 draw하는 것은, "unpredictable"한 number를 고른다는 뜻이다.

보통 computer programs들은 deterministic (주어진 input에서는 항상 같은 output이 나온다는 뜻) 하기 때문에, 

unpredictable한 number를 고르는 것은 상당히 어렵다! 아무리 random한 number를 뽑아내는 프로그램을 사용해도, 그 알고리즘을 살펴보면 어떤 원리인지 다 파악 가능하다. 따라서, 컴퓨터가 생성해내는 random number는 "가짜"이다.

-> 따라서, 이 알고리즘들을 pseudo-random number generators라고 하고, pseudo-random numbers를 생성한다. 

만약, pseudo-random numbers를 사용하는 프로그램을 작성했는데 에러가 났다고 가정해보자. 

problem을 debugging하기 위해, 똑같은 pseudo-random numbers를 얻는 과정을 똑같이 수행하고 싶을 것이다.

이를 수행하기 위해, 각 routine에 seed라고 하는 number를 부여한다. 

seed(씨앗값)는, 말 그대로 random number를 만들 때 사용하는 최초의 값을 지정해주는 역할을 한다.

pseudo-random number genertor는 output을 sequence(previous value에 dependent)로 생성해내기 때문에, seed값이 같다면 같은 random number를 생성해낸다.  

ex. np.random.seed(1)의 값과 np.random.seed(1)의 값은 같지만, np.random()의 값과 np.random()의 값은 다름.

매번 같은 sequence의 random number를 생성하는 것은 "unpredictable"하지 않으므로, 이는 주로 system design / debugging phase에 주로 사용된다. 

 Some Common Distributions

여러 종류의 distribution에 대해 알아보자.

[The Uniform Distribution 균일 분포]

input이 0부터 1 사이일 때, output이 1이 출력되고 있다. 이 distribution은 중요한 점이 두 가지 있다.

(1) 다른 모든 value의 probability가 0이기 때문에, 0부터 1 사이에서만 value를 얻을 수 있다는 것과, 

(2) 0부터 1 사이의 모든 value는 equally probable하다는 것이다. (0.25, 0.33, 0.793718 그 어디에서도 값이 같음)

이와 같은 형태의 distribution을 uniform, constant, 혹은 flat하다고 한다. 

또한, 모든 non-zero value가 특정 range(0부터 1)안에 있기 때문에, finite하다고 할 수 있다. 

보통 uniform distribution을 생성하는 library function에서는 이 range를 0에서 1 혹은 -1에서 1 등으로 설정할 수 있게 한다. 또한, 위에서 설명했던 것과 같이, line 아래의 넓이는 1이 되어야 한다. (1.0 * 1.0 = 1.0)

[The Normal Distribution 정규 분포]

Gaussian Distribution이라고도 하고 간단하게 bell curve라고 부르기도 한다.

uniform distribution과는 다르게 부드럽고, 뾰족한 모서리가 없이 종 모양으로 되어있다.

가운데 bump외의 값은 대부분 0에 가깝지만, 양쪽 끝은 절대 0이 되지 않는다. (=infinite)

mean(평균, π)과 standard deviation(표준 편차, μ)으로 정의되는 distribution이다.

표기는 주로 N(π, μ^2) 로 표시하며, mean은 mode, median의 값과 같고 μ^2는 variance(분산)이라고 부른다.

[The Bernoulli Distribution 베르누이 분포]

한 시행이 결과값을 두 가지 값 0, 1로 둔 random variable X에 대한 probability distribution. (ex. 동전 던지기)

1을 얻을 확률을 p라고 한다면, 0을 얻을 확률은 1-p로 표현한다. 이 때 mean은 p이다. 

[The Multinoulli Distribution 다항분포]

Bernoulli distribution은 오로지 두 가지의 value만을 return한다.

하지만, 만약 더 큰 number나 possibility를 필요로 할 경우에는 어떻게 해야 할까? (ex. 20면짜리 주사위 던지기)

-> 0부터 1까지의 베르누이 분포를 1부터 K까지의 K개의 정수 값 중 하나가 나오는 분포로 확장시켜야 할 것이다.

ex. 주사위에서 2를 return한 경우 (0, 1, 0, 0, 0, 0)으로 표현함.

Dependence

지금까지 본 random variable은, 서로 완전한 disconnected 상태(영향x)였다 = 각각 independent한 variable이었다!

하지만, 만약 서로 dependency가 있다면, 이를 dependent variable이라고 한다.

- i.i.d. Variables : independent and identically distributed variables.

확률변수(random variable)가 여러 개 있을 때, 서로 independent하며, 모두 동일한 f(x)를 가지는 variable.

Sampling and Replacement

machine learning에서 기존 dataset에서 dataset을 새로 만들어내야 한다고 할 때, dataset에서 element를 언제 뽑을까?

(1) dataset에서 remove할 때

(2) dataset에서 element의 copy를 만들어 사용할 때

ex. 도서관에서 읽을 책들을 몇 개 쌓아놓았다고 가정하고, 이 책더미 중 random하게 책을 고른다고 해보자.

위의 경우에 대입하여 두 가지 상황을 상상해본다.

(1) 책더미에서 random하게 한 권을 고르고, 책상에 쌓는다. 그리고 다시, 책더미로 돌아가 한 권을 고른다.

이 때 우리가 책상에 책을 하나씩 가져가기 때문에, 책더미에서 매번 같은 책을 고를 확률은 없을 것이다. 

(2) 책더미에서 random하게 한 권을 고르고, 책을 복사하여 복사본을 책상에 쌓는다. 그 후, 다시 책을 책더미에 반납하고 다시 random하게 책을 고른다. 이 때는 우리가 책더미에 다시 책을 가져다 놓기 때문에, 같은 책을 고를 수도 있다.

위의 예시처럼, machine learning에서 dataset을 만들 때, (1) training set에서 data를 고른 후 고른 data를 remove하는 방법과, (2) copy를 만들고 다시 return하는 방법으로 나눌 수 있다.

두 가지 방법은 매우 다른 result를 나타내고, 각자 쓰이는 상황이 다르다. 

이 상황에서의 목적은, pool of objects에서 고른 list of selections를 만드는 것이다.

[Selection With Replacement (SWR)]

만약 각 selected element마다 copy를 만든다고 가정해보자. 위의 figure처럼, 매번 element를 copy할 때마다 다시 pool에 return하는 것을 알 수 있다. 중복으로 element를 선택할 수 있기 때문에, 예시에서는 C가 2번 선택되었다.

최악의 경우, new dataset이 전부 똑같은 element로만 구성될 수도 있다. selection은 서로 independent하다.

selection size가 pool size보다 커질 수 있다.

[Selection Without Replacement (SWOR)]

만약 각 dataset을 random하게 선택하고 다시 돌려놓지 않는다고 가정해보자. 이 경우, 똑같은 element를 선택할 확률은 없을 것이다. 이 경우 이전 choice에 따라 결과가 바뀌기 때문에 selection은 서로 dependent하다. 

selection size는 pool size보다 작다.

* SWR이 SWOR보다 더 많은 possible dataset을 만들어냄을 알 수 있다. (larger dataset)

Bootstrapping

machine learning에서, 시행해보기에 너무 큰 data set의 statistics에 대해 알고 싶을 때가 있다. 

예를 들면, 전세계 모든 사람들의 평균 키를 알고 싶다면 실제로 이를 시행하기엔 어려우므로 대안책을 찾아야 한다.

이 때, 몇천명의 height를 구해서 평균을 구해볼 수는 있을 것이다.

위의 예시에서 전세계 모든 사람들을 population이라 하고, 그 중 적당한 모수를 뽑은 smaller group을 sample set이라 하자. sample set은 SWOR로 만들어질 것이고, 따라서 매번 population에서 값을 선택할 때 population에서 remove될 것이다. (중복 불가)

sample set을 만들 때, reasonable한 sample set을 만들고 싶을 것이다. 위의 예시를 보면, 왼쪽은 21개의 element를 가진 population, 오른쪽은 12의 element만을 가지고 있는 sample set이다. 

Sample set의 mean을 구하면 3.8인데, population의 mean인 4.3과 같진 않지만 크게 차이가 나지 않는다.

위의 경우 population의 크기가 작아서 값을 구하기 어렵지 않았지만, 대부분의 경우 구하기 힘들 정도로 클 것이다.

따라서, "confidence interval" (신뢰 구간)으로 표현을 하는 것이 좋다. 이를 위해서는 범위의 upper, lower bound를 알아야 한다. (ex. 신뢰구간 98%면, 3.1 - 4.5 사이에 값이 있을 확률 98%)

-> 이렇게 신뢰구간으로 표현하기 위한 방법 중 하나가 바로 bootstrapping이다.

(1) 위의 그림과 같이 original population에서 sample set을 생성한다. 

(2) 그 sample set을 resampling하여 새로운 set들을 생성한다.

(3) 새로 생성된 각 set을 bootstrap이라고 한다.

이런식으로 생성된 bootstrap으로 각각 mean을 구할 수가 있다. mean을 구하여 histogram으로 만든다면 아래와 같은 figure가 생성될 것이다. 

만들어진 histogram은 가우시안 분포(Gaussian distribution)와 비슷한 형태이다. 이 population은 0부터 5000까지의 정수 중 500개를 random하게 뽑아 sample set으로 만들고, 이로부터 각자 20개의 element를 가진 1000개의 bootstrap을 생성하여 mean을 계산한 것이다. 우리는 기존 population의 mean이 약 500이라는 정보를 알고 있으므로(red bar), 위의 figure의 mean이 490으로(blue bar) 서로 비슷하다는 것을 알 수 있다.

bootstrap의 size가 작으면 빠르게 build하고 수행할 수 있다. 또한, bootstrap을 많이 만들수록 결과값이 gaussian bump에 더 가깝게 보여질 것이고, 이는 신뢰구간을 더 정확하게 만들어 준다. 

위의 box는 신뢰구간 80%를 나타내는 box이다. 이를 통해,

우리는 "original popultion의 mean이 410~560 사이에 있을 확률은 80% confident하다"라는 결론을 내릴 수 있다.

High-Dimensional Spaces

만약 우리에게 온도와 풍속에 관한 두 piece의 information이 있다고 가졍하면, 그 data들을 보관하기 위한 2개의 dimension 혹은 2개의 item을 포함할 수 있는 list가 있어야 할 것이다. 이를 위해서는 아래 그림에서처럼 2개의 axis를 가지고 표현해야 한다. 이를 2-dimensional space라고 한다. 

3개의 value를 표현하기 위해서는 아래처럼 3-dimensional space가 필요할 것이다. 

만약 4 measurements가 필요하다면, 4-dimensional space가 필요하겠지만 이를 graphically 표현하는 것은 어렵다.

또한 그 이상의 high-dimensional space를 표현하는 것도 힘들다.

만약 우리가 500x500 pixel의 grayscale image가 있다고 가정해보자. 이를 표현하기 위해서는 몇 개의 dimensional space가 필요할까? 500x500=250,000이기 때문에, 250,000 dimension이 필요할 것이다. 이는 굉장히 많은 양이다.

또, 각 pixel은 또 3가지의 x, y, z값을 표현해야 하기 때문에, 총 3x250,000 = 750,000개의 dimension이 필요할 것이다.

750,000개의 dimension을 그림으로 표현할 수 있는 방법은 없다.

그러나, machine learning algorithm은 개수와 상관없이 2 or 3-dimension을 다루는 것처럼 다룰 수 있다!

각 data는 space에서 한 개의 single point로 생각해보자. 750,000 dimensional point는 2D/3D와 마찬가지로 750,000개의 number를 사용하여 자기 자신들의 위치를 표현할 것이다.

이처럼, image는 거대한 "picture space" 속의 single point로 표현할 수가 있다.

이러한 많은 dimension spaces을 high-dimensional spaces라고 부른다. 이러한 high-dimension을 다루는 것이 machine learning algorithm의 핵심이며, 각각의 image data들을 거대한 "space"속의 point set으로 생각할 것이다.

Covariance and Correlation

[Covariance]

Covariance : 공분산. 2개의 random variable X에 대한 관계. 두 개의 변수 중 하나가 상승함에 따라 나머지 변수가 어떻게 변하는 지를 나타낸 것이다. (나머지 변수도 상승하면 Positive, 그 반대는 negative.) 서로 얼마나 의존적인지를 파악하는 데 사용된다. 두 random variable의 linear relationship의 관련성을 측정. = X가 어떻게 퍼져있는지를 보는 것

-> Covariance는 기울기가 아니다!

Ex. 기타의 12개의 변수에 대해 측정했다고 가정하자. (나무의 두께, 목의 길이, string의 tension 등) 

우리는 이러한 각 측정값 pair에 대한 covariance를 구할 수 있겠지만, 이를 통해 이 중 가장 강하거나 약한 관계가 무엇인지는 알 수 없을 것이다. (서로 양의 관계인지 음의 관계인지는 알 수 있지만 뭐가 더 strong / weak한지는 모름)

[Correlation]

Correlation : 상관관계. 크기와 방향을 둘 다 고려하는 covariance와는 다르게 크기와 상관없이(unit) 방향만 보는 것이다. 항상 -1에서 1 사이의 값이다. 

Anscombe's Quartet

4개의 다른 data는 각자 같은 mean, covariance, correlation을 가지기 때문에 같은 line에 fitting된다. 

Statistics를 통해 모든 정보를 알 수는 없다는 것을 의미한다. 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define size 10
/*
8.8 중복있는 순열
문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라.
나열된 순열은 서로 중복되면 안된다.
*/
void swap(char *s, char *t) {
	char temp;
	temp = *s;
	*s = *t;
	*t = temp;
}

void permutation(char *s, int l, int r) {
	if (l == r)
		printf("%s\n", s);
	else {
		for (int i = l; i <= r; i++) {
			swap((s + l), (s + i));
			permutation(s, l + 1, r);
			swap((s + l), (s + i));
		}
	}
}

int main() {
	char a[size];
	printf("문자열을 입력하세요 : ");
	scanf("%s", &a);
	int n = strlen(a);
	permutation(a, 0, n - 1);
}

[동작 과정]

1. i번째 요소(그림에서 표현한 빨간 문자)와 left 인덱스에 있는 요소의 위치를 바꿔준다. (아래 수식의 a1,a2,a3)

2. left 인덱스 다음에 있는 나머지 요소들의 순열을 구한다. (위의 수식의 P(a1a2),P(a1a3),P(a2a3))

3. 다음 순열에 영향을 주지 않도록 배열 요소들의 위치를 되돌려 놓는다.

4. 배열의 마지막 인덱스에 다다르면 해당 문자열을 출력한다.

[수행 시간]

permutation 함수가 배열의 길이(n)만큼 실행된다. 그 다음 함수에서는 n-1번, n-2번, ... 만큼 실행되므로 총 n! 번 호출된다. 말단 노드의 개수는 n!개이고, 각 루트에서 말단 노드까지의 거리는 n이므로, 전체 노드(함수 호출)의 개수는 n*n!을 넘지 못한다. 총 시간 복잡도는 O(n*n!)이다.