[Bayesian] Bayesian Deep Learning - Set theory

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

 

핵심 키워드

$Set\ theory,\ Set,\ Element,\ Cardinality,\ Countable,\ Function,\ Mapping $

 

Set theory

---

$set$ / $element$ / $subset$ / $universal\ set$ / $set\ operations$

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

 

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

 

partition of $A$

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

 

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} = \{\ \emptyset, \{1\}, \{2\}, \{3\}, \{1,\ 2\}, \{1,\ 3\}, \{2,\ 3\}, \{1\ 2,\ 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.$  $\aleph_{0}$ 이라고 부른다. 

 

uncountable : continuum $e.i.$  $c = 2^{\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.\bar{d_{1}}\bar{d_{2}}\bar{d_{3}}. . . $ such that $\bar{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 $\aleph_{0}$ bits where $\aleph_{0}$ is the number of all integers.

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

 

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

 

 

 

 

Function or mapping $f : U \rightarrow 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