[ML 확률과 통계] 순열과 조합

오늘부터, 통계의 중요한 요점들에 대해서 공부하고 정리해보려한다.

가장 기본적인 통계 개념부터 부터 가볍게 지나치지않고 상세하게 정리해가보도록 하자.

 

 

먼저, 확률이란?

확률이란, 특정한 사건이 일어날 가능성을 수로 표현한것을 의미한다.

그리고, 확률은 0부터 1사이의 실수로 표현되는데, 어떤 사건에 대해 수치표현을 통해

객관적이고 합리적인 의사결정을 할 수 있는 근거가 된다.

 

 

기계학습 모델을 확률적으로 이해해보자

우리는 N개의 학습 데이터로 기계학습 모델을 학습한다.

이때, 일반적으로 기계학습 모델의 출력은'확률'형태를 띤다.

ex) image classification model

'θ'가 이미지 x에 대해서 0.75의 확률로 '고양이'일것이라고 예측했다.ex) text generation model 'θ'가 '나는 밥을' 이후에 '먹었다'라는 단어가 나올 확률을 0.42로 예측했다.

 

경우의 수

그리고, 확률을 이해하기 위해 '경우의 수'라는 개념을 먼저 이해해야한다.

그리고, 경우의 수를 계산하기 위한 방법으로는 순열(Permutation)과 조합(combination)이 있다.

순열과 조합을 하나씩 알아보자.

 

순열(Permutation)

서로 다른 n개에서 r개를 중복 없이 뽑아 특정한 순서로 나열하는 것을 의미한다.

다시 풀어쓰면, "서로다른 n개에서 r개를 뽑아 순서가 있게 나열하는 것"이라고 정리할 수 있다.

예를들어, a,b,c 세개의 알파벳중 2개를 뽑아 순서있게 나열하는 경우는 아래와 같다.

ab

ac

ba

bc

ca

cb

이처럼 나열할때, '나열하는 개수'를 '순열의 수'라고 한다.

즉, a,b,c 3개의 단어중 2개를 뽑는 순열의 수는 위의 6개라고 할 수 있다.

 

순열을 표현하는 방법이 여러가지라 헷갈릴 수 있는데, 아래와 같이 이해해보자.

용어	의미	예시
순열	순서가 있는 나열
n개에서 r개를 택하는 순열	n개에서 r개를 뽑아 순서있게 나열	a,b,c에서 2개를 뽑아 나열
순열의 수	순서가 있게 나열하는 경우의 수	a,b,c에서 2개를 뽑아 나열하는 경우의 수 : 6가지

 

우리는 지금 '순열'에 해당하는 케이스에서 경우의 수를 구해야하기때문에,

'순열의 수'를 좀 더 간편하게 구하는 방법을 확인해보자.

 

위 a,b,c에 대해 2개를 택하는 순열을 나열하는 경우를 다시 대입해보면,

'a'뒤에 올 단어는 'b'또는 'c'이며, 'a'는 당연히 중복해서 나올 수 없다.

마찬가지로, 'b'뒤에 나올 단어는 'a'또한 'c'이며, 'b'는 중복해서 나올 수 없다.

 

수식으로 바꿔보면,

첫번째 자리에 올 수 있는 경우의 수는 : n개

두번째 자리에 올 수 있는 경우의 수는 : n-1개

세번째 자리에 올 수 있는 경우의 수는 : n-2개

...

r번째 나올 수 있는 경우의 수는 : n-(r-1)개

즉, 이걸 이어붙이면, n x (n-1) x (n-2) x ... x n-(r-1) 의 공식이 완성된다.

 

순열은 'Permutation'이라고하는데, 앞 글자를 따서,

n개에서 r개를 뽑는 순열의 수를 구한다를 'nPr'이라고 표현할 수 있고,

순열의 수를 구하는 공식은 아래와 같이 요약 정의할 수 있다.

* nPr = n x (n-1) x (n-2) x ... x n-(r-1)

 

여기서 끝이 아니다. 위 공식을 '팩토리얼'이라는 개념으로 좀 더 간략하게 표현해보자.

(팩토리얼로 표현할 경우, 좀 더 식이 간결해지고, 계산이 편리해지기 때문이다.)

 

* nPr = n x (n-1) x (n-2) x ... x n-(r-1)

다시, 위 식의 우변은 몇개의 인수가 곱해져있을까?

바로 r개이다. n부터 1씩 줄어드는 배열이 r개가 있고, 이 r개의 인수가 곱해진것이다.

식을 간소화 하기 위해, 위 식의 우변 '분자'와 '분모'에 (n-r)!을 곱해보자.

 

분자는 n!과 같습니다. 따라서 아래와 같이 변형될 수 있다.

 

 

1) 순열의 수 공식(n = r 일때)

nPr = n! (n팩토리얼)

 

2) 순열의 수 공식(n!=r 일때)

참고)0!은 1이다.

 

그렇다면, 머신러닝 모델을 학습하는 과정에서 '순열'이라는 개념은 언제 활용될까?

위 그림과 같이 각 Epoch으로 model에 데이터가 input될때, 데이터는

매번 일정한 순서로 투입되지 않는다.

그리고, 데이터가 투입되는 경우의 수는 순열의 개념이 도입되어, 

nPn이 된다. 

 

python을 이용하면 간단하게 순열을 계산할 수 있다.

 

조합(Combination)

서로 다른 n개에서 r개를 중복없이 순서를 고려하지 않고 뽑는것을 의미한다.

'n개에서 r개를 뽑는 경우의 수'라는 개념은 순열과 동일하나, 순서를 고려하지 않고 뽑는다는 점에서 순열과 다르다.

아래의 그림을 통해 그 개념은 간단하게 이해할 수 있다.

 

마찬가지로, combination또한 python을 통해 간단하게 구현할 수 있다.

 

 

중복순열 (Permutation with Repetition)

서로 다른 n개에서 중복을 포함해 r개를 뽑아 특정한 순서로 나열하는 것을 의미한다.

모든 중복 순열의 수(경우의 수)는 다음의 공식으로 계산할 수 있다.

<중복 순열의 수 공식>

예시)

Q. 세 개의 숫자 1,2,3을 이용해 만들 수 있는 두자리의 자연수의 개수는?

(단 같은 숫자를 여러 번 사용하거나, 사용하지 않은 순자가 있어도 괜찮다. 본인을 포함하는 조합을 경우에 포함시키는 방법)

- 모든 경우 : 11, 12, 13, 21, 22, 23, 31, 32, 33

A. 경우의 수 : 3² = 9

 

python 으로 계산해보자

 

[Output]

 

중복조합 (Combination with Repetition)

• 서로 다른 n개에서 중복을 포함해 순서를 고려하지 않고, r개를 뽑는것을 의미한다.
• 모든 중복 조합의 수(경우의 수)는 다음의 공식으로 계산할 수 있다.
• 중복 조합의 수 공식

예시) 딥러닝에서는 학습된 여러 모델의 결과를 활용하여 최종적인 결과를 생성하는 앙상블(Ensemble)방법이 존재한다.

ensemble의 케이스에 대해서 조금 더 자세히 살펴보자.

[전제]

• 서로 다른 딥러닝 archetecture 1번, 2번, 3번이 존재한다. 
• 중복을 허용하여 4개를 골라서 딥러닝 모델 4개를 학습하고자 한다.

[문제]

이때, 가능한 학습의 모든 조합의 수는?

단, 같은 아키텍처를 여러번 사용하거나, 선택하지 않는 아키텍처가 있어도 된다.

이말인즉슨, 학습할 4개의 모델을 [1,2,3,1]로 선택할 수도 있고, 1번 archetecture를 학습하여 [1,1,1,1]도 가능하다.

학습 순서는 상관없기 때문에, [1,2,3,1]과 [1,2,1,3]은 같은 경우에 속한다.

 

위 케이스는 python을 통해서 간단하게 구할 수 있다.

 

[output]

 

 

 

Reference

1) Blog

https://hsm-edu.tistory.com/1484