페이지

2024년 9월 30일 월요일

Circom으로 영지식 증명 시작하기

Circom으로 영지식 증명 시작하기

Circom 2 Getting started 문서를 따라하면서 작성한 문서입니다.

  • 실습 환경: Windows 11

1. 소프트웨어 설치

  1. Downloads 페이지에서 circom Windows binary를 클릭하고 파일 circom-windows-amd64.exe 를 원하는 디렉토리에 저장합니다. 여기서는 파일 이름을 circom.exe로 바꾸고 아래 경로에 저장합니다.
    C:\DevTools\circom.exe
    
  2. snarkjs를 설치합니다.
    npm install -g snarkjs
    

2. circuit 생성하기

  1. 아래 내용을 multiplier2.circom 에 저장합니다.

    pragma circom 2.0.0;
    
    /*This circuit template checks that c is the multiplication of a and b.*/  
    
    template Multiplier2 () {
       // Declaration of signals.
       signal input a;
       signal input b;
       signal output c;
    
       // Constraints.
       c <== a * b;
    }
    
    component main = Multiplier2();
    

3. circuit 컴파일하기

  1. multiplier2.circom 파일을 컴파일합니다.

    circom multiplier2.circom --r1cs --wasm --sym --c
    

    컴파일 결과 다음과 같은 파일들이 생성됩니다.

    multiplier2.r1cs
    multiplier2.sym
    multiplier2_cpp\
        calcwit.cpp
        calcwit.hpp
        circom.hpp
        fr.asm
        fr.cpp
        fr.hpp
        main.cpp
        Makefile
        multiplier2.cpp
        multiplier2.dat
    multiplier2_js\
        generate_witness.js
        multiplier2.wasm
        witness_calculator.js
    

4. witness 계산하기

입력 값, 중간 신호, 출력 값을 witness라고 합니다.

  1. multiplier2_js 디렉토리로 이동합니다.

    cd multiplier2_js
    
  2. 아래 내용을 input.json 파일에 저장합니다.

    {"a": "3", "b": "11"}
    
  3. witness를 계산하여 witness.wtns 파일에 저장합니다.

    node generate_witness.js multiplier2.wasm input.json witness.wtns
    

5. circuit을 영지식으로 증명하기

증명을 생성하기 위하여 아래 두 파일을 사용합니다.

  • multiplier2.r1cs: 회로를 기술하는 제약사항 포함
  • witness.wtns: 모든 계산된 신호 값 포함

여기서는 Groth16 zk-SNARK 프로토콜을 사용하고자 합니다. 이 프로토콜은 trusted setup을 필요로 하고 이 과정은 두 단계로 구성됩니다.

  • Powers of tau - circuit에 독립적
  • Phase 2 - circuit에 의존적
5.1. Powers of Tau
  1. “powers of tau” ceremony 시작

    snarkjs powersoftau new bn128 12 pot12_0000.ptau -v
    
  2. ceremony에 기여

    snarkjs powersoftau contribute pot12_0000.ptau pot12_0001.ptau --name="First contribution" -v
    
5.2. Phase 2
  1. Phase 생성

    snarkjs powersoftau prepare phase2 pot12_0001.ptau pot12_final.ptau -v
    
  2. .r1cs 파일과 연관된 .zkey 파일 생성

    snarkjs groth16 setup ..\multiplier2.r1cs pot12_final.ptau multiplier2_0000.zkey
    
  3. ceremony의 phase 2에 기여

    snarkjs zkey contribute multiplier2_0000.zkey multiplier2_0001.zkey --name="1st Contributor Name" -v
    
  4. verification key 내보내기

    snarkjs zkey export verificationkey multiplier2_0001.zkey verification_key.json
    
5.3. 증명 생성
  1. circuit 및 witness와 연관된 증명을 생성합니다.

    snarkjs groth16 prove multiplier2_0001.zkey witness.wtns proof.json public.json
    

    위 명령은 다음 두 파일을 생성합니다.

    • proof.json: 증명 포함
      {
       "pi_a": [
        "13983182679953556458842508347137149918023927201985471435159758927740558853016",
        "17126988695844741179284716898691257368385629126542168835554345497343624722940",
        "1"
       ],
       "pi_b": [
        [
         "19140696255248677436910729284929621534969442224058440363361064354121562854264",
         "14257009146984576436317952378148206632799369157719061977972167958840456095938"
        ],
        [
         "7733560110556055181607998374149392520454003067800483949057392794063019344423",
         "2891268127818819654691304244486325795969498402824384674233464052246905803426"
        ],
        [
         "1",
         "0"
        ]
       ],
       "pi_c": [
        "21608704327549608970596366226125688092932784974035385756433099903167703539664",
        "19614360261086173764968380312474156102058426242974580364381559870892304372835",
        "1"
       ],
       "protocol": "groth16",
       "curve": "bn128"
      }
      
    • public.json: 공개 입력 및 출력 값 포함
      [
      	"33"
      ]
      
5.4. 증명 검증
  1. 아래 명령을 수행하여 증명을 검증합니다.

    snarkjs groth16 verify verification_key.json public.json proof.json
    

    위 명령의 수행 결과는 다음과 같습니다.

    [INFO]  snarkJS: OK!
    

6. 정리

실습을 정상적으로 마쳤을 때 multiplier2_js 디렉토리의 파일 목록은 다음과 같습니다.

generate_witness.js
input.json
multiplier2.wasm
multiplier2_0000.zkey
multiplier2_0001.zkey
pot12_0000.ptau
pot12_0001.ptau
pot12_final.ptau
proof.json
public.json
verification_key.json
witness.wtns
witness_calculator.js

Written with StackEdit.

2024년 7월 27일 토요일

카이제곱 검정 제대로 이해하기

카이제곱 검정 제대로 이해하기

1. 개념 이해

비교란 무엇인가?

비교의 대상은 두 개이고 두 비교 대상의 차이를 살펴 보는 것이다.

  • 여기서는 관찰값기댓값의 차이를 사용한다.
    • 관찰값: 관찰을 통해 얻는 값
    • 기댓값: 관찰값에 대한 기댓값으로서 어떤 가정을 바탕으로 함.
  • 두 비교 대상에 대하여 비교할 수 있는 지점은 한 개일 수도 있고 여러 개일 수도 있다.

비교의 목적은 무엇인가?

  • 관찰값관찰값을 비교 대상으로 삼을 수는 없는가?
    • 비교할 수 있다. 그런데 어떻게 비교할 것인가?
      • 기댓값을 찾고 관찰값들이 기댓값을 중심으로 어떤 분포를 따르는지 이해하는 것이 필요하다.
        • 왜 그런가?
          • 분포를 가정하지 않으면 흔히 일어나는 차이인지 아니면 드물게 일어나는 차이인지 객관적으로 표현하기가 어렵다.
  • 기댓값을 찾으려면 왜 그런 기대를 하게 되었는지와 관련하여 어떤 가정을 세워야 한다.
    • 그 가정 위에서 기댓값을 구하고 차이를 계산했더니 흔히 일어나는 차이에 해당하면 그 가정은 유효하다고 간주하고 드물게 일어나는 차이에 해당하면 그 가정은 유효하지 않다고 간주한다.
    • 결국 관찰값과 기댓값의 차이를 통해 가정이 유효한지 아닌지 판단하는 것이므로 비교의 목적은 어떤 가정을 채택할 것인지 버릴 것인지를 판단하기 위함이라고 말할 수 있다.

2. 차이의 정도와 의미

차이의 정도를 수치로 나타낼 수 있는가?

비교 대상 간의 총체적인 차이는 무엇으로 정의할 것인가?

  • 개별 데이터 지점에서의 차이 값의 제곱의 합이라고 정의하자. 절대값의 합이 아니라 제곱의 합으로 정의한 이유는 수학적으로 다루기가 훨씬 쉽기 때문일 것이다.
  • 아래의 수식은 피어슨 카이제곱 통계량이고 이것으로 총체적인 차이를 계산한다. OiO_iii번째 데이터 지점에서의 관찰값, EiE_iii번째 데이터 지점에서의 기댓값을 나타낸다.

χ2=i=1m(OiEi)2Ei(1) \chi^2 = \sum_{i=1}^{m} \frac {(O_i-E_i)^2}{E_i} \tag{1}

특정 값의 총체적인 차이가 발생할 가능성은?

  • 차이의 정도에 대한 가정
    • 개별 데이터 지점에서 관찰값기댓값의 차이의 정도는 확률변수이고 정규분포를 따른다.
      • 오차에 대한 가정을 주로 이렇게 한다는 점을 참고하자.
      • 편차 제곱을 기댓값으로 나눔으로써 표준화를 시도한다.
    • 모든 데이터 지점에서 기댓값은 5 이상이어야 한다.
      • 대표본 가정
  • 그렇다면 총체적인 차이가 특정 값 이상일 가능성은?
    • 총체적인 차이 값은 확률변수이고 자유도를 파라미터로 하는 카이제곱 분포를 따른다.
      • 좀 더 정확하게 표현하자면 이런 경우의 분포를 카이제곱 분포라고 정의한 것이다.
    • 카이제곱 분포표에서 자유도와 유의수준에 해당하는 카이제곱 값을 찾을 수 있다.
      • 총체적인 차이가 카이제곱 분포표에서 찾은 카이제곱 값보다 작으면 흔히 일어날 수 있는 차이로 간주하고 그렇지 않으면 쉽게 일어나기 어려운 차이로 간주한다.

차이의 정도가 유의미한가?

  1. 유의수준 α\alpha를 설정한다. 여기서는 α=0.05\alpha = 0.05로 하자.
  2. 자유도가 얼마인지 파악한다.
  3. 개별 데이터 지점에 대하여 기댓값을 파악하거나 계산한다.
  4. 피어슨 카이제곱 통계량을 계산한다.
  5. 카이제곱 분포표에서 자유도유의수준에 해당하는 카이제곱 값을 찾는다.
  6. 계산한 카이제곱 값이 분포표에서 찾은 카이제곱 값보다
    • 작으면 차이가 유의미하지 않다고 보고 대립가설을 기각한다.
    • 크면 차이가 유의미하다고 간주하고 대립가설을 채택한다.

차이가 유의미하다는 것은 무슨 뜻인가?

검정 목적별로 해석을 달리한다.

  • 적합도 검정 (Goodness-of-fit Test)
    • 주머니속 사탕 색깔의 구성 비율이 특정 비율을 따르는지? ⇒ 구성 비율에 대한 추측이 사실이 아닐 가능성이 높다.
  • 동질성 검정 (Test of Homogeneity)
    • 성별에 따른 메뉴 선호도가 유사한지? ⇒ 성별에 따른 메뉴 선호도가 유사하지 않을 가능성이 높다.
  • 독립성 검정 (Test of Independence)
    • 성별과 메뉴 선호도가 서로 관련이 없는지? ⇒ 성별과 메뉴 선호도가 서로 관련이 있을 가능성이 높다.

다음 두 가지 설명이 동질성 검정과 독립성 검정의 차이를 이해하는데 도움이 될 것이다.

  • 독립성 검정의 결과
    • 서로 관련이 없다.
      • 동질성 검정 필요 없음
    • 서로 관련이 있다.
      • 동질성 검정의 결과
        • 유사하다.
        • 유사하지 않다.
          • 서로 관련은 있으나 유사하지는 않은 경우
            • 예를 들자면 남자가 좋아하는 메뉴는 여자가 싫어하고 남자가 싫어하는 메뉴는 여자가 좋아함
  • 동질성 검정의 결과
    • 유사하다.
      • 독립성 검정 필요 없음
    • 유사하지 않다.
      • 독립성 검정의 결과
        • 서로 관련이 없다.
        • 서로 관련이 있다.
          • 유사하지는 않으나 서로 관련은 있는 경우
            • 예를 들자면 남자가 좋아하는 메뉴는 여자가 싫어하고 남자가 싫어하는 메뉴는 여자가 좋아함

카이제곱 검정 예를 좀 더 구체적으로 살펴 본다면?

  • 적합도 검정
    • 관찰값의 분포를 통해 모집단의 분포를 확인하는 검정
      • 예시: 주머니 속 사탕을 복원추출하여 파악한 색깔 구성 비율을 토대로 주머니 속 사탕 색깔이 골고루 섞여 있다고 볼 수 있는지?
        • 첫 번째 행은 관찰도수, 두 번째 행은 기대도수
        • 관찰도수와 기대도수의 차이를 사용하여 χ2\chi^2 구하기
  • 동질성 검정
    • 각기 다른 모집단으로부터 표본을 추출하여 특성 값에 따라 분류하고 두 모집단의 특성 값 비율이 유사한지 검정
      • 예시: 성별에 따른 메뉴 선호도가 유사한지?
        • 행은 집단, 열은 특성 값
        • 행의 주변도수 크기 고정
        • 열의 주변도수(marginal frequency)를 구하고 이들의 분포를 활용하여 각 행의 특성 값들에 대하여 기대도수 구하기
        • 관찰도수와 기대도수의 차이를 사용하여 χ2\chi^2 구하기
  • 독립성 검정
    • 두 종류 이상의 범주형 변수를 사용하여 자료를 분류하였을 때 변수들이 서로 독립적인지 검정
      • 예시: 성별과 메뉴 선호도가 서로 관련이 없는지?
        • 표본 크기 고정
        • 두 변수가 서로 독립적이다라는 전제로 기댓값 구하기
        • 관찰도수와 기대도수의 차이를 사용하여 χ2\chi^2 구하기

카이제곱 검정의 세 종류는 서로 다른 목적을 가지고 있지만 공통점은 다음과 같다.

  • 관찰값기댓값의 차이를 계산한다. 관찰값과 관찰값의 차이를 계산하는 것이 아님에 주목하자.

더 많은 예시

  • 적합도 검정
    • 멘델의 유전법칙에 의하면 4종류의 식물이 9:3:3:1의 비율로 나오게 되어 있다고 한다. 240그루의 식물을 관찰하였더니 120:40:55:25로 나타났다. 유의수준 5%로 적합도 검정을 하시오
    • 어느 공정의 부적합품률은 15%로 알려져있다. 시료를 80개 추출하여 검사한 결과 불량이 16개이다. 유의수준 5%로 적합도 검정을 하시오.
    • 두 정당에 대한 지지율이 한 달 전에는 54:46이었다.
  • 동질성 검정
    • 남,녀 각각 500명을 임의로 추출하였고, 성별에 따른 선호도가 관련성이 있는지, 유의수준 0.05에서 검정하시오.
    • 기존약과 신약의 효과 비교
    • 성별에 따른 흡연 여부의 분포
  • 독립성 검정
    • 영화 장르와 간식류 구매는 서로 연관이 있는지 검정하시오.
    • 보호구 착용과 부상 정도
    • 성별과 흡연 여부의 관련성

3. 카이제곱 분포와 검정

카이제곱 분포

양의 정수 kk에 대하여 kk 개의 독립적이고 표준정규분포를 따르는 확률변수 X1X_1, …, XkX_k를 정의하면 자유도 kk의 카이제곱 분포는 확률변수

Q=i=1kXi2(2) Q = \sum_{i=1}^{k} X_i^2 \tag{2}

가 따르는 분포입니다.


이미지 출처: 카이제곱 분포와 검정, 공돌이의 수학정리노트

피어슨 카이제곱 통계량

χ2=i=1m(OiEi)2Ei(3) \chi^2 = \sum_{i=1}^{m} \frac {(O_i-E_i)^2}{E_i} \tag{3}

  1. 기댓값을 파악한다.
  2. 관찰값과 기댓값의 차이를 구하여 제곱하고 기댓값으로 나눔으로써 정규화를 한다.
  3. 각각의 관찰 속성에 대하여 위와 같이 구한 값을 더한다.

모든 관찰값이 5 이상이면 카이제곱 분포 식 (1)에 근사한다고 증명되어 있다.

  • 관찰값이 5보다 작은 경우라면 카이제곱이 아니라 피셔의 정확 검증 시도

카이제곱 검정

예를 들어 자유도 kk인 카이제곱 분포에 대해 아래와 같이 검정을 수행한다.

  1. 유의수준 α\alpha를 정한다.
    • 예: α=0.05\alpha = 0.05
  2. 자유도 kk인 확률변수의 관찰값들에 대하여 카이제곱 값 QQ를 구한다.
    • 예: k=2k = 2 => Q=6.1Q = 6.1
  3. 카이제곱 분포표에서 자유도 kk인 경우 유의수준 α\alpha에 해당하는 카이제곱 값 χ2\chi^2을 찾는다.
    • 예: k=2,α=0.05k = 2, \alpha = 0.05 => χ2=5.99\chi^2 = 5.99
  4. 계산한 카이제곱 값이 카이제곱 분포표에서 찾은 값보다 크면 귀무가설을 기각하고 대립가설을 채택한다.
    • 예: Q>χ2Q > \chi^2 => 차이가 유의하므로 귀무가설 기각, 대립가설 채택

참고 자료

Written with StackEdit.

2024년 7월 24일 수요일

독일 V2 로켓과 런던 폭격 - 푸아송 분포와 카이제곱 검정

독일 V2 로켓과 런던 폭격 - 푸아송 분포와 카이제곱 검정

아래 자료들을 참고하면서 실습을 하였습니다.

푸아송 분포

실제값

n_squares = 576
n_bombs = 537

# 구역당 떨어진 폭탄 수의 평균
m = n_bombs / n_squares
print(f'{m:.3f}')
0.932
# 구역당 떨어진 폭탄 수
n_bombs_per_square = [0, 1, 2, 3, 4, 5]

# 해당 구역 수 (관찰도수)
observed_num_of_squares = [229, 211, 93, 35, 7, 1]

print(f'# of squares: {sum(observed_num_of_squares)}')
# of squares: 576

기댓값

import math

def poisson_distribution(m, k):
    return pow(m, k) / math.factorial(k) * pow(math.e, -m)

# 푸아송 분포에 따른 기대 구역 수 (기대도수)
expected_num_of_squares = [n_squares * poisson_distribution(m, k) for k in n_bombs_per_square]
print([round(v, 2) for v in expected_num_of_squares])

n_expected_squares = sum(expected_num_of_squares)
expected_num_of_squares[-1] += n_squares - n_expected_squares
print([round(v, 2) for v in expected_num_of_squares])

print(f'# of squares: {sum(expected_num_of_squares)}')
[226.74, 211.39, 98.54, 30.62, 7.14, 1.33]
[226.74, 211.39, 98.54, 30.62, 7.14, 1.57]
# of squares: 576.0
import matplotlib.pyplot as plt

plt.figure(figsize=(10, 6))

plt.plot(n_bombs_per_square, observed_num_of_squares, marker='o', label='observed')
plt.plot(n_bombs_per_square, expected_num_of_squares, marker='x', label='expected')

plt.xlabel('No. of flying bombs per square')
plt.ylabel('No. of squares')
plt.legend()
plt.grid(True)
plt.show()

png

카이제곱(χ2{\chi}^2) 검정

다음은 AN APPLICATION OF THE POISSON DISTRIBUTION 글의 끝 부분을 인용한 것입니다.

The occurrence of clustering would have been reflected in the above table by an excess number of squares containing either a high number of flying bombs or none at all, with a deficiency in the intermediate classes. The closeness of fit which in fact appears lends no support to the clustering hypothesis.
Applying the x2 test to the comparison of actual with expected figures, we obtain x2 = 1.17. There are 4 degrees of freedom, and the probability of obtaining this or a higher value of x2 is .88.

관찰도수가 특정 분포를 따르는지 여부를 검정하는 것이므로 적합도 검정(Goodness-of-fit Test)에 해당합니다.

# 피어슨 카이제곱 통계량
x2 = 0
for o_num, e_num in zip(observed_num_of_squares, expected_num_of_squares):
    item_val = pow(o_num - e_num, 2) / e_num
    x2 += item_val
    print(f'o_num: {o_num:8.4f}, e_num: {e_num:8.4f} => item_val: {item_val:.4f}')
    
print(f'** x2: {round(x2, 2)}')
o_num: 229.0000, e_num: 226.7427 => item_val: 0.0225
o_num: 211.0000, e_num: 211.3904 => item_val: 0.0007
o_num:  93.0000, e_num:  98.5387 => item_val: 0.3113
o_num:  35.0000, e_num:  30.6223 => item_val: 0.6258
o_num:   7.0000, e_num:   7.1372 => item_val: 0.0026
o_num:   1.0000, e_num:   1.5687 => item_val: 0.2062
** x2: 1.17

값의 종류는 6 개이고 관찰값으로부터 파라미터 mm을 추정하였으므로 자유도 kk는 다음과 같습니다.

k=(61)1=4 k = (6 - 1) - 1 = 4

카이제곱 분포표에 따르면 자유도가 4이고 유의수준 5%에 해당하는 χ2\chi^2 값은 9.49입니다. 위에서 구한 카이제곱 값이 이보다 작으므로 귀무가설을 채택합니다.

  • 귀무가설: 관찰도수는 푸아송 분포를 따른다.
  • 대립가설: 관찰도수는 푸아송 분포를 따르지 않는다.

참고

  • 큰 수의 법칙, 나무위키

    때문에 책 <이공계의 뇌로 산다>에서 소개된 노벨경제학상 수상자 대니얼 카너먼은 우스갯소리로 이러한 불충분한 표본으로 잘못 만들어진 p 값으로 인한 '잘못된 큰 수의 법칙 적용 사례’를 두고 '작은 수의 법칙’이라고 얘기했다고 한다. 즉 실제 있는 법칙은 아니다. 또한 잘못된 p 값 예시로 V2의 런던폭격분포를 예로 들었다.

Written with StackEdit.

2024년 7월 23일 화요일

독일 V2 로켓과 런던 폭격 - 푸아송 분포 응용

독일 V2 로켓과 런던 폭격 - 푸아송 분포 응용

관심을 가졌던 사항은 2차 세계 대전 말기 독일 V2 로켓에 의한 런던 폭격 지점의 분포와 푸아송 분포 응용 사례였는데 우연히 접한 기사를 흥미있게 읽다가 오류로 의심되는 부분을 발견하고 이를 확인하는 과정에서 글을 쓰게 되었습니다.

기사 인용

  • [문학이 사랑한 통계⑬] 로저 멕시코와 함께하는 확률론 강의, 2019.01.03, 시사위크

    • 도서 내용 중 일부 - 토머스 핀천, 중력의 무지개, 이상국 옮김, 새물결

      로저는 그녀에게 V폭탄의 통계에 대해 애써 설명했다. 천사의 눈에나 보일 영국 지도 안의 분포와 이 아래 인간의 눈에 보이는, 그들 자신이 살아남을 기회의 차이에 대해.

      “그러나 이미 폭격을 몇 번이나 받은 곳도 있잖아. 그러니까-” “미안하지만 그게 바로 몬테카를로 오류라는 거야. 특정한 지역에 얼마나 많이 떨어졌든 미래의 확률은 차이가 없어. 로켓들은 각자, 서로와 아무 관계없이 떨어져. 폭탄은 개가 아니야. 관계도 모르고, 기억도 없어. 적응이란 것도 없어.” 교과서의 푸아송 공식으로 예측되는 분포 그대로, 정말로 로켓들은 런던 전역에 떨어진다.

    • 기사 내용 중 일부

      런던 대공습에 나선 독일의 폭격기 조종사들은 과연 폭탄을 떨어트릴 때 분명한 목표물을 갖고 있었을까. 이 주제에 대해선 실제로 연구가 진행된 바 있다. 2차 세계대전 당시 영국 통계학자 R.D.클라크는 런던 남부를 576개(24_24) 구역으로 나누고, 각각의 구역에 떨어진 *_폭탄의 개수를 세는 방식으로 통계검정을 진행했다. 만약 독일 공군이 특별한 타깃 없이 무작위로 폭탄을 떨어트렸다면(평균확률밀도가 일정하다면) 구역별로 폭탄이 떨어진 횟수의 분포는 푸아송분포를 따를 것이다.

확인이 필요한 사항

위 글에서 다음 두 가지 사항이 맞는지 확인해 볼 필요가 있습니다.

  • 도서 내용 중

    • 로저가 V폭탄의 통계에 대해 설명했다고 하는데 V1, V2 로켓과는 다른 V폭탄이란 것이 있었던 걸까? 폭탄과 로켓은 다르니까. (참고: 현대 무기 분류에 따르면 로켓이 아니라 미사일에 해당한다고 하지만 과거에는 로켓이라고 불렀음)
  • 기사 내용 중

    • 폭격기 조종사들이 떨어트리는 폭탄에 이어서 R.D.클라크의 연구를 언급했다. 그런데 R.D.클라크가 연구에 사용한 데이터가 2차 대전 초기 런던 대공습 당시에 독일 공군이 투하한 폭탄이 떨어진 지점에 대한 것인지, 아니면 2차 대전 말기 독일이 개발해서 원거리에서 발사한 V2 로켓이 떨어진 지점에 대한 것인지?

도서 내용의 오류 여부

우선 V폭탄이란 것이 있었는지부터 살펴 보겠습니다.

  • V1(로켓), 나무위키

    Vergeltungswaffe 1(보복병기 1호)는 제2차 세계 대전 당시 나치 독일의 '피젤러’사에서 개발한 무기이다. 약자인 V-1, V1은 아돌프 히틀러가 선전 선동 목적으로 붙인 이름이다.

    당시에는 순항 미사일이라는 개념이 없었기 때문에 '비행폭탄’이라고 불리기도 했다. 폭탄(850kg)이 든 시가형 동체에 작은 날개와 펄스제트 엔진이 붙어있는 형태로, 세계 최초의 제트 추진 순항 미사일로 평가된다. 다만, 나온 시기가 시기이다 보니 앞에 작은 프로펠러를 달아 그것이 돌아간 숫자로 거리를 재서 목표 상공에서 연료 공급을 끊어 추락하는 방식이라 도시 정도 크기의 목표를 향한 무차별 폭격만이 가능했다.

"2차 대전 독일 V폭탄"으로 검색하면 V1(로켓), V2(로켓)이 나오므로 V폭탄이란 모델이 따로 있었던 것은 아닌 것으로 보입니다. V폭탄이 V1, V2를 지칭한다고 하면 이것들을 만들었을 당시에 '비행폭탄(flying bombs)'이라고 불렀으므로 폭탄이라는 용어를 쓰는 것이 틀렸다고 말하기는 어렵고 더군다나 소설의 배경에 해당하는 시점에서는 자연스러운 용어일 수도 있겠습니다.

기사 내용의 오류 여부

  • Poisson distribution, Britannica

    The Poisson distribution is now recognized as a vitally important distribution in its own right. For example, in 1946 the British statistician R.D. Clarke published “An Application of the Poisson Distribution,” in which he disclosed his analysis of the distribution of hits of flying bombs (V-1 and V-2 missiles) in London during World War II. Some areas were hit more often than others. The British military wished to know if the Germans were targeting these districts (the hits indicating great technical precision) or if the distribution was due to chance. If the missiles were in fact only randomly targeted (within a more general area), the British could simply disperse important installations to decrease the likelihood of their being hit.

이제 위의 브리태니커 사전 내용을 살펴 보면 다음 두 가지 사항이 명확해집니다.

  • 비행폭탄이라고 쓰고 괄호 속에 V-1, V-2 미사일을 덧붙였습니다.
  • R.D.클라크가 연구한 데이터는 V-1, V-2 미사일 폭격 지점의 분포입니다.

따라서 기사에서 발견된 오류는 다음과 같습니다.

  • 런던 대공습에 나선 독일의 폭격기 조종사들은 과연 폭탄을 떨어트릴 때 분명한 목표물을 갖고 있었을까.

위 문장 하나만 놓고 보면 오류가 아니지만 인용한 도서의 내용과 기사의 내용이 2차 대전 말기 독일의 미사일 공격을 대상으로 하고 있고 2차 대전 초기의 런던 대공습이나 폭격기 조종사들이 떨어트린 폭탄과는 무관하므로 문맥상 오류라고 볼 수 있겠습니다.

푸아송 분포 응용 목적

기사의 오류 여부를 확인하다가 뜻하지 않게 브리태니커 사전으로부터 R.D.클라크가 수행한 푸아송 분포 응용의 목적이 무엇이었는지 알게 되었습니다.

  • 독일 미사일의 공격이 정밀하다면 영국군은 주요 시설 보호에 초점을 맞추어야 하고 그렇지 않다면 주요 시설들을 이곳 저곳 분산해서 배치하는 것만으로도 타격 위험을 줄일 수 있기 때문입니다.

더 읽어 볼 만한 자료

Written with StackEdit.

2024년 7월 7일 일요일

데이터 시각화 요약 정리

데이터 시각화 요약 정리
  • 데이터 시각화 유형
    • 시간 시각화
      • 막대 그래프(Bar Chart)
      • 누적 막대 그래프
      • 그룹 막대 그래프
      • 선 차트
      • 영역 차트
      • 누적 영역 차트
    • 공간 시각화
      • 코노플레스 지도
      • 버블맵
      • 카토그램(Cartogram)
    • 분포 시각화
      • 파이 차트(Pie Chart)
      • 도넛 차트(Donut Chart)
      • 트리맵 차트(Tree Map Chart)
    • 관계 시각화
      • 산점도
      • 산점도 행렬
      • 버블 차트(Bubble Chart)
    • 비교 시각화
      • 체르노프 페이스(Chernoff Face)
      • 플로팅 바(Floating Bar)
      • 평행 차트(Parallel Chart)
      • 스타 차트(Start Chart)
      • 히트맵(Heatmap)
    • 인포그래픽
  • 벤 프라이의 시각화 방법론
    1. 획득
    2. 분해
    3. 선별
    4. 마이닝
    5. 표현
    6. 정제
    7. 상호작용
  • 자크 베르댕의 그래픽 7 요소
    1. 위치
    2. 크기
    3. 모양
    4. 명도
    5. 기울기
    6. 질감
  • 에드워드 터프티의 시각 정보 디자인 7 원칙
    1. 정보의 밀도를 높이라.
    2. 비교를 강조하라.
    3. 다중 변수를 표현하라.
    4. 데이터 왜곡을 피하라.
    5. 잉크의 효율적인 사용.
    6. 간결하고 명확한 디자인.
    7. 시간 순서를 존중하라.
    8. 정량적 자료의 정량성을 유지하라.

Written with StackEdit.

2024년 5월 21일 화요일

OAuth 2.0과 OpenID Connect 요약

OAuth 2.0과 OpenID Connect 요약

Imgur

1. 표준

2. 용어 및 약어

  • 인증(Authentication) - 사용자 신원 검증
  • 인가(Authorization) - 접근 권한 부여
  • 정보주체(Resource Owner) - 정보 소유자
  • 인증서버(Authorization Server) - 사용자 인증 수행
  • 신원확인서버(Identity Provider, 줄여서 IdP) - 사용자 인증 수행 및 사용자 정보 제공 서버
  • 정보제공서버(Resource Server) - 정보 서비스를 제공하는 서버

3. 질문과 답

  1. OAuth 2.0과 OpenID Connect(OIDC)를 한 줄로 설명한다면?
    • OAuth 2.0 - 접근 권한 부여 프레임워크 (사용자 인증 부분을 정의하지 않고 자율에 맡김)
    • OpenID Connect - 사용자 신원 인증 규격 (OAuth 2.0에서 자율에 맡겨 두었던 사용자 인증 부분을 정의함)
      • 그렇다고 OAuth 2.0의 부분집합은 아님
      • OAuth 2.0의 확장이라고 말하는 것도 적합한 표현은 아님
      • OpenID Connect를 OAuth 2.0의 상위 계층으로 표현하는 것도 가능해 보임(HTTP를 TCP의 상위 계층으로 두는 것과 유사)
      • 규격을 정의한 단체가 다름을 떠나서 개념만 놓고 보면 OpenID Connect는 OAuth 2.0의 한 부분을 정의하고 있다.
  2. OAuth 2.0의 Authorization Code Flow에서 OpenID Connect가 만드는 차이는?
    • Authorization Endpoint에 요청할 때 scope 항목의 값으로 openid를 지정
    • Token Endpoint의 응답으로 Access TokenID Token 전달
  3. Authorization Code Flow에서 Authorization Code 전송 과정이 필요한 이유는?
    • Authorization Code 전송 과정이 없는 경우 Access Token이 브라우져를 경유하여 웹 서비스로 전달됨
      • 웹 서비스 --> 브라우져 --> IdP – (access token) --> 브라우져 – (access token) --> 웹 서비스 – (로그인 성공) --> 브라우져
        • 브라우져에서 (access token) 탈취 위험 높음
    • Authorization Code 전송 과정이 있는 경우 Access Token이 IdP에서 곧바로 웹 서비스로 전달됨
      • 웹 서비스 --> 브라우져 --> IdP – (authorization code) --> 브라우져 – (authorization code) --> 웹 서비스 – (authorization code) --> IdP – (access token) --> 웹 서비스 – (로그인 성공) --> 브라우져
        • IdP에서 웹 서비스로 곧바로 (access token)이 전달되므로 탈취 위험 낮음
    • 참고
      • 보안 관점에서 브라우져 환경보다는 서버 환경을 신뢰하고 있는 현실을 고려하는 것이 이해에 도움이 됨
      • (authorization code) 수명은 짧게 설정하고 (access token) 수명은 상대적으로 길게 설정함
  4. 클라이언트는 Access TokenID Token을 해석할 수 있는가?
    • Access Token: 해석 불가
    • ID Token: 해석 가능
      • 대칭 알고리즘을 사용했으면 인증서버가 공유한 비밀키, 비대칭 알고리즘을 사용했으면 인증서버의 공개키를 사용하여 해석
  5. UserInfo Endpoint의 용도는?
    • ID Token에 포함된 정보로는 부족해서 더 많은 사용자 정보를 요청할 때 사용
  6. 브라우져가 Client Secret이나 Access Token에 접근하는 경우도 있는가?
    • 없어야 함!!!
  7. IdP에 Redirect URI를 등록해 놓고도 인증요청을 보낼 때 Redirect URI 필드에 값을 채워서 보내야 하는 이유는?
    • 웹 서비스 이중화를 위해 여러 대의 서버를 구성해 놓은 경우 IdP에 여러 개의 Redirect URI를 등록해 놓을 수 있다. 그래서 각각의 웹 서비스는 자신의 Redirect URI를 인증요청 메시지에 포함해야 한다.
    • IdP에는 한 개의 Redirect URI가 등록되어 있고 인증요청 메시지는 Redirect URI를 포함하고 있지 않을 때에는 IdP 구현에 따라 등록되어 있는 값을 사용해서 정상 처리할 수도 있고 오류로 처리할 수도 있을 것 같다.

4. 사용 지침

  • Implicit Flow - 쓰지 말라!!!
    • OAuth 2.0 Security Best Current Practice - IETF

      In order to avoid these issues, clients SHOULD NOT use the implicit
      grant (response type “token”) or any other response type issuing
      access tokens in the authorization response, such as “token id_token”
      and “code token id_token”, unless the issued access tokens are
      sender-constrained and access token injection in the authorization
      response is prevented.

    • Is the OAuth 2.0 Implicit Flow Dead? - Okta

      The OAuth Working Group has published some new guidance around the Implicit flow and JavaScript-based apps, specifically that the Implicit flow should no longer be used.

  • Resource Owner Password Credentials Flow - 쓰지 말라!!!

5. 참고 자료

Written with StackEdit.

2024년 5월 7일 화요일

가설 검정 제대로 이해하기

가설 검정 제대로 이해하기

(주의: 공부하면서 작성하는 문서라서 오류가 있을 수 있습니다.)

1. 문제 정의

1.1. 사례

  • 기존 가설: 20 대 한국인 남성의 100 미터 달리기 평균 속도는 17 초
  • 새로운 실험 결과: 무작위로 추출한 20 대 한국인 남성 500 명의 100 미터 달리기 평균 속도는 16 초

위 사례에서 새로운 실험 결과가 우연히 일어났다고 보는 것이 적절할까요 아니면 가설이 유효하지 않은걸까요? 정답이 존재하지 않는 이런 종류의 문제를 다루기 위해서는 차이가 얼마나 의미있는지 표현하는 객관적인 방법이 있어야 하지 않을까요?

1.2. 문제

  • 기존 가설과 새로운 실험의 결과가 양립하는 정도체계적인 과정을 통해 숫자로 표현하는 방법은 무엇인가?

2. 용어 정리

2.1. 출처: 위키백과, WIKIPEDIA

  1. 통계적 추론

    • 추론 통계 또는 추론 통계학(inferential statistics)으로 불린다.
    • 기술 통계학(descriptive statistics)과 구별되는 개념
    • 도수 확률(frequency probability)과 사전 확률(prior probability)을 기반으로 하는 베이즈 추론의 두 학파가 있다.
    • 추정(estimation)과 가설 검정(hypothesis test)으로 나눌 수 있다.
  2. 가설 검정

    • 통계적 가설 검정(statistical hypothesis test)
    • 모집단 실제의 값이 얼마가 된다는 주장과 관련해, 표본의 정보를 사용해서 가설의 합당성 여부를 판정하는 과정
    • 가설 검정 또는 가설검증(hypothesis test)이라고 부르는 경우도 많다.
  3. 통계적 가설

    • 하나의 특정 주장을 모수를 이용해 나타낸 형태를 지칭
    • 귀무가설(Null hypothesis, H0H_0, 영가설)과 이와 반대에 있는 대립가설(Alternative hypothesis, H1H_1)로 나타낸다.
  4. 모수

    • 매개변수(媒介變數), 파라미터(parameter), 모수(母數)는 수학통계학에서 어떠한 시스템이나 함수의 특정한 성질을 나타내는 변수
    • 함수의 수치를 정해진 변역에서 구하거나 시스템의 반응을 결정할 때는 독립변수는 변하지만 매개변수는 일정
  5. 가설 검정 5단계 절차

    1. 유의수준의 결정, 귀무가설(H0H_0)과 대립가설(H1H_1) 설정
    2. 표집(sampling) 및 검정통계량의 설정
    3. 기각역의 설정
    4. 검정통계량 계산 및 영가설 확인
    5. 통계적인 의사결정
  6. 유의 확률

    • 유의 확률(有意 確率, 영어: significance probability, asymptotic significance) 또는 p-값(영어: p-value, probability value)은 귀무가설이 맞다고 가정할 때 얻은 결과보다 극단적인 결과가 실제로 관측될 확률이다.
    • p-값(p-value)은 귀무 가설(null hypothesis)이 맞다는 전제 하에, 표본에서 실제로 관측된 통계치와 ‘같거나 더 극단적인’ 통계치가 관측될 확률이다. 여기서 말하는 확률은 ‘빈도주의’ (frequentist) 확률이다.
    • p-값(p-value)는 관찰된 데이터가 귀무가설과 양립하는 정도를 0에서 1 사이의 수치로 표현한 것이다. p-value가 작을수록 그 정도가 약하다고 보며, 특정 값 (대개 0.05나 0.01 등) 보다 작을 경우 귀무가설을 기각하는 것이 관례
  7. 귀무가설과 대립가설 설정

    • 양측 검정(two-sided test, two-tailed test)
      • 기각 영역(rejection region)이 양쪽에 있는 것이고, 그러므로 유의수준도 양 극단으로 갈라져 한쪽의 면적이 절반이 된다.
    • 단측 검정(one-sided test)
      • 좌측 검정(lower tailed test)
      • 우측 검정(upper tailed test)
  8. 표본 분포(sampling distribution)

    • 표본 분포(sampling distribution 또는 finite-sample distribution) 또는 표집분포는 크기 n의 확률 표본(random sample)의 확률 변수(random variable)의 분포(distribution)이다.
    • 모집단에서 임의로 추출된 표본의 평균을 표본 평균이라고 하며 표본 평균도 그 값이 변하는 확률 변수인데 그 확률 분포표본 평균분포라고한다.
    • 특히 표집 분포(sampling distribution)는 연구 대상이 되는 모집단에서 다중 복수의 표본들을 추출한 자료들을 통해서 통계적 가설을 검증할 때 필요한 분포이다. 따라서 모집단으로부터의 충분한 여러 표집(sampling)에서 얻게되는 표본들의 표본평균들은 표집분포를 갖게되고 이 표집 분포는 모집단의 분포에 수렴한다.
      • 이러한 중심극한정리(cetral limit theorem)에서 표집 분포의 평균값(μXˉ\mu_{\bar X})은 모집단의 평균값(μ\mu)에 근사하게 된다. ⇐ 가설 검정의 기반 !!!
  9. 검정 통계량(test statistic)

    • 통계적 가설 검정(statistical hypothesis testing)에 사용할 목적으로 표본으로부터 유도한 값
    • 검정 통계량의 중요한 성질은 귀무가설 하에서 검정 통계량의 표집 분포를 정확하게 또는 근사적으로 계산할 수 있어야 한다는 것이고 그럴 수 있어야 p-value를 계산하는 것이 가능해진다.
    • 검정 통계량은 기술 통계량과 일부 동일한 성질을 공유하고 있으며 많은 통계량들이 검정 통계량으로 그리고 기술 통계량으로도 쓰일 수 있다.
    • 검정 통계량은 통계적 가설 검정을 위해 특별히 고안된 것인데 반해 기술 통계량은 쉽게 해석될 수 있다.
    • 예를 들어 표본의 범위는 중요한 정보를 제공하는 기술 통계량이지만 그것들의 표집 분포를 결정하는 것은 어려우므로 검정 통계량으로 사용하기에는 적절하지 않다.
    • 가장 널리 사용되는 검정 통계량과 통계적 가설 검정 모델
    • 널리 사용되는 검정 통계량 두 가지는 t-statistic과 F-statistic
  10. 1종 오류와 2종 오류

    • 1종 오류 - 귀무가설을 잘못 기각하는 오류
      • 거짓 양성 또는 알파 오류라고도 한다.
    • 2종 오류 - 귀무가설을 잘못 채택하는 오류
      • 거짓 음성 또는 베타 오류라고도 한다.
  11. t-검정

    • t-검정 (t-test) 또는 스튜던트 t-테스트 (Student’s t-test)는 검정통계량귀무가설 하에서 t-분포를 따르는 통계적 가설 검정법이다.
    • 예를 들어 t-테스트를 사용하여 두 데이터 세트(집단)의 평균이 서로 유의하게 다른지 여부를 판별할 수 있다.
  12. t값

    • t값(t score)은 z값(z score)이 소수(小數)로서 음수와 양수에 걸쳐 분포하는 것을 재설정해줌으로써 자연수와 백분위수로 표현해 보여줄 수 있다는 점에서 데이터의 가독성을 보다 높인 값이다.
  13. 카이제곱 검정

    • 카이제곱 검정(chi-squared test) 또는 χ2\chi ^2 검정카이제곱 분포에 기초한 통계적 방법으로, 관찰된 빈도가 기대되는 빈도와 의미있게 다른지의 여부를 검정하기 위해 사용되는 검정방법이다. 자료가 빈도로 주어졌을 때, 특히 명목척도 자료의 분석에 이용된다.
    • 카이제곱 값의 계산: χ2=(관측값기댓값)2기댓값\chi ^2 = \sum \frac{(관측값 - 기댓값)^2}{기댓값}
    • 동질성 검정독립성 검정 두 유형이 있다.
  14. 검정력

    • 대립가설이 사실일 때, 이를 사실로서 결정할 확률이다.
  15. 자유도

  16. 통계적 유의성

  • 검정통계량은 표본 크기의 함수이므로 표본 크기가 커질수록 검정통계량의 값은 커져서 실질적으로는 유의성이 없어도 통계적으로는 유의한 것으로 판정될 수 있다. 이때의 오류는 1종오류가 된다. 즉, 통계적 유의성은 오류가능성을 동반한다.

2.2. 부연 설명

  • 유의 수준
    • 귀무가설 하에서의 검정통계량실험 표본의 검정통계량차이가 유의하다고 말할 수 있는 수준
    • 유의 수준을 0.05로 정한다는 말의 의미:
      • 귀무가설이 유효하다는 전제 하에서는 실험 표본의 검정통계량이 발생할 확률이 5% 미만이다.
    • 귀무가설이 유효하다는 전제 하에서는 쉽게 발생할 수 없을 것이라고 생각했던 사건이 관찰되었다면 우연히 일어난 것이거나 귀무가설 자체가 유효하지 않아서일 가능성이 있다. 이럴 때 차이가 의미있다고 판단하기 위해 사용할 기준, 즉 유의 수준을 미리 정해 놓았다면 그것과 비교해서 귀무가설을 선택하거나 기각하면 된다.
      • 이러한 비교가 가능하려면 통계 모델이 있어야 하고 그에 따른 검정통계량을 계산할 수 있어야 한다. 그리고 계산된 검정통계량의 값으로부터 유의 확률(p-value)을 알 수 있는 참조 테이블이 필요하다.

3. 통계적 가설 검정 예시

예시를 통해서 구체적으로 설명해 보겠습니다.

  1. 유의수준의 결정, 귀무가설(H0H_0)과 대립가설(H1H_1) 설정

    • 유의 수준: p>.05p > .05 (공식적인 표기는 소수점 앞의 '0’을 생략)
    • 귀무가설: 20 대 한국인 남성의 100 미터 달리기 평균 속도는 17 초
    • 대립가설: 20 대 한국인 남성의 100 미터 달리기 평균 속도는 17 초가 아님
  2. 표집(sampling) 및 검정통계량의 설정

    • 크기가 nn인 표본 집단 선정
    • 검정통계량: 표본 평균
    • 귀무가설 하에서 크기가 nn인 표본 집단의 표본 평균의 표집 분포계산

XˉN(μ,σ2n) \bar X \sim N(\mu, \frac{\sigma^2}{n})

  1. 기각역의 설정

    • 양측 검정
  2. 검정통계량 계산 및 영가설 확인

    • 관찰 표본의 표본 평균으로 앞에서 계산한 표집 분포 상의 p-value를 계산
      • 확률 분포 XˉN(μ,σ2n)\bar X \sim N(\mu, \frac{\sigma^2}{n}) 상에서 관찰 표본의 표본 평균이 좌측 꼬리에 있을 경우 표본 평균 이하의 값이 나올 확률이 p-value, 우측 꼬리에 있을 경우 표본 평균 이상의 값이 나올 확률이 p-value
  3. 통계적인 의사결정

    • value>0.052value > \frac{0.05}{2} 이면 귀무가설 채택, value<=0.052value <= \frac{0.05}{2} 이면 귀무가설 기각

4. 더 읽어 볼 만한 자료

  • 검정 통계량, 정보통신기술용어해설
  • 표집분포의 이해, 2020.01.08, DB의 DB
  • 가설검정 방법과 유의수준, p 값(p value) 개념 정리, 처음부터 배우는 데이터과학
    • 예시: 혈압 개선 약품의 효능 검정
  • T 검정과 Z 검정이란? 두 집단 차이를 통계적으로 검증하기, 2022.03.03, 처음부터 배우는 데이터과학
    • 예시: 쇼핑몰의 지역별 객단가 분석
    • z검정과 t검정의 차이에 대한 간략한 설명
  • 카이제곱 분석 이해하기, 2023.09.23, 게으름의 흔적
    • 예시: 대학에서 전공(과학, 예술)과 학습 스타일(집단 학습, 개별 학습)의 관계에 대해 조사
  • 데이터 분석 초보자를 위한 T-test & Chi-squared test, 2020.09.18, Gayeon Kim

    각 가설 검정 방법은 각자가 검정할 수 있는 가설의 형태가 미리 정해져 있으며, 우리는 이를 임의로 바꿀 수 없다.

    • 귀무가설 예시
      • t 검정
        • 예시-1. Adelie 펭귄의 평균 몸무게는 8kg일 것이다.
        • 예시-2. Adelie 펭귄의 평균 몸무게는 3.72kg일 것이다.
        • 예시-3. Adelie 펭귄의 평균 부리 깊이와 Gentoo 펭귄의 평균 부리 깊이는 같다.
        • 예시-4. Adelie 펭귄의 평균 부리 깊이와 Chinstrap 펭귄의 평균 부리 깊이는 같다.
      • 카이제곱 검정
        • 예시-5. 펭귄의 성비는 1:1일 것이다. (적합성 검정)
        • 예시-6. 펭귄의 몸무게와 플리퍼 길이는 연관이 없다. (독립성 검정)
  • 파이썬 카이제곱 검정 예, 2023.06.27, 사막의 수도자
    • 예시-1. 가족의 크기에 따라 구매하는 차의 크기가 다른지 검정 (독립성 검정)
    • 예시-2. 요일별 커피 판매량이 다른지 검정 (적합성 검정)
  • [통계] t검정(T-test), 2023.05.24, nbac406
    • 예시-1. 게임A와 게임B의 평균 플레이 시간은 같은지 검정
    • 예시-2. 강남과 강북의 휘발유 평균 차이는 있는지 검정
  • [이론] 카이제곱(Chi-Squared Test) 검정이란?, 2021.04.10, 꿈꾸는 직장인
    • 카이제곱 검정 유형: 적합도 검정, 동질성 검정, 독립성 검정
    • 예시. 연령과 선호 SNS가 서로 독립인지 검정 (계산 과정을 구체적으로 보여 줌)

Written with StackEdit.

Circom으로 영지식 증명 시작하기

Circom으로 영지식 증명 시작하기 Circom 2 Getting started 문서를 따라하면서 작성한 문서입니다. 실습 환경: Windows 11 1. 소프트웨어 설치 Downloads 페이지에...