For a better world

적분은 크게 부정적분과 정적분으로 나뉜다. 부정적분은 미분의 역연산이며, 정적분은 넓이/부피를 계산하는 방법이다. 실용적 관점에서 정적분이 많이 쓰이므로 적분은 대개 정적분을 의미한다. 부정적분과 정적분의 차이는 계산 형태와 적분상수 여부다. 부정적분은 대부분 답이 식으로 도출되며 정적분은 대부분 값으로 도출된다. 이는 부정적분은 $\int $처럼 정해진 구간이 없고 정적분은 $\int_a^b$처럼 정해진 구간이 있기 때문이다. 따라서 정해진 구간이 없는 부정적분은 적분상수가 있고, 정해진 구간이 있는 정적분은 적분상수가 계산 과정에서 사라진다. 이러한 부정적분과 정적분은 도출되는 형태는 다르지만 결국 공통적인 목표는 구간의 넓이/부피를 구하는 것이다. 

부정적분 (indefinite integral, 不定積分)

부정적분에서의 부정은 넓이/부피를 계산할 수 있는 적분 구간을 정할 수 없다는 의미다. 따라서 모든 구간에 대해 일반화를 통해 $f(x)$의 넓이가 이러할 것이라 표현할 수 밖에 없어 식의 형태로 도출된다. 만약 함수 $f(x)$의 부정적분을 $F(x)$로 둔다면 ${d\over dx}F(x) = f(x)$으로 표현할 수 있다. 부정적분은 정적분과 달리 식의 형태로 나타나고 적분상수가 있으므로, $\int f(x)dx = F(x) + C$로 표현할 수 있다. 이 때 $F(x)$를 $f(x)$의 원시함수라고도 부른다. 

정적분 (definite integral, 定積分)

정적분은 넓이와 부피를 계산할 수 있는 적분 구간이 정해져 있다는 의미다. 따라서 구간의 넓이가 계산되어 수치 형태로 도출된다. 부정적분이 가능한 모든 범위에 대한 일반화라면 정적분은 정해진 구간에 대한 특수화라 볼 수 있다. 정적분의 기호를 풀어 쓰면 $a$와 $b$ 구간에서 높이를 $f(x)$로 두고, 밑변(적분변수)을 $dx$로 두어 넓이를 계산하는 것이다. 참고로 정적분이 $\int_a^b f(x)dx = F(b) - F(a)$로 주어져 있다면 $\left[F(x)\right]_a^b$로도 표현할 수 있다. 그 이유는 정적분하는 과정에서 부정적분을 거치기 때문에 부정적분 식을 따로 쓰기 위한 목적이다. 

P.S 향후 필요의 경우 정적분의 종류인 중적분, 이상적분, 스틸체스 적분, 르베그 적분, 리만 적분 등에 대한 내용 추가 예정

Reference

[1] 적분 https://namu.wiki/w/%EC%A0%81%EB%B6%84

[2] 부정적분과 정적분 사이 관계 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=piry777&logNo=100160884382

[3] 부정적분의 개념,미분과 부정적분과의 관계 https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=sbssbi69&logNo=90172290254

정보보안학 석사 과정을 졸업한지 1년 쯤 되어가고, 관심분야도 보안에서 딥러닝으로 바뀐지 꽤 오래 되었네요. 불현듯 자기 전 작년 종합시험 준비로 고통받던 때가 떠올라 이 글을 쓰게 됐습니다. 재학 기간 동안 두 번의 시험 기회가 있었고 첫 번째 기회를 날리는 고배를 마신 뒤 절치부심하는 마음으로 정리한 내용입니다. 중간/기말/종합시험 모두에 어느 정도 도움이 되리라 생각합니다. 가급적 논리적 서술이 가능하도록 정의, 배경, 특징, 장점, 단점, 차이점, 방법, 활용, 종류, 목표 등을 고려해 작성하였습니다. 아래에 예상 질문들은 강의 내용을 총 정리하다보니 자연스럽게 시험에서 이런 것을 물어볼 것 같다고 예상한 질문과 답안들입니다. 중간에 예상 답안이 부재한 경우는 2가지 이유입니다. 첫 번째는 교수님께서 매학기 수업마다 조금씩 설명을 더 해주거나 덜 해주는 파트가 있어 듣지 못해 정리할 수 없었던 부분입니다. 두 번째는 얼추 설명은 해주셨지만 정확히 이해 못하고 모호하게 알고 있는 부분은 지웠습니다. 댓글로 추가해주신다면 업데이트 하도록 하겠습니다. 또 틀린 부분이 있다면 지적해주시면 감사하겠습니다. 참고로 아래 내용들은 강의 요약 내용을 바탕으로 작성한 것이므로 포함하지 않는 내용과 설명들이 있습니다. 원본이 필요할 경우 댓글 남겨주시면 보내 드리겠습니다. 전체 글 내용은 고려대학교 정보보호대학원 김승주 교수님 보안공학 강의 내용을 기반으로 작성되었습니다.
 

보안공학이란 무엇인가?

H/W와 S/W를 만드는 개발 단계인 요구사항 분석, 설계, 구현, 배포, 유지보수에 이르기 까지 각 단계마다 모두 보안을 고려하고 제품을 판매하는 단계에서도 보안내재화가 이루어졌는지 제대로 이루어졌는지 확인하는 것이다.
 

보안공학의 목표는 무엇이고 왜 보안공학은 어려운가?

보안공학은 trusthworthy(dependable)한 시스템을 만드는 것을 목표로 한다. 보안공학은 random한 에러를 다루는 소프트웨어공학과 달리 random한 에러와 함께 의도적으로 발생한 intentional 에러도 함께 다루기 때문에 더 어렵다.
 

보안공학의 핵심인 Define & Design Approach, Shift left testing, traceability는 무엇인가?

• define & design approach: 보호해야할 자산을 정확하게 식별한 다음, 자산의 중요도와 이에 따른 요구사항을 정의하고 설계하는 것을 의미한다.
• shift-left testing: 매 개발 단계마다 testing을 수행 함을 의미한다. shift-left testing에서 보안 담당자의 역할은 개발자가 testing에 사용할 수 있는 도구를 만들어 공급하고, 개발자가 진행한 testing에 대해 적절성 여부를 검증하는 작업을 진행한다. 이러한 shift-left testing은 자동화가 가능하고, 이른 단계에서 testing을 진행할 수 있다는 장점이 있다.
• traceability: 

만약 보안공학에서 보안내재화 개발 프로세스를 통해 요구사항분석부터 설계, 구현까지 완벽히 수학적으로 다 증명돼도 모의해킹이 필요한가?

모든 것을 수학적으로 증명했다 하더라도 모의해킹이 필요하다. 수학적 증명은 전제조건을 가지고 있으며 이 전제조건이 제대로 지켜지고 있는지를 검증하기 위해서는 모의해킹이 반드시 필요하다. 이는 수학적 증명과 모의해킹이 상호보완 하는 관계라고 볼 수 있다.
 

바람직한 S/W 요구사항 도출 조건의 6가지와 그 특징은 무엇인가?

• Unambiguity: 다른 사람이 요구사항을 검토한 결과는 동일해야 하며 요구사항에 모호함이 없어야 한다.
• Prioritization: 요구사항의 구현과 관련하여 우선순위가 부여되어야 한다.
• Verifiability: 요구사항이 제품에 적절하게 구현되어야 하고, 검증하기 위한 Security Testing Requirement도 함께 도출되어야 한다.
• Completeness: 모든 필요한 요구사항이 전부 도출되어야 한다. (지정된 모든 요구사항은 전달해야 하는 기능을 완전히 설명해야 한다)
• Correctness: 해당 요구사항은 자체 모순을 가지거나 충돌되지 않고 그 기능을 정확하게 설명해야 한다.
• Feasibility: 해당 요구사항은 자원 및 제약조건에서 실행 가능해야 한다.

보안성 평가에서 TCSEC의 보안등급 중 A2는 왜 사용하지 않는가?

• TCSEC을 처음 만들 당시 A2 등급인 Code Proof(Code Assurance)까지 넣으려고 하였다. 하지만 TCSEC을 제작자는 Code Assurance의 입증이 어렵다고 판단하여 마지막에 A2를 제거하고 A1만 남겼다. Code Assurance는 Software testing과 Software verification으로 구성되는데, 특히 software testing에서 만약 소스코드가 대략 10,000줄이 이상 넘어가게 된다면 포인터 등으로 인한 복잡성 때문에 수학적 안정성 입증이 어려워지기 때문이다. 

TCSEC의 단점을 서술하시오

보안등급평가에 있어 Assurance와 Functionality가 서로 분리되어 있지 않아, High Assurance임에도 불구하고 낮은 보안등급으로 평가하는 결점이 있다.
 

보안성 평가 표준인 CC, CAVP, CMVP, C&A, RMF A&A, DITSCAP에 대해 설명하시오.

• CC: (개념) 보안성 평가와 관련해서 가장 권위있는 국제 표준이다. 보안성 평가 국제표준(ISO/IEC 15408)의 공통평가기준(CC)에 따라 정보보호시스템의 기능 및 취약성을 평가/인증하는 제도이다. (배경) 미국의 TCSEC으로부터 유럽연합의 ITSEC, 캐나다의 CPCPEC, FC 등이 만들어지게 되었고 이를 만든 각국가의 평가기관들은 국가적으로 독립된 평가 기준을 통합하는 프로젝트를 시작하였고 이를 CC 프로젝트라 하였다. CC 프로젝트는 TCSEC의 단점을 보완하고 기존의 평가 기준들간의 개념적/기술적 차이를 통합하여 국제 표준화를 만들자는 목표로 추진되어 만들어 졌다. (목적) CC인증은 평가과정에서 IT제품(H/W, F/W, S/W)에 적용되는 보안 기능과 보증수단에 대한 공통의 요구 사항들을 제시한다. 이를 통해 독립적으로 수행된 보안성 평가의 결과들을 비교할 수 있도록 한다. 평가 결과는 소비자가 IT 제품이 그들의 보안 요구를 충족시키는지 결정하는데 도움을 줄 수 있다.
• CAVP (Cryptographic Algorithm Validation Program): 암호 알고리즘을 중심으로 제대로 구현되었는지를 검증한다.
• CMVP (Cryptographic Module Validation Program): 특정한 암호 모듈이 특정한 암호 알고리즘을 올바르게 구현했느냐에 대한 구현 적합성을 시험/인증 한다. CMVP와 CC의 공통점은 제품이 요구사항분석단계부터 설계, 구현에 이르기까지 보안내재화 프로세스를 충실히 따랐는가를 본다. 이것이 발전해서 C&A 제도가 되었다.
• C&A (Certification & Accrediation): 
• RMF A&A: 2015년 DoD Cyber Strategy를 발표했고, 이 내용은 전산시스템 뿐만 아니라 F35 스텔스 전투기나 무인 드론과 같은 첨단 무기체계들도 보안내재화 개발 프로세스를 적용하라는 것을 요구한 것이다. RMF A&A는 이러한 요구사항을 충족시키고 실제로 준수하였는지 평가하기 위해 만들어진 표준이다.

(다소 설명이 빈약하다 생각들어 몇몇 부분은 추가되면 좋을 것 같습니다)
 

CAVP, CMVP, CC, DITSCAP, NIST C&A, RMF A&A의 정의 및 비교와 국내외 정책비교를 서술하라.

EAL 보안성평가에서 낮은등급에서 높은등급이 되기 위해 필요한 조건은?

Requirements, functional specification, HLD, LLD, implementation에 대해 formal method로 정형명세화 하여 수학적으로 만족함을 입증하여야 한다.

Information Security, Information Assurance or Cybersecurity의 차이를 서술하시오

핵심 차이는 trusthworthy라고 할 수 있다. information security는 컴퓨터와 컴퓨터에 들어있는 전자적 정보를 지키는 것을 의미하며, cybersecurity는 사이버공간과 연동된 모든것을 지키는 것을 의미하는데 여기에는 digital과 non-digital 정보도 함께 포함된다.
 

걸프전이 최초의 Information Assurance인 이유는 무엇인가?

이 질문에 대해 답을 정리하진 못했습니다. 다만 이 예상 질문과 관련한 부분적인 내용들을 기술하면 다음과 같습니다.

• 걸프전의 맥락에서 사용되어 정리하고 가야할 용어인 information security와 cybersecurity가 있다. 두 용어의 큰 차이점이자 추구하는 목표는 trustworthy이다.
  • Information Security: 컴퓨터와 컴퓨터 속에 들어 있는 전자적인 데이터를 보호하겠다라는 의미를 가진다.
  • Informaton Assurance or Cybersecurity: 사이버공간과 연동된 모든 것을 보호하겠다라는 의미를 가지며, 그 모든 것은 전자적인 형태(digital)의 데이터여도 되고 전자적인 형태(non-digital)가 아니여도 된다.
• 걸프전은 정보보증(Information Assurance)이라는 패러다임 shift를 발생시킨 선구자 역할을 했다는 점에서 의미가 있다.
• 걸프전에서는 패러다임 shift가 information security에서 information assurance로 바뀌었고, 이는 적의 정보는 교란시키고 내 정보를 유지시키는 것이 중요하다고 인식하게 되면서 이를 위한 목표인 trustworthy를 달성하기 위함이다. 
• 걸프전을 통해 Information Assurance가 중요해졌다. 이는 원할때 Access 가능해야 하고, 그 정보는 항상 relability와 security를 유지 가능해야 함을 의미한다.

Risk Management란 무엇이고, 구성요소와 이에 대한 정의는 무엇인가?

Risk Management는 기본적으로 Risk를 제거하는 것이 아니라 줄이는 것이다. 하지만 Risk를 줄인다하더라도 잔존 위협(Residual Risk)가 남아있게 된다. 이 때 이 잔존 위협을 어떻게 잘 관리할지 고려하는 것을 Risk Management라고 한다. 참고로 이를 위해선 자산별, 중요도 별 등급화가 되있어야 Risk를 측정할 수 있다. Risk Management 방법은 크게 4가지로, Risk Transfer, Risk Avoidance, Risk Reduction, Risk Retention이 존재한다.

• Risk Transfer: 위협을 보험사와 같은 제 3자에게 전가하는 것을 의미한다.
• Risk Avoidance: 위협을 회피하는 것을 의미하는 것으로 단적 예로 스마트TV에 카메라 떼는 것과 같다.
• Risk Reduction: 보안 대책을 만들어 위험을 감소시키는 것을 의미한다.
• Risk Retention: 위험의 확률이 낮으면 위험을 안고 가는 것을 의미한다.

결과적으로 이를 통해 Risk Avoidance를 제외하고 어떤 것이 ROI가 높은지 비교하여 그에 맞는 대응책을 세운 뒤, 높은 리스크부터 낮은 리스크로 대응해야 한다.
 

Risk Assessment의 특징과 그 한계를 설명하시오.

Risk Assessment는 quantitative risk analysis (정성적), qualitative risk analysis (정량적)로 크게 둘로 나뉜다. 리스크 분석은 정량적으로 분석하는 것이 객관성을 담보할 수 있다는 장점이 있지만 적용하고자 하는 사람의 탄탄한 수학적 이론이 뒷받침 되어야 하므로 실적용엔 무리가 있다. 따라서 무기체계분석이나 자동차보안성평가와 같은 필드에서는 정성적 분석 방법을 사용하는 것이 특징이다. (Risk = Probability * Damage Potential)
 

Goldwasser의 Semantic security와 Shannon의 Perfect Secrecy의 차이점을 서술하시오.

• Shannon's perfect secrecy : 무한한 컴퓨팅 자원을 가진 passive attacker로 부터 암호문에서 평문에 대한 어떠한 정보(단, 1bit라도)도 누출되서는 안된다.
• Goldwasser's semantic security : 유한한 컴퓨팅 자원을 가진 passive attacker로부터 암호문에서 평문에 대한 어떠한 정보(단, 1bit라도)도 노출되서는 안된다.

MDTD(Model Driven Test Design)가 test case create에 도움이 되는 이유는?

testing하려는 대상을 작은 task 단위로 모델링하여 해당 task에 집중적으로 testing할 수 있기 때문이다.
 

Model Checking 이론을 바탕으로 Code Assurance를 달성하는 방법 및 프로세스를 상세히 서술하시오.

프로그램을 model로 만들고 model checker에 requirement(ex: correctness property)를 넣었을 때 model checker에서 model이 requirement를 충족하는지에 대한 여부를 Yes/No로 알려준다. 만약 No의 경우에는 counter measure도 함께 알려준다. 결과적으로 model checker를 통해 해당 프로그램의 model이 requirement를 충족하는지 판단한다. (Model Checker는 완전 자동화가 가능하다는 장점이 있고, Automatic Theorem Prover에 비해 적용 범위가 작다는 단점이 있다.)

데이터 거버넌스에 대해 설명하시오

데이터거버넌스의 핵심은 데이터 사일로(칸막이) 문제로 인해 도입된 개념으로 데이터 활용을 위한 전사적인 경영체계라 할 수 있다. 조직은 이러한 데이터 거버넌스를 통해 데이터 활용 계획과 데이터 보호 계획을 수립하여 활용도를 극대화 시켜서 궁극적으로 데이터 사일로를 제거하는 것을 목표로 한다.
 

14가지 Security Design Principle과 각각이 의미하는 바를 서술하시오.

• Least Privilege: 사람 또는 시스템에게 부여할 최소한의 권한을 부여하는 것을 의미한다. 하지만 이 최소권한의법칙을 지키기 위해 보안레벨을 사용자와 오브젝트 사이에 어떻게 설정해야 하는가는 쉽지 않다.
• Fail-Safe Default: 두 가지 의미를 가진다. 첫 째는 명시적 허용이 아니면 거부를 의미한다. 예를 들어 방화벽 룰셋에 명시되지 않은 패킷이 있을 경우 drop하는 것과 같다. 둘 째는 만약 프로그램이 비정상 상태로 빠질 경우, 바로 직전에 안전했던 상태로 돌아가는 것을 의미한다. 이를 통해 프로그램을 항상 안전한 상태로 유지시킬 수 있게 한다. 예를 들어 윈도우 블루스크린이 표시되어 먹통이 되는 상태로 빠지지 않게 하는 것과 같다.
• Economy of Mechanism: H/W, S/W를 개발할 때 가능한한 시스템을 단순하고 작은 사이즈로 설계하고 구현해야 함을 의미한다. 단순하고 작은 사이즈로 설계하는 것은 모듈화 설계와 같다. 장점은 요구사항을 달성하고 있는지 검증이 쉬워진다. 심플할수록 assurance level이 높아진다. simple and small이 의미하는 바는 검증하기 쉽도록하여 assurance level을 극대화 시킨다는 것이 핵심이다.
• Complete Mediation: 자원에 접근할 때 마다 반드시 그 권한에 대해 확인해야하는 것을 의미한다. 모든 접근을 전부 확인하는 것을 zero-trust라고 한다. 하지만 실질적으로 모든 접근에 대한 확인은 부하로 인한 속도저하가 심해서 구현하기 어려운 것이 특징이다.
• Design by Contract: 어떤 일을 처리할 때 항상 확인된 인터페이스를 통해서만 해당 일을 처리해야함을 의미한다. 예를 들어 중요한 시스템일수록 사전 정의된 인터페이스 또는 사전 정의된 프로토콜을 통해서만 중요 자원에 접근할수 있도록 하는 것을 의미한다.
• Open Design: 어떤 시스템을 만들었을 때 그 시스템의 설계도나 소스코드가 공개되어도 안전도가 유지될 수 있어야 한다는 것을 의미하고, 시스템의 안전성을 설계도나 소스코드의 폐쇄성에 의존하지 않아야 한다는 것을 의미한다. 예를 들어 군에서 같은 모듈을 사용하는 무전기를 분실하게 되면 리버싱하여 소스코드를 알아낼 수 있기 때문에 시스템을 만들때 설계도나 소스코드가 공개됐다고 전제한 다음 시스템을 만들라는 것이다. 그래서 만약 안전하다면 오픈 디자인 원칙에 충실하다 할 수 있다. 동의어는 Kerckhoff's 법칙이라고도 하며, 반대말로 Security through Obsecurity 또는 Security by Obsecurity라고도 한다. 
• Seperation of Prvilege: 중요시스템에 접근할 때는 그 권한을 분산 또는 분리해야 함을 의미한다. 예를 들어 핵무기를 동작시킬 때 두 사람의 암호를 동시에 입력해야 작동하는 것과 같다.
• Least Common Mechanism: 시스템의 공통 모듈을 최소화해서 활용해야 함을 의미한다. 이는 보안에서 한 부분에 문제가 생겼을 때 다른 부분으로 파급되는 것을 최소화하는 것이 중요하기 때문이다. 하지만 현실적용에는 어려운 부분이 있는데 이는 공통모듈을 쓰면 생산성은 높아지나, Economy of mechanism의 개념과 정면으로 위배되는 특징이 있기 때문에 시스템을 만들다보면 이 개념에 충실하기 쉽지 않은 것이 특징이다.
• Psychological Acceptability: Usable Security라고도 부르며 이는 시스템이 사용하기 편리해야 함을 의미한다.
• Defense in Depth: 보안 시스템을 둘 때 계층을 두어 한 계층이 뚫히더라도 다음 계층이 막아줄 수 있도록 시스템을 설계해야 함을 의미한다.
• Effective Logging: 로그를 잘 남겨야 함을 의미하는 것으로, 개인정보보호법으로 인해 로그에 어떤 정보가 들어가면 안되는지 또한 중요해진 것이 특징이다.
• Build In, Not Bolt On: 시스템을 개발한 다음 보안제품을 사서 쓸 것이 아니라, 처음 만들 때 보안이 Build In되도록 만들어야 함을 의미한다.
• Design for Updating: 업데이트를 어떻게 할 것인가를 설계해야 함을 의미한다.
• Centralized vs Decentralized: 중앙화 시킬 것인지 분산화 시킬 것인지를 의미한다.

What is 'sound'?

Threat Modeling의 개념과 절차적 특징을 서술하시오.

Threat Modeling은 목표 시스템에 대한 어떤 위협요소가 없는지를 공격자의 입장에서 체계적으로 분석할 수 있는 방법론을 의미한다. 이를 통해 목표 시스템의 attack surface 식별, 얼마만큼의 위협이 발생하는 가를 측정할 수 있다. 또한 보안대책과 보안대책에 대한 테스트와 같은 일련의 청사진을 도출해낼 수 있다는 것이 특징이다. 전반적인 프로세스는 다음과 같다.

1. DFD를 통해 우선적으로 모델링한 후 지켜야할 자산을 중요도 별로 우선순위를 식별한다.
2. 분석대상 시스템에 대해 취약점정보와 관련된 attack library를 수집한다.
3. 공격자의 관점에서 STRIDE를 이용하여 어떤 element에 취약점이 매핑될 수 있는지를 확인한다.
4. 매핑된 정보를 기반으로 공격시나리오를 생성 후 attack tree로 표현한다.

SRIDE: 모델링된 시스템에서 element 별로 공격자의 입장에서 취약점을 도출할 수 있는 보안위협모델링 방법이다. Spoofing(위장), Tampering(변조), Repudiation(부인), Information DIsclosure(정보유출), Denial of Service(서비스거부), Elevation of prvilege(권한상승)으로 구성되어 있다. SRIDE에는 분석 방법이 2가지로 stride-per-element와 stride-per-interaction이 있다. stride-per-element는 element 별로 S,T,R,I,D,E 공격이 발생할 수 있을지 검증하는 것을 의미하고 stride-per-interaction은 trust boundary를 넘나드는 데이터 흐름들에 대해 중점적으로 분석하는 방법을 의미한다.
 
Attack Tree: 수집한 취약점 정보를 엮어 공격시나리오화 시킬 수 있는 방법으로, 하나의 목표 별로 하나의 Attack Tree가 만들어지는 것이 특징이다.
 
DREAD: DREAD는 5가지 항목으로 구성되어 있고 각각은 다음과 같다.

• Damage Potential: 공격자가 굉장히 민감한 데이터를 탈취하거나 파괴할 수 있음을 의미한다.
• Reproducibility: Timing winodow가 크거나 작음을 의미하는 것으로, Timing window가 작은 예시로는 컴퓨터가 부팅될 때만 공격이 가능하고 Timing winodw가 큰 예시로는 컴퓨가 켜져 있으면 언제든 가능할 때를 의미한다.
• Exploitability: 공격 프로그램으로 만들기가 얼마나 쉬운가를 의미한다.
• Affected Users: 공격으로부터 영향을 받는 사용자가 얼마나 많은가를 의미한다.
• Discoverability: 해당 취약점을 얼마나 발견하기 쉬운가를 의미한다.

Risk score = DREAD/5이다. 이러한 Risk score의 단점은 절대적이지 않고 사람마다 상대적인 것이다. 따라서 2010년 이후 MS에선 더이상 사용하지 않고, security response center bulletin ratings를 사용해 사람마다 오차가 생기는 것을 막고자 하였다.
 

LINDDUN을 설명하시오.

LINDDUN은 DFD를 작성한 뒤 개인정보보호의 관점으로 보안위협식별을 수행하는 방법이다. LINDDUN을 이루는 구성요소와 이에 대한 설명은 아래와 같다.

• Linkability: 
• Identifiability: 
• Non-repudiation: 
• Detectability: 
• Disclosure of Information: 
• Unawareness: 
• Non-compliance: 

TARA를 설명하시오.

Threat Assessment and Remediation Analysis로 2011년 MITRE에서 만들어진 것으로, 국가의 지원을 받는 해커들이 있다는 전제하에 위협모델링을 어떻게 할 수 있을까를 위해 만들어졌다. 일반적인 해커와 달리 국가의 지원을 받는 해커는 기존의 Threat Modeling을 할 수 없는데 이는 투입비용의 한계가 없기 때문이다.
 

Structured Threat Assessment Process란 무엇인가?

핵심은 모의해킹과 위협모델링(Threat modeling)을 합쳐서 수행하는 것을 의미한다. 

 
Formal Method의 특징을 서술하시오

어떤 시스템에 대한 요구사항을 수학적 기법을 이용하여 요구사항을 정확하게 기술하고 그 요구사항이 제대로 달성되었는지를 검증하는 것을 의미하는 것으로, 크게 formal specification과 formal verification으로 구성된다.
 

Security Policy와 Security Policy Modeling의 개념과 차이점을 서술하시오.

• security policy는 security requirement의 집합으로, 어떤 것을 보호해야하고 그것을 어떻게 보호할 수 있을까를 의미한다.
• security policy modeling은 좁은 의미로는 security policy를 정형명세로 기술해둔 것을 의미하고, 넓은 의미로는 security policy를 정형명세로 기술하고 그 요구사항이 제대로 충족되었는지를 검증까지 하는 것이다. 검증에는 두 가지 의미가 포함된다. requirement 간의 모순점이 없는지를 검증하고, 설계도가 요구사항을 전부 반영하여 제대로 설계되었는지를 검증한다.
• 또한 보안성평가의 국제표준인 CC을 확인하면 EAL1~EAL7이 있는데 EAL4까지는 security policy를 제출할 것을 요구하나 EAL5부터는 security policy model을 제출할 것을 요구한다. 여기서 model은 정형명세로 제출하는 것을 의미한다.

DAC의 개념, 특징, 장단점 등에 대해 서술하시오.

DAC은 임의적 접근통제정책을 의미하는 것으로 데이터의 소유주가 데이터에 접근가능한 권한을 결정할 수 있고, 운영체제에 의해 시행되는 것이 특징이다. 장점으로는 필요한 사람에게 권한을 부여할 수 있는 최소권한법칙을 달성하기 쉽고 협업이 편하다는 장점이 있다. 반면 카피에 취약한 구조로 내가 권한을 부여했던 사람이 다시 다른 사람에게 데이터에 접근하는 권한을 부여할 수 있다는 것이 단점이다. 따라서 군에서는 이를 사용할 수 없는데 이에 대안으로 만들어진 것이 강제적 접근정책인 MAC이다.
 

MAC의 개념, 특징, 장단점 등에 대해 서술하시오.

MAC은 강제적 접근통제정책을 의미하는 것으로 주체와 객체의 보안등급에 따라 허가 또는 제한하는 것이 특징이다. 중앙집중형으로 엄격한 보안을 제공할 수 있는 것이 장점이나 모든 접근에 대해 확인해야 하므로 성능 저하가 발생할 수 있다는 단점이 있다. 또한 최소권한의법칙을 충족하지 못한다는 단점이 있고, 이 때문에 보안레벨로만 접근권한을 통제하지 않고 Compartment의 개념을 추가하여 최소권한의법칙을 달성하고자 하는 MLS 정책이 만들어졌다.
 

BLP 모델의 개념, 특징, 장단점 등에 대해 서술하시오.

벨과 라파듈라는 MLS 정책또한 충분하지 않기 때문에 Define and Design Approach를 해야 한다고 주장하며 1973년 BLP 모델을 제시하였다. 가장 먼저 달성해야할 것을 정의하고, 접근통제정책이 올바르게 시행되려면 SS-Property, *-Property가 만족해야되어야 한다고 하였다.

• SS-Property (Simple Security Property): 기존의 MLS의 특징인 사용자가 가진 보안등급과 compartment의 범위가 접근하려고 하는 object의 보안등급과 compartment 범위보다 커야지만 object에 접근할 수 있음을 의미한다.
• *-Property (Start Property): 기존 MLS를 충족하는 시스템은 SS-Property만 충족한다는 단점을 보완하기 위해 나온 개념으로 subject가 SS-property를 만족했다는 전제하에 보안등급이 높은 object에서 데이터를 읽고 낮은 등급의 object에 쓰면 안된다는 것을 의미한다. 어떤 것을 충족하고 어떤 것을 충족하지 않는지를 명확히 표현하는 것이 중요하다는 것을 보였다는 점에서 의의가 있는 것도 특징이다.

BLP 모델은 security property를 기밀성 관점에서만 고려하기 때문에 무결성 관점을 고려하지 못한다는 단점이 있고, Covert Channel에 취약하다는 단점이 있다.
 

BLP 모델에서 권한이 높은 프로세스와 권한이 낮은 프로세스간의 통신 방법은 무엇인가?

권한이 높은 프로세스가 권한이 낮은 프로세스와 통신을 해야할 때가 있지만 권한이 높은 곳에서 낮은 곳으로의 데이터가 쓰이는 것을 막았기 때문에 데이터를 전달할 수 없다는 단점이 있다. 이를 해결하기 위한 대안이 2가지가 있는데 첫 번째는 subject security level을 순간적으로 낮추는 방법이 있고, 두 번째는 *-Property를 위반해도 되는 Trusted subject group을 생성하여 서로간의 등급이 다르더라도 데이터를 주고 받을 수 있도록 하는 방법이 있다. 첫 번째 방법을 실제로 구현한 것이 MULTICS이다.
 

McLean이 BLP 모델에서 비판한 평정속성은 무엇을 의미하는가?

Tranquility(평정속성): 시스템이 한 번 세팅되면 사용자들의 권한은 바뀌지 않음을 의미한다. 벨과 라파듈라는 BLP 모델의 전제를 평정속성으로 하였지만 McLean으로부터 전제조건이 위반되었다고 지적하였다.
 

BLP 모델에서 주어진 formal method를 참고하여 SS-Property를 표현하시오.

SS Property = No Read Up

• A state $(b, M, f)$ satisfies the SS-Property if
  • $\forall (s, o, a) \in b,$ such that $a \in \{read, write\}$
  • $f_O(o) \leq f_S(s)$
  a subject can only observe objects of lower classification.

read 또는 write를 하고 있는 모든 subject와 object에 대해 object의 보안등급이 subject의 보안등급보다 낮으면 모든 action은 read 또는 write이다.
 
 

BLP 모델에서 주어진 formal method를 참고하여 *-Property를 표현하시오.

BiBa 모델의 개념, 특징, 장단점 등에 대해 서술하시오.

BLP 모델이 나온 뒤 기밀성만 다룬다는 단점을 보완하기 위해 무결성 관점을 다루기 위해 나오게 된 것으로 BLP 모델과 logical dual이라 할 수 있다. 무결성 관점에서는 정보의 흐름이 높은 곳에서 낮은 곳으로 가야한다. BLP 모델과 동일하게 SS-property와 *-Property를 동일하게 주장하였다.

• SS- property (Read up)
  • subject의 integrity level이 object의 integrity level보다 높거나 같아야 데이터를 읽을 수 있음을 의미한다.
• *-property (Write down)
  • subject의 integrity level이 object의 integrity level보다 높거나 같아야데이터를 쓸 수 있음을 의미한다.

클락 윌슨의 상용 컴퓨터 시스템과 군 전용 시스템에 대한 비교 논문의 의의를 서술하시오.

1983년 클락윌슨이 상용컴퓨터시스템의 보안정책과 군에서 쓰는 보안정책의 비교논문을 낸 바 있다. 내용의 핵심은 군에서는 Integrity가 중요하지 않을지 모르나 상용시스템에서는 Confidentiality보다 Integrity가 훨씬 중요하기 때문에 Integrity와 관련한 security requirement를 명확히 정의하고 디자인하는 것이 중요하다고 주장하였다. 이 논문은 사람들이 접근통제정책이 confidentiality 뿐만 아니라 Integrity도 중요하다고 생각하게 되었다는 점에서 의의가 있다.
 

Clark-Wilson Model을 설명하시오

가장 큰 특징 & 종류 및 개념
Clark-Wilson 모델의 가장 큰 특징은 Well formed transaction을 정의했다는 것이고 이는 절차가 잘 정의된 프로세스를 의미한다.
Clark-Wilson Model은 CDIs, UDIs, TP, IVPs의 4가지 요소로 구성된다.

• CDIs: Contrained Data Items의 약자로 Integrity가 중요한 데이터셋을 의미한다.
• UDIs: Unconstrained Data Items의 약자로 Integrity가 중요하지 않은 데이터셋을 의미한다.
• TP: Transformation Procedures로 일종의 업무 매뉴얼을 의미하는 것으로 업무 매뉴얼에 따라 절차가 엄격히 정의된 프로세스를 통해서만 접근 가능한 것이 특징이다. 예컨데 CDIs에 접근하려는 USER는 반드시 TP를 통해서만 접근해야 한다.
• IVPs: Integrity Verification Procedures의 약자로, 주기적으로 CDIs의 무결성이 올바르게 지켜지고 있는지를 검증한다.

이러한 Clark-Wilson 모델의 예는 은행시스템이 있다. 은행에서 돈과 관련된 모든 데이터는 CDIs에 해당하고 이외의 데이터는 UDIs에 해당한다. TP는 입금, 출금, 계좌이체와 같이 명확히 정해진 절차가 있고 이 절차에 따라 움직이는 것을 의미한다. 그리고 어제 은행이 가지고 있던 돈에서 오늘 들어온 돈을 더하고 나간 돈을 빼는 것과 같이 정기적으로 검증과정을 거치는 것을 IVPs라고 한다.
Clark-Wilson 모델은 크게 두 개의 업적을 가진다. 첫 번째는 상용시스템에서 Integrity가 중요할 수 있음을 강조했다는 점이다. 두 번째는 기존 BLP, Biba모델은 사용자가 데이터에 접근한다 생각하였지만 Clark-Wilson은 사용자는 프로그램(TP)에 접근하고 프로그램이 데이터에 접근한다고 하였다.
 

HRU (Harrison-Ruzo-Ullman) 모델에 대해 서술하시오.

HRU 모델은 BLP 모델의 전제조건이었던 평정속성을 위반했다는 McLean에 비판에 의해 권한이 바뀌어도 보안을 유지할 수 있는 방안을 연구한 모델이다. 동작원리는 권한을 요구하는 요청이 올 경우 임시로 matrix를 변경해보고 state가 잘 유지되는지를 검증한다. 예를 들어 matrix를 바꿨을 때도 기존과 동일하게 SS-property가 충족되는지를 체크하는 것이다. 충족된다면 바꾸고 충족되지 않으면 바꾸지 않는다는 것이 기본 개념이다. 하지만 HRU 모델은 state가 잘 유지되는지를 체크하는 것이 쉽지 않다는 단점이 있다. 따라서 HRU 모델에서는 제약조건을 추가하였다.

• Monotonic protection system: destory나 delete 명령이 없는 시스템을 의미한다.
• Monocondtional system: 각 명령의 조건 부분에 하나의 조건만 있는 시스템을 의미한다.
• Finite number of subjects: subject의 개수가 finite한가?

Chinese Wall 모델에 대해 서술하시오.

Chinese Wall 모델은 HRU 모델이 더 발전된 형태이다. 접근권한이 사전에 세팅되고 요청이 있을 때마다 접근권한이 동적으로 변경되는 특징을 가진다. 또한 Chinese-Wall 모델은 subject의 접근권한이 바로 직전에 한 행동에 의해 다음 접근권한이 결정된다는 특징을 가지고 있다. 예를 들어 변호사가 CITI 은행의 변호를 맡는 순간 KB, NH, SH와 같은 다른 은행에 대한 접근권한이 차단된다. 하지만 S-OIL, GS 칼텍스와 같은 이해상충집단(COI, Conflict Of Interest)이 아닌 클래스의 데이터에는 접근할 수 있다. Brewer와 Nash가 Chinese-wall 모델을 정의할 때도 SS-property와 *-Property를 충족해야 한다고 하였다.

• SS-Property: 데이터에 접근하는 동시에 이해상충집단에 해당하는 데이터의 접근하지 못함을 의미한다. 하지만 만약 이해상충되더라도 접근을 계속 유지하고 있거나 완전히 COI Class에 속한다면 접근 가능하다.
• *-Property: Information flow에 있어 이해상충집단간의 un-sanitised information이 흐르지 못하도록 하는 것이다. 또한 write access는 이해상충집단에 속해있는 object가 현재 읽혀지지 않고 있거나, 또는 un-sanitised information을 가지고 있을때만 허용된다.

RBAC에 대해 서술하시오

RBAC은 역할기반접근통제정책이다. 기존의 DAC, MAC에서의 접근권한이 사람에게 부여되지만 실제 세상에서의 접근권한은 사람에게 부여되는 것이 아닌 그 사람의 역할에 부여된다는 점에 기반하였다. (그림 그리기) User와 Role사이에 Session이 있고, 이는 동시에 여러 개의 역할을 할당받기 위해 필요한 개념으로, 윈도우에서 창을 여러개 띄워 놓는 것과 같다. RBAC에서 role이 분리되어야할 경우가 2가지가 존재하는데 첫 번째로는 static seperation of Duty로 예를 들어 한 사람이 총무의 역할을 맡으면서 동시에 감사의 역할을 맡을 수 없음을 의미한다. 두 번째로는 dynamic seperation of Duty로 예를 들어 은행 업무를 하고 있는 직원의 역할을 가진 동시에 고객의 역할을 할 수없음을 의미한다.
 

우리나라의 리스크 관리에 있어 최대 문제점은 무엇인가?

데이터의 중요도에 따른 데이터의 등급화가 되어 있지 않다는 것이 핵심이다. 중국의 경우에도 의료, 금융, 개인정보 등을 Low, Medium, High, Very High와 같이 4단계로 나누나 우리나라의 경우 그렇지 않다. 또한 데이터의 중요도에 따라 데이터의 등급을 나눈 뒤 망분리와 망연계가 명확히 되어야 하지만 잘 이루어지지 않고 있는 것이 실태이다.
 

Covert Channel은 무엇이고 Side Channel과 어떻게 다르며 이 Covert Channel을 해결하기 위한 방안은 무엇인가?

Covert Channel은 설계자가 의도하지 않았던 방향으로 데이터를 유출하는 채널을 의미한다. Side Channel과의 차이점은 Covert Channel의 경우 송신자와 수신자간의 Covert Channel에 대한 약속이 필요하고, Side Channel의 경우 송신자가 필요하지 않고 수신자 입장에서 별도의 채널을 통해 정보를 추출하는 것이다.
Covert Channel은 기본적으로 전부 막을 수는 없으나 이를 해결하기 위한 방안으로 Lattice Based 모델이 있다. Lattice Based 모델은 수학에서 이야기하는 Lattice 구조를 이용하여 정보가 흘러도되는 것과 흐르면 안되는 것을 포멀하게 정의하는 모델이다. Lattice 구조가 성립하는 조건으로는 GLB와 LUB가 있고, 모든 Subset에 대해서 GLB와 LUB가 존재할 경우에 해당한다. 하지만 현업에서 실제로 사용하기에는 복잡하다는 단점이 존재하고 이를 조금 더 적용하기 쉽고, 구현에 용이하게 만든 모델이 Non-Interference 모델이다. Non-Interference 모델은 covert-channel과 Inference attack을 주로 다룬다.
 

Execution Monitor의 개념과 특징을 서술하시오.

• Execution Monitor는 이벤트가 발생할 때 시스템 정책들에 위반되는 사항이 있는지 확인하는 시스템이다. 구체적으로 어떤 함수가 error 상황을 야기하도록 하는 위험한 함수인지 아닌지를 검증하는 것으로, 그 함수 외부로 undesirable exception이 propagate 되지 않는지 또 그 결과에 대한 report가 제대로 되는지를 모니터링 한다.
• Execution Monitor는 운영체제 안에서 동작하는 것으로 프로그램을 한 줄 한 줄 실행시켜보며 이벤트가 발생했을 때 EM 시스템이 괜찮은지 검증 후 괜찮다면 실행시키고 문제가 발생하면 빠져나오는 시스템이다. EM을 활용하면 DAC, MAC 정책에서 정책을 위반 여부를 관찰할 수 있는 것이 특징이다. 하지만 Information flow security 같이 정보가 제대로 흐르는지 아닌지는 EM으로 체크할 수 없다. 예를 들어 DDOS 같은 경우는 EM으로 체크할 수 없는데, 이는 EM이 항상 과거의 데이터를 보기 때문에 DDOS와 같이 미래를 보아야 하는 공격은 체크할 수 없는 단점이 있다. 즉 EM으로 모든 보안정책을 제어하기에 한계가 있고 불충분하기에 RM에 다른 요구사항이 추가되어야해서 복잡한 구조를 가지게 된다.

Liveness property와 Safety property에 대해 서술하시오.

Liveness property는 프로그램은 언젠가 종료될 것이지만 언제인지 알 수 없다는 의미를 가지며, Safety property는 나쁜일은 생기지 않는다는 것을 의미한다. Liveness property는 미래를 보아야 하기 때문에 어렵고 safety property는 과거를 보기 때문에 비교적 쉽다. Execution Monitor는 safety property에 속하는 것은 전부 측정할 수 있다. 하지만 EM으로는 모든 보안정책을 제어하기엔 한계가 있고, 불충분하기에 Reference Monitor에 다른 것이 추가되어야 해서 복잡한 구조를 가지게 된다.
 

Reference Monitor의 세 가지 기본원칙을 설명하시오

• Reference Monitor: 감시 프로그램인 Reference Monitor는 운영체제에서 발생하는 모든 이벤트를 감시할 수 있어야 하고 정책에 위반되는 것을 차단해야 한다.
• Simplicity & Assurance: RM이 중요하기 떄문에 수학적으로 증명해야 한다. 하지만 RM이 복잡하다면 수학적 증명이 어려워진다. 따라서 RM을 단순하게 만들고 이를 통해 Assurance를 높여야 한다.
• Evaluation & Certification: 평가제도를 운영하여 정부가 이를 받아들이도록 해야 한다.

Reference Monitor의 세 가지 요구조건을 더 명확히 표현하여 설명하시오

• Complete Mediation: RVM이 있어서 운영체제에서 발생하는 모든 이벤트를 통제할 수 있어야 한다. (Reference Validation Mechanism)
• Tamper-Proof: RVM은 해커가 리버싱할 수 없어야 하고 non-bypassible하여 해커가 우회할 수 없어야 한다.
• Verifiable: RVM은 충분히 작아서 수학적으로 검증 가능해야 한다.

Trusted Computing Base (TCB)를 설명하시오.

Security Kernel과 다른 보호메커니즘을 결합한 것으로, TCB는 신뢰가 필요한 모든 H/W와 S/W가 포함된다. (Security kernel: Reference Monitor를 실제로 구현해둔 것을 의미한다.)
 

Authentication vs Identification을 설명하시오.

Authentication은 사용자 인증을 의미하고, Identifiaction은 개인 식별을 의미한다. 예를 들어 네이버에 아이디와 비밀번호로 로그인하는 것은 사용자 인증에 해당하고 범죄현장에서 지문을 발견하여 데이터베이스에서 매칭하여 범인을 알아내는 것은 개인 식별에 해당한다. 내가 나임을 증명한다면 Authentication이고, 타인이 나를 식별한다면 Identification이다.
 

High Assurance Crypto Library란 무엇인가?

설계부터 구현까지 수학적으로 전부 증명된 것을 의미한다.
 

Secure Design Principle 12가지를 서술하시오

1. Least Privilege: 사람 또는 시스템이 필요로 하는 최소한의 권한만 부여하는 것을 의미한다.
2. Fail-Safe Defult: 명시적 허용이 아니면 거부를 의미한다. 예를 들어 방화벽 룰셋에 설정되어 있지 않다면 패킷을 drop하는 것과 같다.
3. Economy of mechanism: H/W나 S/W를 만들 때 설계를 심플하고 작게 만들어야 함을 의미한다.
4. Complete Mediation: 중요 자원에 접근하려는 것을 모두 통제할 수 있어야 함을 의미한다.
5. Design by Contract: 정해진 인터페이스나 프로토콜로만 중요 자원에 접근할 수 있어야 함을 의미한다.
6. Open Design: 설계도의 소스코드가 공개되더라도 안전도를 유지할 수 있어야 할 수 있어야 함을 의미한다.
7. Seperation of Privilege: 중요 권한은 분리되어야 함을 의미한다.
8. Least Common Mechanism: 공통 모듈 사용 최소화를 의미하는 것으로, Economy of mechanism과 정면으로 위배되는 특징이 있다.
9. Psychological Acceptability: 심리적으로 사용하기 좋아야함을 의미하는 것으로 Usable security라고도 불린다.
10. Defense In Dept: 보안 시스템을 둘 때 계층적으로 구성해야함을 의미한다.
11. Effective Logging: 효율적인 로깅이 가능해야 함을 의미한다. 최근 개인정보보호법으로 인해 무엇을 기록하지 말아야 할지도 고려해야 하는 것이 특징이다.
12. Built In, Not Bolt on: 시스템을 만들고 나서 보안을 고려하는 것이 아니라 시스템을 만들때 함께 보안을 고려하는 것을 의미한다.

Design Assurance를 쉽게 달성하는 방법은?

Design Assurance를 쉽게 달성하기 위해서는 전제조건을 맞추어 두면 된다. 또한 가정(Assumption)이 많으면 쉽게 달성할 수 있다.
 

Design Assurance를 입증하는 방법에 대해 서술하시오

크게 2가지로 나뉘며 Symbolic method와 Confidential method로 나뉜다.

• Symbolic Method:  수학적 증명을 자동화하는데 사용하는 방법으로, 주로 리플레이 공격을 분석하는데 사용된다. 하지만 confidential method와 달리 복잡한 공격에 대해서는 증명이 어렵다는 단점을 가진다.
• Computational Method: 정교한 공격에 대해 수학적 증명이 가능한 방법으로 골드아서와 미칼리가 주로 기여한 분야이다. Symbolic method와 달리 자동화시키기 어렵기 때문에 대부분 manual하게 증명하는 것이 특징이다.

SPN (Substitution-Permutation Network)의 특징을 서술하시오.

주로 대칭키인 AES 암호화에 사용되는 네트워크로, 네트워크 내부적으로 크게 Diffusion과 Confusion이 있다. Diffusion은 확산으로 암호문과 평문사이의 관계를 알아낼 수 없도록 복잡하게 섞어주는 것을 의미한다. 주로 permutation을 통해 데이터의 순서를 바꾸는 방법(P-Box)을 사용한다. Confusion은 혼돈으로 키와 암호문간의 관계를 알아낼 수 없도록 복잡하게 섞는 것을 의미한다. 주로 Substituion을 통해 다른 symbol로 바꾸는 방법(S-box)을 사용한다.  이러한 Diffusion과 Confusion을 극대화하기 위해서는 permutation과 substitution을 반복적으로 하면된다. 이러한 대칭키 암호에서 Design Assurance를 입증하기 위한 전제조건으로는 S-box와 P-box는 안전한 것으로, 특히 S-Box는 랜덤하다는 전제가 필요하다.
 

RSA 암호의 특징에 대해 설명하시오

디피와 헬만이 공개키 암호를 정의하였고 이러한 정의를 충족하여 만들어진 최초의 공개키 암호가 RSA 암호이다. RSA 암호의 안전성은 소인수분해에 기반한다. 하지만 RSA 암호의 해독방법은 소인수분해 말고도 존재하여 안전성은 증명되지 않았다. 대신 소인수분해 문제를 제외하고 RSA 암호에 대한 공격기법이 개발되면 그에 맞추어 업그레이드 시키는 것이 특징이다.
 

레빈암호 시스템에 대해 설명하시오

레빈암호시스템은 RSA 암호시스템과 달리 수학적구조가 아름답다. RSA 암호시스템은 기본적으로 안전성은 소인수분해 문제의 어려움에 기반하지만 소인수분해이외에도 암호를 해독할 수 있는 방법이 존재한다. 따라서 RSA 암호를 해독할 수 있는 공격 방법이 만들어질 때 마다 암호시스템을 업그레이드한다. 이와는 달리 레빈암호시스템은 해독가능한 방법이 소인수분해 밖에 없다는 것을 수학적으로 증명되어 있다. 이러한 레빈암호시스템은 Design Assurance를 만족하는 최초의 공개키 암호라는 것에 의의가 있다.
 

Random Oracle Model이란 무엇인가?

전제조건이 해쉬암호는 안전하다는 것으로, 정확히는 해시암호의 출력은 랜덤함을 전제하는 것을 의미한다. 이를 통해 기존의 theoretical한 암호시스템과 practical한 암호시스템이 결합되기 시작되었다는 점에서 의의가 있는 것이 특징이다.
 

Perfect Secrecy의 특징을 서술하시오.

Perfect secrecy는 샤논이 만든 개념으로 passive 공격자가 무한한 컴퓨팅 파워가 있더라도 암호문으로부터 어떠한 정보도 얻어낼 수 없는 것을 의미한다. 하지만 이는 대칭키에서는 성립하지만 공개키암호에는 적용할 수 없다는 단점을 가진다. 이는 공개키가 있기 때문에 전수조사로 비밀키를 찾을 수 있기 때문이다.
 

Semantic Security의 특징을 서술하시오

기존의 샤논이 만든 개념인 perfect secrecy의 단점인 공개키에서는 적용할 수 없다는 단점을 보완하기 위해 골드아서 박사가 정의한 개념으로 "유한한 컴퓨팅 파워를 가진 공격자가 암호시스템으로부터 그 어떠한 1비트의 정보도 알아낼 수 없음"을 의미한다. design assurance의 관점에서 요구사항이 한 단계 진화할 수 있었고 이후에는 이러한 정의를 충족하는 암호 알고리즘이 만들어지게 되었다는점에서 의의가 있다.
 

공개키암호의 message space가 작으면 발생할 수 있는 문제는 무엇이고 해결방법은 무엇인가?

공개키 암호에서 message space가 작다면 대칭키 암호와 달리 전수조사를 통해 해독이 가능하다는 문제점이 있다. 이를 해결하기 위한 방안으로는 같은 메시지더라도 출력값이 달라지게 하기 위해 랜덤패딩을 붙이는 방법이 있다. 이러한 랜덤패딩을 붙이는 방법이 Polynomial Security(IND-CPA)이다. 즉, 암호알고리즘이 polynomial security를 만족하려면 랜덤패딩이 필요하다.
 

Polynomial security (IND-CPA)의 특징을 서술하시오.

기존의 공개키암호시스템에서 message space가 작다면 대칭키암호시스템과 달리 전수조사를 통해 알아낼 수 있다는 단점을 보완하기 위해 나온 개념으로, 동일한 평문이 동일한 암호문을 출력하지 않도록 랜덤패딩을 붙이는 방법을 의미한다. 즉, polynomial security를 만족하려면 랜덤패딩이 필요하다. polynomial security는 semantic security와 다르게 표현되었지만 동치라는 특징을 가진다. 즉 암호알고리즘에 랜덤패딩을 추가하면 암호문으로부터 그 어떠한 정보도 노출되지 않는다.
 

암호문을 위/변조하는 Active Attacker를 막는 설계 방법은 무엇인가?

크게 3가지 방법이 있다. 첫 번째는 전자서명을 사용하는 것이다. 암호문에 전자서명을 붙여서 보내는 방식으로 가능하다. 하지만 공개키 암호문을 설계하는데 전자서명도 사용해야하기 때문에 비효율적인 방법에 해당한다. 두 번째는 Message Authentication Code를 붙이는 방법이 있다. 하지만 이 또한 MAC 알고리즘의 안전성에 대해 증명해야한다는 단점이 있다. 세 번째는 고정된 형태의 패딩을 추가하는 것이다. 하지만 semantic security를 만족하려면 랜덤한 패딩을 추가해야한다. 이러한 문제점을 해결하기 위한 방법이 OAEP이다.
 

OAEP(IND-CCA)의 특징을 서술하시오.

IND-CCA의 경우 기존의 골드아서와 미칼리의 semantic security가 passive한 공격자로 전제한다는 단점을 보완하기 위해 나온 개념으로 active한 공격자에서도 암호시스템을 안전하게 만들기 위한 방법이다. 이는 고정된 형태의 패딩을 추가하는 방식으로 충족시킬 수 있다. 하지만 semantic security를 만족하기 위해서는 랜덤패딩을 추가하여야 한다. OAEP는 이러한 고정패딩과 랜덤패딩을 함께 추가하는 방법으로 Chosen Cipher Attack에 안전하다는 특징을 가진다.
 

Non-malleability (NM-CCA)의 특징을 서술하시오.

전통적으로 암호문을 해독하거나 부분정보를 끄집어내는 방법과 달리 암호문을 해독하지 않고 암호문에 변조를 가하는 것을 의미한다. 이를 통해 암호문이 갖추어야 할 requirement가 semantic security와 non-malleability가 되었다. 하지만 후에 이는 다르게 표현되었으나 동치임이 확인되었고 결국 semantic security, polynomial security, non-malleability는 다르게 표현되었지만 하나라는 요구조건임을 확인하였다는 점에서 의의가 있다.
 

암호에서 Active 공격을 방어하기 위해 사용하는 방법은 무엇인가?

암호에서 active 공격이 많이 발생하기 때문에 암호알고리즘만 사용하지 않고 MAC과 함께 사용되는 경우가 많다. 크게 3가지 방법이 있다.

• Encrypt-and-MAC: 메시지에 대해 암호화시키고 그것과 별개로 메시지에 대해 MAC 코드를 만드는 방법이다.
• MAC-then-Encrypt: 메시지에 대해 MAC을 만들고 원래 메시지 뒤에 붙인 뒤 전체를 암호화시키는 방법이다.
• Encrypt-then-MAC: 메시지를 먼저 암호화시키고 그 암호문에 대해 MAC을 붙이는 방법이다.

여기서 주요 쟁점은 설계방법에 따른 안전도 문제(합성보안 문제)가 제기되는데 통상적으로 Encrypt-then-MAC이 가장 안전하다고 알려져있다.
 

Compositional Security란 무엇인가?

합성보안문제로 예를 들어 블록체인에서 떠오르는 분야인 DeFi에서도 사용되는 개념이다. DeFi는 머니레고시스템이라고도 부르는데 이는 소스코드가 공개되어 있어 자신들이 만들고자하는 서비스를 만들어 DeFi 시스템에 붙이는게 가능하다. 이 때 공개된 소스코드에 취약점이 있다면 DeFi 전체시스템에 대해 합성보안 문제가 야기된다. 또한 BlackHat 2017에서 발표되었던 WPA2의 사례와 같다. 유닛테스트에서는 안전함이 증명되었지만 통합테스트(합성)에서는 안전하지 않았다.
 

Zero-knowledge 시스템의 특징을 서술하시오.

암호화 알고리즘과 전자서명은 단방향으로 보내면 되는 1-way 형식이지만 세상에는 interactive하게 동작하는 것이 많다는 점에 착안하여 어떤 client, server, verifier가 interactive하게 동작했을 때 안전하다는 것은 어떻게 입증하는가와 같은 문제가 대두되면서 도입된 개념이다. 영지식 증명의 개념은 3가지 조건을 만족해야 한다.

• 완전성(Completeness): 어떠한 정보가 참일 경우에 정직한 증명자는 정직한 검증자에게 그것을 납득시킬 수 있어야 한다.
• 건전성(Soundness): 어떤 정보가 거짓일 경우에 부정직한 증명자는 거짓말을 통해 정직한 검증자에게 그것이 ‘참’임을 납득시킬 수 없어야 한다.
• 영지식성(Zero-Knowledge): 검증자는 어떤 정보가 참 혹은 거짓이라는 사실 이외에는 아무것도 알 수 없어야 한다.

CC와 EAL7에서 소프트웨어 검증보다 소프트웨어 테스팅에 의존하는가? or Code Assurance의 한계는 무엇인가?

Software Fault, Error, Failure를 설명하고 왜 구분해야 하는지에 대한 이유를 서술하시오.

• Software Fault: 소프트웨어 자체가 가지고 있는 결함을 의미하는 것으로 문제가 발생하는 근본 원인이다.
• Software Error: 불안정한 프로그램 상태를 의미하는 것으로 어떤 값을 넣어 software의 문제가 있는 Falut까지 도달하면 내부적으로 이상상태가 발생하는 것을 의미한다.
• Software Failure: Fault까지 도달하여 내부적으로 불안정한 프로그램 상태가 외부로 표출되는 것을 의미한다.

구분 없이 모두 합쳐서 bug라 부르면 안된다. 명확히 구분해야 test case가 제대로 되었는지 아닌지 구분할 수 있기 때문이다. 만약 모두 합쳐 bug라 부른다면 test case를 설명할 방법이 없어진다.
 

Software Fault의 종류는 무엇이 있는가?

• Random Fault: 사람의 실수에 의해 발생하는 Fault를 의미한다.
• Intentional Fault: 의도성을 가지고 발생시킨 Fault를 의미한다.

Software Testing과 Debugging의 차이점을 서술하시오.

Software testing은 소프트웨어를 체크할 수 있는 test value인 input값을 뽑아내는 것을 의미한다. 반면 debugging은 외부로 표출된 failure를 보고 결함이 있는, 문제의 원인이 되는 fault부분을 찾아가는 것을 의미한다.
 

Static testing과 Dynamic testing의 차이점을 서술하시오

Static testing은 프로그램을 실행시키지 않고 테스팅하는 것을 의미하는 것으로 소스코드, 바이너리, 중간언어가 될 수 있다. 반면 Dynamic testing은 프로그램을 실행시키면서 테스팅하는 것을 의미하는 것으로 체계적인 테스팅을 위해 DART라는 프로그램을 사용하기도 한다.
 

Black box testing이 먼저인가 White box testing이 먼저인가 그리고 이유를 설명하시오.

black box testing이 먼저이다. 개발공정상 개발단계 전까지 코드가 없기 때문에 white box testing을 할 수 없다. black box testing은 바이너리가 아닌 코드가 없이 테스팅하는 것을 의미한다. 때문에 설계문서와 같은 모든 것들이 black box testing의 대상이 된다. 이후 코드가 완성되면 white box testing까지 하여 정교한 테스팅이 가능해진다.
 

Validation과 Verification의 차이점을 서술하시오

Validation은 사용자의 마음에 맞도록 만들어졌는가를 의미하는 것으로 Verification보다 어려운 것이 특징이다. 여기에는 사용자의 요구를 전부 분석하여 requirement를 제대로 도출하였는지까지가 들어간다. Verification은 specification이 있고 이를 통해 requirement가 제대로 도출되었다고 전제하고 requirement가 specification대로 만들었는지 검증하는 것으로 validation보다 쉽다는 것이 특징이다.
 

test case 선정 시 잘 도출하였는지 평가하기 위해 네 요소를 사용하는데 이 네 요소와 특징에 대해 서술하시오.

4가지 요소는 RIPR이다.

• Reachability: test input 값이 문제의 근원인 소프트웨어 fault가 있는 지점까지 도달해야 함을 의미한다.
• Infection: test input 값이 문제의 근원인 소프트웨어 fault까지 있는 지점까지 도달하여 프로그램 내부 상태가 불완전한 상태(error state)로 만드는 것을 의미한다.
• Propagation: 불완전한 상태가(erorr state)가 전이되어 최종적으로 Incorrect한 final state로 가는 것을 의미한다.
• Revealability: 프로그램의 Incorrect한 final state가 실제로 외부로 드러나는 것을 의미한다.

Test requirement와 Coverage Criteria의 관계는 무엇인가?

test case → test set → test requirement → coverage criterion → coverage criteria의 단계를 가지는 구조이다.
둘 간의 관계를 예시를 들면 다음과 같다. 예를 들어 젤리의 맛이 6가지와 색이 4가지가 있을 때 Coverage Criteria는 두개가 될 수 있다. 젤리봉투를 뜯었을 때 맛이 6가지가 있어야 한다는 C1의 Criterion과 색이 4가지가 있어야 한다는 C2의 Criterion이다. C1과 C2를 합쳐 Coverage Criteria라고 하며, 이를 통해 test requirement를 도출할 수 있다.
 

소프트웨어를 모델링하는 대표적인 방법을 서술하시오. (Coverage Criteria를 줄 때 사용하는 방법)

소프트웨어를 모델링하기 위해 사용하는 방법은 크게 4가지로 Input domain, Graph, Logical Expression, Syntax Structure 방식이 있다. 어떤 방법론을 사용하느냐에 따라 coverage criteria는 다른 형태로 주어진다.

• Input Domain model based testing: 함수에 들어가는 입력 값만보고 테스트케이스를 만드는 계획을 세우는 방법을 의미한다.
• Graph model based testing: 소스코드를 그래프의 형태로 바꾸어 모델링하는 방법으로 소프트웨어 테스팅에 가장 많이 사용되는 기법이다.
• Logical Expression model base testing: 조건문만 가지고 test case를 도출하는 모델링 방법으로, predicates라고도 부른다.
• Syntax Structure model based testing: 문법 규칙을 주고 문법 규칙에 따라 test case를 생성하는 모델링 방법이다. 그래프만큼 모델링에 많이 사용되며 grammar-based modeling이라고도 한다.

Generator와 Recognizer를 설명하시오.

Generator는 coverage criteria를 주면 알아서 test case를 만들어주는 것을 의미하며, Recognizer는 test case가 주어지면 어느 coverage까지 달성하는지를 분석해주는 것이다.
 

Graph model based testing의 특징을 서술하시오.

소스코드를 그래프의 형태로 바꾸어 모델링하는 방법으로 소프트웨어 테스팅에서 가장 많이 사용되는 기법이다. 크게 2가지 기법으로 Structural coverage criteria와 Data flow coverage criteria로 분류 된다. (분류 특징 서술하기). 그래프 모델링 기법은 소스코드에 사용하는 것이 주로 일반적이나 설계단계의 문서와 더불어 제품을 개발하는 여러 단계에 테스팅하는데 활용할 수 있다. 그래프 모델링에서 test case 도출을 어렵게하는 요소로는 루프가 있다. 기존에는 루프를 만나면 사이클을 한 번만 돈다고 가정하였으나 이는 abstraction gap이 크다는 단점이 존재한다. 따라서 이를 해결하기 위한 방안으로 touring, sidetrips, detours라는 prime path 를 사용하여 abstraction gap을 줄이려는 노력을 하고 있다.
 

Call-Graph를 설명 하시오

Control Flow Graph, Data Flow Graph 이외에 Call Graph가 있는데 이는 어떤 모듈이 어떤 모듈을 부르는가에 대한 호출 관계를 표시하는 그래프이다. 모듈을 어떻게 분배시킬까에 대한 sub-system level에서 사용되며, 결과적으로 design integration test에 활용한다.
(좀더 포멀하게 바꿀 수 있으면 좋겠습니다.)
 

Logical Expression Model based testing에 대해 서술하시오.

조건문만 가지고 test case를 도출해내는 모델링 방법으로 이를 predicates라고도 한다. logic expression은 소스코드에서 발견되는 predicates와 clause에 따라 이를 테스트할 수 있는 test case를 도출하는 것이 특징이다. clause에는 major clause와 minor clause가 있다. major clause는 predicates를 결정짓는 핵심이되는 것을 의미하며, minor clause는 그 이외의 것을 의미한다. 효율적인 test case 도출을 위해서는 major clause를 도출해내는 것이 중요하다. 하지만 logical expression 모델링 방법은 프로그램을 실행시키전까지는 파악하기 어렵다는 단점을 가진다. 예를 들어 어떤 값에 n을 나누거나 y를 나눌 때 어떤 값이 나올지 알기 어려운 것과 같다.
 

Syntax Structure Based Testing에 대해 서술하시오.

문법 규칙에 따라 test case를 생성하는 모델링 방법이다. Graph-based 모델링 방법만큼 많이 사용되며 Grammar-based modeling이라고도 한다. grmmar가 구성되면 두 가지 목적으로 사용가능하다. 첫 번째는 grammar에 맞춰 여러 test case를 생성할 수 있고, 두 번째로는 어떤 값이 grammar를 충족하는지에 대한 여부를 확인할 수 있다.
 

Structural Coverage Criteria과 Data Flow Coverage Criteria의 특징을 서술하시오.

Control Flow는 structural coverage criteria와 연계되고 Data Flow는 data flow coverage criteria로 연계된다. structural coverage criteria는 노드와 엣지로 그래프를 정의하고 분기(e.g. if)를 통해 프로그램이 실행되는 코드가 달라지는 것을 기준으로 하는 방법이다. 대표적으로 node coverage, edge coverage, edge-pair coverage, complete path coverage, specified path coverage 등이 있다.
data flow coverage criteria는 프로그램이 어떻게 변수가 정의되고 사용되는지를 기반하여 커버리지 기준을 적용하는 방법을 의미한다. 즉, 데이터 흐름 그래프상에서 각 변수의 def-use-pair가 다양한 방식으로 실행되도록 하는 기준이다. 대표적으로 all-defs coverage, all-uses coverage, all-du-paths coverage이 있다.
 

mutant에 대해 설명하시오

mutant는 원본 프로그램이 있고 일부를 바꾸었을 때를 의미한다. mutant는 크게 valid mutant와 Invalid mutant로 나뉜다. valid mutant는 시드값을 바꾸었을 때 그래머를 만족하는 mutant를 의미하며, Invalid mutant는 시드값을 바꾸었을 때 그래머를 만족하지 않는 mutant를 의미한다. 주로 mutation testing에 사용 된다.
 

mutation testing을 설명하시오.

grammar(subject)로부터 ground string(seed) 값을 뽑아낸다. 이후 ground string(seed)에서 일부를 바꾸면 mutant가 생성된다. 이 때 test case를 generate하여 ground string와 mutant에 각각 넣고 같은지를 비교하며 이를 mutation testing이라 한다. 쉽게 말해 원본 프로그램은 run tests on subject에 들어가고 변형된 프로그램은 run tests on mutant에 들어간다. 이후 test case를 생성하여 각각의 프로그램에 넣었을 때 원본 프로그램과 변형된 프로그램을 구분할 수 있으면 이를 mutant를 죽였다 표현하고 이를 mutation testing이라 한다. 
 

program-based mutation testing에 대해 서술하시오.

test case가 제대로 만들어졌는지 test할 때 주로 사용되는 testing 기법이다. coverage 개념과는 다르며, 얼마나 많은 mutant를 제거하였는지가 핵심이다. 즉, grammar를 따르지 않은 mutant와 grammar를 제대로 따른 원본을 test case가 구별해낼 수 있는 가이다.
 

여러 소프트웨어 테스팅 기법 중 grammar-based mutation testing이 가지는 특징은 무엇인가?

Input domain, graph, logical expression 등의 테스팅 기법과 달리 grammar-based mutation testing은 test case를 test 할 수 있다는 것이 가장 큰 특징이다. 또한 기본적인 grmmar를 정해두고 조금씩 변형해가며 input을 넣어보는 퍼징에도 효과적으로 사용할 수 있다.
 

Software verification의 특징을 서술하시오

software testing의 한계인 실제로 버그가 없음을 입증하기 위해 모든 가능한 인풋값에 대해 전부 테스트해보아야 한다는 것을 보완하기 위해 나온 것으로, software가 requirement를 충족하는지 충족하지 않는지를 수학적으로 증명하는 방법이다. 하지만 문제점은 어떤 software가 requirement를 충족하는지 하지 않는지를 증명하는 것은 undecidable problem에 속하기 때문에 이론적으로 software verification이 불가능하다고 입증되었다. 하지만 현실에서 마주하는 것은 모든 software가 아닌 특정 타입의 software이기 때문에 범위를 줄이게 되면 불가능하지 않다. software verification에서 사용되는 요소 기술의 종류는 symbolic execution, automatic theorem prover, model checker 등이 있다.
 

Concrete Execution이란 무엇인가?

프로그램을 실행시키면서 변수 값이 어떻게 변형되어 가는지 확인하며 프로그램이 제대로 동작하는지 하지 않는지를 검증하는 것이다.
 

Symbolic Execution에 대해 서술하시오.

기호실행은 프로그램에 구체적인 값을 넣지 않고 모든 것을 기호로 바꾸어 전개시키고, 실제 테스팅하고자 하는 영역의 방정식을 충족하는 값을 구하는 방식이다. 전개된 상태에서 방정식만 풀면 어떤 경로를 테스트할지 test case를 자동으로 뽑아낼 수 있다. 즉 testing input generation이 가능하여 어떤 경로로 갈지 바로 뽑아낼 수 있다는 것이 장점이다. 반대로 path explosion 때문에 적용이 쉽지 않은 것이 단점인데 이는 구체적인 값이 아니라 기호를 넣으면 길이가 긴 경로가 나올 수 있기 때문이다. 이에 대한 대안으로는 pre-conditioned symbolic execution으로, 이는 프로그래밍할 때 BOF와 같이 에러가 많이 발생할 수 있는 조건에 사용할 수 있다. 보안관점에서는 buggy path만 체크하면 경우의 수가 줄어 Exploitable한 path에 대해 symbolic execution하여 효과적인 test case 도출이 가능하다.
 

Automatic Theorem Prover에 대해 서술하시오.

software verification에서 자주 사용되는 요소 기술 중 하나이다. 프로그램을 정형명세로 바꾸어 표현하는 것이 특징이다. 구성요소는 3가지로 variable, precondition, postcondition이 있다. 만약 a와 b를 더한 결과인 result를 출력해주는 프로그램이 있다 가정할 경우 a,b,result는 variable에 해당하고 이에 할당된 초기값은 precondition에 해당한다. 마지막으로 a, b, result에 대한 관계는 postcondition에 해당한다. 프로그램이 전부 수행되었을 때 Automatic Theorem Prover가 자동으로 정형명세를 충족하였는지 검증하며, 이를 Floyd-Hoare Triple이라고도 한다.
 

Floyd-Hoare Triple에 대해 서술하시오.

Variable, Precondition, Postcondition으로 구성되는 것으로, Precondition {P}가 주어졌을 때 논리적 흐름에 따라 전개되면 반드시 Postcondition {Q}에 도달한다. 따라서 프로그램에 Precondition과 Postcondition을 정형명세로 바꾸어 중간 중간 끊어서 주게되면 실제 프로그램이 제대로된 논리 흐름을 따르는지 검증할 수 있는 것이 특징이다. 이러한 Precondition과 Postcondition을 정형명세로 표현하면 Theorem Prover가 정형명세를 지키고 있는지를 검증한다.
 

(Automatic) Theorem Prover와 Model Checker의 차이를 서술하시오.

Model Checker는 기본적으로 automatic theorem prover에서 확장된 개념이다. 둘간의 차이점은 크게 자동화 여부, 적용 범위, requirement 개수로 3가지다.
자동화여부: theorem prover의 경우 프로그램 중간중간에 precondition과 postcondition을 정형명세로 다 입력해주어야 하는 반자동이다. 반면 model checker는 프로그램을 모델로 바꾸고 모델이 도달해야할 요구사항을 준 뒤 충족했는지의 여부를 yes or no로 출력 가능한 것으로 완전 자동에 해당한다.
적용범위: theorem prover의 경우 반자동이기에 적용 범위가 넓어 많은 프로그램에 적용할 수 있다 반면 model checker는 적용할 수 있는 프로그램이 theorem prover 보다는 적다는 단점을 가진다.
requirement 개수: theorem prover는 반자동인 대신 체크할 수 있는 (security) requirement개수가 많고, model checker는 완전자동이지만 적용할 수 있는 (security) requirement 개수가 적다.
 

Model Chcker에 대해 서술하시오.

모델 체커는 프로그램을 모델링하여 모델체커에 넣고 도달해야할 requirement를 주어 도달여부를 검증하는 것으로, 관점을 조금 바꾸면 exploit을 자동 생성하는 도구를 만들어 counter example을 뽑을 수 있는게 특징이다. 아래와 같이 아키텍처가 구성된다(그림 그리기). 이를 활용하여 cyber grand challenge에서 취약점 탐지 자동화 도구가 나왔었다. 하지만 이는 모든 가능한 exploit 코드를 만들어지는 것은 아닌데 이는 취약 가능성이 높은 buggy path만 보기 때문이다.
 

부분 적분은 미적분학에서 두 함수의 곱을 적분하는 기법이다. 치환 적분은 미적분학에서 기존 변수를 새로운 변수로 바꾸어 적분하는 기법이다. 부분 적분은 변수가 바뀌지 않으므로 적분 구간이 바뀌지 않지만, 치환 적분은 변수가 바뀌므로 적분 구간이 바뀐다. 부분 적분은 치환 적분이 적용되지 않을 때 사용한다. 

부분적분

부분적분에서는 두 함수를 $f(x)$와 $g(x)$로 두고 적분을 진행한다. 이 때 $f(x)$와 $g(x)$로 두는 함수의 기준이 존재한다. 그 기준은 미분의 용이성과 적분의 용이성이다. 일명 로다삼지로 알려져 있는데 로그함수, 다항함수, 삼각함수, 지수함수를 뜻한다. 만약 로그함수에 가깝다면 미분이 쉬우므로 $f(x)$로, 지수함수에 가깝다면 적분이 쉬우므로 $g(x)$로 두어야 한다. 이는 추후 계산의 용이성을 위함이다. 두 함수를 두는 방법의 예로, 로그함수와 삼각함수가 곱해진 경우라면 로그함수는 $f(x)$로 삼각함수는 $g(x)$로 둔다. 또 다항함수와 지수함수가 곱해진 경우라면 다항함수를 $f(x)$로 지수함수를 $g(x)$로 둔다. 로다삼지의 예시로 로그함수는 $logx$, $\ln x$를 말하고, 다항함수는 $n$차 다항식/일차함수/이차함수를 말한다. 또 삼각함수는 $sin$, $cos$, $tan$, $secx$, $cscx$, $cotx$를 말하고, 지수함수는 $n^x$, $e^x$를 말한다. (참고로 지수함수를 부정적분하는 공식은 $\int e^{f(x)}dx = {e^{f(x)} \over f'(x)} + C$다.)

그렇다면 부분적분의 공식은 무엇이고 어떻게 유도될까? 부분적분의 공식은 다음과 같다.

$\int f(x)g'(x)dx = f(x)g(x) - \int f'(x)g(x)dx$

이를 유도하는 과정은 매우 간단하다. 부분적분은 미분가능한 두 함수 $f(x)$, $g(x)$가 있을 때 두 함수의 곱인 $f(x)g(x)$를 미분한다. 미분한 결과는 $\{f(x)g(x)\}' = f'(x)g(x) + f(x)g'(x)$이다. 이 상태에서 다시 적분하면 $f(x)g(x)$가 되어야 할 것이다. 따라서 양변을 x에 대해 적분하면 $f(x)g(x) = \int f'(x)g(x)dx + \int f(x)g'(x)dx$가 된다. 이 때$\int f'(x)g(x)dx$를 이항하게 되면 위 공식이 된다.

그렇다면 3개의 예시를 통해 실제로 부분적분을 적용해보자. 만약 $\int xe^xdx$라면 미분이 쉬운 다항식인 $x$를 $f(x)$로, 적분이 쉬운 지수함수인 $e^x$를 $g'(x)$로 둔다. 부분적분 공식에 의해 $\int xe^xdx = xe^x - \int 1\times e^xdx$가 되므로 결과적으로 $xe^x-e^x+C$가 된다. $e^x$를 적분하면 $e^x$가 되므로. (+미분해도 $e^x$)

두 번째로 $\int \ln xdx$라면 $f(x)$를 $\ln x$로 $g'(x)$를 1로 둔다. 부분적분 공식에 의해 $\int \ln xdx = x\ln x - \int {1\over x}xdx$이다. 따라서 $\int \ln x = x\ln x - \int dx$가 되므로 결과는 $\int \ln x = x\ln x - x + C$가 된다.

세 번째로 $\int x\sin 2xdx$라면 $f(x)=x$로, $g'(x)=\sin 2x$로 둔다. 부분적분 공식에 의해 $\int x\sin 2xdx = x\times -{1\over 2}cos2x - \int 1\times -1{1\over 2}cos2xdx$가 되고 추가 계산하면 결과적으로 $\int x\sin 2xdx = -{1\over 2}xcos2x + {1\over}4\sin 2x + C$가 된다.

이러한 부분적분을 매우 쉽게할 수 있는 경우가 있다. 만약 계속 미분하면 0이되는 함수와 계속 적분할 수 있는 함수와의 곱이라면 가능하다. 아래 그림의 두 예시와 같은 과정으로 이뤄진다. 참고로 +와 -는 차례대로 번갈아가며 적용한다. 또 아래의 $g(x)$는 위의 $g'(x)$와 같다.

치환 적분

치환 적분은 복잡한 함성함수를 적분할 때 사용하는 방법으로 $ g(x) = t$ (이 때 g(x)는 미분가능 함수)와 같이 적분 변수($x$)를 다른 변수($t$)로 바꾸어 적분하는 방법이다. 예를 들어 $\int \cos(2x+1)dx$와 같은 함수를 적분해야 하는 상황에서 $2x+1 = t$와 같이 치환하여 단순화 시키는 것이다. 먼저 결론을 말하자면 치환 적분의 공식은 다음과 같다.

$\int f(x)dx = \int f(g(t))g'(t)dt$

그렇다면 이 치환 적분의 공식은 어떻게 유도될까? 간단하다. 먼저 $dy \over dx$는 $x$에 대한 $y$의 변화량이다. 하지만 이는 ${dy \over dx} = {dy \over dt} {dt \over dx}$로도 표현할 수 있다. 이후 $\int f(x)dx$라는 식이 있을 때 $x = g(t)$로 둔다. 이때 $x$를 미분하면 ${dx\over dt} = g'(t)$가 된다. 이를 기존의 식에 대입하면 $\int f(g(t))g'(t)dt$가 된다. 즉 $x$에 대한 적분을 $t$에 대한 적분으로 치환한 것이다.

이 치환 적분 공식을 2개의 예시에 적용해보자. 첫 번째로 $\int \cos (2x+1)dx$의 부정적분을 구해보자. 먼저 $2x+1 = t$로 둔다. 이후 양변을 $x$에 대해 미분하면 ${dt\over dx}=2$이므로, $dx={1\over 2}dt$가 된다. 따라서 이를 적분하고자 했던 식에 대입하면 $\int \cos t \times {1\over 2}dt$이 된다. 이제 이를 적분하면 ${1\over2} \sin t + C$의 형태가 되며 t에 대환 치환을 다시 $x$로 돌려주면 결과적으로 ${1\over 2}\sin (2x+1) +C$로 적분 계산 값이 도출된다.

두 번째 예시는 $\int x{\sqrt{x+1}}dx$이다. 마찬가지로 $x+1 = t$로 치환한다. $x$에 대해 미분하면 ${dt\over dx} = 1$이므로 $dt = dx$가 된다. 따라서 이를 대입해주면 $\int (t-1)\sqrt{t}dt$가 되고, 조금 난잡해보일 수 있지만 루트 표현식을 분수 표현식으로 바꾸면 $\int (t{3\over 2}-t{1\over 2})dt$가 된다. 이제 적분할 수 있다. 계산하면 ${2\over 5} t^2\sqrt{t} - {2\over 3}t\sqrt{t} +C$가 된다. $t$로 치환된 값을 다시 $x$로 풀어주면 결과적으로 ${2\over 5}(x+1)^2 \sqrt{x+1} - {2\over 3}(x+1)\sqrt{x+1} + C$로 적분 계산 값이 도출된다.

Reference

[1] 부분적분 쉽게하기 https://www.youtube.com/watch?v=E8N1E5ZAiIU 

[2] 부분적분, 치환적분 https://m.blog.naver.com/biomath2k/221860999596

[3] 치환적분 유도와 문제 예시 https://www.youtube.com/watch?v=SLnYC7mvyhk 

[4] 치환적분 문제 예시 https://blog.naver.com/biomath2k/221861047023

통계에서 확률변수와 확률분포가 있다. 확률변수는 이산확률변수와 연속확률변수로 나뉘고, 마찬가지로 확률분포도 이산확률분포와 연속확률분포로 나뉜다. 이산의 대표적인 분포는 이항분포가 있고 연속의 대표적인 분포는 정규분포가 있다. 하지만 이외에도 베르누이 분포, 기하분포, 초기하분포, 포아송분포, 균등분포, 지수분포, 카이제곱 분포 등이 있고 총 12가지 분포에 대해 정리하고자 한다. 이러한 확률 분포들이 필요한 핵심 이유는 모수 추정에 있다. 모수 추정에 있어 어떤 확률 분포를 따른다고 가정하면 특정 상황을 잘 표현할 수 있기 때문이다.

간단 용어 정리

표본공간: 사건에서 발생 가능한 모든 결과의 집합

확률변수: 표본공간에서 일정 확률을 갖고 발생하는 사건에 수치를 일대일 대응시키는 함수

확률분포: 흩어진 확률변수를 모아 함수 형태로 만든 것

이산확률변수: 확률변수 개수가 유한해 정수 구간으로 표현되는 확률변수

연속확률변수: 확률변수 개수가 무한해 실수 구간으로 표현되는 확률변수

확률밀도함수: 확률변수의 분포를 나타내는 함수이자 확률변수의 크기를 나타내는 값

이산 확률 분포

1. 베르누이 분포 (Bernoulli distribution)

베르누이 분포는 시행의 결과가 오직 두 가지인 분포를 말한다. 예를 들어 성공/실패나 합격/불합격 또는 앞면/뒷면이 있다. 이를 일반화하면 베르누이 분포는 특정 사건 A가 나타날 확률과 A가 나타나지 않을 확률을 나타낸 분포이다. 일반적으로 확률 변수에 사건 A가 발생할 경우를 1, 발생하지 않을 경우를 0으로 부여한다. 즉 베르누이 분포는 확률변수가 1과 0 두 가지로만 나타내는 확률분포다.

베르누이 시행을 따르는 경우의 예시로는, 동전과 주사위가 있다. 동전이 앞면이 나올 경우와 나오지 않을 경우로 나눌 수 있고, 주사위에서 어떤 수가 나올 확률과 그렇지 않은 경우로 나눌 수 있다. 만약 주사위에서 5가 나올 확률과 그렇지 않은 확률을 구하는 경우라면 베르누이 시행이지만 5,6이 나올 확률과 그렇지 않은 경우를 구하는 것이라면 베르누이 시행이 아니다. 예시를 통해 계산 방법을 알아보자. 상자 안에 흰 공7개와 검은공 3개가 있다고 가정하고 확률변수를 흰공이 나오면 성공(1), 검은공이 나오면 실패(0)로 둘때, 확률변수 값은 $p(1)=0.7, p(0)=0.3$이 된다. 이를 $\displaystyle p(x) = 0.7^x \times 0.3^{1-x}$로 나타낼 수 있고, 이를 일반화 한 식은 다음과 같다.

$\displaystyle p(x) = p^x(1-p)^{1-x}$

이 때 $x=(0, 1)$

다음으로 베르누이 분포에서 평균과 분산을 구하는 과정은 다음과 같다.

$\displaystyle E(x) = \sum xp(x)$

             $= 0p(0) + 1p(1)$

             $= p(1)$

             $= p$

$\displaystyle V(x) = E(x^2) - \{E(x)\}^2$

              $\displaystyle = \sum x^2p(x) - p^2$

              $= 0p(0) + 1p(1) - p^2$

              $= p - p^2$

              $= p(1-p)$

$\therefore$ $E(x) = p$, $V(x) = p(1-p)$이다.

2. 이항분포 (Binomial distribution)

이항 분포는 베르누이 시행을 여러번 하는 것이다. 정의를 내리면, 어떤 사건 A가 발생할 확률이 $p$인 베르누이 시행을 $n$번 시행했을 때 사건 A가 발생한 횟수를 확률 변수로하는 분포다. 수식으로는 다음과 같이 나타낸다.

$\displaystyle P(X = r) = {}_nC_r\ p^r(1-p)^{n-r} = {n \choose k}p^r(1-p)^{n-r}$

이 때 $r= (0, 1, 2, \dots, n)$이고 $(p+q = 1)$이다.

만약 주사위를 10번 던져서 숫자 5가 r번 나올 확률을 구한다면 다음과 같다.

만약 주사위 10번 던져서 숫자 5가 한 번 나올 확률: ${}_{10}C{}_1\times({1\over6})^1\times ({5\over 6})^9$

만약 주사위 10번 던져서 숫자 5가 두 번 나올 확률: ${}_{10}C{}_2\times({1\over6})^2\times ({5\over 6})^8$

만약 주사위 10번 던져서 숫자 5가 세 번 나올 확률: ${}_{10}C{}_3\times({1\over6})^3\times ({5\over 6})^7$

만약 주사위 10번 던져서 숫자 5가 r 번 나올 확률: ${}_{10}C{}_r\times({1\over6})^r\times ({5\over 6})^{n-r}$

이러한 사건의 시행으로부터 나오는 확률을 구해 분포도를 그리면 이항분포가 된다. 정확히는 확률변수 X의 확률분포를 이항분포라고 한다. 기호로는 $\displaystyle B(n, p)$와 같이 나타내며 위의 예시로는 $\displaystyle B(10, {1\over6})$이 된다. 만약 $X \sim B(n, p)$일 때 이항분포의 평균과 분산은 각각 $\displaystyle E(x) = np$ 이며 $\displaystyle V(x) = np(1-p)$이다. 평균을 구하는 과정만 기술해보자면,

$\displaystyle E(x) = \sum xp(x)$

              $\displaystyle = \sum_{r=0}^n r{n \choose r}p^r (1-p)^{n-r}$

              $\displaystyle = \sum_{r=0}^n r{n! \over (n-r)r!} p^r (1-p)^{n-r}$ (이 때 0을 대입하면 값이 0이되니 $r=1$부터 시작해도 되므로)

              $\displaystyle = \sum_{r=1}^n r{n! \over (n-r)r!} p^r (1-p)^{n-r}$ (약분을 위해 $r$을 묶어서 한 번 빼주고, $n$과 $p$도 마찬가지로 한 번씩 앞으로 빼주면)

              $\displaystyle = \sum_{r=1}^n r {n(n-1)! \over r(r-1)! (n-r)!} p p^{r-1} (1-p)^{n-r}$ (약분해주고 남은 np는 상수이며 앞으로 뺄 수 있으므로)

              $\displaystyle = np\sum_{r=1}^n {(n-1)! \over (r-1)!(n-r)!} p^{r-1} (1-p)^{n-r}$ ($n-1 = m$로 치환, $r-1 = x$로 치환하면)

              $\displaystyle = np\sum_{r=1}^n {m! \over x!(n-r)!} p^x (1-p)^{n-r}$ (이 때 $n-1 = m - x$이므로 대입해주면)

              $\displaystyle = np\sum_{r=1}^n {m! \over x!(m-x)!} p^x (1-p)^{m-x}$

              $\displaystyle = np\sum_{x=0}^m {m! \over x!(m-x)!}p^x (1-p)^{m-x}$ (이 때 $np$ 뒤의 형태는 시행횟수 m, 확률 p를 가지는 이항분포이므로 합은 1이 되어 사라지고)

              $= np$

$\therefore E(x) = np$

3. 기하분포 (Geometric distribution)

기하분포는 베르누이 시행을 반복할 때 처음으로 알고자 하는 사건 A 관찰에 성공하기 까지의 시도 횟수를 확률변수로 가지는 분포이다. 예를 들어 연애에서 결혼까지 이어질 확률이 10%라면 $x$번째 연애에 결혼하게 되는 것을 $p(x)$라 할 수 있다. 만약 3번째 연애에 결혼한다 가정하면 다음과 같은 계산이 가능하다.

$p(1) = 0.1$

$p(2) = 0.9 \times 0.1$

$p(3) = 0.9 \times 0.9 \times 0.1$

이를 일반화 하면 $\displaystyle p(x) = (1-p)^{x-1} \times p$이 된다. ($x$번째에 성공하므로 $x-1$까지는 실패)

이 기하분포의 통계량 중 평균과 분산은 $X \sim Geo(p)$일 때 $\displaystyle E(x) = {1\over p}, V(x) = {1-p\over p^2}$이다. 평균을 구하는 과정만 기술해보자면, 

$\displaystyle E(x) = \sum xp(x) = \sum x(1-p)^{x-1}p = \lim_{n \to \infty} \sum_{x=1}^n x(1-p)^{x-1}p$ (n이 무한히 커질 수 있음. p를 앞으로 꺼내주고 식을 전개하면)

$\displaystyle E(x) = \lim_{n \to \infty} p\{1(1-p)^0 + 2(1-p)^1+3(1-p)^2+ \cdots + (n-1)(1-p)^{n-2}+n(1-p)^{n-1}\}$ (평균값 도출 위해 양변에 (1-p)를 곱하면)

$\displaystyle (1-p)E(x) = \lim_{n \to \infty} p\{(1-p)+2(1-p)^2+3(1-p)^3+\cdots+(n-1)(1-p)^{n-1}+n(1-p)^n\}$ (위 식에서 이 식을 빼면)

$\displaystyle pE(x) = \lim_{n \to \infty} p\{1+(1-p)+(1-p)^2+(1-p)^3+\cdots+(1-p)^{n-1}+(1-p)^n\}$ (첫항1, 공비(1-p), 항수n인 등비수열합이므로)

$\displaystyle E(x) = \lim_{n \to \infty} \{{1(1-(1-p)^n \over1-(1-p)} - n(1-p)^n\}$ (로피탈 정리에 의해 0으로 수렴하는 $(1-p)^n$을 고려하면)

$\displaystyle E(x) = {1\over 1-(1-p)} = {1\over p}$

$\displaystyle \therefore E(x) = {1\over p}$

4. 음이항분포 (Negative binomial distribution)

음이항 분포의 여러 정의 중 하나는 기하 분포를 일반화한 분포다. 정확히는 음이항분포에는 5가지 정의가 존재하고 그 중 하나의 정의가 기하 분포의 일반화에 해당한다. 앞서 기하분포를 설명한 대로, $n$번째 시행에서 처음으로 사건 A 관측에 성공할 확률이다. 수식으론 $\displaystyle p(x) = (1-p)^{x-1} \times p$으로 표현했다. 음이항분포의 한 정의는 $n$번째 시행에서 $k$번째 성공이 나올 확률이다. 즉 $n$번 시행 이전인 $n-1$번의 시행까지 $k-1$개의 성공이 있어야 하며, 마지막 n번째에 한 번 더 성공해야 한다. 이를 수식으로 정의하면 $n-1$에서 $k-1$개가 나올 경우의 수를 고려해야 하므로 $\displaystyle p(x) = {}_{n-1}C_{k-1}p^{k-1}(1-p)^{n-k}p$가 된다.

앞서 언급했듯 음이항분포는 5가지 정의가 존재한다. 이 5가지 정의엔 $n, k, r$이 사용된다. $n$: 전체 시행횟수, $k$: 성공 횟수, $r$: 실패 횟수이다. 이 때 $n = k + r$의 관계가 성립한다. 이 관계식에서 어떤 것을 독립 변수, 종속변수, 상수로 두느냐에 따라 음이항분포의 정의가 나뉜다.

1. $r$이 상수, $k$가 독립변수인 경우: $r$번 실패까지 성공이 $k$번 발생한 확률이다.

2. $r$이 상수, $n$이 독립변수인 경우: $r$번 실패까지 $n$번 시행할 확률이다.

3. $k$가 상수, $r$이 독립변수인 경우: $k$번 성공까지 $r$번 실패할 확률이다.

4. $k$가 상수, $n$이 독립변수인 경우: $n$번 시행에서 $k$번째 성공이 나올 확률이다.

5. $n$이 상수, $k$ 또는 $r$이 독립변수인 경우: $n$번 시행에서 $k$번 성공 또는 $r$번 실패할 확률 (= 기존 이항분포와 동일한 식)

혼동이 있을 수 있지만 결론을 먼저 말하자면 일반적으로 1번 정의를 음이항분포라고 한다. 4번 정의는 기하분포를 일반화한 것이다. 1번 정의에 대한 예시를 들기 포커 게임에서 이길 확률(p) 0.3일 때 5번의 패배가 나오기까지 발생한 승리가 $k$번일 확률 분포 $p(x)$를 구한다고 해보자. 그러면 $r=5, p=0.3$이며 $x=(0, 1, 2, 3, 4, 5)$가 된다. 

p(0): 5번 패배할 때까지 0번 이긴 경우다.

(_ _ _ _ 실): 마지막 실패 제외, 모두 실패가 들어간다. 4번 중 4번 패배 + 0번 이길 경우의 수 이므로 ${}_4C_0 (0.7)^4 (0.3)^0 (0.7)$

p(1): 5번 패배할 때까지 1번 이긴 경우다.

(_ _ _ _ _ 실): 마지막 실패 제외, 5번 중 4번 패패 + 1번 이길 경우의 수 이므로 ${}_5C_1 (0.7)^4 (0.3)^1 (0.7)$

p(2): 5번 패배할 때 까지 2번 이긴 경우다.

(_ _ _ _ _ _ 실): 마지막 실패 제외, 6번 중 4번 패배 + 2번 이길 경우의 수이므로 ${}_6C_2 (0.7)^4 (0.3)^2 (0.7)$

p(3): 5번 패배할 때 까지 3번 이긴 경우다.

(_ _ _ _ _ _ _ 실): 마지막 실패 제외, 7번 중 4번 패패 + 3번 이길 경우의 수므로 ${}_7C_3 (0.7)^4 (0.3)^3 (0.7)$

. . . ($k \rightarrow \infty$)

이를 일반화한 수식은 ${}_{x+k-1}C_{x} (1-p)^r p^x$이 된다. 이를 달리 표현하면 $X \sim NB(r, p)$이다. 다른 정의를 사용하고 싶다면 $r$ 자리에 다른 상수를 넣어 사용할 수 있다. 이런 음이항분포의 평균과 분산은 각각 $\displaystyle E(x) = {pr \over 1-p}$와 $\displaystyle V(x) = {pr \over (1-p)^2}$이다. 이 중 평균을 구하는 과정만 기술하자면, 

$\displaystyle E(x) = \sum xp(x)$

              $\displaystyle = \sum_{x=0}^\infty x {}_{x+r-1}C_x p^x (1-p)^r$ ($x=0$은 0이므로 $x=1$부터여도 무관하며 조합식을 팩토리얼로 풀어주면)

              $\displaystyle = \sum_{x=1}^\infty x {(x+r-1)! \over (r-1)!x!} p^x (1-p)^r$ ($x$을 약분하면)

              $\displaystyle = \sum_{x=1}^\infty {(x+r-1)! \over (r-1)!(x-1)!} p^x (1-p)^r$ ($p$로 한 번 묶어주면)

              $\displaystyle = p \sum_{x=1}^\infty {(x+r-1)! \over (r-1)!(x-1)!} p^{x-1} (1-p)^r$ (분자 분모에 $r$을 곱해주면)

              $\displaystyle = p \sum_{x=1}^\infty {r(x+r-1)! \over r(r-1)!(x-1)!} p^{x-1} (1-p)^r$ ($r$을 앞으로 빼주고 팩토리얼을 합해주면)

              $\displaystyle = pr \sum_{x=1}^\infty {(x+r-1)! \over r!(x-1)!} p^{x-1} (1-p)^r$ ($x-1 = y$로 치환해주면)

              $\displaystyle = pr \sum_{y=0}^\infty {(y+r)! \over r!y!} p^y (1-p)^r$ (조합식으로 변경해주면)

              $\displaystyle = pr \sum_{y=0}^\infty {}_{y+r}C_y p^y (1-p)^r$ ($r = k-1$로 치환해주면)

              $\displaystyle = pr \sum_{y=0}^\infty {}_{y+k-1}C_y p^y (1-p)^{k-1}$ ($(1-p)^{-1})$으로 묶어주면)

              $\displaystyle = {pr \over 1-p} \sum_{y=0}^\infty {}_{y+k-1}C_y p^y (1-p)^k$ (이 때 시그마 안의 식은 음이항분포의 확률분포 함수와 모양이 같으므로 합은 1이 된다.)

              $\displaystyle = {pr \over 1-p}$

$\displaystyle \therefore E(x) = {pr \over 1-p}$

어떤 확률변수 $X$가 $NB(r, p)$의 음이항분포를 따를 때 이 확률변수 $X$의 평균은 $\displaystyle {pr \over 1-p}$가 된다.

5. 초기하 분포 (Hypergeometric distribution)

초기하 분포는 아래 그림처럼 크기가 $m$인 모집단에서 크기 $n$인 표본을 추출했을 때 모집단 내 원하는 원소 $k$개 중 표본 내에 $x$개 들어있을 확률 분포를 의미한다.

쉬운 비유는 로또가 있다. 로또는 크기 45의 모집단을 가지고, 그 중 원하는 수 $k=6$개이다. 이 때 추출한 표본 6개 중 $k$가 $x$개 들어있을 확률이다. 따라서 $p(0)$는 번호 0개 맞은 경우이며 $p(1)$은 번호 1개가 맞은 경우이고, ..., $p(6)$는 번호 6개가 맞아 1등된 확률을 의미한다. 

이러한 초기하 분포식 유도를 위해선 먼저 모집단에서 표본을 추출할 경우의 수를 구해야 한다. 이는 크기 $m$인 모집단에서 크기 $n$인 표본을 뽑을 경우의 수 이므로 ${}_mC_n$이다. 또 원하는 원소가 $k$개 들어있고 크기가 m인 모집단에서, 크기가 $n$인 표본을 뽑을 때 원하는 원소 x개가 들어있을 경우의 수는 ${}_kC_x \times {}_{m-k}C_{n-x}$다. 그 이유는 표본의 $x$이외의 값은 $n-x$개로 나타내며 이는 모집단의 $m-k$개로부터 추출된 것이기 때문이다. 이를 기반으로 전체 경우의수를 나타내면 다음과 같다.

$\displaystyle p(x) = {{}_kCx \times {}_{m-k}C_{n-x} \over {}_mCn}$

여기서 $m, k, n$은 사전에 결정되는 상수이며 $x$는 확률 변수에 해당한다. 이 초기하 분포식을 기반으로 구한 평균과 분산은 각각 $\displaystyle E(x) = {kn \over m}$, $\displaystyle V(x) = n {k\over m}{m-k \over m}{m-n\over m-1}$이다. 평균을 구하는 과정만 기술해보자면, 

$\displaystyle E(x) = \sum xp(x)$

              $\displaystyle = \sum_{x=0}^\infty {{}_kCx \times {}_{m-k}C_{n-x} \over {}_mCn}$ (이 때 ${}_kCx$를 팩토리얼로 풀어주면)

              $\displaystyle = \sum_{x=0}^\infty x{k! \over x!(k-x)!} {{}_{m-k}C_{n-x} \over {}_mC_n}$ (이 때 0을 대입하면 0이므로 x=1부터 시작되어도 무관. x 약분 하고 k를 밖으로 꺼내주면)

              $\displaystyle = k\sum_{x=1}^\infty {(k-1)! \over (x-1)!(k-x)!} {{}_{m-k}C_{n-x} \over {}_mC_n}$ (여기서 ${}_mC_n$을 팩토리얼로 전개하면 ${}_mC_n = {m! \over n!(m-n)!} = {m \over n}{(m-1)! \over (n-1)!(m-1)!} = {m\over n}{}_{m-1}C_{n-1}$)

              $\displaystyle = k\sum_{x=1}^\infty {(k-1)! \over (x-1)!(k-x)!} {n\over m} {{}_{m-k}C_{n-x} \over {}_{m-1}C_{n-1}}$ (여기서 맨 앞의 식을 조합 형태로 변환)

              $\displaystyle = k\sum_{x=1}^\infty {}_{k-1}C_{x-1} {n\over m} {{}_{m-k}C_{n-x} \over {}_{m-1}C_{n-1}}$ (여기서 $n\over m$은 상수이므로 앞으로 빼고 ${}_{m-k}C_{n-x}$를 변형하면)

              $\displaystyle = {kn\over m} \sum_{x=1}^\infty {}_{k-1}C_{x-1} {{}_{(m-1)-(k-1)}C_{(n-1)-(x-1)} \over {}_{m-1}C_{n-1}}$ (여기서 $x-1=y$로 치환하면)

              $\displaystyle = {kn\over m} \sum_{y=0}^\infty {}_{k-1}C_y {{}_{(m-1)-(k-1)}C_{(n-1)-(y)} \over {}_{m-1}C_{n-1}}$ (시그마 내 식은 크기 $m-1$인 모집단, $n-1$인 표본, 원하는 원소 $k-1$개, 원하는 원소 $y$인 초기하 분포의 모양과 같으므로 시그마 식은 초기하 분포 값을 다 더해주면 1)

              $\displaystyle = {kn\over m}$

$\displaystyle \therefore E(x) = {kn \over m}$

6. 포아송 분포 (Poisson distribution)

포아송 분포는 이항 분포에서 유도된 특수한 분포다. 이항 분포에서 시행 횟수 $n$이 무수히 커지고 사건 발생 확률 $p$이 매우 작아질 경우 필요하다. 그 이유는 시행 횟수 $n$이 무한히 커질 때 이항 분포 정의인 $\displaystyle {}_nC_r\ p^r(1-p)^{n-r}$에서 $n!$ 계산이 현실적으로 가능하지 않은 경우가 있기 때문이다.

포아송 분포를 다르게 표현하면 단위 시간이나 단위 공간에서 랜덤하게 발생하는 사건 발생횟수에 적용되는 분포다. 예를 들어 1시간 내에 특정 진도 5이상의 지진 발생 확률에도 적용할 수 있다. 지진은 언제나 발생할 수 있지만 그 발생횟수는 작을 것이며 또 알 수 없다. 또 보험사는 1000건의 보험계약이 있지만 고객이 보험금을 청구 확률은 얼마가 될 지 알 수 없는 것이다.

이러한 경우에 포아송 분포가 사용되며 많은 경우에 적용된다. 포아송 분포에서는 사건발생 횟수와 확률은 알 수 없지만 대신 사건발생 평균횟수는 정의할 수 있다. 그 이유는 이항 분포에서 평균 $E(x) = np$이기 때문이다. 푸아송 분포에서는 $np$를  $\lambda$로 표현한다. ($\lambda = np$)

포아송 분포의 정의는 이항 분포 정의에서 유도되어 $\displaystyle p(x) = {\lambda^x e^{-\lambda} \over x!}$이다. 이를 사용해 포아송 분포의 평균과 분산을 구하면 각각 $E(x) = \lambda$와 $V(x) = \lambda$이다. 이 때 평균을 구하는 과정만 기술해보자면,

$\displaystyle E(x) = \sum_{x=0}^\infty\ xp(x)$ 이므로

              $\displaystyle =\sum_{x=0}^\infty x {\lambda^x e^{-\lambda} \over x!}$ (이 때 $x$에 0대입해도 0이므로 1부터 시작 가능)

              $\displaystyle =\sum_{x=1}^\infty x {\lambda^x e^{-\lambda} \over x!}$ ($x$ 약분하고, 상수인 $e^{-\lambda}$를 앞으로 빼주고, $\lambda$도 하나 앞으로 빼주면)

              $\displaystyle =\lambda e^{-\lambda} \sum_{x=1}^\infty {\lambda^{x-1} \over (x-1)!}$ ($x-1 = n$으로 치환. $x=1$이면 $n=0$이므로)

              $\displaystyle =\lambda e^{-\lambda} \sum_{n=0}^\infty {\lambda^{n} \over n!}$ (이 때 시그마 값은 매클로린 급수 정의에 의해 $e^\lambda$. ($\displaystyle f(x) = \sum_{n=0}^\infty {f^{(n)}(0) \over n!} {x}^n$에서 $e^\lambda$대입. $e^x$의 $n$계 도함수는 자기 자신))

              $\displaystyle = \lambda e^{-\lambda} e^\lambda$

              $\displaystyle = \lambda$

$\displaystyle \therefore E(x) = \lambda$

연속확률분포

7. 균등분포 (Uniform distribution) 

균등분포의 정의는 정해진 범위에서 모든 확률변수의 함수값이 동일한 분포이다. 연속확률분포에서 균등분포는 연속균등분포라 불려야 한다. 이산확률분포에서도 균등분포를 정의할 수 있기 때문에 구분이 필요하기 때문이다. 균등분포 함수로 표현하면 다음과 같다.

$\displaystyle f(x)= \begin{cases} {1 \over b-a}, & a\lt x \lt b \\ 0 & {x\lt a, b\lt x} \end{cases}$

확률변수의 범위를 $a\leq x \leq b$라고 하고, 이 확률변수들의 함수 값을 $f(x)$라고 하면다음과 같은 확률밀도 그래프를 그릴 수 있다. 참고로 어떤 확률변수 $X$가 균등분포를 따른다면 $X~ U(a, b)$로 표현한다.

이 때 연속확률변수에서의 확률은 확률밀도로 표현되고 확률밀도는 넓이를 의미한다. 이 때 전체 확률밀도는 1이므로 $(b-a)f(x) = 1$이 된다. 따라서 $f(x) = {1 \over (b-a)}$이다. 

균등분포에서 평균과 분산은 각각 $\displaystyle E(x) = {b+a \over 2}$와 $\displaystyle V(x) = {(b-a)^2 \over 12}$이다. 여기서 평균을 나타내는 과정만 기술해보자면, 연속확률변수에서 평균은 $\displaystyle E(x) = \int_{-\infty}^\infty xf(x)dx$이므로

$\displaystyle E(x) = \int_a^b x{1 \over b-a}dx$

              $\displaystyle =\left[{1\over b-a} {1\over 2}x^2 \right]_a^b$

              $\displaystyle ={b^2-a^2 \over 2(b-a)}$

              $\displaystyle = {(b+a)(b-a) \over 2(b-a)}$

              $\displaystyle = {b+a \over 2}$

$\displaystyle \therefore E(x) = {b+a \over 2}$

8. 정규분포 (Normal distribution)

정규분포는 대표적인 연속확률분포에 속하며 가우시안 분포라고도 불린다. 정규분포의 확률밀도함수는 아래의 수식으로 나타낸다. (유도과정은 크게 두 가지 방법을 사용하는데 첫 번째론 과녁 맞추기 예시를 통한 유도와 두 번째론 이항분포로부터 유도하는 방법이 있다. 유도과정은 길어지므로 생략하며 고등수학만 활용해도 유도 가능하다.)

$\displaystyle f(x) = {1 \over \sqrt{2\pi \sigma^2}} \exp (-{(x-\mu)^2 \over 2\sigma^2})$

여기서 $\mu$는 평균을 나타내며 $\sigma^2$는 분산(표준편차 제곱)을 뜻한다. 이는 곧 정규분포는 아래 그림과 같이 평균과 분산에 따라 다양한 분포를 가지게 됨을 의미한다. 이 때 정규분포의 가장 높은 함수값을 가지는 확률변수 $X$는 평균이다. 만약 어떤 확률변수 $X$가 평균이 $\mu$고 분산이 $\sigma^2$인 정규분포를 따른다고 하면 기호로 $N(\mu, \sigma^2)$와 같은 형태로도 나타낼 수 있다. 

이러한 정규분포에는 몇 가지 특징이 있다. 첫 번째는 정규분포는 확률밀도함수의 한 종류이므로 전체 넓이는 전체 확률을 의미하므로 1이 된다. 두 번째는 정규분포는 평균을 기준으로 대칭성을 띤다. 평균 기준 왼쪽과 오른쪽이 각각 0.5의 확률을 갖는다. 세 번째는 정규분포별 평균과 표준편차가 다르더라도 아래 그림과 같이 표준편차 구간 별 확률은 어느 정규분포에서나 같다는 것이다. 

가령 예를 들어 $\displaystyle N(100, 5^2)$의 정규분포와 $\displaystyle N(64, 4^2)$ 정규분포가 두 개가 있을 때, 그 모양이 서로 다르더라도 위 그림과 같이 표준편차($\sigma$)로 나뉘어진 구간의 면적(확률)은 모두 같음을 의미한다. 

이런 정규분포는 표준화 과정을 통해 표준 정규 분포(standard normal distribution)를 얻을 수 있다. 표준 정규 분포란 평균이 0 표준편차가 1인 분포를 말한다. 표준화 과정은 $\displaystyle Z = {X - \mu \over \sigma}$으로 이뤄진다. 모든 확률변수에 대해 평균을 뺀 뒤 표준편차로 나눠주는 것이다. $Z \sim N(0, 1)$의 형태로 표현하며 이를 표준정규분포 또는 Z-분포라 부른다.

이런 표준화 과정을 통해 표준정규분포로 만들면 서로 다른 모수 값(평균, 표준편차, 분산 등)을 가진 정규분포를 가진 집단 간의 비교 문제를 해결할 수 있다. 흔히 예를 드는 것으로 수학 시험 점수 비교다. 가령 A, B반의 수학 점수가 정규분포를 따른다 가정할 때 A반: 평균 70, 표준편차 30 / B반: 평균 80, 표준편차 15라면 비교로 성적 우위를 가리기 어렵다. 때문에 표준화를 통해 정규분포를 표준정규분포로 바꿔줌으로써 집단간 비교 문제를 해결할 수 있다.

9. 카이제곱분포 (Chi-square distribution)

카이제곱분포란 표준정규분포에서 파생된 것으로 한 마디로 말하면 표준정규분포의 확률변수를 제곱합한 분포다. 카이제곱 분포는 신뢰구간과 가설검정, 독립성 검정 등에서 자주 사용된다. 먼저 카이제곱분포의 기본적인 형태를 보자. 표준정규분포에서는 평균이 0이고 표준편차가 1이었다. 따라서 평균 0을 기준으로 -와 +가 있지만 카이제곱분포는 확률변수를 제곱하였으므로 +만 존재한다. 

카이제곱분포의 형태에서 앞 부분에 확률 변수 값이 큰 이유는 뒤로갈수록 정규분포의 양끝과 같은 편향이 상대적으로 적어지기 때문이다. 이 카이제곱 분포를 조금 더 덧붙여 설명하면, $k$개의 서로 독립적인 표준정규분포의 확률변수를 각각 제곱한 후 더하여 얻는 분포다. 이 때 $k$는 표준정규분포를 따르는 확률변수의 개수로 카이제곱 분포의 형태를 결정하는 자유도로서 역할을 한다. 이 $k$에 따라 카이제곱 분포의 형태가 아래와 같이 달라진다. 자유도의 크기가 증가할수록 점점 대칭성을 갖게 되며 통상 $k=30$이상이면 거의 정규분포에 가까워진다고 한다. 

이러한 카이제곱분포의 수식은 $\displaystyle f(x|k) = {1 \over 2^{k\over 2}\gamma ({k\over 2})} x^{{k\over 2}-1}e^{-{x\over 2}}$로 표기한다. 카이제곱분포의 평균과 분산은 각각 $E(x) = k$, $V(x) = 2k$이다. 이 중 카이제곱분포 수식을 통해 평균을 구하는 과정만 기술해보자면, (확률변수 $X$가 $k$ 자유도를 갖는 카이제곱분포를 따른다고 가정)

$\displaystyle E(x) = \int_0^\infty xf(x)dx$ (적분구간은 0부터 시작함 카이제곱분포는 표준정규분포의 확률분포를 제곱한 것이므로)

              $\displaystyle =\int_0^\infty x{1\over 2^{k\over2} \gamma({k\over 2})} e^{-{x\over 2}} x^{{k\over 2}-1}dx$ (이 때 $x*x^{-1} = 1$이 되고, 상수를 앞으로 빼주면)

              $\displaystyle ={1 \over {2^{k\over 2} \gamma({k\over 2})}} \int_0^\infty e^{-{x\over 2}} x^{x\over 2} dx$ (여기서 부분적분을 적용하면)

              $\displaystyle ={1 \over {2^{k\over 2} \gamma({k\over 2})}} \left\{ \left[-2e^{-{x\over 2}} x^{x\over 2} \right ]_0^\infty - \int _0^\infty -2e^{-{x\over 2}} {k\over 2}x^{{k\over 2}-1}dx \right\}$

              $\displaystyle ={1 \over {2^{k\over 2} \gamma({k\over 2})}} \left\{ \left[-2e^{-{x\over 2}} x^{x\over 2} \right ]_0^\infty +k \int _0^\infty e^{-{x\over 2}} x^{{k\over 2}-1}dx \right\}$ (이 때 부분적분한 앞 항은 로피탈 정리에 의해 0으로 수렴됨)

              $\displaystyle ={1 \over {2^{k\over 2} \gamma({k\over 2})}} \left\{k \int _0^\infty e^{-{x\over 2}} x^{{k\over 2}-1}dx \right\}$ (앞의 항을 다시 적분식으로 넣어주면)

              $\displaystyle =k\int_0^\infty {1\over {2^{k\over 2} \gamma({k\over 2})}} e^{-{x\over 2}} x^{{k\over 2}-1}dx$ (여기서 적분식은 k자유도를 갖는 카이제곱분포함수와 동일하므로 적분 시 1이 됨)

              $\displaystyle =k$

$\displaystyle \therefore E(x) = k$ (어떤 확률변수 $X$가 $Q \sim \chi_k^2$의 카이제곱분포($k$ 자유도 갖는)를 따를 때 이 확률변수 $X$의 평균은 $k$다)

10. 지수분포 (Exponential distribution)

지수분포는 포아송 분포에서 유도된다. 위에서 포아송 분포는 단위 시간당 사건의 평균 발생 횟수였다. 수식으로는 $\displaystyle p(x) = {\lambda^x e^{-\lambda} \over x!}$였다. 여기서 $\lambda$는 단위 시간당 사건의 평균발생횟수($\because \lambda=np$)이며 $x$는 사건 발생 횟수이다. 예를 들어 하루 동안 모범 택시를 평균적으로 3번 마주친다면 $\displaystyle p(x) = {3^xe^{-3} \over x!}$이 된다.

지수분포는 이러한 포아송 분포가 만족하는 상황에서 사건 A가 일어날 때까지 걸리는 시간이 T이하일 확률이다. 즉 기존 포아송에서 시간까지 더 알고자 하는 것이다. 이를 일반화한 정의는 단위 시간당 사건 A의 평균발생횟수가 $\lambda$일 때, 사건 A가 처음 발생할 때 까지 걸리는 시간이 T이하일 확률이다. 지수 분포는 아래 수식으로 표현한다.

$\displaystyle f(T) = \lambda e^{-\lambda T}$

위 지수 분포 유도를 위해 하나의 예를 들어 설명 하자면, 모범 택시를 마주칠 때 까지 걸리는 기간이 5일 이하일 확률을 $\displaystyle p(0\leq t \leq 5) = \int_0^5 f(t)dt$로 표현할 수 있다. 이 확률을 구하기 위해서는 두 가지 방법이 있다. 첫 번째는 1일차에 만날 확률, 2일차에 만날 확률, ..., 5일차에 만날 확률을 구해 모두 더해주는 방식이고, 두 번째는 여사건을 사용하는 방법이다. 여사건을 통해 확률을 구하는 식은 (1 - 5일동안 모범 택시 마주치지 않을 확률 p)이다. 

여사건으로 계산을 해보자면 먼저 1일차에 모범택시를 만나지 않을 확률을 구하면 $\displaystyle p(0) = {3^0e^{-3} \over 0!} = e^{-3}$이 된다. 따라서 5일동안 모범 택시를 마주치지 않을 확률은 $\displaystyle e^{{-3}\times 5}$가 된다. 이 모범 택시를 마주칠 확률은 곧 $\displaystyle \int_0^5 f(t)dt = 1 - e^{-15}$와 같다.

이렇게 구한 포아송 분포를 지수분포로 일반화 하여 어떤 사건이 발생할 때 까지 걸리는 기간이 T이하일 확률을 나타내는 과정을 나타내보자. 우선 $\displaystyle p(0\leq t\leq T) = \int_0^T f(t)dt = 1 - e^{-\lambda T}$이 있고, 여기서 구해야할 것은 지수분포를 나타내는 $\displaystyle \int_0^T f(t)dt$이다. 지수분포 식은 T로 미분해서 얻을 수 있다. $f(t)$의 부정적분을 $F(T)$로 두면, 이 적분식은 $\displaystyle F(T) - F(0) = 1-e^{-\lambda T}$가 된다. 이 식의 양변을 T로 미분하면 $\displaystyle f(T) = \lambda e^{-\lambda T}$가 되며 이 함수는 지수분포를 나타내는 식이다.

이 지수함수 분포에 대한 평균과 를 이용해 평균과 분산은 각각 $\displaystyle E(x)={1 \over \lambda}$, $\displaystyle V(x)={1\over \lambda^2}$이다. 이 중 평균을 구하는 과정만 기술해보자면,

$\displaystyle E(t) = \int_0^\infty tf(t)dt$

              $\displaystyle = \int_0^\infty t \lambda e^{-\lambda t}dt$ (여기서 부분적분을 사용하면)

              $\displaystyle = \left[ -te^{-\lambda t} \right]_0^\infty - \int_0^\infty -e^{-\lambda t}dt$ ($\because \int e^{f(x)} = {e^{f(x)} \over f'(x)}$이며 부분적분 공식에 의해 $\int f(x)g'(x)dx = f(x)g(x) - \int f'(x)g(x)$이므로)

              $\displaystyle = \left[ -te^{-\lambda t}\right]_0^\infty + \left[-{1\over \lambda}e^{-\lambda t}\right]_0^\infty$ (이 식은 위 식에서 뒤 항을 적분해준 결과임. 여기서 극한값을 이용해 표현하면)

              $\displaystyle = \lim_{t \to \infty} (-te^{-\lambda t}) - 0 + \lim_{t \to \infty} -{1\over \lambda} e^{-\lambda t} - (- {1\over \lambda}e^0)$ (이 때 $\lim_{t \to \infty} -{1\over \lambda}e^{-\lambda t}$는 0이 되므로)

              $\displaystyle = \lim_{t \to \infty} (-te^{-\lambda t}) + {1\over \lambda}$ (여기서 -를 앞으로 빼고 지수 표현식을 분수로 바꿔주면)

              $\displaystyle = -\lim_{t \to \infty} {t \over e^{\lambda t}} + {1\over \lambda}$ (여기서 $1 = {1 \over \lambda } \lambda$이므로 이를 추가해주면)

              $\displaystyle = -{1 \over \lambda} \lim_{t \to \infty} {\lambda t \over e^{\lambda t}} + {1\over \lambda}$ (이 때 로피탈 정리에 의해 $\displaystyle \lim_{t \to \infty} {\lambda t \over e^{\lambda t}}$는 0이 됨)

              $\displaystyle = {1\over \lambda}$

$\displaystyle \therefore E(t) = {1 \over \lambda}$

11. 감마분포 (Gamma distribution)

감마분포는 지수분포의 확장이다. 지수분포에서 한 번의 사건이 아닌 여러 개의 사건으로 확장한 것이다. 구체적으론 지수분포는 포아송 분포가 만족하는 상황에서 사건 A가 일어날 때까지 걸리는 시간이 T이하일 확률이었다. 감마분포는 $\alpha$번째 사건이 발생할때까지 걸리는 시간이 T이하일 확률이다. 예를 들어 평균적으로 주유소를 30분에 한 번씩 마주친다면 주유소를 4번 마주칠 때까지 걸리는 시간이 T이하일 확률과 같은 것이다. 감마분포 또한 여러 곳에 활용되지만 주로 감마분포는 모수의 베이지안 추정에 활용된다.

감마함수는 $\displaystyle \gamma(\alpha) = \int_0^\infty x^{\alpha-1}e^{-x}dx, (\alpha \gt 0)$로 표기한다. 이 감마함수는 팩토리얼 계산을 자연수에서 복소수범위까지 일반화한 함수라고 한다. 이 감마 함수를 근간으로한 감마분포함수는 $\displaystyle f_x(x) = {1 \over \gamma(\alpha)\beta^\alpha} x^{\alpha-1}e^{-x\over \beta}$로 표기한다. ($\displaystyle 0 \leq x \leq \infty$, ($\alpha \gt 0, \beta \gt 0)$). 감마분포에서 $\alpha$는 형태 모수(shape parameter), $\beta$는 척도 모수(scale parameter)라고 한다.

감마분포의 평균과 분산은 각각 $E(x)=\alpha \beta$, $V(x) = \alpha \beta^2$이다. 여기서 감마분포의 평균을 구하는 과정만 기술하자면, 

$\displaystyle E(x) = \int_0^\infty xf(x)dx$

              $\displaystyle = \int_0^\infty  x{1 \over \gamma(\alpha)\beta^\alpha} x^{\alpha-1}e^{-x\over \beta}dx$ ($xx^{-1}=1$, 상수 부분을 앞으로 빼주면)

              $\displaystyle = {1 \over \gamma(\alpha) \beta^\alpha} \int_0^\infty x^\alpha e^{-{x\over \beta}}dx$ (${x\over \beta} = t$로 치환)

              $\displaystyle = {1 \over \gamma(\alpha) \beta^\alpha} \int_0^\infty (t\beta)^\alpha e^{-t} \beta dt$ ($\beta^\alpha$는 약분되어 사라지고 상수 $\beta$를 앞으로 빼주면)

              $\displaystyle = {\beta \over \gamma(\alpha)} \int_0^\infty t^\alpha e^{-t}dt$ (이 때 $\gamma$ 함수의 원형과 동일하므로)

              $\displaystyle = \beta {\gamma(\alpha+1) \over \gamma(\alpha)}$ ($\gamma$ 함수는 팩토리얼이므로 $\alpha$만 남게 됨)

              $\displaystyle = \beta \alpha$

$\displaystyle \therefore E(x) = \alpha \beta$

12. 베타분포 (Beta distribution)

베타분포는 베이즈 추론에서 사전 확률을 가정할 때 사용되기 때문에 중요하다. 베타분포의 정의는 두 매개변수 $\alpha$와 $\beta$에 따라 [0, 1] 구간에서 정의되는 연속확률분포이다. $\alpha$와 $\beta$는 아래와 같이 베타분포 그래프의 형태를 결정하는 형태 모수(shape parameter)다. 만약 $\alpha = \beta$라면 베타분포는 대칭이 된다. 또 $\alpha$와 $\beta$가 커질수록 정규분포와 모양이 비슷해진다. 

베타분포의 근간인 베타함수의 수식은 $\displaystyle B(\alpha, \beta) = {\gamma (\alpha) \gamma(\beta) \over \gamma(\alpha + \beta)} = \int_0^1 x^{\alpha -1}(1-x)^{\beta -1}dx$로 표현한다. 이 베타함수를 기반으로하는 베타분포의 확률밀도함수는 $\displaystyle f_x(x) = {\gamma(\alpha + \beta) \over \gamma(\alpha) \gamma(\beta)} x^{\alpha-1}(1-x)^{\beta-1}, (0 \lt x \lt 1, \alpha, \beta \gt 0)$이다. 평균과 분산은 각각 $\displaystyle E(x) = {\alpha \over \alpha + \beta}$, $\displaystyle V(x) = {\alpha \beta \over (\alpha+\beta)^2(\alpha+\beta+1)}$인데, 이 중 평균을 구하는 과정만 기술하면,

$\displaystyle E(x) = \int_0^1 xf(x)dx$ 

              $\displaystyle =\int_0^1 x{1\over B(\alpha, \beta)}x^{\alpha-1}(1-x)^{\beta-1}dx$

              $\displaystyle ={B(\alpha+1, \beta) \over B(\alpha, \beta)} \int_0^1 {1 \over B(\alpha+1, \beta)} x^{(\alpha+1)-1}(1-x)^{\beta-1}dx$

              $\displaystyle ={\gamma(\alpha+\beta) \over \gamma(\alpha)\gamma(\beta)} {\gamma(\alpha+1)\gamma(\beta) \over \gamma(\alpha+\beta+1)}$

              $\displaystyle = {\alpha \over \alpha+\beta}$

$\displaystyle \therefore E(x) = {\alpha \over \alpha+\beta}$

Reference

[1] 베르누이분포 https://www.youtube.com/watch?v=3rOIcMF0-ls 

[2] 이항분포 https://www.youtube.com/watch?v=XzJkxIkP4Pg 

[3] 기하분포 https://www.youtube.com/watch?v=NzQRbVP5eow 

[4] 기하 분포 https://blog.naver.com/PostView.naver?blogId=chunsa0127&logNo=222049190534 

[5] 음이항 분포 https://www.youtube.com/watch?v=bBo7rN3SvCg 

[6] 초기하 분포 https://www.youtube.com/watch?v=HT1en9f2AcE 

[7] 포아송 분포 https://www.youtube.com/watch?v=JOWYEDwqAtY 

[8] 균등 분포 https://www.youtube.com/watch?v=LeUfJHzOSXo 

[9] 정규 분포 https://m.blog.naver.com/algosn/221308973343

[10] 카이제곱 분포 https://math100.tistory.com/44

[11] 카이제곱 분포 https://www.youtube.com/watch?v=2ER99k6f5eQ 

[12] 지수 분포 https://www.youtube.com/watch?v=OywjNb4jmtc 

[13] 감마 분포 https://soohee410.github.io/gamma_dist

[14] 베타 분포 https://soohee410.github.io/beta_dist

[15] 이미지 https://quantitative-probabilitydistribution.blogspot.com/2021/01/various-types-of-probability.html

신경계를 이해하기 위해서는 가장 작은 단위인 뉴런의 동작을 우선 이해해야 한다. 뉴런 동작의 핵심은 이온(ion)의 움직임이다. 이온은 전하를 띠는 원자와 분자를 의미한다. 예를 들어 소금인 염화나트륨은 양전하를 띠는 나트륨 이온(Sodium, Na+)와 음전하를 띠는 염소 이온(Chloride, Cl-)로 나뉜다. 이 두 이온은 뉴런의 전기 신호 전달에서 중요한 역할을 하며 추가적으로 칼륨 이온 칼륨 이온(Potassium, K+)과 유기음이온 (A-)(단백질 분자)도 마찬가지다.

이러한 이온들은 일종의 출입문인 이온 채널을 통해 세포막 내/외부로 이동한다. 세포막에 나트륨 채널과 칼륨 채널이 있다. 세포막을 기준으로 외부에는 나트륨 이온, 세포막 내부에는 칼륨이 존재한다. 세포막 외부는 양극으로로 대전, 세포막 내부는 음극으로 대전되어 있는데 만약 나트륨 채널이 열려 세포막으로 들어오게 되면 안과 밖이 극이 바뀌는 탈분극 상태가 발생하며 뉴런에서 신호가 발생하게 된다.

이러한 탈분극 상태에 의한 신호 전달을 자세히 이해하기 앞서 뉴런의 구조를 먼저 살펴보면, 뉴런에는 크게 네 가지 주요 영역이 있다. 수상돌기, 세포체, 축삭돌기, 축삭 종말이다. 간단히 설명하자면 수상돌기/축삭돌기는 각각 신호 수신/발신 역할을 한다. 세포체(Cell body)는 세포호흡(Cell respiration)과 폴리펩티드 생산과 관련한 세포 소기관을 갖고 있다. 축삭 종말은 안쪽에 소포(vesicle)이라는 작은 막이 있어 신경전달물질을 저장하는 역할을 한다. 이외에 미엘린은 절연체로 축삭을 감쌈으로써 입력 신호를 더 빠르게 전달할 수 있도록 경로를 매끄럽게 만드는 역할을 한다. 

수상돌기에는 가시 모양으로 뻗은 돌기들이 있다. 이 부분에서 다른 뉴런들로부터 유입 신호(incoming signal)을 받는다. 유입신호는 세포체로 이동하는 과정에서 통합된다. 만약 신호 통합이 세포막(cell membrane)을 가로질러 충분히 강하게 탈분극 한다면 축삭(axon)이 시작되는 세포막에서 극파(spike)가 발생되어 축삭을 따라 전파된다. 만약 극파가 축삭 종말(axon terminal)에 도달하면 신경전달물질이 시냅스 간극으로 방출되고 일부는 시냅스 후 뉴런의 수용체에 결합한다. 참고로 이러한 신경 전달 과정은 단방향인 수상 돌기 → 세포체 → 축삭돌기 → 축삭 종말로만 흐른다.

유입 신호가 축삭 종말에 도달하기 전에는 축삭 돌기에서는 휴지 전위(Resting potential)를 유지한다. 휴지 전위란 뉴런이 흥분하여 신호를 전달하기 전, 준비 상태를 말한다. 만약 휴지 전위가 없다면 뉴런은 더 이상 신호를 전달할 수 없게 된다. 그렇다면 이런 휴지 전위는 왜 발생할까? 휴지 전위는 결과적으로 이온의 불균등한 분포(농도)차이 때문에 발생한다. 세포막을 기준으로 세포막 외부에는 나트륨 이온의 농도가 높고 세포막 내부에는 칼륨 이온의 농도가 높다. 

휴지 상태에서는 세포막에 있는 나트륨 채널과 칼륨 채널이 모두 닫힌 상태이다. 이런 휴지 상태에서는 세포막 외부는 내부에 비해 양극(positive)로 대전된 상태이며 세포막 내부는 외부에 비해 음극(negative)로 대전된 상태이다. 즉 세포막을 넘어 전압 차이가 발생한다. 

만약 이 휴지상태에서 유입 신호가 축삭 돌기에 도달한다면 탈분극 단계로 바뀐다. 탈분극 단계에는 나트륨 이온이 세포의 분극이 역전될 때 까지 세포 내부로 들어가며 결과적으로 세포 내부가 양극으로 대전된다. 이 상태가 되면 재분극 단계(Repolarizing phase)로 바뀌어 나트륨 이온 채널이 닫히고 칼륨 이온 채널이 열린다. 이 때 칼륨 이온은 세포 외부로 방출되며, 방출됨으로써 평형을 이루게 되어 다시 휴지 전위 상태가 된다.

여기서 평형 상태를 유지하기 위해서는 크게 두 가지 메커니즘이 작용한다. 첫 번째는 정전기력이다. 정전기력에 의해 양이온과 음이온이 서로 끌어 당기게 된다. 두 번째 힘은 확산(diffusion)이다. 확산은 모든 물질이 농도가 높은 곳에서 낮은 곳으로 퍼져나가려는 성질이 있음을 의미한다. 예를 들어 칼륨 이온의 경우 세포막 안쪽에 많이 위치하기 때문에 농도가 높다. 따라서 농도가 낮은 세포막 외부로 빠져나가려고 한다. 하지만 칼륨 이온은 양이온이기 때문에 음이온이 더 많은 세포막 내부로 정전기력에 의해 끌리게 된다. 추가적으로 이런 평형 상태를 유지하는 데 있어 기여하는 것은 위 그림 중간에 있는 나트륨-칼륨 펌프이다. 이는 일종의 경비원으로 만약 휴지전위에서 양전하를 띤 나트륨 이온이 일부 채널을 통해 유입되면 다시 바깥으로 방출하는 역할을 한다. 

다시 돌아와, 유입 신호로부터 휴지전위 → 탈분극 → 재분극 → 휴지전위와 같은 일련의 단계가 축삭 돌기를 따라 연쇄적으로 발생하며 축삭 종말에 다다라서는 축삭 종말에 있는 신경전달물질이 다음 뉴런으로 방출되며 신경 전달이 이루어진다. 

Reference

[1] 『뇌처럼 현명하게: 신경철학 연구』

[2] 『나는 뇌 입니다』

[3] Image: https://en.wikipedia.org/wiki/Resting_potential

1. 모수 추정 개요

통계학의 대전제는 분석 대상 전체(모집단)를 분석하기에는 많은 비용이 발생하므로 부분(표본)을 통해 모집단의 특성을 파악하는 것이다. 모집단의 일부인 표본에 통계 분석 방법을 적용해 모수를 추정하는 방법을 모수 추정이라 한다. 모수는 모집단의 특성을 나타내는 수치를 의미한다. 모수의 종류는 모평균, 모분산, 모비율, 모표준편차, 모상관관계 등이 있다. 이런 모수들은 모집단 전체에 대한 값들이므로 알려지지 않은 수치다. 모집단의 특성을 파악하기 위해서는 이 모수들을 산출할 필요가 있다. 하지만 모집단 전체를 대상으로 산출하기에 비용이 많이 들어 현실적으로 가능하지 않다. 따라서 앞서 말한 것 처럼 표본을 추출하여 모집단의 일반적 특성을 추론하는데, 이를 통계적 추론이라 한다. 또 모수와 마찬가지로 표본의 특성을 나타내는 수치 종류로 표본평균, 표본분산, 표본비율, 표본표준편차, 표본상관관계 등이 있다. 이러한 수치들을 표본 통계량이라 한다. 정리하면 표본 통계량을 기반으로 모수를 구하는 것을 모수 추정 또는 통계적 추론이라 한다. 하지만 이러한 통계적 추론에는 부분을 통해 전체를 추정하는 격이므로 오차가 발생할 수 밖에 없다. 이러한 모수 추정에서 발생하는 오차를 표준오차라고 한다.

2. 모수 추정 방법: 점 추정(point estimation)과 구간 추정(interval estimation)

2.1 점 추정 (point estimation)

점 추정이란 표본으로부터 추론한 정보를 기반으로 모집단의 특성을 단일한 값으로 추정하는 방법이다. 예를 들어 대한민국 남녀 100명씩 표본으로 추출해 키를 조사한 결과 평균이 167.5가 나왔다면 모 평균을 단일한 점인 167.5로 추정하는 방법이다. 이러한 추정을 위해 표본평균과 표본분산 등을 계산해 모집단 평균과 모집단 분산 등을 추정한다. 이 때 표본평균과 표본분산 등은 모수를 추정하기 위해 계산되는 표본 통계량이자 추정량이라 부른다. 이 추정량은 추정치를 계산할 수 있는 함수(확률변수)이다. 이 추정량을 통해 표본에서 관찰된 값(표본평균, 표본분산 등)을 넣고 추정치(모평균, 모분산 등)를 계산한다. 

표본평균과 표본분산 등의 추정량(표본 통계량)을 구하기 위해 먼저 표본이 추출되어야 한다. 표본 추출에 있어 가장 중요한 것은 무작위성(비편향성)이다. 편향되어 어떤 표본이 자주 추출된다면 모집단의 일반화된 특성을 추론할 수 없기 때문이다. 아래 그림을 보면 두번째는 편향은 작되 분산이 큰 경우고, 세 번째는 편향이 크되 분산이 작은 경우다. 네 번째는 편향도 크고 분산도 큰 경우다. 모수 추정의 목표는 표본으로부터 구한 표본 분산과 표본 편향 등의 추정량(표본 통계량)이 모수(과녁)와 오차가 작은 첫 째 그림과 같은 형태가 되는 것이다. (만약 모수와 표본 간의 관계를 더 자세히 알고 싶다면 중심극한정리를 볼 것, 모수추정을 가능하게 하는 수학적 근간이다.)

위 그림이 나타내는 바와 같이 추정량에 따라 추정치가 달라지므로 모수와 오차가 적은 추정치를 구하기 위해서는 추정량 선정에 있어 4가지 기준을 고려해야 한다. 아래 4가지를 설명하기 위해 수식 몇 가지만 간단히 정의하자면 모수: $\theta$ 표본 통계량: $\hat{\theta}$ 기대값: $E$이다.

1. 비편향성 (unbiasedness): 표본으로부터 구한 통계량 기대치가 추정하려는 모수의 실제 값과 같거나 가까운 성질을 의미 한다. 즉 편향(편의)은 추정량의 기대치와 모수와의 차이를 의미하는 것으로  $E(\hat{\theta}) - \theta = 0$이다. 편향이 0에 가까워질수록 좋은 추정량이 된다. 이러한 비편향성을 띠는 추정량을 unbiased estimator라고 하며 결국 편향이 적은 추정량을 선택해야 한다. $E(\hat{\theta}) = \theta$을 최대한 만족하는.

2. 효율성 (efficiency): 추정량 분산이 작게 나타나는 성질을 의미한다.

3. 일치성 (consistency): 표본 크기가 클수록 추정량이 모수에 점근적으로 근접하는 성질을 의미한다.

4. 충분성 (sufficiency): 어떤 추정량이 모수 $\theta$에 대해 가장 많은 정보를 제공하는지 여부를 나타내는 성질을 의미한다.

2.2 구간 추정 (interval estimation)

점 추정의 추정치가 모수와 같을 확률이 낮고 따라서 신뢰성이 낮다는 한계를 극복하기 위해 나온 방법이 구간 추정이다. 구간 추정을 통해 표본으로부터 추정한 정보를 기반으로 모수 값을 포함할 것이라 예상되는 구간을 제시한다. 이 구간을  신뢰 구간이라 한다. 신뢰 구간은 표본평균의 확률분포에 모평균이 신뢰수준 확률로 포함되는 구간을 의미한다. 즉 어떤 구간 내에 몇 % 확률로 존재하는지 추정하는 것이다. 구간 추정은 구간의 [하한, 상한]으로 표현하고 구간의 간격(interval)이 작을수록 모수를 정확하게 추정할 수 있다. 따라서 구간 추정은 점 추정에 비해 신뢰성이 높다는 장점이 있다. 신뢰성이 높다하여 점 추정이 불필요한 것은 아니다. 점 추정치를 기반으로 구간 추정이 이뤄지기 때문이다. 

3. 추정량 정확성 평가 척도

그렇다면 추정량의 '좋다'의 기준인 정확성 평가는 어떻게 이뤄질까? 추정량이 모수와 근사할수록 좋을 것이다. 이를 위해 정확성 평가는 정량적으로 이뤄지며 일반적으로 크게 3가지 방법을 사용한다. 평균 제곱 오차(MSE), 제곱근 평균 제곱 오차(RMSE), 가능도(Likelihood)이다. 

3.1 평균 제곱 오차 (MSE, Mean Squared Error)

오차의 제곱에 대해 평균을 취한 것으로 값이 작을수록 좋다. 식으로는 다음과 같이 나타낸다. 참고로 $\theta$는 $X$로 표기하였다.

$n$은 표본 수 $x_i$는 관측된 표본 $\hat{x_i}$는 추정값이다. 

$MSE(\hat{X}) = E(X - \hat{X})^2 = {1\over n} \sum_{i=1}^n (x_i - \hat{x_i})^2$

3.2 제곱근 평균 제곱 오차 (RMSE, Root Mean Squared Error)

오차의 제곱에 대해 평균을 취한 값에 제곱근을 씌워준 것으로 값이 작을수록 좋다. 식으로는 다음과 같이 나타낸다.

$MSE(\hat{X}) = \sqrt{E(X - \hat{X})^2} = \sqrt{{1\over n} \sum_{i=1}^n (x_i - \hat{x_i})^2}$

3.3 가능도 (Likelihood)

가능도에 대한 개념 이해

일반적으로 가능도를 이해하기 위해 확률과 비교하며 함께 설명된다. 그 이유는 가능도는 확률의 반대 개념이기 때문이다. 그렇다면 어떻게 반대될까? 이를 잘 나타내는 그림은 다음과 같다. (출처: adioshun)

즉 확률이란 모수를 알고 있는 상태에서 표본이 관찰될 가능성을 의미하는 값이다. 모수를 알고 있다는 것을 다른 말로 확률분포가 결정되어 있는 상태라고 할 수 있다. 반면 가능도는 모수를 모르는 상태(=확률분포를 모르는 상태)에서 관측한 표본이 나타날 가능성에 기반해 모수 추정(확률분포 추정)을 진행한다. 즉, 가능도는 표본을 관측해 이 표본들이 어떤 확률분포를 갖는 모집단에서 추출되었는지를 역으로 찾는 것을 의미한다.

가능도의 필요성에 대한 배경

이런 가능도는 왜 필요할까? 왜 만들어졌을까? 그 이유는 확률의 한계 때문이다. 확률은 이산형 확률과 연속형 확률로 나뉜다. 이 때 연속형 확률에서 특정 표본이 관찰될 확률은 전부 0으로 계산되기 때문에 표본이 관찰될 확률을 비교하는 것이 불가능하다. 예를 들어 아래와 같이 연속형 확률을 표현하기 위한 확률 밀도 함수(PDF, Probability Density Function)가 있다 가정하자.

이 때 a와 b사이의 여러 표본들이 추출되어 관측될 수 있는 확률은 a와 b사이의 면적과 같다. 즉 a에서 b까지 적분하면 면적(확률)을 구할 수 있게 된다. 하지만 만약 어떤 특정 하나의 표본이 추출되면 하나의 직선만 되므로 넓이를 계산할 수 없게 된다는 문제점이 있는 것이다. 즉, 특정 관측치에선 확률값이 전부 0이 되어 버리는 것이다. 이러한 한계점을 해결해주는 것이 가능도인 것이다.

가능도에 대한 예시와 특징

가능도란 한 마디로 추출된 표본으로부터 어떤 분포를 가진 확률밀도함수의 y값을 구해 모두 곱해준 값을 의미한다. 또 다른 의미로 가능도는 관측된 표본이 어떤 분포로부터 나왔을지를 수치로 표현한 것을 말한다. 아래 그림을 살펴보자 (출처: 공돌이의 수학정리노트)

만약 모수로부터 추출된 표본이 [1, 4, 5, 6, 9]가 있고, 모수의 후보인 주황색 확률밀도함수와 파란색 확률밀도함수 중 어떤 것이 더 모수와 가깝다고 추정할 수 있을까? 직관적으로 주황색 확률밀도함수라 할 수 있다. 이를 수치적으로 계산하기 위해서는 각 후보 확률밀도함수를 대상으로 각 표본을 전부 넣고 해당 확률밀도함수의 y값(높이)인 기여도를 구해 모두 곱해준다. 이렇게 기여도를 모두 곱하면 likelihood 값이 된다. 이때 이 likelihood 값이 가장 큰 확률밀도함수가, 모수가 지닌 분포를 따를 가능성이 가장 높다. 또 이런 가장 높은 likelihood 값으로 모수의 확률밀도함수를 추정하는 방법을 최대가능도법(Maximum Likelihood Estimation, MLE)이라 한다. 참고로 주의해야할 것은 가능도 함수는 확률 함수가 아니기 때문에 모두 합해도 1이 되지 않는다. 그 이유는 가능도의 수치적 계산은, 관측값이 나올 수 있는 확률분포를 추정하여 얻은 값을 모두 곱해주기 때문이다. 

가능도 함수의 수식적 이해

앞서 설명한대로 가능도는 어느 한 분포에 대하여 표본들의 기여도를 전부 곱해준 값이라 했다. 이러한 가능도를 함수로 표현하면 다음과 같다. 

$P(X|\theta) = \prod_{k=1}^nP(x_k|\theta)$

가능도 함수에 사용한 수식 기호는 다음과 같은 의미를 지닌다.

$\theta = \theta_1, \theta_2, \theta_3, \dots, \theta_m$: 어떤 분포를 따른다 가정하는 확률분포함수 집합 

$X = x_1, x_2, x_3, \dots, x_n$: 모수에서 추출된 표본의 집합

$p$: 확률밀도함수(기여도, 높이값)

따라서 정리하자면 확률밀도함수에 표본을 넣고 구한 기여도인 $p(x|\theta)$값을 전부 곱해주게 되면 어떤 한 확률밀도함수에 대한 liklihood 값이 된다. 그리고 표본에 대해 이 likelihood 값이 가장 큰 확률밀도함수가 모수를 잘표현한다고 하며 이런 모수를 찾는 것을 최대가능도법이라 한다.

참고로 일반적으로 계산의 용이를 위해 자연 로그를 취해주는 아래의 log likelihood 함수를 사용한다.

$logP(X|\theta) = \sum_{k=1}^nlogP(x_k|\theta)$

4. 추정량 구하는 방법

추정량을 구하는 방법에는 일반적으로 크게 3가지 방법을 사용한다. 최대 가능도 추정법, 적률 방법, 베이즈 추정법이다. 이 세 방법은 모두 점 추정에 속하는 방법들이다. 

4.1 최대가능도법 (MLE, Maxmimum Likelihood Estimation)

최대우도추정이라고도 불리는 MLE는 위에서도 설명한 바와 마찬가지로 모수 $\theta$를 추정하는 방법 중 하나이다. 관측치가 주어졌을 때 likelihood 함수 값을 최대화하는 $\theta$를 찾는 것이 목표이다. 이 $\theta$는 어떤 확률밀도함수들을 표현한 것이다. 또 관측치 $X = x_1, x_2, x_3, \dots, x_n$이 있을 때 이들을 수식으로 표현하면 likelihood 함수는 다음과 같은 형태를 가진다.

$P(X|\theta) = P(x_1, x_2, x_3, \dots, x_n | \theta)$

이 때 MLE란 likelihood 함수 값을 최대로 만드는 확률밀도함수($\hat{\theta}$)를 찾는 것이다. 이를 나타내면 다음 형태와 같다.

$\hat{\theta} = argmax\ P(X|\theta)$

이 때 관측한 표본이 독립이라 가정하는 i.i.d (independent and identical distributed) 가정이 충족된다면 아래가 성립한다.

$P(X|\theta) = \prod_{k=1}^n P(x_k|\theta)$

* i.i.d란 확률변수가 여러 개($x_1, x_2, x_3, \dots, x_n$) 있을 때 이들이 상호독립적이고 모두 동일한 확률분포 p(x)를 가지는 것을 말한다. 

4.2 적률 방법(Method of Moments)

적률 방법 또는 적률추정법이라 불리는 방법은 아래 링크를 참조 가능하다.

[확률/통계] 적률추정법 이해하기 (Method of Moments Estimator)

4.3 베이즈 추정 (Bayseian)

베이즈 추정은 베이즈 정리를 기반으로 한다. 베이즈 정리는 사전 확률(prior probability)과 사후 확률(posterior probability)의 관계를 나타내는 정리다. 이 베이즈 정리는 조건부 확률을 기반으로 한다. 조건부 확률이란 사건 A가 발생했다는 전제하에 사건 B가 일어날 확률이다. P(B|A)=P(B∩A)P(A)로 표현한다. 베이즈 정리는 이 조건부 확률에서 유도된 것으로 다음과 같은 수식으로 나타낸다.

위 두 수식은 동일한 것으로 변수명만 달리했다. 그 이유는 이해를 조금 더 쉽게 돕기 위함으로 왼쪽은 조건부 확률로부터 유도될 때 흔히 사용하고, 오른쪽은 베이즈 정리가 결국 모수(θ) 추정을 목적으로 한다는 것을 보이기 위함이다. 수식의 의미를 하나씩 분석해보자면, 먼저 posterior는 새로운 표본 X가 관측됐을 때 어떤 모수값을 갖는지를 의미한다. likelihood는 어떤 표본 X가 관찰되었을 때 어떤 확률분포를 갖는 모집단(모수)에서 추출되었을 확률을 의미한다. prior는 사전확률인 모수값을 의미하며, evidence는 모집단으로부터 표본 X가 관측될 확률이다. 결국 이 베이즈 정리를 요약하면 가능도(likelihood), 사전확률(prior), 관측 데이터(evidence)를 이용해 사후 확률(posterior)를 예측하는 방법이다.

간단 용어 정리

추정 (Estimation) : 표본 통계량(표본 평균, 표본 분산 등)에 기초해 모집단의 모수(모 평균, 모 분산 등)를 추정하는 것

추정량 (Estimate) : 모수를 추정하는 통계량. 표본 통계량은 모두 추정량이 될 수 있음. 추정량은 어떤 표본 분포를 띤 확률변수가 됨. 추정량은 관측된 표본에 따라 모수를 추정하는 것으로써 관측 표본 때 마다 값이 달라지는 확률변수임.

추정치 (Estimated value): 모수를 추정해 나온 특정 값

추정기 (Estimator): 관측 표본으로부터 추정량을 계산하는 함수

P.S 아래 표는 개인적으로 향후 재 참조를 위해 추가

틀린 부분이나 오탈자 지적은 언제든 환영합니다.

Reference

[1] https://ssung-22.tistory.com/42

[2] https://ai-times.tistory.com/472

[3] https://process-mining.tistory.com/131

[4] https://math100.tistory.com/49

[5] http://www.ktword.co.kr/test/view/view.php?m_temp1=3755 

[6] https://m.blog.naver.com/mykepzzang/221568285099

[7] https://dlearner.tistory.com/43

[8] https://angeloyeo.github.io/2020/07/17/MLE.html

주성분 분석이란 무엇일까?

주성분 분석은 차원 축소에 사용되는 대표적인 알고리즘이다. 차원 축소는 고차원 공간 데이터를 저차원 공간으로 옮기는 것을 말한다. 그렇다면 이 차원축소가 왜 필요할까? 고차원으로 표현된 데이터는 계산 비용 많고 분석에 필요한 시각화가 어렵기 때문이다. 또 고차원을 이루는 피처 중 상대적으로 중요도가 떨어지는 피처가 존재할 수 있기 때문이다. 따라서 중요도가 낮은 피처를 제외하는 대신 계산 비용이나 비교적 준수한 성능을 얻는다. 주성분 분석을 진행하면 차원 축소로 인해 표현력이 일부 손실된다. 만약 4차원에서 2차원으로 축소를 통해 첫 번째 주성분과 두 번째 주성분을 얻고, 이 두 개가 원래 피처 표현력의 90%를 띤다면 나머지 10%의 손실을 감수하더라도 계산 효율을 얻게 된다. 

주성분 분석을 통해 저차원 공간으로 변환할 때 피처 추출(feature extraction)을 진행한다. 이는 기존 피처를 조합해 새로운 피처로 만드는 것을 의미한다. 이 때 새로운 피처와 기존 피처 간 연관성이 없어야 한다. 연관성이 없도록 하기 위해 직교 변환을 수행한다. 직교 변환을 수행하면 새로운 피처 공간과 기존 피처 공간이 90도를 이루게 된다. 즉 내적하면 0이 되는 것이다. 이러한 직교 변환을 수행할 때 기존 피처와 관련 없으면서 원 데이터의 표현력을 '잘' 보존해야 한다. 잘 보존하는 것은 주성분 분석의 핵심인 분산(Variance)을 최대로 하는 주축을 찾는 것이다.

여기서 분산이란? 데이터가 퍼진 정도를 의미한다. 예를 들어 만약 4차원 공간이 있고 3차원 공간으로 차원 축소를 한다면 3차원 공간상에서 데이터 분포가 넓게 퍼지는, 즉 분산을 가장 크게 만드는 벡터를 찾아야 한다. 만약 3차원 공간이 있고 2차원 공간으로 차원 축소한다면, 2차원 공간상에서 데이터 분포가 가장 넓게 퍼지도록 하는 벡터를 찾아야 한다. 만약 2차원 공간이 있고 1차원 공간으로 차원 축소 한다면 1차원 공간상에서 데이터 분포가 가장 넓게 퍼지게 만드는 벡터를 찾아야 한다.

애니메이션으로 이해하자면 다음과 같다. 

2차원 공간을 1차원으로 줄일 때 2차원에 넓게 퍼진 데이터 분포를 1차원 상에서도 똑같이 넓게 퍼질 수 있도록 하는 "벡터"를 찾아야 한다. 여기서 "벡터"는 곧 주축을 의미한다. 이 때 주축과의 동의어를 Eigen vector라고 한다. 주축을 찾고 주축에 피처들을 사상시키게 되면 주성분이 된다. 다르게 말해 피처들을 주축에 사상시킬 때 분산이 최대가 되는 주성분이 만들어진다. 이렇게 분산이 가장 큰 주성분을 첫 번째 주성분, 두 번째로 큰 축을 두 번째 주성분이라 한다. 

그렇다면 이 주축인 Eigen vector는 어떻게 구하고, Eigen vector에 피처를 어떻게 사상시킬수 있는 것일까? Eigen vector를 구하기 위해서는 특이값 분해 (SVD, Singular Value Decomposition)가 수행된다. 또 사상을 위해서 공분산 행렬이 필요하다. 따라서 사실상 PCA를 한마디로 말하면 데이터들의 공분산 행렬에 대한 특이값 분해(SVD)로 볼 수 있다. 먼저 공분산 행렬에 대해 알아보자.

공분산 행렬이란 무엇일까?

공분산은 한 마디로 두 피처가 함께 변하는 정도, 즉 공변하는 정도를 나타낸다. 수식으로 표현하면 다음과 같다.

$\sum = Cov(X) = {X^TX\over n}$

여기서 n은 행렬 X에 있는 데이터 샘플 개수를 나타내며 $X$란 전체 피처와 데이터 값을 나타낸다. X의 열축은 피처가 되고 X의 행축은 데이터 개수가 된다. 예를 들어 $x_1, x_2, x_3 $ 피처 3개가 있다고 가정하면 $X^T \times T$는 아래와 같이 표현할 수 있다. 

$X^T \times X = $ $\begin{vmatrix} 0.1 & 0.4 & 0.7 \\ 0.2 & 0.5 & 0.8 \\ 0.3 & 0.6 & 0.9 \end{vmatrix}$ $\times$ $\begin{vmatrix} 0.1 & 0.2 & 0.3 \\ 0.4 & 0.5 & 0.6 \\ 0.7 & 0.8 & 0.9 \end{vmatrix}$

전치 행렬과 행렬을 내적하게 되면  아래와 같은 대칭 행렬이 만들어진다.

$\begin{vmatrix} dot(x_1,x_1) & dot(x_1,x_2) & dot(x_1,x_3) \\ dot(x_2,x_1) & dot(x_2,x_2) & dot(x_2,x_3) \\ dot(x_3,x_1) & dot(x_3,x_2) & dot(x_3,x_3) \end{vmatrix}$

이 행렬에서 모든 대각 성분은 같은 피처 간 내적이므로 분산에 해당한다. 대각 성분 이외에는 모두 다른 피처 간 내적이므로 공분산에 해당한다. 즉 이러한 피처 간 내적을 통해 수치적으로 i번 피처와 j번 피처가 공변하는 정도를 알 수 있게 된다. 이것이 수식이 나타내는 의미이다. 수식에서 n으로 나눈 것은 공분산이 커질 수 있으므로 데이터 개수로 나누어 평균을 구한 것이다. 이렇게 만들어진 행렬을 공분산 행렬이라 한다. 

공분산 행렬이 가지는 의미는 무엇이고 어떻게 활용할까?

공분산 행렬은 피처 간에 서로 함께 변하는 정도를 의미한다고 했다. 공분산 행렬은 이러한 공변의 의미와 더불어 한 가지 의미가 더 있다. 그 의미는 바로 벡터에 선형 변환(사상)을 가능하게 하는 것이다. 즉, 공간상에 한 벡터가 있을 때 공분산 행렬을 곱해주게 되면 그 벡터의 선형 변환이 이루어진다. 이는 선형대수학에서 행렬이 벡터를 선형 변환시키는 역할을 하기 때문이다. 즉 공분산 행렬엔 피처간 공변 정보가 담겨 있으므로 이를 주축인 Eigen vector에 사상시키면 주성분을 구할 수 있다. 다음으로 주축을 구하기 위한 특이값 분해(SVD)를 살펴보자.

특이값 분해란 무엇이며 이를 통해 어떻게 Eigen vector를 구할 수 있을까?

먼저 특이값 분해란 일종의 행렬에서 이뤄지는 인수 분해다. 정확히는 행렬을 대각화하는 방법 중 하나이다. 대각화하는 이유는 대각화된 행렬의 대각선에 있는 값이 특이값(Singular Value)에 해당하기 때문이다. PCA에서 특이값 분해 대상은 위에서 본 공분산 행렬이다. 공분산 행렬을 특이값 분해 함으로써 PCA에 필요한 주축인 Eigen vector와, Eigen vector 스케일링에 필요한 Eigen value를 얻을 수 있다. Eigen value를 얻은 뒤 내림차순으로 정렬했을 때 가장 첫 번째 값이 분산을 최대로 하는 값이다.

일반적으로 특이값 분해는 고유값 분해(EVD)와 함께 설명된다. 고유값 분해의 경우 m x m의 정방 행렬에서만 사용할 수 있지만, 특이값 분해의 경우 m x n 인 직사각 행렬에도 적용가능하다. 따라서 일반화가 가능하단 장점이 있다. 또 특이값이란 고유값에 루트를 씌운 값이다. 그렇다면 특이값 분해는 어떻게 진행될까? 먼저 실수 공간에서 임의의 m x n 행렬에 대한 특이값 분해는 다음과 같이 정의된다.

$ A = U\sum V^T$

수식 성분이 나타내는 바는 다음과 같다. 참고로 여기서 $\sum$이란 합을 의미하는 기호가 아니라 행렬을 의미한다. 

$A = m \times n $ 직사각 행렬 (diagonal matrix)

$U = m \times m $ 직교 행렬 (orthogonal matrix)

$\sum = m \times n$ 직사각 대각행렬 (diagonal matrix)

$V = n \times x $ 직교 행렬 (orthogonal matrix)

특이값 분해를 이해하기 앞서 두 가지 선형대수적 특성을 알아야 한다. 첫 번째는 $U$, $V$가 직교 행렬이라면 선형대수적 특성에 의해 $UU^T = VV^T = E$, $U^{-1} = U^T, V^{-1} = V^T$가 만족한다는 것이다. 여기서 $E$는 항등행렬이다. 여기서 항등행렬이란 가령 $U$에 역행렬인 $U^{-1}$를 곱했을 때 나오는 행렬을 의미한다. 두 번째론 대칭 행렬은 고유값 분해가 가능하며 또 직교행렬로 분해할 수 있다는 것이다. 앞에 보았던 공분산인 행렬 $A$는 대각선으로 기준으로 값들이 대칭을 띠는 대칭 행렬이었다. 그러므로 고유값 분해 또는 직교행렬로 분해할 수 있다. 또 행렬 $A$가 대칭행렬이므로 $A^T$도 대칭 행렬이다.

결과적으로 PCA는 특이값 분해를 통해 $\sum$를 구하고자 한다. 이 $\sum$는 $AA^T, A^TA$를 고유값 분해해서 나오는 고유값들에 루트를 씌운 값들이 대각선에 위치하는 행렬이다. 그리고 $AA^T$와 $A^TA$의 고유값이 같다. 이를 증명하는 하는 과정은 다음과 같다.

앞서 특이값 분해의 정의는 $A = U\sum V^T$라고 했다. 이때 $A$는 대각행렬이므로 고유값 분해가 가능하다. 

$AA^T = (U\sum V^T)(U\sum V^T)^T$

            $= U\sum V^T V\sum^T U^T$ (이 때 $V^TV$ = $V^{-1}V$ 즉 직교행렬이므로 항등 행렬이 되어 사라짐)

            $= U(\sum \sum^T)U^T$

즉 $AA^T$를 고유값 분해하면 = $U(\sum \sum^T)U^T$가 된다. 또,

$A^TA = (U\sum V^T)^T(U\sum V^T)$

            $= V\sum^T U^TU\sum V^T$ (이 때 $U^TU$ = $U^{-1}U$ 즉 직교행렬이므로 항등 행렬이 되어 사라짐)

            $= V(\sum ^T\sum)V^T$

즉 $A^TA$를 고유값 분해하면 = $ V(\sum ^T\sum)V^T$가 된다.

그리고 이를 정리하고 덧붙이면,

$U$는 $AA^T$를 고유값 분해 해서 얻은 직교행렬이다. 그리고 U의 열벡터를 A의 left singular vector라 부른다.

$V$는 $A^TA$를 고유값 분해 해서 얻은 직교행렬이다. 그리고 V의 열벡터를 A의 right singular vector라 부른다.

$\sum$은 $AA^T, A^TA$를 고유값 분해해서 나온 고유값($\lambda$, eigen value)들의 제곱근을 대각원소로 하는 직사각 대각행렬이다. 

이 $\sum$의 대각원소들을 행렬 A의 특이값(singular value)라 부른다. 아래 수식과 같다. 

$\begin{vmatrix} \sqrt\lambda_1 & 0 & 0 & \dots \\ 0 & \sqrt\lambda_2 & 0 & \dots \\ 0 & 0 & \sqrt\lambda_3 & \dots \\ 0 & 0 & 0 & \dots \end{vmatrix}$

* 참고로 $\sum$의 경우 직사각 대각행렬이므로 m > n이거나 m < n인 경우로 나뉜다. 이 두 경우 모두 항상 대각선에만 특이값이 있어야 한다는 점만 상기하면 혼동되지 않는다. 

특이값들($\sum\sum^T or \sum^T\sum)$을 제곱하게 되면 $AA^T, A^TA$의 고유값과 같다.

결국 특이값 분해를 수행하게되면 $AA^T$와 $A^TA$의 고유벡터와, 고유값이 도출된다.

이후 고유벡터의 방향으로 피처들을 사상시키고, 고유값의 크기만큼 스케일링 해줌으로써 PCA 과정이 마무리 된다.

Reference

[1] Eigen Vector, Eigen Value: https://m.blog.naver.com/galaxyenergy/222123501087

[2] Covariance, SVD: https://www.youtube.com/watch?v=jNwf-JUGWgg 

[3] SVD: https://blog.naver.com/galaxyenergy/222865992256

[4] SVD: https://rfriend.tistory.com/185

[5] SVD: https://darkpgmr.tistory.com/106

[6] Image: https://medium.com/vlgiitr/principal-components-analysis-82a7682323e6

최단 거리 알고리즘이란 그래프 상에서 노드 간의 탐색 비용을 최소화하는 알고리즘이다. 일반적으로 네비게이션과 같은 길찾기에 적용된다. 최단 거리 알고리즘 종류는 크게 3가지가 있다. 1. 다익스트라(Dijkstra) 2. 플로이드 워셜(Floyd Warshall) 3. 벨만 포드(Bellman Ford)이다.

1. 다익스트라 (Dijkstra) 알고리즘

다익스트라 알고리즘은 그래프 상에서 특정 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 다르게 표현하면 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 알고리즘 중 하나이다.

다익스트라는 그리디와 동적 계획법이 합쳐진 형태이다. 현재 위치한 노드에서 최선의 경로를 반복적으로 찾으면서도 계산 해둔 경로를 활용해 중복된 하위 문제를 풀기 때문이다. 다익스트라는 만약 그래프에 음의 가중치가 있다면 사용할 수 없다. 그 이유는 그리디를 통해 최단 경로라고 여겨진 경로 비용을 DP 테이블에 저장한 뒤, 재방문하지 않는데, 만약 음의 가중치가 있다면 이러한 규칙이 어긋날 수 있기 때문이다. 음의 가중치가 포함된다면 플로이드 워셜이나 벨만 포드 알고리즘을 사용해 최단 경로를 구할 수 있다. 다만 시간 복잡도가 늘어나는 단점이 있기에 해결하고자 하는 문제에 맞게 사용해야 한다.

만약 아래와 같은 그래프가 있다 가정하고 동작 원리를 확인해보자.

위와 같은 초기 노드와 간선을 테이블에 나타내보자면 다음과 같다. 예를 들자면 1행 4열은 1번 노드에서 4번 노드로 가는 것을 나타내며 비용은 8이 든다.

다익스트라 알고리즘은 특정 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘이라 했다. 예를 들어 특정 한 노드를 1이라 가정하면 [0, 3, INF, 8, 9]는 다음과 같은 과정을 통해 업데이트 된다.

아래와 같이 노드 1을 선택하게 되면 1과 연결된 3개의 간선을 확인한다.

이 중에서 다른 정점으로 가는 최소 비용이 2번 노드가 가장 작기 때문에 2번 노드로 이동하고, 노드 1번은 방문 처리한다. 이 때 테이블 값 변화는 없다.

2번 노드에 연결된 노드는 1번과 3번이다. 하지만 1번의 경우 이미 방문했고, 비용이 크므로 볼 필요 없다. 2와 최소비용으로 연결된 노드는 3이기 때문에 노드 3으로 이동하고, 2를 방문처리 한다. 이 때 테이블 값 변화가 발생한다. 1과 3은 연결되지 않았었다. 하지만 그리디와 같이 계속해서 최적의 상태를 업데이트 하므로 다른 노드를 탐색하다 3을 방문할 수 있기 때문에 1 → 2 → 3으로 이동하는 동안의 비용인 5로 업데이트 해준다.

다음으로 3번 노드에 연결된 간선은 총 3개이다. 하지만 2의 경우 방문처리 되었으니 노드 4, 5번 두 개만 고려하면 된다.

노드 4, 5번 중 더 비용이 적은 것은 4번 노드이므로, 4번 노드로 이동하고 3번 노드는 방문처리 해준다. 마찬가지로 테이블 값 변화가 발생한다. 기존에는 1 → 4로 가는 비용이 8이었지만 1 → 2 → 3 → 4를 거치는 것이 6이 들기에 테이블 값을 6으로 업데이트 시켜준다.

다음으로 4번 노드에 연결된 간선은 총 2개이다. 하지만 두 개 모두 방문처리 되었고 5로 가는 간선이 없다.

따라서 테이블 값 업데이트는 없다. 또 알고리즘은 여기서 끝이 난다. 최종적으로 1에서 다른 모든 노드까지의 비용은 아래 테이블이 된다.

이를 코드로 구현하기 위해서는 가중치에 중요도가 있으므로 자료구조 힙을 사용해 표현해준다. 전체 코드는 다음과 같다.

""" This is input value. you can just copy and paste it. 
5 6 1
1 2 3
1 4 8
1 5 9
2 1 2
2 3 2
3 2 2
3 4 1
3 5 3
4 1 8
4 3 1
5 1 9
"""

import heapq

def dijkstra(start):
    heap = []
    heapq.heappush(heap, [0, start]) # 최소힙은 배열의 첫 번째 값을 기준으로 배열을 정렬.
    INF = float('inf')
    weights = [INF] * (vertex+1) # DP에 활용할 memoization 테이블 생성
    weights[start] = 0 # 자기 자신으로 가는 사이클은 없으므로.
    
    while heap:
        weight, node = heapq.heappop(heap)
        if weight > weights[node]: # 비용 최적화 전부터 큰 비용일 경우 고려할 필요 없음.
            continue
        
        for n, w in graph[node]: # 최소 비용을 가진 노드를 그리디하게 방문한 경우 연결된 간선 모두 확인
            W = weight + w
            if weights[n] > W: # 여러 경로를 방문해 합쳐진 가중치 W가 더 비용이 적다면 
                weights[n] = W # 업데이트
                heapq.heappush(heap, (W, n)) # 최소 비용을 가진 노드와 합쳐진 가중치 추가

    return weights

vertex, edge, start = map(int, input().split())
graph = [[] for _ in range(vertex+1)]
for i in range(vertex+edge):
    src, dst, weight = map(int, input().split())
    graph[src].append([dst, weight])

weights = dijkstra(start)
print (weights) # [inf, 0, 3, 5, 6, 8]

최종 출력되는 최소 비용 중 1에서 1로 가는 사이클은 없으므로 0이 된다. 또한 만약 주어진 문제가 1에서 3으로 가는 최소비용을 구하는 것이라면 5가 되고, 1에서 4로가는 최소 비용을 구하는 것이라면 6이 된다.

참고로 시간 복잡도는 $O((V+E) \log V)$이다.

위와 알고리즘을 동일하게 이용하여 백준 1916번: 최소비용 구하기 문제를 해결할 수 있다.

2. 벨만 포드 (Bellman Ford) 알고리즘

벨만 포드 알고리즘은 가중 유향 그래프 상에서 특정 한 노드로 부터 다른 노드까지의 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘의 한계점을 보완하기 위해 나왔다. 그 한계점이란 간선이 음수일 때 최단 경로를 구할 수 없다는 것이다. 사실 정확히는 음의 가중치 자체가 문제가 되진 않는다. 문제는 사이클 형성 여부에 따라 달렸다. 만약 사이클을 형성하면 문제가 된다. 아래 그림을 보자.

만약 다익스트라 알고리즘을 통해 특정 한 노드(1)에서 다른 노드(2)로의 최소 거리를 구하는 문제를 해결하려 한다면 가중치 3 → 4 → 5를 거쳐 비용이 12가 된다. 하지만 중간에 사이클이 있기 때문에 3 → 4 → -6 → 4 → -6 → 4 → -6 ...이 되어 비용이 무한히 작아지게 된다.

이러한 문제점을 해결하기 위해 나온 알고리즘이 벨만 포드이다. 기본적으로 다익스트라와 동일하지만 핵심 차이점은 간선의 가중치가 음일 때도 최소 비용을 구할 수 있다. 다만 시간복잡도가 늘어나기 때문에 가중치가 모두 양수일 경우 다익스트라를 사용하는 것이 좋다. 시간 복잡도가 늘어나는 이유는 그리디하게 최소 비용 경로를 찾아가는 다익스트라와 달리, 벨만 포드는 모든 경우의 수를 고려하는 동적 계획법이 사용되기 때문이다.

그렇다면 모든 경우의 수를 어떻게 고려할까? 그 방법은 매 단계 마다 모든 간선을 전부 확인하는 것이다. 다익스트라는 출발 노드에서만 연결된 노드를 반복적으로 탐색하며 다른 모든 노드까지의 최소 거리를 구했다. 하지만 벨만 포드는 모든 노드가 한번씩 출발점이 되어 다른 노드까지의 최소 비용을 구한다.

아직 조금 추상적이니 구체적인 아래 그림을 보며 동작 과정을 알아보자.

위와 같은 그래프가 있다고 할 때 모든 노드가 한 번씩 출발 노드가 될 것이다. 복잡하지 않다. Itertation 1회, 2회일 때를 이해하면 귀납적으로 적용하여 이해할 수 있기 때문이다.

위와 같은 초기 상태의 그래프가 있을 때, 가중치를 담을 DP 테이블 값은 아래와 같이 모두 INF가 된다.

[Iteration 1]
첫 번째로 노드 1번을 먼저 탐색해보자.

1번 노드에 연결된 인접노드에 해당하는 간선의 가중치를 업데이트 해준다.

가중치 업데이트에 있어 시작 노드는 사이클이 없으므로 0이 되고, 2~5모두 연결된 간선이 있으므로 해당 가중치 값을 업데이트 해준다.

[Iteration 1]
이제 2번 노드를 보자. 2번 노드는 3번과 연결되어 있다.

1 → 3 경로 비용인 3보다
1 → 2 → 3 경로 비용인 -8이 더 작으므로 DP 테이블 값을 3에서 -8로 업데이트 해준다.

[Iteration 1]
이제 3번 노드를 보자. 4번과 5번 노드에 연결되어 있다.

1 → 4 비용인 9보다
1 → 2 → 3 → 4 비용인 -3이 작으므로 9를 -3으로 업데이트 해준다.

또
1 → 5 비용인 8보다
1 → 2 → 3 → 5 비용인 -15가 작으므로 8을 -15로 업데이트 해준다.

[Iteration 1]
이제 4번 노드를 보자. 3번 노드와 연결되어 있다.

DP 테이블의 3번에 담긴 비용인 -8이
1 → 4 → 3 비용인 5보다 작으므로 업데이트 하지 않는다.

[Iteration 1]
이제 5번 노드를 보자. 3번 노드와 연결되어 있다.

DP 테이블 3번의 -8이
1 → 5 → 3의 비용 -5보다 더 작으므로 업데이트 하지 않는다.

이를 노드 개수(V) - 1까지 반복 진행한다. 그리고 추가적으로 음의 사이클의 존재 여부를 파악하고 싶다면 마지막으로 1번더 반복하여 총 V번의 반복 했을 때 V-1번 했을 때와 값이 달라진다면 음의 사이클이 있는 것이라 판별할 수 있다. 음의 사이클이 있다면 반복시 무한히 작아지기 때문이다.

Iteration1 종료시 [inf, 0, -6, -8, -3, -15]

Iterataion2 종료시 [inf, 0, -6, -28, -23, -35]

Iteration3 종료시 [inf, 0, -6, -48, -43, -55]

Iteration4 종료시 [inf, 0, -6, -68, -63, -75]

가되며 마지막으로 여기서 한 번더 수행했을 때 값이 바뀐다면 음의 사이클이 존재하는 것이다.

Iteration5 종료시 [inf, 0, -6, -88, -63, -75]

이를 코드로 구현하면 다음과 같다.

"""
5 9
1 2 -6
1 3 3
1 4 9
1 5 8
2 3 -2
3 4 5
3 5 -7
4 3 -4
5 3 -13
"""

import sys
input = sys.stdin.readline

def bellman_ford(start):
    weights[start] = 0
    for i in range(V):
        for src, dst, weight in graph:
            W = weights[src] + weight
            if weights[src] != INF and weights[dst] > W:
                weights[dst] = W
                if i == V -1:
                    return False # negative cycle exists
    return True # there is no cycle

V, E = map(int, input().split())
graph = []
for _ in range(E):
    src, dst, weight = map(int, input().split())
    graph.append([src, dst, weight])

INF = float('inf')
weights = [INF] * (V+1)

if bellman_ford(1): # 출발 노드를 인자 값으로 넣어줄 것
    for i in range(2, V+1): # 출발 노드인 1을 제외하고 다른 모든 노드로 가기 위한 최단 거리 출력
        print (weights[i], end = ' ')
else:
    print ("There is negative cycle.")

위의 알고리즘을 활용하여, 백준 1865-웜홀 문제를 해결할 수 있다.

참고로 시간 복잡도는 $O(VE)$ 이다.

3. 플로이드 워셜 (Floyd Warshall) 알고리즘

플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 구할 수 있다. 한 노드에서 다른 모든 노드까지의 최단 거리를 구하는 다익스트라와 벨만포드 알고리즘과 대조된다. 플로이드 워셜 알고리즘은 그래프 상에서 음의 가중치가 있더라도 최단 경로를 구할 수 있다. 하지만 음의 가중치와 별개로 음의 사이클이 존재한다면 벨만 포드 알고리즘을 사용해야 한다. 

플로이드 워셜 알고리즘은 모든 노드 간의 최단거리를 구하고 이 때, 점화식이 사용되기에 동적 계획법에 해당한다. 동적 계획법에 해당하므로 최단 거리를 업데이트할 테이블이 필요하다. 이 때 모든 노드간의 최단 거리이므로 2차원 배열이 사용된다. 특정 한 노드에서 출발하는 다익스트라가 1차원 배열을 사용하는 것과 차이점이 있다. 

플로이드 워셜 알고리즘의 핵심은 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. 아래 점화식을 살펴보면 다음과 같다.

$D_{ij} = min(D_{ij}, D_{ik} + D_{kj})$

$i$에서 $j$로 가는 것과 $i$에서 $k$를 거쳐 $j$로 가는 것 중 어느 것이 최소 비용인지를 찾는 것이다.

구현은 매우 간단하여 3중 for문이 사용된다. 아래 코드는 위 점화식을 기반으로 코드화 시킨 것이다.

for k in range(1, V+1): # via
    graph[k][k] = 0 # 사이클 없으므로 자기 자신 0
    for i in range(1, V+1): # src
        for j in range(1, V+1): # dst
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

코드와 함께 동작 과정을 아래 그래프를 통해 살펴보자.

노드 4개와 간선 7개로 구성된 그래프다. 이를 바탕으로 DP 테이블 초기 상태를 만들면 다음과 같다. 하나의 노드에서 다른 노드로 바로 갈 수 있다면 가중치를, 없다면 INF를 저장해준다. 

이제 3중 for문을 사용해 거쳐가는 노드를 설정 후 해당 노드를 거쳐갈 때 비용이 줄어드는 경우 값을 업데이트 시켜줄 것이다. 먼저 거쳐가는(k) 노드가 1일 때의 경우를 살펴보자

[Iteration 1] 거쳐가는 노드 K = 1

Iteration 1의 테이블 첫 번째 행을 업데이트 해보자. 노드 1에서 노드 1을 거쳐 노드 1~4까지 탐색하는 경우이다. 

graph[1][1] = min(graph[1][1], graph[1][1]+graph[1][1]) : 0과 0+0을 비교하므로 업데이트 X(graph[k][k] = 0)

graph[1][2] = min(graph[1][2], graph[1][1]+graph[1][2]) : 5와 0+5를 비교하는 것이므로 업데이트 X

graph[1][3] = min(graph[1][3], graph[1][1]+graph[1][3]): INF와 0+INF를 비교하는 것이므로 업데이트 X

graph[1][4] = min(graph[1][4], graph[1][1]+graph[1][4]): 7과 0+7을 비교하는 것이므로 업데이트 X

Iteration 1의 테이블 첫 번째 행을 업데이트 한 결과는 다음과 같다. 업데이트는 없었으므로 전과 동일하다. 다만 graph[k][k] = 0에 의해 첫번째 값만 INF에서 0으로 바뀌었다. 

Iteration 1의 테이블 두 번째 행을 업데이트 해보자. 노드 2에서 노드 1을 거쳐 노드 1~4까지 탐색하는 경우이다.

graph[2][1] = min(graph[2][1], graph[2][1]+graph[1][1]): 4와 4+0을 비교하는 것이므로 업데이트 X

graph[2][2] = min(graph[2][2], graph[2][1]+graph[1][2]): INF와 4+9를 비교하는 것이므로 업데이트 O

graph[2][3] = min(graph[2][3], graph[2][1]+graph[1][3]): -3과 4+INF를 비교하는 것이므로 업데이트 X

graph[2][4] = min(graph[2][4], graph[2][1]+graph[1][4]): INF와 4+7을 비교하는 것이므로 업데이트 O

Itertaion 1의 테이블 두 번째 행을 업데이트 한 결과는 다음과 같다. 업데이트는 두 번 이뤄졌다. 

Iteration 1의 테이블 세 번째 행을 업데이트 해보자. 노드 3에서 노드 1을 거쳐 노드 1~4까지 탐색하는 경우이다.

graph[3][1] = min(graph[3][1], graph[3][1]+graph[1][1]): 6과 6+0을 비교하는 것이므로 업데이트 X

graph[3][2] = min(graph[3][2], graph[3][1]+graph[1][2]): INF와 11을 비교하는 것이므로 업데이트 O

graph[3][3] = min(graph[3][3], graph[3][1]+graph[1][3]): INF와 6+INF를 비교하는 것이므로 업데이트 X

graph[3][4] = min(graph[3][4], graph[3][1]+graph[1][4]): 4와 13을 비교하고 원래 4였으므로 업데이트 X

Itertaion 1의 테이블 세 번째 행을 업데이트 한 결과는 다음과 같다. 업데이트는 한 번 이뤄졌다.

Iteration 1의 테이블 네 번째 행을 업데이트 해보자. 노드 4에서 노드 1을 거쳐 노드 1~4까지 탐색하는 경우이다.

graph[4][1] = min(graph[4][1], graph[4][1]+graph[1][1]): INF와 INF+0을 비교하므로 업데이트 X

graph[4][2] = min(graph[4][2], graph[4][1]+graph[1][2]): INF와 INF+5를 를 비교하므로 업데이트 X

graph[4][3] = min(graph[4][3], graph[4][1]+graph[1][3]): 2와 INF+INF를 비교하고 원래 2였으므로 업데이트 X

graph[4][4] = min(graph[4][4], graph[4][1]+graph[1][4]): INF와 INF+7을 비교하므로 업데이트 X 

Itertaion 1의 테이블 네 번째 행을 업데이트 한 결과는 다음과 같다. 업데이트는 이뤄지지 않았다.

이러한 과정을 노드의 수만큼 반복해주면 된다. 이를 요약하면 다음과 같다.

Iteration2는 노드 1~4에서 노드2를 거쳐 노드 1~4를 탐색하는 경우가 될 것이다.

Iteration3은 노드 1~4에서 노드3을 거쳐 노드 1~4를 탐색하는 경우가 될 것이다.

Iteration4는 노드 1~4에서 노드4를 거쳐 노드 1~4를 탐색하는 경우가 될 것이다.

이를 코드로 나타내면 앞서 본 것과 동일하다. 중요한 것은 거쳐서 노드 k를 거쳐갈때 다이렉트로 가는 것보다 비용이 적어지는가를 판단하는 것이다. 

for k in range(1, V+1): # via
    graph[k][k] = 0 # 사이클 없으므로 자기 자신 0
    for i in range(1, V+1): # src
        for j in range(1, V+1): # dst
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

이러한 플로이드 워셜 알고리즘을 구현하는 전체 코드는 다음과 같다.

""" This is input value. you can just copy and paste it.
4 7
1 2 5
1 4 7
2 1 4
2 3 -3
3 1 6
3 4 4
4 3 2
"""
import sys
input = sys.stdin.readline

V, E = map(int, input().split())
INF = float('inf')
graph = [[INF] * (V+1) for _ in range(V+1)]

for _ in range(E):
    src, dst, weight = map(int, input().split())
    graph[src][dst] = weight

for k in range(1, V+1): # via
    graph[k][k] = 0
    for i in range(1, V+1): # src
        for j in range(1, V+1): # dst
            graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])

for i in range(1, V+1):
    for j in range(1, V+1):
        print (graph[i][j], end= ' ')
    print()

3중 for문을 사용하므로 시간복잡도는 $O(N^3)$가 된다.

이러한 플로이드 워셜 알고리즘을 이용하여 백준 11404번 플로이드 문제를 해결할 수 있다.

제목: Deep Residual Learning for image Recognition

학회: IEEE Conference on Computer Vision and Pattern Recognition

게재: 2016년

컴퓨터 비전에서 높은 이미지 인식 능력 모델의 발전은 AlexNet → VGGNet → GoogLeNet → ResNet 순으로 이뤄진다. 이러한 높은 인식 능력의 배경에는 네트워크의 깊이를 늘림으로써 high level feature부터 low level feature를 효율적으로 추출할 수 있기 때문이다. 대개 네트워크의 깊이를 늘림으로써 모델의 성능이 늘어난다. 하지만 반드시 그렇지는 않다. 아래 그래프가 이를 뒷받침 한다.

위 그래프를 보면 상대적으로 더 깊은 네트워크가 training error가 더 높다. 즉 성능이 더 낮아진다. 왜 이렇게 낮아질까? 네트워크 깊이를 늘리는 데 있어 한계가 있기 때문이다. 그리고 그 한계란 gradient vanishing 문제를 말한다. 이는 레이어가 깊을수록 역전파를 하는 과정에서 미분 값이 줄어들기 때문에 앞단 레이어는 영향을 거의 받지 못하기 때문이다. 이 문제를 해결하기 위해 ResNet이 만들어졌다. 즉 ResNet은 gradient vanishing 문제를 해결하는 모델인 것이다. 그 핵심 방법은 아래 그림 오른쪽과 같이 residual network를 사용하는 것이다.

residual network는 앞단 레이어의 출력값이 입력으로 들어온 x를 feed forward 한 값에 다시 x를 더해준다. 이게 왜 효과가 있을까? 왼쪽 일반 신경망과의 학습 방식이 다르기 때문이다. 일반 신경망은 입력 $x$를 통해 출력 $H(x)$를 얻는 $H(x) = x$다. 반면 오른쪽 residual network는 $H(x) = F(x) + x$가 된다. 중간에 $F(x)$가 추가된 것이다. 이 때 이 추가된 $F(x)$를 0이 되도록 학습한다면 일반 신경망인 $H(x) = x$와 같아진다. 하지만 이렇게 둘러온다면 하나의 큰 장점이 있다. 일반 신경망처럼 역전파가 진행될 때 $H(x) = x$에서 미분하는 것과 달리 residual network를 이용해 미분하게 되면 $H'(x) = F'(x) + 1$이 된다. 즉 1도 남기 때문에 기울기가 0에 수렴하여 소실되지 않고 역전파가 끝까지 진행될 수 있는 것이다.

이해가 안될 경우를 대비해 조금 더 설명하면, $H(x) = F(x) +x$을 이항하면 $F(x) = H(x) - x$가 된다. 이 때 $F(x)$를 0에 근사하게 만든다면 $H(x) - x$도 0에 근사하게 된다. 다시 이항하면 기존 신경망과 같이 $H(x) = x$의 형태가 된다. 양쪽 모두 역전파로 인해 미분되어 0에 근사하게 되면 기울기 소실 문제가 발생하는 것이다. 참고로 $H(x) - x$을 residual이라 부르며, residual network에선 기존 신경망의 학습 목적인 $H(x)$를 최소화 해주는 것이 아니라 $F(x)$를 최소화 시켜주는 것이다. $F(x) = H(x) - x$이므로.

ResNet에서는 residual network를 아래 두 가지 방식을 사용해 구현했다. 첫 번째는 바로 위 그림과 마찬가지로 단순한 구조를 사용하는 Identity 방식과, 두 번째는 1x1 convolution 연산을 통해 차원을 스케일링 해주는 Projection 방식이다. 

기존의 Identity 방식에 더해 Projection 방식이 더해진 이유는 입력/출력 차원이 다를 때 스케일링 해주기 위함이다.  또 Projection 방식은 네트워크를 깊게 만들어줄 때 학습 시간을 줄이기 위해 사용하는데, 위 두 구조가 비슷한 시간 복잡도를 갖기 때문이라고 한다.

다시 돌아와 이러한 residual network 구조를 사용하는 것이 ResNet 이해의 핵심이다. 이렇게 residual network를 모델 레이어로 쌓으면 다음과 같은 성능 증가를 가져오게 된다.

좌측의 residual network를 적용하지 않은 plain network를 살펴보면 레이어를 깊게 해줄수록 성능이 오히려 떨어지게 된다. 반면 residual network를 모델에 적용하게 되면 레이어가 깊더라도 error rate가 떨어져 성능이 더 좋아지는 것을 확인할 수 있다. 

그렇다면 더욱 더 residual network를 쌓게 되면 어떤 결과가 나올까? 아래를 보자. 참고로 ResNet에서 50개의 layer가 넘어가는 모델들은 Projection 방법 (Bottleneck building block)을 사용하여 만든 모델이다. 반대로 50개 미만은 Identity 방법 (Basic building block)으로 만들었다.

좌측 residual network를 적용하지 않은 plain network의 경우에는 레이어가 깊어질수록 성능이 계속 떨어지는 것을 볼 수 있다. 반면 가운데 그래프처럼 ResNet을 적용하면 error율이 아닐 때 보다 더 감소한 것을 볼 수 있다. 또한 110개의 네트워크를 쌓더라도 성능이 증가하는 것을 볼 수 있다. 다만 우측 그래프처럼 residual network를 1202개까지 쌓게 되면 오히려 110개를 쌓았을 때 보다 성능이 좋지 않다. 하지만 이를 두고 1202개 가량을 쌓았을 때가 ResNet의 한계라고 해석할 수 없다. 그 이유는 CIFAR-10 데이터셋만으로는 불충분해 overfitting 되었을 가능성이 있기 때문이고, 또 ResNet 논문 저자들은 그 어떤 Dropout과 같은 Regularization을 적용하지 않았다고 말했다. 따라서 강력한 Regularization을 적용한다면 성능 향상의 여지가 있는 것이다.

마지막으로, ResNet 모델의 개선 여지가 있음에도 불구하고 아래 표와 같이 이전에 나온 VGGNet과 GoogLeNet 모델보다도 높은 성능을 보였다. 

ResNet을 구현하기 위해 먼저 가장 핵심인 ResNet 모델 아키텍처를 살펴보면 다음과 같다.

하나의 max-pool 레이어와, 하나의 average-pool 레이어를 제외하고 모두 convolution 레이어로 구성되어 있다. 또 18, 34 layer는 레이어 구조상 Basic Building Block을 사용하며 50, 101, 152 layer는 Bottleneck Building Block을 사용한다. 

그리고 논문에서 구현에 적용되었던 augmentation 기법과 레이어 특이 사항, 하이퍼파라미터 값을 정리하면 다음과 같다.

1. Augmentation

• 이미지를 스케일 별 augmentation을 위해 이미지 사이즈를 256~480 범위에서 랜덤 샘플링 진행
• 픽셀별 mean substracted을 진행하고, 224x224 이미지에 crop을 랜덤 샘플링 수행하거나 수평 플립을 적용한 이미지에서 crop을 랜덤 샘플링함
• color augmentation을 사용함

2. Layer

• Batch Normalization 적용 (convolution 이후, activation function 이전)
• weight initialization 진행
• Dropout 미사용
• residual network에서 차원이 증가한다면 아래 두 가지 방식 적용
  
  1. 제로 패딩으로 차원 증가에 대응: 추가적인 파라미터 없어 좋음
  2. 1x1 convolution으로 차원 스케일링 해준 뒤 다시 원래 차원으로 스케일링 진행 

3. Hyper-parameter

• 옵티마이저: SGD 사용
• 배치 사이즈: 256
• weight decay: 0.0001, momentum: 0.9
• 학습율: 0.1로 시작해서 validation error가 줄지 않으면 x10씩 줄여나감.
• $60\times 10^4$ iteration까지 진행되었음

ResNet 구현을 위해 가장 먼저 핵심이 되는 Identity 방식의 Basic building block을 만들어준다. 

import torch
from torch import Tensor
import torch.nn as nn


class BasicBlock(nn.Module):
    expansion_factor = 1
    def __init__(self, in_channels: int, out_channels: int, stride: int = 1):
        super(BasicBlock, self).__init__()
        self.conv1 = nn.Conv2d(in_channels, out_channels, kernel_size=3, stride=stride, padding=1, bias=False)
        self.bn1 = nn.BatchNorm2d(out_channels)
        self.relu1 = nn.ReLU()

        self.conv2 = nn.Conv2d(out_channels, out_channels, kernel_size=3, stride=1, padding=1, bias=False)
        self.bn2 = nn.BatchNorm2d(out_channels)

        self.relu2 = nn.ReLU()
        self.residual = nn.Sequential()
        if stride != 1 or in_channels != out_channels * self.expansion_factor:
            self.residual = nn.Sequential(
                nn.Conv2d(in_channels, out_channels*self.expansion_factor, kernel_size=1, stride=stride, bias=False),
                nn.BatchNorm2d(out_channels*self.expansion_factor))
                
    def forward(self, x: Tensor) -> Tensor:
        out = x
        x = self.conv1(x)
        x = self.bn1(x)
        x = self.relu1(x)

        x = self.conv2(x)
        x = self.bn2(x)
        x += self.residual(out)
        x = self.relu2(x)
        return x

다음으로 또 다른 구조인 Projection 방식의 Bottleneck building block을 만들어 준다.

class BottleNeck(nn.Module):
    expansion_factor = 4
    def __init__(self, in_channels: int, out_channels: int, stride: int = 1):
        super(BottleNeck, self).__init__()

        self.conv1 = nn.Conv2d(in_channels, out_channels, kernel_size=1, stride=1, bias=False)
        self.bn1 = nn.BatchNorm2d(out_channels)
        self.relu1 = nn.ReLU()
        
        self.conv2 = nn.Conv2d(out_channels, out_channels, kernel_size=3, stride=stride, padding=1, bias=False)
        self.bn2 = nn.BatchNorm2d(out_channels)
        self.relu2 = nn.ReLU()
        
        self.conv3 = nn.Conv2d(out_channels, out_channels * self.expansion_factor, kernel_size=1, stride=1, bias=False)
        self.bn3 = nn.BatchNorm2d(out_channels*self.expansion_factor)
        
        self.relu3 = nn.ReLU()
        self.residual = nn.Sequential()
        if stride != 1 or in_channels != out_channels * self.expansion_factor:
            self.residual = nn.Sequential(
                nn.Conv2d(in_channels, out_channels*self.expansion_factor, kernel_size=1, stride=stride, bias=False),
                nn.BatchNorm2d(out_channels*self.expansion_factor))
        
    def forward(self, x:Tensor) -> Tensor:
        out = x
        x = self.conv1(x)
        x = self.bn1(x)
        x = self.relu1(x)

        x = self.conv2(x)
        x = self.bn2(x)
        x = self.relu2(x)
        
        x = self.conv3(x)
        x = self.bn3(x)
        
        x += self.residual(out)
        x = self.relu3(x)
        return x

위 두 구조에 따라 ResNet을 구성할 수 있도록 모델을 구성해준다.

class ResNet(nn.Module):
    def __init__(self, block, num_blocks, num_classes=10):
        super(ResNet, self).__init__()
        self.in_channels = 64
        self.conv1 = nn.Sequential(
            nn.Conv2d(in_channels=3, out_channels=64, kernel_size=7, stride=2, padding=3, bias=False),
            nn.BatchNorm2d(num_features=64),
            nn.ReLU(),
            nn.MaxPool2d(kernel_size=3, stride=2, padding=1))

        self.conv2 = self._make_layer(block, 64, num_blocks[0], stride=1)
        self.conv3 = self._make_layer(block, 128, num_blocks[1], stride=2)
        self.conv4 = self._make_layer(block, 256, num_blocks[2], stride=2)
        self.conv5 = self._make_layer(block, 512, num_blocks[3], stride=2)
        self.avgpool = nn.AdaptiveAvgPool2d(output_size=(1, 1))
        self.fc = nn.Linear(512 * block.expansion_factor, num_classes)

        self._init_layer()

    def _make_layer(self, block, out_channels, num_blocks, stride):
        strides = [stride] + [1] * (num_blocks-1)
        layers = []
        for stride in strides:
            layers.append(block(self.in_channels, out_channels, stride))
            self.in_channels = out_channels * block.expansion_factor
        return nn.Sequential(*layers)

    def _init_layer(self):
        for m in self.modules():
            if isinstance(m, nn.Conv2d):
                nn.init.kaiming_normal_(m.weight, mode='fan_out', nonlinearity='relu')
            elif isinstance(m, (nn.BatchNorm2d, nn.GroupNorm)):
                nn.init.constant_(m.weight, 1)
                nn.init.constant_(m.bias, 0)

    def forward(self, x: Tensor) -> Tensor:
        x = self.conv1(x)
        x = self.conv2(x)
        x = self.conv3(x)
        x = self.conv4(x)
        x = self.conv5(x)
        
        x = self.avgpool(x)
        x = torch.flatten(x, 1)
        x = self.fc(x)
        return x

ResNet 아키텍처에 표시된 레이어의 개수를 맞춰준 모델을 반환하는 클래스를 정의한다. 

class Model:
    def resnet18(self):
        return ResNet(BasicBlock, [2, 2, 2, 2])

    def resnet34(self):
        return ResNet(BasicBlock, [3, 4, 6, 3])

    def resnet50(self):
        return ResNet(BottleNeck, [3, 4, 6, 3])

    def resnet101(self):
        return ResNet(BottleNeck, [3, 4, 23, 3])

    def resnet152(self):
        return ResNet(BottleNeck, [3, 8, 36, 3])

마지막으로 간단한 테스트를 위해 모델을 불러오고 랜덤 생성한 데이터를 넣어주고 결과를 확인한다.

model = Model().resnet152()
y = model(torch.randn(1, 3, 224, 224))
print (y.size()) # torch.Size([1, 10])

데이터셋으로 직접 학습 시켜보고자 한다면 train 코드는 아래 링크에 함께 구비해두었다.

전체 코드: https://github.com/roytravel/paper-implementation/tree/master/resnet

Reference

[1] https://github.com/weiaicunzai/pytorch-cifar100/blob/master/models/resnet.py

[2] https://github.com/kuangliu/pytorch-cifar/blob/master/models/resnet.py

[3] https://github.com/pytorch/vision/blob/main/torchvision/models/resnet.py

논문: Going Deeper with convolutions
게재: 2015년
학회: CVPR

GoogLeNet이란?

GoogLeNet은 한 마디로 네트워크의 depth와 width를 늘리면서도 내부적으로 inception 모듈을 활용해 computational efficiency를 확보한 모델이다. 이전에 나온 VGGNet이 깊은 네트워크로 AlexNet보다 높은 성능을 얻었지만, 반면 파라미터 측면에서 효율적이지 못하다는점을 보완하기 위해 만들어졌다.

CNN 아키텍처와 GoogLeNet

2010년 초/중반 CNN 아키텍처를 활용해 높은 이미지 인식 능력을 선보인 모델은 AlexNet (2012) → VGGNet (2014) → GoogLeNet (2014) → ResNet (2015) → ... 순으로 계보가 이어진다. 이 모델들은 네트워크의 depth와 width를 늘리면서 성능 향상이 이루어지는 것을 보며 점점 depth와 width를 늘려갔다. 하지만 이렇게 네트워크가 커지면서 두 가지 문제점이 발생했다. 첫 번째는 많은 파라미터가 있지만 이를 학습시킬 충분한 데이터가 없다면 오버피팅이 발생하는 것이고, 두 번째는 computational resource는 늘 제한적이기에 비용이 많이 발생하거나 낭비될 수 있다는 점이다. GoogLeNet은 이러한 문제점을 해결하기 위해 fully-connected layer의 neuron 수를 줄이거나 convolution layer의 내부 또한 줄여 상대적으로 sparse한 network를 만들고자 만들어졌다. 결과적으로 GoogLeNet은 가장 초반에 나온 AlexNet보다도 파라미터수가 12배 더 적지만 더 높은 성능을 보이는 것이 특징이다. 결과적으로 GoogLeNet은 ILSVRC 2014에서 classification과 detection 트랙에서 SOTA를 달성했다.

Inception: GoogLeNet 성능의 핵심

파라미터 효율적이면서도 높은 성능을 낼 수 있는 GoogLeNet 아키텍처의 핵심은 내부 Inception 모듈의 영향이다. Inception 모듈을 보기전 먼저 GoogLeNet 아키텍처를 살펴보면 다음과 같다.

왼쪽(아래)에서 출발하여 오른쪽(위)으로 점점 깊어진다. Inception 모듈은 위 GoogLeNet 네트워크에서 사용되는 부분 네트워크에 해당한다. 그 부분 구조는 아래와 같다. 두 가지 버전이 있다.

두 버전 모두 이미지 feature를 효율적으로 추출하기 위해 공통적으로 1x1, 3x3, 5x5 필터 크기를 갖는 convolution 연산을 수행한다. 이렇게 이미지의 다양한 영역을 볼 수 있도록 서로 다른 크기의 필터를 사용함으로써 앙상블하는 효과를 가져와 모델의 성능이 높아지게 된다. 참고로 필터 크기를 1x1, 3x3, 5x5로 지정한 것은 필요성에 의한 것이기보다 편의성을 기반으로 했다. 만약 짝수 크기의 필터 크기를 갖게 된다면 patch-alignment 문제라고하여 필터 사이즈가 짝수일 때 patch(필터)의 중간을 어디로 두어야 할지 결정해야하기에 번거로워지기 때문이다.

두 버전의 Inception 모듈을 비교해보자면, 먼저 좌측 naive Inception 모듈의 경우 1x1, 3x3, 5x5 convolution 연산과 3x3 max pooling 연산을 병렬 수행한 뒤 concatenation을 통해 결과를 합쳐주는 구조로 되어 있다. 하지만 결과적으로 이는 잘 동작하지 않았다. 그 이유는 convolution 결과와 max pooling 결과를 concatenation하면 기존 보다 차원이 늘어나는 문제점이 발생했기 때문이다. 정확히는 max pooling 연산의 경우 channel 수가 그대로 보존되지만 convolution 연산에 의해 더해진 channel로 인해 computation 부하가 늘어나게 된다. 이 과정을 도식화 한 것은 아래 그림과 같다. (출처: 정의석님 블로그)

위 그림과 같이 output channel의 크기가 증가하여 computation 부하가 커지는 문제점을 해결하기 위해 우측 두 번째 Inception 모듈이 사용된다. 두 번째 Inception 모듈을 통해 output channel을 줄이는 즉 차원을 축소하는 효과를 가져온다. 실제로도 이러한 효과로 인한 computation efficiency 때문에 GoogLeNet 아키텍처에서도 첫 번째 naive Inception 모듈이 아닌 두 번째 dimension reduction Inception 모듈을 사용한다.

그렇다면 두 번째 Inception module에서의 차원축소는 어떻게 이루어질까? 이에 대한 핵심은 1x1 convolution 연산에 있다. 1x1 convolution 연산은 Network in Network (Lin et al) 라는 연구에서 도입된 방법이다. 이름 그대로 1x1 필터를 가지는 convolution 연산을 하는 것이다. 1x1 convolution 연산은 아래 GIF와 같이 동작한다. 그 결과 feature map 크기가 동일하게 유지된다. 하지만 중요한 것은 1x1 filter 개수를 몇 개로 해주느냐에 따라 feature map의 차원의 크기(채널)를 조절할 수 있게 되는 것이다. 따라서 만약 input dimension 보다 1x1 filter 개수를 작게 해준다면 차원축소가 일어나게 되며, 그 결과 핵심적인 정보만 추출할 수 있게 된다.

Global Average Pooling (GAP)

GoogLeNet 아키텍처에선 Global Average Pooling 개념을 도입하여 사용한다. 이는 마찬가지로 Network in Network (Lin et al) 에서 제안된 것으로, 기존 CNN + fully connected layer 구조에서 fully-connected layer를 대체하기 위한 목적이다. 그 이유는 convolution 연산의 결과로 만들어진 feature map을 fully-connected layer에 넣고 최종적으로 분류하는 과정에서 공간 정보가 손실되기 때문이다. 반면 GAP은 feature map의 값의 평균을 구해 직접 softmax 레이어에 입력하는 방식이다. 이렇게 직접 입력하게 되면 공간 정보가 손실되지 않을 뿐만 아니라 fully-connected layer에 의해 파라미터를 최적화 하는 과정이 없기 때문에 효율적이게 된다.

Auxiliary classification

먼저 Auxiliary란 보조를 뜻하는 것으로 Auxiliary classification은 최종 classification 결과를 보조하기 위해 네트워크 중간 중간에 보조적인(Auxiliary) classifier를 두어 중간 결과 값을 추출하는 것이다. 아래 그림은 GoogLeNet 아키텍처를 부분 확대한 것이다. Auxiliary Classification 과정은 이 중 노란 박스 열에 해당한다.

이렇게 Auxiliary classifier를 중간 중간에 두는 이유는 네트워크가 깊어지면서 발생하는 gradient vanishing 문제를 해결하기 위함이다. 즉 네트워크가 깊어지면 loss에 대한 back-propagation이 영향력이 줄어드는 문제를 해결하기 위해 도입된 것이다. 이렇게 함으로써 중간에 있는 Inception layer들도 적절한 가중치 업데이트를 받을 수 있게 된다. 하지만 Inception 모듈 버전이 늘어날수록 Auxiliary classifier를 점점 줄였고 inception v4에서는 완전히 제외했다. 그 이유는 중간 중간에 있는 layer들은 back-propagation을 통해 학습이 적절히 이루어 졌지만 최종 classification layer에서는 학습이 잘 이루어지지 못해 최적의 feature가 뽑히지 않았기 때문이다.

파이토치로 GoogLeNet 구현하기

GoogLeNet 모델의 핵심은 Inception 모듈을 구현하는 것이다.
1. Inception 모듈 구현에 앞서 Inception 모듈에서 반복적으로 사용될 convolution layer를 생성하기 위해 ConvBlock이란 클래스로 다음과 같이 구현해준다. convolution layer 뒤에 batch normalization layer와 relu가 뒤따르는 구조이다.

import torch
import torch.nn as nn
from torch import Tensor

class ConvBlock(nn.Module):
    def __init__(self, in_channels, out_channels, **kwargs) -> None:
        super(ConvBlock, self).__init__()
        self.conv = nn.Conv2d(in_channels, out_channels, **kwargs)
        self.batchnorm = nn.BatchNorm2d(out_channels)
        self.relu = nn.ReLU()

    def forward(self, x: Tensor) -> Tensor:
        x = self.conv(x)
        x = self.batchnorm(x)
        x = self.relu(x)
        return x

2. ConvBlock 클래스를 활용하여 Inception module을 구현하기 위한 Inception 클래스를 다음과 같이 구현해준다.

import torch
import torch.nn as nn
from torch import Tensor

class Inception(nn.Module):
    def __init__(self, in_channels, n1x1, n3x3_reduce, n3x3, n5x5_reduce, n5x5, pool_proj) -> None:
        super(Inception, self).__init__()
        self.branch1 = ConvBlock(in_channels, n1x1, kernel_size=1, stride=1, padding=0)

        self.branch2 = nn.Sequential(
            ConvBlock(in_channels, n3x3_reduce, kernel_size=1, stride=1, padding=0),
            ConvBlock(n3x3_reduce, n3x3, kernel_size=3, stride=1, padding=1))
        
        self.branch3 = nn.Sequential(
            ConvBlock(in_channels, n5x5_reduce, kernel_size=1, stride=1, padding=0),
            ConvBlock(n5x5_reduce, n5x5, kernel_size=5, stride=1, padding=2))

        self.branch4 = nn.Sequential(
            nn.MaxPool2d(kernel_size=3, stride=1, padding=1),
            ConvBlock(in_channels, pool_proj, kernel_size=1, stride=1, padding=0))
        
    def forward(self, x: Tensor) -> Tensor:
        x1 = self.branch1(x)
        x2 = self.branch2(x)
        x3 = self.branch3(x)
        x4 = self.branch4(x)
        return torch.cat([x1, x2, x3, x4], dim=1)

Inception 클래스를 확인하면 내부적으로 4개의 branch 변수를 만든다. 이 4개의 branch라는 변수는 각각 아래 Inception module에서 네 갈래로 분기되는 것을 구현해준 것이다.

Inception 모듈에 들어갈 인자는 다음과 같다.
1x1 convolution의 경우 kernel_size=1, stride= 1, padding=0
3x3 convolution의 경우 kernel_size=3, stride= 1, padding=1
5x5 convolution의 경우 kernel_size=5, stride= 1, pading=2
max-pooling의 경우 kernel_size=3, stride=1, padding=1

kernel_size는 아키텍처에 보이는 그대로와 같고, GoogLeNet에서는 stride를 공통적으로 1로 사용했다. 각각의 padding은 추후 네 개의 branch가 합쳐졌을 때의 크기를 고려하여 맞춰준다.

3. Auxiliary Classifier를 구현하기 위해 아래와 같이 InceptionAux라는 클래스로 구현해주었다. 1x1 convolution의 output channel의 개수는 논문에 기술된 대로 128을 적용해주었으며 dropout rate 또한 논문에 기술된 대로 0.7을 적용해주었다.

import torch
import torch.nn as nn
from torch import Tensor

class InceptionAux(nn.Module):
    def __init__(self, in_channels, num_classes) -> None:
        super(InceptionAux, self).__init__()
        self.avgpool = nn.AvgPool2d(kernel_size=5, stride=3)
        self.conv = ConvBlock(in_channels, 128, kernel_size=1, stride=1, padding=0)
        self.fc1 = nn.Linear(2048, 1024)
        self.fc2 = nn.Linear(1024, num_classes)
        self.dropout = nn.Dropout(p=0.7)
        self.relu = nn.ReLU()

    def forward(self, x: Tensor) -> Tensor:
        x = self.avgpool(x)
        x = self.conv(x)
        x = x.view(x.size()[0], -1)
        x = self.fc1(x)
        x = self.relu(x)
        x = self.dropout(x)
        x = self.fc2(x)
        return x

InceptionAux 클래스는 아래와 그림과 같이 Auxiliary Classification 과정을 구현해 준 것이다.

4. ConvBlock, Inception, InceptionAux를 활용하여 GoogLeNet을 다음과 같이 구현할 수 있다.

import torch
import torch.nn as nn
from torch import Tensor

class GoogLeNet(nn.Module):
    def __init__(self, aux_logits=True, num_classes=1000) -> None:
        super(GoogLeNet, self).__init__()
        assert aux_logits == True or aux_logits == False
        self.aux_logits = aux_logits

        self.conv1 = ConvBlock(in_channels=3, out_channels=64, kernel_size=7, stride=2, padding=3)
        self.maxpool1 = nn.MaxPool2d(kernel_size=3, stride=2, padding=1, ceil_mode=True)
        self.conv2 = ConvBlock(in_channels=64, out_channels=64, kernel_size=1, stride=1, padding=0)
        self.conv3 = ConvBlock(in_channels=64, out_channels=192, kernel_size=3, stride=1, padding=1)
        self.maxpool2 = nn.MaxPool2d(kernel_size=3, stride=2, ceil_mode=True)

        self.a3 = Inception(192, 64, 96, 128, 16, 32, 32)
        self.b3 = Inception(256, 128, 128, 192, 32, 96, 64)
        self.maxpool3 = nn.MaxPool2d(kernel_size=3, stride=2, padding=1, ceil_mode=True)
        self.a4 = Inception(480, 192, 96, 208, 16, 48, 64)
        self.b4 = Inception(512, 160, 112, 224, 24, 64, 64)
        self.c4 = Inception(512, 128, 128, 256, 24, 64, 64)
        self.d4 = Inception(512, 112, 144, 288, 32, 64, 64)
        self.e4 = Inception(528, 256, 160, 320, 32, 128, 128)
        self.maxpool4 = nn.MaxPool2d(kernel_size=3, stride=2, padding=1)
        self.a5 = Inception(832, 256, 160, 320, 32, 128, 128)
        self.b5 = Inception(832, 384, 192, 384, 48, 128, 128)
        self.avgpool = nn.AvgPool2d(kernel_size=8, stride=1)
        self.dropout = nn.Dropout(p=0.4)
        self.linear = nn.Linear(1024, num_classes)

        if self.aux_logits:
            self.aux1 = InceptionAux(512, num_classes)
            self.aux2 = InceptionAux(528, num_classes)
        else:
            self.aux1 = None
            self.aux2 = None

    def transform_input(self, x: Tensor) -> Tensor:
        x_R = torch.unsqueeze(x[:, 0], 1) * (0.229 / 0.5) + (0.485 - 0.5) / 0.5
        x_G = torch.unsqueeze(x[:, 1], 1) * (0.224 / 0.5) + (0.456 - 0.5) / 0.5
        x_B = torch.unsqueeze(x[:, 2], 1) * (0.225 / 0.5) + (0.406 - 0.5) / 0.5
        x = torch.cat([x_R, x_G, x_B], 1)
        return x
        
    def forward(self, x: Tensor) -> Tensor:
        x = self.transform_input(x)

        x = self.conv1(x)
        x = self.maxpool1(x)
        x = self.conv2(x)
        x = self.conv3(x)
        x = self.maxpool2(x)
        x = self.a3(x)
        x = self.b3(x)
        x = self.maxpool3(x)
        x = self.a4(x)
        aux1: Optional[Tensor] = None
        if self.aux_logits and self.training:
            aux1 = self.aux1(x)

        x = self.b4(x)
        x = self.c4(x)
        x = self.d4(x)
        aux2: Optional[Tensor] = None
        if self.aux_logits and self.training:
            aux2 = self.aux2(x)

        x = self.e4(x)
        x = self.maxpool4(x)
        x = self.a5(x)
        x = self.b5(x)
        x = self.avgpool(x)
        x = x.view(x.shape[0], -1) # x = x.reshape(x.shape[0], -1)
        x = self.linear(x)
        x = self.dropout(x)

        if self.aux_logits and self.training:
            return aux1, aux2
        else:
            return x

Inception 모듈에 들어갈 모델 구성은 Table 1의 GoogLeNet 아키텍처를 참고하였다.

전체 코드는 다음과 같이 구현할 수 있다.

import torch
import torch.nn as nn
from torch import Tensor
from typing import Optional

class Inception(nn.Module):
    def __init__(self, in_channels, n1x1, n3x3_reduce, n3x3, n5x5_reduce, n5x5, pool_proj) -> None:
        super(Inception, self).__init__()
        self.branch1 = ConvBlock(in_channels, n1x1, kernel_size=1, stride=1, padding=0)

        self.branch2 = nn.Sequential(
            ConvBlock(in_channels, n3x3_reduce, kernel_size=1, stride=1, padding=0),
            ConvBlock(n3x3_reduce, n3x3, kernel_size=3, stride=1, padding=1))
        
        self.branch3 = nn.Sequential(
            ConvBlock(in_channels, n5x5_reduce, kernel_size=1, stride=1, padding=0),
            ConvBlock(n5x5_reduce, n5x5, kernel_size=5, stride=1, padding=2))

        self.branch4 = nn.Sequential(
            nn.MaxPool2d(kernel_size=3, stride=1, padding=1),
            ConvBlock(in_channels, pool_proj, kernel_size=1, stride=1, padding=0))
        
    def forward(self, x: Tensor) -> Tensor:
        x1 = self.branch1(x)
        x2 = self.branch2(x)
        x3 = self.branch3(x)
        x4 = self.branch4(x)
        return torch.cat([x1, x2, x3, x4], dim=1)


class GoogLeNet(nn.Module):
    def __init__(self, aux_logits=True, num_classes=1000) -> None:
        super(GoogLeNet, self).__init__()
        assert aux_logits == True or aux_logits == False
        self.aux_logits = aux_logits

        self.conv1 = ConvBlock(in_channels=3, out_channels=64, kernel_size=7, stride=2, padding=3)
        self.maxpool1 = nn.MaxPool2d(kernel_size=3, stride=2, padding=1, ceil_mode=True)
        self.conv2 = ConvBlock(in_channels=64, out_channels=64, kernel_size=1, stride=1, padding=0)
        self.conv3 = ConvBlock(in_channels=64, out_channels=192, kernel_size=3, stride=1, padding=1)
        self.maxpool2 = nn.MaxPool2d(kernel_size=3, stride=2, ceil_mode=True)

        self.a3 = Inception(192, 64, 96, 128, 16, 32, 32)
        self.b3 = Inception(256, 128, 128, 192, 32, 96, 64)
        self.maxpool3 = nn.MaxPool2d(kernel_size=3, stride=2, padding=1, ceil_mode=True)
        self.a4 = Inception(480, 192, 96, 208, 16, 48, 64)
        self.b4 = Inception(512, 160, 112, 224, 24, 64, 64)
        self.c4 = Inception(512, 128, 128, 256, 24, 64, 64)
        self.d4 = Inception(512, 112, 144, 288, 32, 64, 64)
        self.e4 = Inception(528, 256, 160, 320, 32, 128, 128)
        self.maxpool4 = nn.MaxPool2d(kernel_size=3, stride=2, padding=1)
        self.a5 = Inception(832, 256, 160, 320, 32, 128, 128)
        self.b5 = Inception(832, 384, 192, 384, 48, 128, 128)
        self.avgpool = nn.AdaptiveAvgPool2d((1, 1))
        self.dropout = nn.Dropout(p=0.4)
        self.linear = nn.Linear(1024, num_classes)

        if self.aux_logits:
            self.aux1 = InceptionAux(512, num_classes)
            self.aux2 = InceptionAux(528, num_classes)
        else:
            self.aux1 = None
            self.aux2 = None

    def transform_input(self, x: Tensor) -> Tensor:
        x_R = torch.unsqueeze(x[:, 0], 1) * (0.229 / 0.5) + (0.485 - 0.5) / 0.5
        x_G = torch.unsqueeze(x[:, 1], 1) * (0.224 / 0.5) + (0.456 - 0.5) / 0.5
        x_B = torch.unsqueeze(x[:, 2], 1) * (0.225 / 0.5) + (0.406 - 0.5) / 0.5
        x = torch.cat([x_R, x_G, x_B], 1)
        return x
        
    def forward(self, x: Tensor) -> Tensor:
        x = self.transform_input(x)

        x = self.conv1(x)
        x = self.maxpool1(x)
        x = self.conv2(x)
        x = self.conv3(x)
        x = self.maxpool2(x)
        x = self.a3(x)
        x = self.b3(x)
        x = self.maxpool3(x)
        x = self.a4(x)
        aux1: Optional[Tensor] = None
        if self.aux_logits and self.training:
            aux1 = self.aux1(x)

        x = self.b4(x)
        x = self.c4(x)
        x = self.d4(x)
        aux2: Optional[Tensor] = None
        if self.aux_logits and self.training:
            aux2 = self.aux2(x)

        x = self.e4(x)
        x = self.maxpool4(x)
        x = self.a5(x)
        x = self.b5(x)
        x = self.avgpool(x)
        x = x.view(x.shape[0], -1) # x = x.reshape(x.shape[0], -1)
        x = self.linear(x)
        x = self.dropout(x)

        if self.aux_logits and self.training:
            return aux1, aux2
        else:
            return x


class ConvBlock(nn.Module):
    def __init__(self, in_channels, out_channels, **kwargs) -> None:
        super(ConvBlock, self).__init__()
        self.conv = nn.Conv2d(in_channels, out_channels, **kwargs)
        self.batchnorm = nn.BatchNorm2d(out_channels)
        self.relu = nn.ReLU()

    def forward(self, x: Tensor) -> Tensor:
        x = self.conv(x)
        x = self.batchnorm(x)
        x = self.relu(x)
        return x


class InceptionAux(nn.Module):
    def __init__(self, in_channels, num_classes) -> None:
        super(InceptionAux, self).__init__()
        self.avgpool = nn.AvgPool2d(kernel_size=5, stride=3)
        self.conv = ConvBlock(in_channels, 128, kernel_size=1, stride=1, padding=0)
        self.fc1 = nn.Linear(2048, 1024)
        self.fc2 = nn.Linear(1024, num_classes)
        self.dropout = nn.Dropout(p=0.7)
        self.relu = nn.ReLU()

    def forward(self, x: Tensor) -> Tensor:
        x = self.avgpool(x)
        x = self.conv(x)
        x = x.view(x.shape[0], -1)
        x = self.fc1(x)
        x = self.relu(x)
        x = self.dropout(x)
        x = self.fc2(x)
        return x
        
if __name__ == "__main__":
    x = torch.randn(3, 3, 224, 224)
    model = GoogLeNet(aux_logits=True, num_classes=1000)
    print (model(x)[1].shape)

위 코드에서 Auxiliary Classifier의 입력 차원 같은 경우는 논문에서 기술된 대로 512, 528을 적용해주었고, fully-connected layer 또한 1024개의 unit으로 설정해주었다.

만약 GoogLeNet으로 간단한 학습을 진행해보고자 할 때 다음과 같이 코드 구현이 가능하다. 다만 CIFAR10 데이터셋을 예시로 사용하므로 위 코드에서 num_classes=10로 바꿔줘야 한다.

import os
import numpy as np 
import torch
import torchvision.datasets as datasets
import torchvision.transforms as transforms
from torch.utils.data import DataLoader
import matplotlib.pyplot as plt
import argparse
from googlenet import GoogLeNet

def load_dataset():
    # preprocess
    transform = transforms.Compose([    
    transforms.ToTensor(),
    transforms.Normalize((0.5, 0.5, 0.5), (0.5, 0.5, 0.5))])

    # load train, test data
    train = datasets.CIFAR10(root="../data", train=True, transform=transform, download=True)
    test = datasets.CIFAR10(root="../data", train=False, transform=transform, download=True)
    train_loader = DataLoader(train, batch_size=args.batch_size, shuffle=True)
    test_loader = DataLoader(test, batch_size=args.batch_size, shuffle=False)
    return train_loader, test_loader


if __name__ == "__main__":
    # set hyperparameter
    parser = argparse.ArgumentParser()
    parser.add_argument('--batch_size', action='store', type=int, default=100)
    parser.add_argument('--learning_rate', action='store', type=float, default='0.0002')
    parser.add_argument('--n_epochs', action='store', type=int, default=100)
    parser.add_argument('--plot', action='store', type=bool, default=True)
    args = parser.parse_args()
    
    np.random.seed(1)
    seed = torch.manual_seed(1)

    # load dataset
    train_loader, test_loader = load_dataset()

    # model, loss, optimizer
    losses = []
    device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
    model = GoogLeNet(aux_logits=False, num_classes=10).to(device)
    criterion = torch.nn.CrossEntropyLoss()
    optimizer = torch.optim.Adam(model.parameters(), lr=args.learning_rate)

    # train
    for epoch in range(args.n_epochs):
        model.train()
        train_loss = 0
        correct, count = 0, 0
        for batch_idx, (images, labels) in enumerate(train_loader, start=1):
            images, labels = images.to(device), labels.to(device)
            optimizer.zero_grad()
            output = model.forward(images)
            loss = criterion(output, labels)
            loss.backward()
            optimizer.step()

            train_loss += loss.item()
            _, preds = torch.max(output, 1)
            count += labels.size(0)
            correct += preds.eq(labels).sum().item() # torch.sum(preds == labels)

            if batch_idx % 100 == 0:
                print (f"[*] Epoch: {epoch} \tStep: {batch_idx}/{len(train_loader)}\tTrain accuracy: {round((correct/count), 4)} \tTrain Loss: {round((train_loss/count)*100, 4)}")
        
        # valid
        model.eval()
        correct, count = 0, 0
        valid_loss = 0
        with torch.no_grad():
            for batch_idx, (images, labels) in enumerate(test_loader, start=1):
                images, labels = images.to(device), labels.to(device)
                output = model.forward(images)
                loss = criterion(output, labels)
                valid_loss += loss.item()
                _, preds = torch.max(output, 1)
                count += labels.size(0)
                correct += preds.eq(labels).sum().item() # torch.sum(preds == labels)
                if batch_idx % 100 == 0:
                    print (f"[*] Step: {batch_idx}/{len(test_loader)}\tValid accuracy: {round((correct/count), 4)} \tValid Loss: {round((valid_loss/count)*100, 4)}")

        # if epoch % 10 == 0:
        #     if not os.path.isdir('../checkpoint'):
        #         os.makedirs('../checkpoint', exists_ok=True)
        #     checkpoint_path = os.path.join(f"../checkpoint/googLeNet{epoch}.pth")
        #     state = {
        #         'epoch': epoch,
        #         'model': model.state_dict(),
        #         'optimizer': optimizer.state_dict(),
        #         'seed': seed,
        #     }
        #     torch.save(state, checkpoint_path)

전체 코드: https://github.com/roytravel/paper-implementation

Reference
[1] https://velog.io/@euisuk-chung/파이토치-파이토치로-CNN-모델을-구현해보자-GoogleNet편
[2] https://wikidocs.net/137251
[3] https://github.com/aladdinpersson/Machine-Learning-Collection/blob/master/ML/Pytorch/CNN_architectures/pytorch_inceptionet.py
[4] https://github.com/Lornatang/GoogLeNet-PyTorch/blob/main/model.py
[5] https://github.com/weiaicunzai/pytorch-cifar100/blob/master/models/googlenet.py
[6] https://github.com/soapisnotfat/pytorch-cifar10/blob/master/models/GoogleNet.py
[7] https://github.com/Mayurji/Image-Classification-PyTorch/blob/main/GoogLeNet.py
[8] https://github.com/cxy1997/MNIST-baselines/blob/master/models/googlenet.py