블로그 이미지
두번째 블로그, 조금은 개인적인 공간;ㅅ;
메시에

태그목록

공지사항

최근에 달린 댓글

글 보관함

calendar

          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30

<Group에 대하여>

 

* Order of Group (|G|) : Group의 원소 개수.

 

ex) | <Zp*, *> |  =  p-1

(소수에 대해서는 모두 역원이 존재하므로. 단 0은 제외이므로 -1)

 

* Properties of Group

- 항등원은 유일하다.

- 역원은 각 원소에 대해서 유일하다.

 

- cancellation property : ab = ac => b = c / ba = ca => b = c

proof -- a의 역원을 양변의 앞에 곱해주면 a가 날아감.

 

* Subgroup

- G에서 원소 몇개 빼내서 만든 집합 H가 Group이면 H는 G의 서브그룹.

 

ex) G = <Z6, +>   H = {0,2,4}   --  H는 G의 Subgroup

    (Z6에서 2의 역원은 4, 4의 역원은 2...)

 

* Subgroup Condition

- 닫혀있고 Inverse가 존재하면 서브그룹이다.

- 사실은 닫혀있기만 해도 서브그룹이다. (증명?)

 

* Direct Product of Group

 

 

* Powers of Elements

 

 

* Homomorphism / Isomorphism

- f : Z => Z4와 같이 한 그룹에서 다른 그룹으로 향하는 함수가 있을 때.

Z에서 항등원인게 Z4에서도 항등원이고, Z에서 역원인게 Z4에서도 역원이고... 등등

연산관계가 똑같이 적용되는 경우에, Homomorphism.

 

- 여기에 역함수도 존재 (역으로 맵핑이 성립) 하는 경우 => Isomorphism.

- 두 집합이 같은 경우 => Endomorphism.

 

 

* Cuclic Group

 

 

* Order of Elements

* Pairs of R.V?

- X, Y 두 개의 확률 변수 사이의 관계에 주목한다.

 

* Joint CDF

- F(x,y) = Pr(X<=x, Y<=y)

- Properties

ㄴ x, y 둘 중 하나라도 마이너스 무한대 => 0

ㄴ 둘 다 무한대 => 1

ㄴ 항상 0과 1 사이의 값을 가짐

ㄴ Pr(x1<X<x2, y1<Y<y2) = F(x2, y2) - F(x1, y2) - F(x2, y1) + F(x1, y1) -- 그림으로 보기

ㄴ Marginal CDF : F(x, 무한대) = F(x), F(무한대, y) = F(y)                   -- 그림으로 보기

 

ex) Uniform (unit square) -- 0<x<1, 0<y<1

 

Joint CDF ::

F(x,y) = 1 (x>1, y>1)

         = 0  (x<0 or y<0)

         = xy (0<x<1, 0<y<1)  --  Joint

   = x  (0<x<1, y>1)  --  Marginal

   = y  (x>1, 0<y<1)  --  Marginal

 

* Joint PDF : Joint CDF를 x, y에 대해서 한번씩 편미분

ex) 위의 예제의 Joint CDF = xy  -->  Joint PDF = 1

ex) 위와 같은 Uniform 분포이나 Unit Square가 아니라 가로 x, 세로 y인 경우?

    -> 면적분했을 때 1이 되어야 함 (Joint CDF) -> Joint PDF = 1/ab

 

- Marginal PDF : f(x)는 f(x,y) 을 y에 대해서 마이너스 무한대부터 무한대까지 적분하여 얻음

 

* Marginal PDF가 두 개 주어진다고 해서 원래의 Joint PDF를 알 수는 없다.

counterexample : Marginal이 같은데 Joint가 다른 경우가 존재.

 

* Joint PMF

 

* Joint PMF, PDF의 Conditional Distribution

:: Joint / Marginal.

다른 하나의 변수가 Condition이 됨

 

11/19 인행심 - 기억

2013.11.19 15:11 | Posted by 메시에

* 기억의 3단계 : 부호화, 저장, 인출

 

* 무엇을 부호화하는가?

- 의미를 부호화                       (ex) 아이, 담배꽁초 사진

- 이미지를 부호화                    (ex) 햇빛 사진

- 정보를 마음속에서 체제화       (ex) 예술관 천장 사진 - 교수님이 설명해주셔서 더 기억남

 

* 세밀한 수준의 부호화 -> 더 기억에 잘 남음.

 

* 시각부호화, 청각부호화, 의미부호화

- 여러가지 방법을 섞어서 적용할수록 더 기억에 잘 남음.

 

* 기억술

- 장소법

- 연상법

- 청크 만들기

ex) 1945727248791988 -> 1945 / 7272 / 4879 / 1988 이렇게 끊어서 외우면 쉽게 외울 수 있음.

- 위계

 

 

* 저장 : 정보의 파지

- 기억의 세 저장소 : 감각기억 / 작업기억 (단기기억) / 장기기억

- 컴퓨터로 따지면 작업기억은 RAM, 장기기억은 하드 디스크

- 하지만 인간의 뇌는 하드디스크처럼 확장할 수 있는 것이 아니다.

 -> 망각을 통해 비우고, 다시 채우고...

 

 

* 인출

- 기억 측정법 : 재인 / 회상 / 재학습

재인 (재인지) : 어제 담배꽁초 사진을 본 적이 있니?

회상 : 어제 본 사진이 무슨 사진이었니?

재학습 : 담배꽁초 사진을 다시 보여준다.

 

- 인출 단서

> 맥락효과 : 물속에서 들었던 단어는 물속에서 더 잘 기억난다.

                  초등학교 시절의 추억은 초등학교에 직접 가보면 더 잘 기억난다.

> 기분과 기억 : 강렬한 경험이나 기분의 변화를 일으킨 사건 -> 더 잘 기억난다.

  cf) PTSD : 기억력 저하를 동반

 

 

* 망각 : 부호화 / 저장 / 인출의 실패

- 부호화 실패 : 주의깊게 관찰하지 않았을 경우, 등등

- 저장 소멸 : 에빙하우스의 망각곡선

                  (새로운 정보의 기억은 급속하게 사라진 후 일정 수준을 유지)

- 인출 실패 : 외부 자극이나 간섭에 의해서

> 설단현상 : 뭐더라... 기억날 것 같은데... 이러다가 초성 주면 딱 기억남. (혀끝에서 맴돔)

> 순행간섭 : 이전의 기억이 새로운 것의 학습을 방해.

> 역행간섭 : 새로운 정보가 이전 기억의 회상을 방해.

 cf) 순행/역행성 기억장애?

* Minimum Cost Spanning Tree

 

1. Kruskal's Algorithm

 

- cost가 가장 작은 edge 순으로 선택해 나가서 모든 node를 연결한다.

- edge를 cost 작은 순으로 정렬, 또는 min-heap을 만든다.

 

2. Prim's Algorithm

 

- 초기 상태 : Set A = 출발점 노드

- Set A에서 Set A의 밖에 있는 노드 사이를 잇는 edge들 중에서 cost가 가장 작은 것을 선택하여 연결, 연결된 노드는 Set A에 추가

- 위 과정을 반복하여 모든 노드를 Set A에 넣으면 종료.

 

3. Sollin's Algorithm

 

Step 1)

- 모든 노드가 edge에 연결될 때까지 cost가 작은 순으로 edge를 뽑는다.

- 단, edge가 이어주는 두 노드가 이미 다른 edge에 연결되어 있다면 뽑지 않는다.

 

Step 2)

- Step 1의 결과로 나온 서브그래프들을 잇는다. (cost가 가장 작은 edge 순으로)

 

 

* Shortest Path Problem

 

- Prim's Algorithm의 응용으로, 이미 방문한 노드를 Set에 넣고 다음 노드로 갔을 때의 각 경로별 cost를 따져보면서 진행.

 

* Thm 3. Zn이 Field  <==>  n이 prime number.

 

proof)

n이 소수고 0<a<n인 a가 있다 하자.

n이 소수이므로 GCD (a,n) = 1. 즉 a와 n은 서로소이다.        

그러면, Bezout's Identity에 의해 as + tn = 1이 되는 s, t가 존재한다.

그러면 as == 1 (mod n)

즉 a의 역원이 되는 s가 반드시 존재하고 a는 unit이 됨.

곱셈에 대한 역원이 존재하므로 field이다.

 

* n이 prime이 아니면, field가 될 수 없다.

- n이 소수가 아니므로 n = n1 * n2, 1<n1, n2<n 인 n1, n2가 존재.

  [n1] != 0, [n2] != 0 이지만 [n1*n2] = [0] 이 될 수 있다. (Zero Divisor가 존재한다)

  따라서 Field는 물론 Integral Domain도 될 수 없다.

 


* Thm 4. [a] : unit  <==>  GCD (a,n) = 1

- [a] 가 unit이다 -> ab = 1 + qn. 

  그런데 a, n 사이에는 공통인수 (common factor) 가 없다. -> a, n은 서로소다.

                         

<Bezout's Identity>

- a, n이 서로소다 -> 1 = au + nv, [u] 가 [a] 의 역원이 되어주므로 [a] 는 unit.

 

 

* Euler's Phi Function

: RSA (공개 키 암호) 기법 등에 응용됨.

 

- residues (나머지) : 0, 1, 2, ..., n-1

- 나머지 중에서 n이랑 서로소인 원소들의 집합 : reduced set of residues

- R.S of residues의 원소 개수 = Euler Phi Func.

 

ex : Phi(10) = 4 (1,3,7,9)

 

 

- GCD (m,n) = 1  =>  Phi(mn) = Phi(m) * Phi(n)

 

 

* Zn* VS. Phi(n)

- Def) Zn* = {[m] | GCD(m,n)=1, 1<=m<=n}

         곱셈에 대한 역원이 존재하는, 즉 n이랑 서로소인 m들의 집합.

 

- |Zn*| = Phi (n).

 

 

 

 

 

1. Scalar Quantization (양자화)

 

* 아날로그 데이터 -> 디지털 데이터로 변환하는 과정

 

1) Sampling : continuous한 시간축을 discrete하게 변환

                   나이키스트 샘플링 이론 (원래 주파수의 2배로 샘플링하면 손실 X)

 

2) Scalar Quantization (양자화) : continuous한 value를 discrete하게 변환

   : Information Loss가 불가피.

 

3) Encoding

 

- Quantization의 예

: 4 bit를 사용해서 양자화한다고 했을 때 값은 0~15 중 하나가 될 수 있음.

  값이 9.2라면 -> 9로 변환. (0.2 손실)

 

 

 

 

* 양자화를 위한 척도

 

- 가능한 한 값의 손실을 적게 할 수 있다면 좋겠다.

 

- Signal Distortion

   d = E[(X-q(X))^2]

 

- SQNR (Signal to Quantization Noise power Ratio) : 이게 작을수록 손실이 적다는 뜻.

  SQNR = E[X^2] / d

                   ㄴ Second Moment

 

- 데시벨 (Decibel) : 10 * log    PowerX / PowerY

                                       10

                             3dB가 높아지면 신호 품질이 두 배.

 

 

 

* Scalar Quantization에서의 척도 계산 예 : Linear Quantization에서

 

- X ~ Uniform (-a/2, a/2), PDF : 1/a

 

- Linear Quantization? : 각 구간을 균등하게 나눔.

 

- 3비트 양자화라고 했을 때

  ㄴ (-a/2, a/2) 구간을 8개의 소구간으로 나눈다.

  ㄴ 각 소구간의 중앙값이 그 구간의 value가 된다.

 

- SQNR의 계산 (필기 참고)

  : E[X^2] 구하기 (적분), d 구하기 (Conditional Expected Value, Thm. of Total Prob.)

 

 

* Thm. of Optimum Quantization

 

- Linear Quantization이 언제나 적합한가?

 : 특정 부분에만 신호가 조밀하게 모여있다면 그 구간을 잘게 자르고

   신호가 별로 없는 부분은 넓게 자르는 것이 더 효율적일 것이다.

 : 사람의 목소리 신호는 Laplace Distribution으로 모형화

 

- 최적의 양자화를 위한 방법

: d의 극소값을 구한다 -> 편미분을 통해 도출

 

1) Conditional mean criterion

(x0, x1) 구간의 양자화 값 y0은 (x0, x1) 구간의 평균값이 되어야 한다.

 

2) Midpoint criterion

구간 구분선 x1의 위치는 양쪽의 양자화 값 y0, y1의 중앙값이 되어야 한다.

 

=> x를 구하려면 y 두 개를 알아야 하고 y를 구하려면 x 두 개를 알아야 한다.

=> 연립방정식.

 

- 여기서 나오는 연립방정식을 Analytical한 방법으로 풀기는 어려우므로

  MATLAB 등으로 계산.

 

 

* 예 : Input은 라플라스 분포, n-bit Quantizer의 경우 

- 라플라스 분포의 대칭성을 이용, 양의 값에 M Level 음의 값에 M Level 총 2M Level 할당

 

- n-bit => 2^n 개의 양자화 Level을 가짐. 즉 2^n = 2M

 

- n이 커지면 직접 계산하는 것은 거의 불가능, MATLAB 이용

 

- 처음에는 구분선 x의 값을 Uniform이라 가정하고 임의로 할당

 -> y를 구한다 -> 그 y를 기준으로 x를 다시 구한다 -> ...

 -> 반복하면 최적의 값으로 수렴하게 됨.

 

 

 

2. Entropy & Source Coding

: 정보를 Code로 표현 -> 더 적은 Data 양으로 많은 정보를 표현하고 싶다!

 

 

* 정량적인 정보 (Information) 의 정의

 

- 정보의 양을 확률과 연관지어 생각

 

- 정보란? 어떤 event에 대한 function

 

- 정보의 양이란? probability of the event

  : 그 정보에 대한 사건이 적게 발생한다면 희귀한 정보 -> 정보의 양이 많은 것.

 

- I (A) = -log (pA)

 

 

* 엔트로피 (Entropy)

 

- 정보 양의 Average

 

- H (X) = <k=0부터 n-1까지 모두 더하기> Pr(X=k) * I (X=k)

           =                 ''                          Pk * log (1/Pk)    

 // Pk란 그 정보에 대한 사건이 발생할 확률

 

* 예 : X=0 또는 X=1이 각각 p, 1-p 확률로 발생

 

H (X) = p * log(1/p)  +  (1-p) * log(1/1-p)

 

- 항상 0이나 1만 발생 => H(X) = 0, 즉 정보가 없는 것.

 

- Entropy가 최대치가 될 때는? => p = 0.5 일 때.

 

 

* Source Coding과 Entropy : Entropy Coding (Variable-Length Coding)

 

- a,b,c,d 네 개의 출력이 있을 때 어떻게 코드 할당을 할 것인가?

 

- a가 나올 확률이 1/2, b는 1/4, c와 d는 1/8이라 했을 때

               a    b    c    d               평균 사용 Bit 수 ( = Entropy )

Code 1  :  00   01  10  11                        2

Code 2  :   0   10  110 111                     1.75 (H(X) 계산에 의해서)

 

Code 2가 더 효율적인 코드 할당이다.

 

- 자주 나오는 정보는 더 적은 심볼로 할당, 잘 안나오는 정보는 많이 할당해도 됨.

 

- Code 3 : 0 1 10 01

이런 건 문제가 있는 코드. 0이 나왔을 때 a인지 d인지 구별을 못함.

Exceptrion이란?

 : Detect & Handling이 가능한 Error.

 : Error != Exception. Exception은 Error의 부분집합.

 

A ---> B  ::  B가 Exception을 확인

B ---> A  ::  신호 'e' 를 보내줌

A  ::  예외를 적절하게 처리

 

 

예외 처리 방법?

 : 프로그램을 종료 or 복구.

 : 에러 메시지 출력, 해당 플로우 스킵 등.

 

 

Java에서의 예외 처리 방법

- try / catch 문

 : try 안의 내용을 실행하다가, 예외가 발생하면 catch로 넘어가 예외 처리

 : DETECT and HANDLE.

 

cf) finally : try / catch와 함께 사용되어, 예외가 발생하든 안하든 항상 실행되는 코드 영역

 

- throws

 : 메서드 옆에 붙임 -> 메서드가 실행 중 예외가 발생하면 에러 띄우고 종료

 : 예외 상황을 '처리' 하지는 못함, just DETECT.

 : 얘가 예외가 발생했음을 알려주면 try / catch 문에서 처리하는 방법 등을 사용

 

- throw e;

 : 예외가 발생했음을 알려줘서 예외 처리 부분으로 이동

 : throws가 붙은 메서드 안에 사용되어, main에 예외 e를 던져줌 -> main에서 핸들링 등

 

    try{
        if(check[i-1] == 1)
             throw new LoopException();            // 예외가 발생한 경우
        check[i-1] = 1;
        i = Integer.valueOf(arr.get(i-1));
        continue;
    }catch(LoopException ee){                       // 여기로 이동.
         ps.println(ee.getMessage());
         break;
    }

 

 

* Pre-Defined Exceptions & User-Defined Exceptions

- 이미 정의되어 있는 예외들 (Bulit-In)

 : Exception (최상위 클래스), IOException, NumberException, IndexOutOfBoundsException

   ...

 

- 유저 정의 예외처리

 : Exception 클래스의 서브클래스로 정의

 

class LoopException extends Exception{
 public LoopException()
 {
  super("LOOP");                            // ee.getMessage에 의해 LOOP를 출력
 }
}

 

 

* try / catch Block의 사용 순서

 : 더 범위가 작은 것부터 먼저 처리하도록 설계

 : 반대로 설계하면 Dead Code (절대 플로우가 닿지 않는 쓸모없는 코드) 가 발생할 수 있음

 

try{

...

}catch (TooSmallException e){      

  ...

}catch (NumberException e){

  ...

}

 

// TooSmallException이 NumberException의 서브클래스이기 때문에,

    NumberException이 위에 있으면 크던 작던 얘가 다 처리해버림.

 

 

이전 1 다음