[Bayesian] Bayesian Deep Learning - Set theory

본 자료는 edwith 최성준님이 강의하신 Bayesian Deep Learning 강의를 참고하였다.

 

핵심 키워드

$Settheory,Set,Element,Cardinality,Countable,Function,Mapping$

 

Set theory

---

$set$ / $element$ / $subset$ / $universalset$ / $setoperations$

대학교로 예를 들자면, $set$은 대학교를 지칭하고, 교수님, 자연계열 학생, 공대생 등등 그러면 $element$는 각 사람들에 해당하는 것이 될 것이고, $subset$은 수학과, 기계공학과 등 학과별 집합이 된다. $universalset$은 학교 내에 포함되는 모든 사람이라 볼 수 있다. $setoperations$은 이러한 집합들을 가지고 할 수 있는 연산이다. 수학과에 학생이 몇 명인가? 수학과의 학생이 40명 이상입니까? Yes or No 이런 것들 모두 $setoperations$라고 할 수 있다. 

 

disjoint set : $A\cap B=\mathrm{\varnothing }$  두 개의 set 사이에 교집합이 없으면 disjoint set이 된다.

 

partition of $A$

      example :$A=\{1,2,3,4\},$ partition of $A:\{1,2,3,4\}$겹치지 않는 $\mathrm{\Sigma }subset=universalset$

 

Cartesian product : $A\times B=\{(a,b):a\in A,b\in B\}$

     $A$와 $B$에서 각각의 $a,b$ 를 가져오고 그 값들의 쌍을 Cartesian Product라 부른다. $e.g.$ 2차원 공간

     example : $A$ = { 1, 2 }, B = { 3, 5 }  $\Rightarrow$ $A\times B=\{(1,3),(1,5),(2,3),(2,5)\}$

  

power set : $2_A$ = the set of all the $subsets$ of $A$

     example : $A=\{1,2,3\}$

     $2^A=\{\mathrm{\varnothing },\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{12,3\}\}$

 

 

 

 

 

Cardinality

---

$|A|:$ finite, infinite, countable, uncountable, denumerable(countably infinite)

finite인 경우는 큰 문제가 되지 않는다. 하지만 그 뒤로 갈수록 이상해지기 시작한다. 정수의 개수와 실수의 개수는 infinite하지만 두 infinite값이 같진 않다. 왜 아닌지에 대해서는 뒤에서 증명할 것이다. 

 

- $|A|=m,|B|=n\Rightarrow |A\times B|=mn$

 

- $|A|=n\Rightarrow |2^A|=2^n$

 

- If there exists one-to-one correspondence between to sets, they have the same cardinality.

 

countable : There is one-to-one correspondence between the set and a set of natural numbers

natrual numbers와 일대일 대응이 이루어 진다면 그 $set$을 countable 이라고 부른다.

 

Are the set of all integers and the set of all rational numbers countable? Yes

 

두 $set$의 cardinality 는 같다.

 

 

denumerable : countably infinite $e.i.$  ${\mathrm{\aleph }}_0$ 이라고 부른다. 

 

uncountable : continuum $e.i.$  $c=2^{{\mathrm{\aleph }}_0}$

    The smallest known uncountable set is $(0,1)$ or $\mathbb{R}$ denoted by $c$

 

$e.g.$ 

Show that the cardinality of $C$ = [0, 1] is uncountable ( Cantor's diagonal argument )

 

$proof)$

1. Suppose that $C$ is countable.

2. Then there exists a sequence $S=\{x_1,x_2,x_3,...\}$ such that all elements in $C$ are coverd.

3. We can represent each $x_i$ using a binary system.

$x_1=0.d_{11}{d}_{12}{d}_{13}...$

 

$x_2=0.d_{21}{d}_{22}{d}_{23}...$

 

$x_3=0.d_{31}{d}_{32}{d}_{33}...$

where $d_{ij}\in \{0,1\}$

만약 $S$가 모든 실수들의 집합을 커버할 수 있다면 $S$가 countable 하다는 것을 증명할 수 있다.

4. Define $x_{new}=0.\overline{d_1}\overline{d_2}\overline{d_3}...$ such that $\overline{d_i}$ = 1 - $d_{ii}$.

5. Clearly, $x_{new}$ does not appear in $S$, which is a contraction. So $C$ must be uncountable.

 

 

Then what is the number of real numbers between 0 and 1?

 

1. We can represent a real number between 0 and 1 using a binary system.

 

$r_1=0.d_{11}{d}_{12}{d}_{13}...$

 

$r_2=0.d_{21}{d}_{22}{d}_{23}...$

 

$r_3=0.d_{31}{d}_{32}{d}_{33}...$

where $d_{ij}\in \{0,1\}$

 

2. To fully distinguish a real number $r_i$ , we need ${\mathrm{\aleph }}_0$ bits where ${\mathrm{\aleph }}_0$ is the number of all integers.

3. $\because$ $c$= $2^{\mathrm{\aleph }}$ ( uncountable )

 

이로써 integer, real number 모두 infinite하지만 집합들의 개수에 대해서는 차이가 있음을 확인할 수 있다.

 

 

 

 

Function or mapping $f:U\to V$

---

domain : $U$, codomain : $V$

image $f(A)=\{f(x)\in V:x\in A\},A\subseteq U$

range : $f(U)$

inverse image or preimage : $f_{-1}(B)=\{x\in U,f(x)\in B\},A\subseteq U$

우리가 실제로 많이 다루는 문제는 inverse image, preimage 다. 강아지에서 라벨을 찾고, 이 사진이 강아지일지 고양이일지 찾는 것이 preimage와 유사하다.

 

one-to-one or injective : $f(a)=f(b)\Rightarrow a=b$

onto or surjective : $f(U)=V$

inverible or bijective : one-to-one and onto