인공지능을 위한 기초수학, 알고리즘 개요 및 Keyword 정리

 

대학원 입시 준비를 하면서 그동안 배운 수학, 알고리즘, 자료구조 등의 내용을 정리해두려 한다. 단순히 대학원 입시 준비 뿐만 아니라 앞으로 석사과정 진학 후에도 유용하게 사용할 수 있도록 정리해둘 것이다.

 

가장 먼저 이 포스팅에서는 얼마 남지 않은 기간동안 어떻게 진행할지 계획을 세워보고, 공부 개요를 짜보려 한다.

양이 매우 많고 범위가 넓으므로 keyword를 정리한 후, 이를 기준으로 개념을 정리할 것이다.

 

 

 

 

 

1. 계획 및 자료

 

개괄적인 공부 계획은 다음과 같다.

1. 포항공대 모집요강에서 제시한 수학과 알고리즘 교재를 기준으로 전체적인 내용 정리
2. Keyword 기준으로 학부 수업에서 정리한 노트에서 발췌하거나 검색하여 따로 정리 및 요약

 

수학 교재는 'Mathematics for Machine learning(http://mml-book.github.io), Marc Peter Deisenroth, A.Aldo Faisal, Cheng Soon Ong'이며, 다음 링크에 공개되어있다.

 

https://mml-book.github.io/

Mathematics for Machine Learning

 

이중 'Part 1'만 POSTECH 인공지능학과 지필시험 범위에 해당한다.

 

Part 1의 목차는 다음과 같다.

 

1. Part 1 - Mathematical Foundations
   1. Introduction and Motivation
      1. Finding Words for Intuitions
      2. Two Ways to Read This Book
      3. Exercises and Feedback
   2. Linear Algebra
      1. Systems of Linear Equations
      2. Matrices
      3. Solving Systems of Linear Equations
      4. Vector Spaces
      5. Linear Independence
      6. Basis and Rank
      7. Linear Mappings
      8. Affine Spaces
      9. Further Reading
   3. Analytic Geometry
      1. Norms
      2. Inner Products
      3. Lengths and Distances
      4. Angles and Orthogonality
      5. Orthonormal Basis
      6. Orthogonal Complement
      7. Inner Product of Fuctions
      8. Orthogonal Projections
      9. Rotations
      10. Further Reading
   4. Matrix Decompositions
      1. Determinant and Trace
      2. Eigenvalues and Eigenvectors
      3. Cholesky Decomposition
      4. Eigendecomposition and Diagonalization
      5. Singular Value Decomposition
      6. Matrix Approximation
      7. Matrix Phylogeny
      8. Further Reading
   5. Vector Calculus
      1. Differentiation of Univariate Functions
      2. Partial Differentiation and Gradients
      3. Gradients of Vector-Valued Functions
      4. Gradients of Matrices
      5. Useful Identities for Computing Gradients
      6. Backpropagation and Automatic Differentiation
      7. Higher-Order Derivatives
      8. Linearization and Multivariate Taylor Series
      9. Further Reading
   6. Probability and Distributions
      1. Construction of a Probability Space
      2. Discrete and Continuous Probabilities
      3. Sum Rule, Product Rule, and Baye's Theorem
      4. Summary Statistics and Independence
      5. Gaussian Distribution
      6. Conjugacy and the Exponential Family
      7. Change of Variables/Inverse Transform
      8. Further Reading
   7. Continuous Optimization
      1. Optimization Using Gradient Descent
      2. Constrained Optimization and Lagrange Multipliers
      3. Convex Optimization
      4. Further Reading

 

 

알고리즘 교재는 '“Algorithms,” Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw-Hill, 2008.'이며, 수학 교재와 달리 공개되어있지 않고, 원서를 구매해야 한다.

시험 범위에는 Chatper 2, 3, 4, 5, 6이 포함되고, 목차는 아래와 같다. (프롤로그 등 1번에 내용을 추가했다. 2번부터 책의 chapter이다.)

 

1.  Prologue
   1. Big-O notation
2. Divide-and-conquer algorithms
   1. Multiplication
   2. Recurrence relations
   3. Mergesort
   4. Medians
   5. Matrix Multiplication
   6. The fast Fourier transform
3. Decompositions of graphs
   1. Why graphs?
   2. Depth-first search in undirected graphs
   3. Depth-first search in directed graphs
   4. Strongly connected components
4. Paths in graphs
   1. Distances
   2. Breadth-first search
   3. Lengths on edges
   4. Dijkstra's algorithm
   5. Priority queue implementations
   6. Shortest paths in the presence of negative edges
   7. Shortest paths in dags
5. Greedy algorithms
   1. Minimum spanning trees
   2. Huffman encoding
   3. Horn formulas
   4. Set cover
6. Dynamic Programming
   1. Shortest paths in dags, revisited
   2. Longest increasing subsequences
   3. Edit distance
   4. Knapsack
   5. Chain matrix multiplication
   6. Shortest paths
   7. Independent sets in trees

 

 

 

 

 

2. Keywords

 

두 교재 뿐만 아니라 학부 과정에서 배운 (특히 자소서, 연구계획서에 썼던) 모든 내용을 세세하게 공부할 시간은 없으니, 머신러닝과 딥러닝에서 특히 중요한 내용을 keywords로 정리해 보았다. (미분, 적분 등과 같이 너무 기초적이고 포괄적인 키워드는 제외했다.)

 

놓치는 내용이 있다면 계속 추가할 예정이다. (써놓은 순서는 무작위이다. 생각나는대로, 공부하다가 발견한대로 작성한 것이다.)

 

• eigen value
• eigen vector
• adjacent matrix
• rank, basis, span
• singular value decomposition
• convex optimization
• chain rule
• gaussian distribution
• \(\beta\) distribution
• likelihood
• prior, posterior
• 베이즈 정리
• 중심극한정리
• 평균 시간복잡도, 최악 시간복잡도
• big O notation, T(n)
• quick sort
• merge sort
• BFS, DFS
• 다익스트라 알고리즘
• 프림 알고리즘
• heap (자료구조)
• linked list
• minimum spanning tree
• strongly connected component
• binary search tree
• pointer