AI/CS 대학원 입시 질문 준비 모음

※ 본 포스팅은 AI/CS 대학원을 준비하면서 작성한 글로, 주관적인 의견이 내포되어 있습니다. 정보의 신뢰를 목적으로 글을 읽는 것은 권장하지 않습니다!

선형대수

고유값과 고유벡터(Eigen Value, Eigen Vector): 행렬 A와 열벡터u를 곱하는 행위를 선형 변환이라고 생각할 수 있는데, 선형변환 이후 방향이 변하지 않는 벡터u를 고유벡터라고 한다. 이 때 크기는 변할 수 있는데, 그 크기가 변한 정도를 고유값이라고 한다.
– A행렬 x u벡터 = lambda x u벡터 식을 만족하는 lambda를 의미한다. 실제로 구할 때는 (A-lambda*I)에 대한 determinent값이 0일 때에 해당하는 lambda를 계산한다.
– A행렬 x u벡터 = lambda x u벡터일 때 단위벡터인 u벡터를 의미한다. 실제로 구할 때는 (A-lambda*I)에 u벡터를 곱한 값이 0을 만족하는 단위벡터 u를 계산한다.
대각화가능(diagonalizable): nxn행렬에서 선형독립(a1v1+a2v2+…anvn=0을 만족하는 a가 모두 0)인 Eigen Vector가 n개 이상인 경우, VAV^-1=Λ인 경우(V는 independent한 eigen vector로 이루어진 행렬, Λ는 eigen value로 이루어진 대각행렬)
고유값 분해(Eigen Decomposition): 고유값과 고유벡터를 이용해서 행렬을 분해하는 기법이다. 대각화가능한 행렬 A가 있다고 할 때, A=VΛV^-1로 분해가 가능하다. (V는 independent한 eigen vector로 이루어진 행렬, Λ는 eigen value로 이루어진 대각행렬) 또한 A가 symmetric하다면, V는 직교행렬이 되어, A=VΛV^T로 분해가 가능하다.
SVD(Singular Value Decomposition): 고유값 분해는 행렬이 정방행렬이면서 대각화가능(diagonalizable) 한 경우에만 가능했다. 그러나 SVD는 행렬이 어떤 형태이든 간에 분해가 가능한 기법이다. 즉 A행렬을 U,Sigama,V^T로 분해할 수 있다는 것이다. 여기서 U와 V는 직교행렬이며 각각 AA^T와 A^TA의 Eigen Vector이다. Sigma는 singular value로 이루어진 대각행렬이며 A^TA의 Eigen Value에 Square root를 씌운 형태이다.
PCA(Principal Component Analysis): 차원 축소를 할 때 사용하는 알고리즘이다. 예를 들어 데이터가 2차원상에 점들로 흩어져 있고, 이 점들을 1차원 공간에 매핑하고 싶다면 각 축에 대응되도록 점을 이동시키는 방법이 가장 간단한 방법일 것이다. 그런데 이렇게 하면 점들이 겹쳐서 정보의 유실이 발생한다. 따라서 점들의 분산을 최대화하는 축을 찾아야 되는데, 이 축을 구하는 방법이 PCA이다. PCA에 따르면, 공분산행렬의 고유값 중 가장 큰 값에 대응되는 고유벡터가 분산을 최대화하는 축에 해당이 된다. 이 축으로 데이터를 정사영 내림으로써 차원 축소를 하는 방법이다.

확률통계

확률변수(Random Variable): 어떠한 실험이 있을 때, 실험에 대한 결과와 실수를 매핑하는 함수이다. 예를 들어, 동전을 두 번 던지는 실험이 있을 때 나올 수 있는 결과는 {앞,앞},{앞,뒤},{뒤,앞},{뒤,뒤}가 된다. 여기서 앞면을 기준으로 실수를 매핑한다고 하면, {앞,앞}은 실수 2, {앞,뒤}와 {뒤,앞}은 실수1, {뒤,뒤}은 실수0 따위로 매핑하는 함수가 확률변수가 된다.
확률벡터(Random Vector)와 확률과정(Random Process): 확률벡터는 각 원소가 확률변수인 열(column)벡터를 의미한다. 확률과정은 확률 실험 결과가 실수를 매핑하는 확률 변수와는 달리 확률 실험 결과가 시간 함수를 매핑하는 함수를 의미한다.
공분산(Covariance)과 상관계수(Correlation Coefficient): 공분산은 두 확률변수가 흩어지거나 밀집된 정도를 나타내는 척도이다. 공분산에 대한 식은 Cov(X,Y)에 대해 E(XY)-E(X)E(Y) 혹은 E[(X-Mx)(Y-My)]로 표현한다. 상관계수는 공분산을 표준편차의 곱으로 나눈 값이다. 상관계수를 이용하는 이유는 공분산이 측정 단위에 의존하는 경향이 있기 때문이다. 예를 들어 몸무게의 단위가 kg도 있고 다른 단위도 있다고 하면, 이러한 단위에 따라 차이를 보인다. 따라서 상관계수를 이용해서 두 확률변수가 상관이 있는지 없는지를 결정한다. 여기서 상관이 있다는 것은 Cov가 양수거나 음수인 상태를 의미하는데, 양수면 X가 증가하면 Y도 증가하는 양의 상관관계를 가지고, 음수면 X가 증가할 때 Y가 감소하는 음의 상관관계를 가진다고 한다. 그렇지 않고 0이면 상관이 없는 형태가 된다.
상관(Correlation): 상관의 수식은 E(XY)이며 상관계수의 수식은 Cov(X,Y)에 표준편차의 곱을 나눈 형태이다. 따라서 상관은 상관계수와 다르며, 두 확률변수의 관계를 따지는 것과는 무관하다.
이산확률변수(Discrete Random Variable)과 연속확률변수(Continuous Random Variable): 이산확률변수는 상태공간(확률변수가 취할 수 있는 숫자들의 집합)이 유한하거나 셈을 할 수 있는 무한집합일 때에 해당하는 확률변수이다. 연속확률변수는 상태공간이 유한구간이거나 무한구간일 때 해당하는 확률변수이다. 이산확률변수의 예시로는 동전 던지기 실험처럼 앞면이 나오는 경우가 몇 개의 숫자로 정해져있는 경우이다. 연속확률변수의 예시로는 1과 2사이의 실수 중 한 수를 고르는 실험으로, 나오는 경우가 무한하다.
확률질량함수(PMF)와 확률밀도함수(PDF): 확률질량함수는 상태공간이 유한할 때 확률 변수X가 취하는 확률의 함수를 의미한다. 예를 들어, 동전을 두 번 던지는 실험에서 X가 0과 2일 때는 1/4, 1일 때는 1/2, 나머지는 0인 함수를 의미한다. 확률밀도함수는 상태공간이 무한할 때 확률 변수 X가 취하는 확률의 함수를 의미한다. 이 때는 확률질량함수처럼 특정 사건에 대한 확률을 나타낸 것이 아니라 특정 구간에 속할 확률을 나타낸다. 예를 들어, 1에서 6사이의 수를 뽑는다고 할 때 구간[1,2]에서 뽑힐 확률은 0.2, 구간[1,3]에서 뽑힐 확률은 0.4가 된다. 이렇게 특정 구간에 속할 확률을 계산하기 위한 함수가 PDF이다.
우도(Likelihood): 특정 사건이 일어날 가능성을 가능도 혹은 우도라고 부른다. 셀 수 있는 사건일 때는 확률이 우도가 되며, 셀 수 없는 사건일 때는 PDF의 y값이 우도가 된다. 예를 들어 동전을 두 번 던졌을 때 앞면이 2번 나올 가능성은 1/4이다. 1에서 6사이의 수를 뽑는다고 할 때 2가 뽑힐 가능성은 0.2이다. (PDF에서 X가 2일 때 Y가 0.2이므로)
최대 가능도 추정(MLE): 관찰값이 주어졌을 때 최대한 가능성이 높은 값을 고르는 방법을 의미한다. (혹은 관찰값이 나올 가능도를 최대로 만드는 값(모수)를 찾는 방법이다.) 예를 들어 키를 다섯번 측정했는데 178부터 182까지 수치가 나왔다고 하자. 이 때 나의 실제 키일 가능성일 가장 높은 값을 찾으려고 하는 것이다. 이 문제는 (반대로) 나의 키가 무엇일 때, 키를 다섯번 측정하면 178부터 182가 나올 가능성이 가장 큰지를 풀어서 해결할 수 있다. 이 때 한 가지 가정이 들어가는데, 나의 실제 키를 평균(m)으로 취하는 정규분포를 따른다는 것이다. 이 정규분포의 PDF에 대한 y값을 구하면, 평균이 180일 때 y값이 가장 크다. 즉 가능도가 가장 높으므로, 가능도를 가장 높게 하는 m인 180으로 추정할 수 있다.
참고 블로그 (6~8): https://rpubs.com/Statdoc/204928
베이즈 정리: P(A|B)는 P(B|A)*P(A)/P(B)의 식에 해당한다는 정리이다. 이 베이즈 정리는 스팸 필터링 알고리즘에 많이 사용된다. 예를 들어 스팸 문자에는 ‘팀장’이라는 문구가 많이 사용된다고 한다. 따라서 ‘팀장’이라는 문구가 올 때 스팸 문자일 확률을 구해보겠다. 즉 P(스팸|팀장)을 구하려고 한다. 근데 ‘팀장’문구가 포함된 문자에서 스팸 문자를 찾는 것보다, 스팸 문자에서 ‘팀장’이라는 문구가 담긴 문자를 찾는 것이 더 쉽다. 따라서 베이즈 정리를 사용하면 P(팀장|스팸)을 이용해서 P(스팸|팀장)을 구할 수 있다.
정규 분포(Gaussian Distribution): 평균에 가까울수록 발생할 확률이 높고 평균에서 멀어질수록 발생할 확률이 적은 그래프이다. 정규 분포의 PDF는 1/sqrt(2pi*sigma²) * e^-[(x-m)²/(2*sigma²)]를 y값으로 가지는 식을 지닌다.

머신러닝

머신러닝이란: 컴퓨터에 데이터가 주어졌을 때 데이터의 패턴을 파악하는 학습을 하고, 새로운 데이터가 들어왔을 때 학습한 내용을 바탕으로 예측하는 기술을 의미한다. 예를 들어 분류 모델같은 경우, 두 데이터를 잘 분류해내는 결정경계가 패턴이 된다. 따라서 새로운 데이터가 입력으로 들어왔을 때, 결정경계와의 위치를 고려해서 1인지 0인지가 결정된다. 그렇지 않고 회귀 모델 같은 경우, 데이터의 계형을 잘 나타내는 회귀곡선이 패턴이 된다. 따라서 새로운 데이터가 입력으로 들어왔을 때, 해당 회귀 곡선에 매핑을 해서 실수를 예측할 수 있다. 이러한 패턴을 파악하는 방법은 SVM, ANN, KNN 등 여러 가지 학습 알고리즘으로 해결한다.
지도학습과 비지도학습: 학습 데이터가 목표값을 가지고 있을 때 학습시키면 지도학습이고, 학습 데이터가 목표값을 가지고 있지 않을 때 학습시키면 비지도학습이다. 따라서 지도학습은 예측값과 목표값의 차이를 기반으로 학습하며, 비지도학습은 각기 다른 학습 알고리즘을 이용한다. (ex) 클러스터링은 유클라디안 거리를 이용한 알고리즘, PCA는 고유값과 고유벡터를 이용한 알고리즘 등등)
모델이란: 학습할 때는 데이터의 패턴을 생성하고, 추론할 때는 패턴을 기반으로 예측을 하는 프로그램이다. 예를 들어 자식 키와 부모 키간의 관계에 대한 학습을 하면 (부모 키=자식 키+1)따위의 패턴을 얻을 수 있다. 이후 부모 키가 160이라는 입력 값이 들어오면, 자식 키를 161이라고 예측할 수 있다. 또한 데이터의 패턴을 모델이라고 쉽게 부르기도 한다.
과대적합과 과소적합: 모델이 너무 복잡해서 학습 데이터에 대한 성능은 높지만 일반화 성능이 낮은 경우 과대적합이라고 한다. 반대로 모델이 너무 간단해서 학습 데이터에 대해서도 성능이 낮은 경우를 과소적합이라고 한다. 과소적합인 경우에는 오히려 테스트 데이터가 학습 데이터보다 성능이 높은 경우도 발생할 수 있다. 과대적합이나 과소적합이 발생하는 이유는 학습을 너무 많이 했거나(너무 적게 했거나) 하이퍼 파라미터를 적절하게 설정하지 않았기 때문이다.
선형회귀(Linear Regression): 종속변수와 독립변수의 관계를 선형 식으로 나타내는 것이다. 종속변수는 분석을 하려고 하는 변수이며, 독립변수는 종속변수에 영향을 미치는 변수이다. 예를 들어, 종속 변수가 자식의 키고 독립 변수가 부모의 키이면, 부모의 키로 자식의 키를 분석하기 위해, 두 변수의 관계를 선형적으로 찾고자 하는 것이다.
로지스틱 회귀(Logistic Regression): 연속된 입력을 받아 이산적인 값을 반환하는 분류 모델이다. 이 때는 선형회귀와는 다르게 직선 대신 S자 곡선(Sigmoid)을 사용해서 분류의 정확도를 높인다.
혼돈행렬(Confusion Matrix): 알고리즘이 얼마나 맞았냐 틀렸냐를 평가하는 행렬이다. TP,FN,FP,TN을 원소로 가지며, TP는 Positive라고 예측했는데 실제로 Postive일 확률, FN은 Negative라고 예측했는데 실제로 Positive일 확률, FP는 Positive라고 예측했는데 실제는 Negative일 확률, TN은 Negative라고 예측했는데 실제로 Negative일 확률에 해당한다.
정확도, 정밀도, 재현율: 정확도는 TP+TN/TP+FN+FP+TN으로 나타내며 전체에서 맞은 비율을 의미한다. 정밀도는 TP/TP+FP로 나타내며 모델이 Positive라고 예측한 것 중에 실제로 맞은 비율을 의미한다. 재현율은 TP/TP+FN로 나타내며 실제 Positive 중 모델이 맞춘 비율을 의미한다. 정밀도와 재현율은 상황에 따라 중요도가 다른데, 암 환자를 예시로 들면 재현율이 더 중요하다. 왜냐하면 암 환자라고 예측했는데 실제로 암 환자가 아닌 경우(정밀도가 낮은 경우)보다 실제 암 환자인데 암 환자가 아니라고 예측한 경우(재현율이 낮은 경우)가 더 피해가 크기 때문이다.
KNN: 새로운 데이터가 주어지면 기존의 데이터 중 가까운 K개와 비교해서 데이터를 분류하는 알고리즘이다. K가 작을수록 패턴이 복잡해져 과적합이 발생할 확률이 높고, K가 클수록 패턴이 너무 간단해서 언더피팅이 발생할 확률이 높아진다.
의사결정나무: 데이터를 무질서도가 적은 방향으로 계속 분할하는 분류 알고리즘이다. 무질서도를 측정하는 척도는 엔트로피 혹은 지니지수를 사용한다.
SVM: 서포트 벡터(결정 경계와 가장 가까이 있는 샘플)와 결정 경계와의 거리를 최대화하는 방향으로 학습시키는 분류 알고리즘이다. 다른 분류 알고리즘과는 달리 여백을 중요하게 여기므로 머신러닝 모델 중에서 성능이 높다.
클러스터링: 비지도학습으로, 데이터를 군집화시키는 알고리즘이다. 먼저 센터를 군집 개수만큼 지정한 후 거리 공식을 이용해서 군집을 형성한다. 이후 평균값으로 센터를 재지정한 후 군집을 업데이트한다. 이러한 과정을 센터가 더이상 변하지 않을 때까지 반복한다. 이 때 거리 공식은 민코스키 거리, 해밍 거리 등을 이용한다.
ANN: 인간의 뉴런을 본따 만든 퍼셉트론으로 이루어진 모델이다. 퍼셉트론은 다수의 정보를 입력받아 reasonable하면 1, 그렇지 않으면 0을 출력하는 구조를 지닌다. 이러한 퍼셉트론은 사용자가 정의함에 따라 여러 층으로 구성될 수 있으며, 은닉층이 2개 이상인 시점부터는 딥 러닝모델이라고 부른다.
앙상블: 동일하거나 서로 다른 학습 알고리즘을 이용해서 여러 모델을 생성하는 개념으로, 여러 모델을 이용하면 한 가지 모델을 이용한 것보다 성능이 향상될 것이라는 기대로 만들어졌다.
배깅과 부스팅: 배깅은 샘플을 여러번 뽑아 각 모델을 훈련하고 결과물을 집계하는 방법이다. 이 때 같은 학습 알고리즘을 이용하면 배깅, 다른 학습 알고리즘을 이용하면 보팅이라고 불린다. 부스팅은 병렬적으로 학습하는 배깅과는 달리, 여러 모델들을 순차적으로 학습시키면서 이전 모델의 에러율을 현재 모델에서 개선해나가는 형태로 학습하는 앙상블 기법이다.
랜덤포레스트: 의사결정나무 모델을 여러 개 이용하는 배깅 방법에 속한다. 그러나 배깅과는 달리 각 모델이 사용하는 데이터의 변수가 다른 점에서 차이가 있다. 예를 들어 데이터에 (성별,나이,연봉)이라는 변수가 있다면, A모델은 (성별,나이)를 사용하고, B모델은 (성별,연봉)을 이용해서 학습한다.
정규화를 하는 이유: 학습에 사용되는 모든 데이터를 동일 선상에서 봐야되기 때문이다. 예를 들어 회귀 분석을 하는데, 종속변수가 자식 수이고 독립 변수가 부모의 나이와 연봉이라고 하자. 근데 부모의 나이와 연봉은 수의 범위 차이가 크므로 정규화를 하지 않으면 연봉이 자식의 수에 끼치는 정도가 훨씬 클 수 있다. 즉 모든 데이터가 의미있기 사용되기 위해 정규화를 거치는 것이다.
홀드 아웃과 교차 검증: 홀드 아웃 방법은 데이터를 학습,검증,테스트로 나누는 전략이다. 학습 데이터는 데이터를 학습하는 용도이며, 검증 데이터는 모델이 오버피팅인지 아닌지를 체크하는 용도이며, 테스트 데이터는 모델이 잘 학습됐는지 평가하는 용도이다. 교차 검증은 학습 데이터를 K조각으로 나누고, 한 조각을 검증용, 나머지 조각을 학습용으로 사용하는 전략이다. 학습할 때마다 검증에 사용되는 조각은 바뀌며, 보통 K번 반복해서 학습한다. 그러면 K개의 모델이 만들어지는데, 이 모델 중 가장 최적인 모델을 이용해서 다시 학습하는 과정까지 진행된다.

딥 러닝

딥러닝이란: 머신러닝의 학습 전략 중 ANN을 발전시킨 학문이다. 또한 ANN에서 퍼셉트론으로 이루어진 은닉층이 2개 이상인 시점부터는 딥 러닝(DNN)이라고 불린다.
머신러닝과의 차이: 1. 딥 러닝 모델은 기본적으로 복잡하기 때문에 오버피팅에 취약하다. 특히 데이터의 개수가 적을 때 오버피팅의 정도가 크므로, 데이터의 개수가 적다면 머신러닝을 사용하는 것이 더 좋을 수 있다. 2. 머신러닝 모델의 입력은 가공된 특징 벡터가 사용된다면 딥 러닝 모델의 입력은 원본 데이터가 사용될 수 있다. 예를 들어 이미지 분류를 한다고 하면, 이미지를 SIFT함수를 거쳐서 벡터로 변환시키고 입력으로 주는 방식은 주로 머신러닝이고, 이미지 자체를 입력으로 주는 방식은 주로 딥러닝이다. 따라서 머신러닝은 특징 벡터에 해당하는 데이터를 받아서 패턴을 파악(분류를 위한 결정 경계를 파악)한다고 생각할 수 있고, 딥러닝은 원본 데이터를 받아서 특징을 자체적으로 추출하고 패턴을 파악한다고 생각할 수 있다.
딥러닝을 사용하는 이유: 딥 러닝 모델은 높은 레벨의 특징을 추출하기에 적합한 구조를 지녔기 때문이다. 예를 들어 객체를 포함하는 이미지가 입력으로 사용될 때, 초기 레이어에서는 에지(경계)나 코너에 대한 낮은 레벨의 특징을 추출하지만, 후반 레이어에서는 객체에 대한 특징을 추출한다. 따라서 높은 레벨의 특징을 이용해서 이미지를 분류하는 컴퓨터 비전 문제를 해결할 수 있다. 이와 비슷한 이유로 자연어 처리나 다른 task에서도 딥 러닝이 사용된다.
퍼셉트론: 뉴런을 본따 만든 구조로, 다수의 정보를 입력으로 받아 정보가 Reasonable하면 1, 그렇지 않으면 0을 반환하는 모델이다. 가중치가 곱해진 입력의 합이 theta보다 크면 Reasonable하고, 작거나 같으면 Reasonable하지 않다고 처리한다.
그래디언트(Gradient): 함수를 각 축으로 편미분한 값들의 모음이다. 그래디언트는 모든 방향으로의 순간 변화율을 구한 것이다. 딥러닝에서 말하는 그래디언트는 오차라고도 불린다. 이유는 수식을 전개해보면 예측값과 실제값의 차이이기 때문이다.
연쇄법칙(Chain Rule): 그래디언트를 구할 때 사용하는 공식이다. 예를 들어 ∂L/∂X (X에 대한 변화량, 그래디언트)를 구할 때 ∂L/∂Z * ∂Z/∂X로 구할 수 있다.
경사하강법(Gradient Descent): 함수 값을 최소화시킬 때 사용하는 방법으로, Gradient의 절댓값이 감소하는 방향으로 함수의 입력에 해당하는 w나 b따위를 변화시키는 것이다. 여기서 Gradient의 절댓값이 감소하는 방향은 -Gradient방향으로 간다는 말과 동치인데, -Gradient방향으로 간다는 것은 함수 값을 가장 빨리 감소시키겠다는 의미이다.
순전파(Forward Propagation): 딥러닝 모델에 위치한 노드들을 거쳐서 예측을 하는 것을 순전파라고 한다. 예를 들어 딥러닝 모델이 자식 키와 부모 키의 관계를 학습했다면 그 패턴은 노드와 연결된 가중치들에 저장된다. 이후 부모 키가 입력으로 들어왔을 때 가중치와 입력간의 곱과 합 연산을 연속하면서 자식 키를 예측할 수 있다.
역전파(Backward Propagation): 상위 레이어에 위치한 파라미터(W,b)의 Gradient를 역으로 전파해서 현재 레이어에 위치한 파라미터의 Gradient를 구하는 과정이다. 즉 연쇄법칙을 이용해서 그래디언트를 구하게 된다. 이렇게 구한 그래디언트들은 경사하강법에 사용돼서 파라미터가 업데이트된다. 참고로 컴퓨터가 계산할 때 역전파 대신 Numerical Gradient를 이용할 수도 있지만, 시간이 너무 소요되기 때문에 사용되지 않는다. 즉 역전파는 미분을 효율적으로 함으로써 그래디언트를 빠르게 구하는 용도로 사용된다.
손실 함수(Loss Function): 모델이 잘 학습됐는지 평가하는 함수로, 함수의 값이 낮을수록 학습을 잘했음을 의미한다. 이는 목적 함수, 손실 함수, 비용 함수 등으로 다양하게 불린다.
평균제곱오차(MSE): 예측값과 실제값의 차이의 제곱에 대한 평균이다. 실수를 예측하는 회귀 문제에서 자주 사용되는 손실 함수이다.
교차 엔트로피(Cross Entropy): 분류 문제에서 자주 사용되는 손실 함수이다. 분류 모델의 출력층에는 모든 클래스별 예측값이 나오는데, 출력층의 각 노드마다 (실제값*log예측값)을 구한 뒤 모두 더하고 마이너스를 앞에 붙이면 한 입력에 대한 교차 엔트로피가 나온다. 교차 엔트로피의 특징은 정답을 예측했을 경우 0에 가까워지고, 오답을 예측했을 경우 무한대에 가까워진다. 즉 오차에 많이 민감한 손실 함수이다.
옵티마이저(Optimizer): 옵티마이저는 머신러닝에서의 최적화 방법이다.
예를 들어 SGD는 배치 사이즈마다 경사하강법을 진행하는 것이다. 그러나 목적함수가 무엇이냐에 따라, 그리고 함수의 입력이 무엇이냐에 따라, Gradient가 너무 가파를 수 있기 때문에 학습 속도가 느리다. (Gradient는 함수 등고선의 수직인 방향임)
따라서 Momentum이라는 개념이 나왔다. Momentum은 경사하강법을 하면서 av항까지 더하는 방식으로 학습을 더 빠르게 한다. (w=w+v, v=av-lr*gradient) 그러나 lr가 무엇이냐에 따라 SGD보다 안 좋은 결과를 초래할 수 있는 문제점이 존재한다.
따라서 Adagrad라는 방식이 나왔다. Adagrad는 gradient의 크기가 너무 크면 lr을 줄이고 gradient의 크기가 너무 작으면 lr을 키우는 방법을 제안한다. 예를 들어 h=h+gradient로 설정하고, lr=lr*1/root(h)로 설정하는 것이다. 그러나 이 방법은 gradient가 너무 커지면 lr가 0이 되면서 학습이 안되는 문제점이 존재한다.
그래서 RMSProp이 나왔다. 이 방법은 현재 구한 gradient의 크기와 이전에 구한 gradient(h)의 크기를 convex combination으로 세팅함으로써 현재 gradient의 크기만 고려한 단점을 극복시켰다. 즉 h={lambda*h}+{(1-lambda)*gradient}로 설정하는 점에서 Adagrad와 차이점이 존재한다.
활성화 함수(Activation Function): 딥 러닝의 순전파 과정을 거치면 XW+b 따위의 값이 나오는데, 이 값이 0보다 크면 1이 나오고 0보다 작으면 0이 나오게 함으로써 딥 러닝 모델이 분류 모델로써 작용이 가능하게끔 하는 함수이다. 하지만 이러한 Step Function이 사용되면 parameter가 조금만 변해도 값이 확 변하는 문제점이 발생한다. 따라서 불연속점인 부분을 미분 가능하게 만든 Sigmoid나 tanh등으로 대체하는 방식으로 사용된다. 또한 이러한 활성화 함수를 이용하면 비선형성을 가지게 해 비선형 분류를 가능하게 한다.
배치 정규화(Batch Normalization): 모델의 입력으로 사용되는 데이터는 잘 분포가 돼 있어야지 좋다. 왜냐하면 데이터의 분포가 밀집돼있다면 데이터의 다양성이 부족하기 때문이다. 따라서 데이터의 입력에 대한 분포를 표준정규분포로 만드는 작업을 하는데, 이것이 배치 정규화이다. 표준화 공식처럼 평균을 빼고 표준편차를 나누는 방법을 사용한다. 이후 scaling과 shifting을 진행한다. 이러한 간단한 방법으로도 많은 성능 향상이 일어났다고 한다.
규제(Regularization): 비용함수에 lambda * L2 norm의 제곱을 더하는 방법이다. 여기서 L2 norm은 weight를 제곱한 뒤 모두 더하고 루트를 씌운 형태이다. 규제를 하면 lambda의 값에 따라 비용함수가 convex한 형태로 변경될 수 있다. 따라서 global optima를 찾기가 더 유리해진다. 또한 경사하강법을 진행할 때 weight를 감소시키고 -gradient방향으로 변화시킨다는 특징이 있다. 따라서 모델의 weight가 전체적으로 감소하면서 오버피팅도 막을 수 있다.
드롭아웃(Dropout): 딥러닝의 layer에 위치한 노드를 일부 제거하는 기법으로 오버피팅을 막는 용도로 사용된다. 왜냐하면 특정 노드가 학습 데이터의 특이한 특징을 저장하고, 그 노드가 결과에 많은 영향을 끼친다면 그 특이한 특징을 만족하지 않는 일반화된 데이터에 대해서는 성능이 낮게 나올 수 있기 때문이다.
Gradient Vanishing: 역전파가 입력 방향으로 진행될수록 Gradient의 값이 미약해지는 현상을 의미한다. 이 문제는 Sigmoid를 활성화 함수로 썼다는 것이 문제점으로 발견돼서 이후에는 ReLU가 활성화 함수로 사용되게 되었다. 또한 배치 정규화도 Gradient Vanishing을 예방해준다고 한다.
Sigmoid vs Softmax: 둘 다 입력을 0과 1사이의 값으로 변환시키는 함수이다. 다만 Sigmoid의 수식은 1/1+exp(-x)이고, Softmax의 수식은 exp(ai)/sigma(i=1->c) exp(ai)이다. 따라서 Softmax는 확률 값을 가지며, 그 합이 1이 된다. 따라서 Softmax는 multi classification을 할 때 각 클래스별 예측 확률을 구하는 용도로 사용된다.
Padding과 Pooling: 패딩은 이미지의 가장자리를 처리하는 기법으로, 만약 패딩을 same으로 해서 이미지의 상하좌우를 모두 0으로 채우면 convolution연산을 거쳐도 특징맵의 크기가 일정해진다. 풀링은 feature map의 크기를 줄이는 기법으로, max pooling을 하면 feature map에 풀링 필터를 포갰을 때 가장 큰 값만 남게 된다. 보통 padding을 same으로 하는 경우는 layer를 깊게 쌓고 싶을 때 사용하며, pooling을 하는 경우는 layer를 얕게 쌓고 싶을 때 사용한다.
CNN이 왜 이미지 처리에 강력한가: CNN은 Inductive Bias를 가지고 있다. Inductive Bias란 처음 보는 입력에 대해서 올바른 출력을 내기 위한 일련의 가정을 의미한다. CNN은 locality와 translation equivalence라는 가정을 가지게 되는데, locality는 이미지의 특징을 구할 때 전체를 보지 않고 특정 영역만 보고도 구할 수 있다는 것이다. 예를 들어 사람 얼굴 이미지에서 코에 대한 특징을 구한다고 하면 코 주변 영역으로만 Convolution연산을 해도 충분하다는 가정이다. translation equivalence는 이미지에서 특정 영역의 위치가 변경된다고 하더라도 이후의 layer에서 변경된 위치가 보존된다는 것이다. 예를 들어 사람 얼굴 이미지에서 눈이 북서쪽에 위치하면 특징맵도 북서쪽에 위치하고, 남서쪽에 위치하면 특징맵에서도 남서쪽에 위치한다는 것이다. 즉 위치 정보를 명확히 가지고 있다. 이러한 두 가정으로 인해 CNN이 이미지 처리에 강력하다.
AE와 VAE: AE와 VAE는 구조적으로 같지만 전혀 다른 배경을 가지고 있다.
AE는 의미있는 잠재벡터를 만들기 위한 모델이다. 예를 들어 이미지가 입력으로 들어오면, 적은 차원으로 의미있는 정보를 가지고 있는 잠재벡터를 구하고자 하는 것이다. 그런데 이 문제는 Unsupervised문제이므로, Supervised문제로 해결하기 위해 Decoder를 뒤에 붙여서 원본 데이터와 생성된 데이터의 오차로 인해 모델을 학습시키는 형태가 된다.
VAE는 이미지를 생성하려는 생성 모델이다. 따라서 AE와 반대로 디코더가 훨씬 중요하다. 그래서 원래는 random noise z가 decoder를 거쳤을 때 그럴듯한 이미지를 생성하려는 것이 목적인데, 이 문제는 거의 불가능에 가깝기 때문에 Encoder를 앞에 붙인 형태이다. Encoder에서 나온 특징들은 각각 확률분포를 나타나게 되는데, 이 확률분포들 중에서 값을 샘플링해서 얻은 값들로 z를 구성하고, 이 z로 그럴듯한 이미지를 만드는 것이 훨씬 쉬운 문제라는 것이다. 예를 들어, 사람 이미지들이 입력으로 들어왔을 때, 그 사람들에 대한 특징들이 각각 확률 분포로 나오게 되고, 거기서 샘플링을 한 것이 z니까 디코더를 통과하면 새로운 사람 이미지가 출력될 수 있다는 아이디어이다.
– 상세 설명: Encoder 부분에서 input의 정규분포를 따르는 latent variable(μ, σ)들을 생성한다. 이를 위해 KL Divergence loss를 통해 생성한 특징 분포가 정규 분포와 유사해지도록 학습한다. 이후 Reparameterization trick을 이용하여 샘플링을 진행한다. 이 방법은 가우시안 노이즈에 σ를 곱하고 μ을 더하는 방식이며, 이를 통해 역전파가 가능해진다. 샘플링을 통하여 만들어진 z를 디코더에 넣고 이미지를 생성한다.
– 정규 분포로 만드는 이유: 평균과 표준편차만으로 분포를 제작할 수 있으므로 수학적으로 편리하고 통계적으로 가장 보편적인 분포이기 때문이다. 따라서 이미지의 feature에 대한 분포도 정규 분포로 가정하는 것이다.
– KL Divergence: 두 분포 사이의 차이를 나타내는 값이며, 크로스 엔트로피에 엔트로피를 뺀 값으로 계산된다. 크로스 엔트로피(P,Q)는 P가 Q일 때 최솟값을 갖는다는 특징이 있으므로 KL의 최솟값은 항상 0을 만족한다.
Attention: 어텐션은 NLP분야에서 제시된 기술로, 기계 번역 문제를 풀 때 처음 사용되었다. 기계번역을 할 때는 번역을 하려는 시퀀스들을 인코더에 넣고, 번역 결과에 대한 시퀀스들을 디코더에 넣는다. 이후 인코더에서 나온 특징들은 디코더에 들어가게 되고, 현재 시점까지의 디코더에서 나온 특징(인코더와 융합된 특징)을 이용해서 다음에 나올 번역 단어를 예측하는 것이다. 여기서 어텐션은 다음 단어를 예측하기 전에 인코더의 입력 문장을 다시 한 번 참고하는 개념이다. 이 때 단순히 참고만 하지 않고 다음 단어를 예측을 할 때 도움이 되는 단어를 집중(Attention)한채로 참고를 하는 기술을 의미한다.
(문장에서 특정 단어에 집중하겠다는 것이 핵심) -> Scale dot product Attention 기법을 사용함
– Computer Vision에서의 Attention: 이미지 혹은 특징맵에서 어떤 부분(위치 or 채널)을 집중해야 되는지 알아내는 기법
Scale dot Product Attention: Attention의 계산 방법 중 하나이다.
1. 데이터에서 무엇을 Query로 쓰고 무엇을 Key와 Value로 쓸지 결정한다.
2. Query와 Key의 유사도를 계산하기 위해 내적을 하고, Key의 dimension으로 나눈다. 이후 softmax를 통해 유사도를 확률로 나타낸다. (scale dot product)
3. 유사도 벡터를 Value와 가중합(weighted sum)한다. (Value랑 행렬 곱을 한다고 생각해도 된다)
예를 들어 ‘나는 학교에 간다’라는 문장과 ‘I go to the School’이라는 문장이 있다고 가정하자.
1. ‘I’ 토큰을 Query로 쓰고, ‘나는’ 토큰, ‘학교에’ 토큰, ‘간다’토큰을 Key와 Value로 사용하겠다.
2. Query와 Key의 scale dot product를 통해 유사도가 각각 0.5, 0.3, 0.2로 구해진다.
3. ‘나는’ value에는 0.5가 곱해지고, ‘학교에’ value에는 0.3이 곱해지고, ‘간다’ value에는 0.2가 곱해진다. 이후 모든 값을 더한다.
결과) ‘나는 학교에 간다’라는 전체적인 정보를 가지면서, Query에 해당하는 ‘I’에 대해 더 집중한 특징이 만들어진다.
– Query: 집중할 단어 (Query: I)
– Key: Query와 유사도를 구할 단어들 (key1: 나는, key2: 학교에, key3: 간다)
– Value: 유사도 벡터를 가중치로 사용해서 weighted sum할 단어들 (value1: 나는, value2: 학교에, value3: 간다)
– Scale dot Product Attention: Query와 유사한 Key를 찾고, 해당 Key와 대응되는 Value를 집중하겠다
– Dimension으로 나누는 이유: 내적 행렬의 차원이 늘어날 수록 softmax 함수에서 작은 기울기(gradient)를 가지기 때문에 이를 완화해 주기 위해 dimension으로 나눈다.
Transformer: 기계 번역을 할 때 어텐션만을 사용하는 모델이다. 예를 들어 한글 문장을 영어 문장으로 번역한다고 하자. 인코더에서는 Self Attention을 통해 한글 문장의 특징을 파악한다. 디코더에서는 Cross Attention을 통해 한글 문장에서 영어 시퀀스와 유사한 부분에 집중한다. 이후 Feed Forward Network와 Softmax를 통해 다음 영어 단어들을 예측하는 구조이다. 기존 Seq2Seq 모델과 달리 행렬(문장 벡터들)을 입력으로 받아 병렬 처리할 수 있으므로, 연산 속도에서 강점을 보인다.
– Self Attention: Query와 Key-Value를 같은 데이터로부터 선정하고 어텐션하겠다
ex) 한글 문장에 속한 단어들로 Q, K, V를 선정한다.
– Cross Attention: Query와 Key-Value를 각각 다른 데이터로부터 선정하고 어텐션하겠다
ex) 한글 문장에 속한 단어로 Q를 선정하고, 영어 문장에 속한 단어들로 K,V를 선정한다.
GAN: 이미지를 생성하는 모델이며, 생성자와 판별자로 구성되어 있다. 생성자는 초기 랜덤 입력을 받아 원본 이미지를 생성하는 학습을 한다. 판별자는 원본 이미지와 생성된 이미지를 구분하는 학습을 한다. 처음에는 판별자부터 학습을 하므로, 생성자는 이미지 생성을 잘 못하고, 판별자는 두 이미지를 잘 비교할 수 있지만, 이후 판별자와 생성자가 번갈아서 학습을 하게 되면 판별자는 두 이미지를 잘 비교할 수 없는 상태에 이른다. 이 때 생성자는 원본 이미지와 아주 유사한 이미지를 생성하게 된다.
YOLO: 객체를 탐지하는 모델이다. 이미지를 여러 그리드로 나누고 각 그리드마다 후보 박스를 선정한다. 후보 박스는 x,y,w,h,c가 저장이 되는데 여기서 x,y,w,h는 후보 박스의 좌표와 크기를 의미하고 c는 이 후보 박스에 객체가 존재할 법할 확률에 IoU를 곱한 값이다. IoU는 실제 BBOX와 후보 BBOX의 교집합을 합집합으로 나눈 값으로 두 BBOX가 일치할 수록 값이 크다. 또한 각 그리드마다 클래스 별 존재 확률을 저장한다. 이러한 구조는 원본 영상이 Convolution 연산을 거치고 나온 결과 feature map이다. 마지막으로 여러 후보 박스들 중에서 가장 객체를 포함할 법한 박스를 NMS라는 알고리즘을 통해 구하게 된다.

코딩

시간복잡도: 알고리즘의 실행 시간을 프로그램의 입력 개수인 n으로 나타내는 방법이다.
스택: Last In First out 구조를 따르는 자료구조이다.
큐: First In First Out 구조를 따르는 자료구조이다.
리스트: 삽입,삭제,탐색 메소드를 지원하는 업그레이드된 배열의 자료구조라고 생각할 수 있다. 배열이 아니라 노드로 이루어진 연결리스트로도 구현할 수 있다.
이진탐색트리: 왼쪽 부분 트리는 모두 루트 값보다 작고 오른쪽 부분 트리는 모두 루트 값보다 큰 형태를 지닌 트리로써 탐색을 하는 평균 시간 복잡도가 O(logn)을 만족한다. 그러나 트리가 균형된 상태가 아니면 최악의 시간 복잡도인 O(n)이 된다.
힙: 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 완전 이진 트리는 최대 힙이고, 항상 작거나 같으면 최소 힙이다. 힙의 특징은 최댓값 삭제 혹은 최솟값 삭제를 O(logn)시간에 할 수 있다는 점이다. 이러한 최댓값과 최솟값을 찾는 문제는 알고리즘 문제 풀이에서 많이 사용이 되므로 힙은 자주 사용되는 자료구조이다.
AVL 트리: 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이가 1이하인 트리를 의미한다. 트리가 거의 균형된 상태이므로 최악의 시간복잡도도 O(logn)시간을 만족한다.
그래프: 연결되어있는 노드와의 관계를 표현하는 자료구조이다.
* 방향 그래프의 최소 에지수: n-1
* 방향 그래프의 최대 에지수: n(n-1)
* 무방향 그래프의 최소 에지수: n-1
* 무방향 그래프의 최대 에지수: n(n-1)/2
(n은 정점의 개수)
트리: 사이클이 없는 그래프를 표현하는 자료구조로, 계층적 구조를 나타낸다.
* 높이가 h인 이진트리의 최소 노드 개수: h개
* 높이가 h인 이진트리의 최대 노드 개수: (2^h)-1개
* n개의 노드를 갖는 이진 트리의 최소 높이: ceil(log2 n+1)
* n개의 노드를 갖는 이진 트리의 최대 높이: n
* 에지의 개수: n-1
(트리의 레벨은 1부터 시작하며, n은 노드의 개수이다)
DFS와 BFS: DFS는 그래프를 깊이 우선적으로 탐색하는 것이다. 따라서 가장 노드가 깊은 곳까지 탐색을 하고 다시 위로 올라오면서 순회를 하게 된다. BFS는 그래프를 너비 우선으로 탐색하는 것이다. 따라서 그래프의 같은 위치를 탐색한 뒤 더 깊은 위치를 탐색하는 방법으로 순회를 하게 된다. DFS는 스택이나 재귀를 이용하고, BFS는 큐를 이용하는 특징이 있다.
(DFS: 처음 방문하는 정점이 v라고 할 때, v를 방문하고 v와 인접하면서 아직 방문하지 않은 정점 w에 대한 DFS를 재귀적으로 수행한다. / BFS: 처음 방문하는 정점이 v라고 할 때, v를 방문하고 v와 인접한 정점들을 방문한다. 이후 두 번째로 방문한 정점과 인접한 정점들, 세 번째로 방문한 정점과 인접한 정점들을 차례대로 방문한다. 이 과정을 반복한다.)
* DFS와 BFS의 시간복잡도: O(n+m) –인접리스트, O(n^2) –인접행렬
(이유: DFS와 BFS는 결국 인접리스트의 모든 원소나 인접행렬의 모든 원소를 순회하는 기법이기 때문에, 인접리스트나 인접행렬의 크기만큼 시간복잡도가 계산된다)
MST: 최소신장트리로, 에지 가중치의 합이 최소가 되는 신장트리를 의미한다. 여기서 신장트리는 원본 그래프의 모든 정점을 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. MST를 구하는 알고리즘은 크루스칼 혹은 프림이 있다.
다익스트라, 밸만-포드: 단일 소스 최단 경로 알고리즘이다. 단일 소스 최단 경로 알고리즘은 소스에 해당하는 정점으로부터 다른 정점들간의 최단 경로를 구하는 것이다. 이 때 경로의 길이는 경로 상에 있는 에지 가중치 합을 의미한다. 다익스트라는 음수가중치가 없다고 가정을 하고 문제를 풀었으며 시간복잡도는 O(n²)이다. 밸만포드는 음수사이클이 없다고 가정을 하고 문제를 풀었으며 시간복잡도는 O(nm)이다. n은 정점의 수, m은 에지의 수에 해당한다.
이진탐색: 배열 원소의 위치를 찾는 시간이 O(logn)을 만족하는 기법으로 정렬이 된 상태에서 진행해야 한다. low,mid,high라는 변수가 사용되며, 처음 low는 배열의 처음 인덱스인 0이고, high는 배열의 마지막 인덱스이다. mid는 low와 high를 더하고 2로 나눈 값이다. 이 때 mid를 인덱스로 갖는 배열 원소가 찾고자 하는 값보다 크면 mid 앞쪽에 찾고자 하는 값이 있으므로 high를 mid-1로 변경한다. 그렇지 않고 더 작다면 mid 뒤쪽에 찾고자 하는 값이 있으므로 low를 mid+1로 변경한다. 이러한 과정을 mid를 인덱스로 갖는 배열 원소가 찾고자 하는 값일 때까지 반복한다.
퀵 정렬: 평균 시간 복잡도가 O(nlogn) 시간을 만족하는 빠른 정렬 기법이다. 처음에 배열에서 피봇을 하나 선정한다. 이후 피봇보다 작은 원소는 피봇보다 왼쪽, 크거나 같은 원소는 오른쪽에 배치한다. 분할된 두 개의 작은 리스트는 재귀적으로 다시 정렬한다. 피봇이 선정될 때 중간값으로 잘 선정된다면 O(nlogn)시간이지만, 가장 큰 값이나 가장 작은 값으로 선정된다면 O(n²)이 될 수도 있다.
합병정렬: 최악의 시간 복잡도가 O(nlogn) 시간을 만족하는 빠른 정렬 기법이다. 처음에는 배열을 두 개의 원소를 가지는 작은 배열들로 분할한다. 이후 작은 배열들을 정렬하는 정복 과정을 거치고 작은 배열들을 합치는 합병 과정을 거치면 된다.
분할정복법: 큰 문제를 작은 부분 문제들로 나누고, 각각을 재귀적으로 해결한 뒤, 부분 문제의 해를 합하여 큰 문제의 해를 구하는 방법이다.
동적계획법: 작은 문제에 대한 답을 메모리에 저장하고, 큰 문제를 풀 때 메모리에 저장된 값을 이용함으로써 동일한 계산을 반복하지 않고 빠르게 해결할 수 있는 방법이다.
탐욕법: 현재 상황에서 가장 좋은 방법을 선택하는 알고리즘이다.
P와 NP: deterministic하게 polynomial time(다항 시간)안에 풀 수 있는 문제들의 클래스를 P라고 부른다. nondeterministic하게 polynomial time안에 풀 수 있는 문제들의 클래스를 NP라고 부른다. 이 때 deterministic하다는 의미는 문제를 푸는 과정과 결과가 동일하다는 것이고, nondeterministic하다는 의미는 문제를 푸는 과정과 결과가 여러가지라는 것이다. 또한nondeterministic time은 여러 과정으로 푼 것들 중 가장 빠른 시간을 의미한다. 실제로 NP문제 같은 경우 병렬 처리를 해야 polynomial time에 문제를 풀 수 있다.
객체지향이란: 컴퓨터의 프로그램을 명령어의 집합으로 보는 것이 아니라 객체들의 집합으로 보는 것을 말한다.
객체지향의 4대 원리: 추상화, 캡슐화, 일반화, 다형성이다. 추상화는 클래스를 만들 때 필요한 속성만을 이용해서 제작하는 것을 말한다. 캡슐화는 정보 은닉을 통해 낮은 결합도를 가지도록 하는 것을 말한다. 일반화는 한 클래스가 다른 클래스를 포함하는 상위 개념일 수 있다는 것이다. 다형성은 서로 다른 클래스의 객체가 같은 이름의 메소드로 호출될 때 각자의 방식으로 동작하는 것이다.
SOLD 원칙이란: 객체지향 프로그래밍의 기본 원칙이다. SRP원칙은 객체는 단 하나의 책임만을 가져야함을 의미한다. OCP는 기존 코드를 변경하지 않으면서 새로운 코드를 작성할 수 있어야됨을 의미한다. LSP는 부모 클래스의 인스턴스 대신 자식 클래스의 인스턴스로 대체돼도 문제되지 않는다는 것을 의미한다. DIP는 의존 관계를 맺을 때 변화하기 어려운 것에 맺어야 된다는 것이다. ISP는 인터페이스를 클라이언트에 특화되도록 만들어야 된다는 것이다.

운영체제

운영체제 역할: 하드웨어 자원을 관리하고 사용자에게 인터페이스를 제공한다. 예를 들어 사용자가 fopen함수로 파일 열기를 요청하면, 운영체제는 하드디스크에 있는 파일을 대신 꺼내준다.
CPU: 논리장치, 제어장치, 레지스터로 이루어진 하드웨어 장치이다. 논리장치는 논리 연산을 수행하는 역할을 하고, 제어장치는 작업을 지시하는 역할을 하고, 레지스터는 데이터를 임의로 보관하는 장소이다.
부팅: 컴퓨터가 켜졌을 때 운영체제를 메모리에 올리는 과정이다. 먼저 ROM이 갖고 있는 바이오스를 실행하면, 바이오스는 주요 하드웨어가 제대로 작동하는지 확인한다. 이후 운영체제를 실행하기 위한 코드인 부트스트랩 코드를 메모리에 올리고 실행하면, 운영체제가 실행이 된다.
버퍼: 속도에 차이가 있는 두 장치 사이에서 그 차이를 완화하는 역할을 하는 장치이다. 예를 들어 CPU와 디스크의 속도 차이를 완화하기 위해 RAM이 버퍼로 작용한다.
프로세스와 스레드의 차이: 실행을 위해 메모리에 올라온 프로그램을 프로세스라고 하며, 프로세스에서 할당된 일을 스레드라고 한다. 프로세스는 운영체제의 작업 단위이며, 스레드는 CPU의 작업 단위이다.
교착 상태: 2개의 프로세스가 다른 프로세스의 작업이 끝날 때까지 기다리며 작업을 못 하는 상태
교착 상태의 조건: 자원은 공유할 수 없어야 되고, 프로세스는 자원을 빼앗을 수 없으며, 프로세스는 자원을 점유한 상태에서 다른 자원을 대기하고 있어야 되고, 프로세스 간 관계는 원을 이루어야 한다.
아사 현상: 운영체제의 잘못된 정책으로 인해 특정의 프로세스의 작업이 지연되는 현상
CPU 스케줄링: 준비 큐에 있는 프로세스를 CPU에 할당하는 기법
CPU 스케줄링 동작 방식 비교
1. FCFS: 큐에 도착한 순서대로 CPU를 할당함
2. SJF: 실행 시간이 가장 짧은 작업부터 CPU를 할당함
3. HRN: 우선 순위가 가장 큰 작업부터 CPU를 할당함
4. 라운드로빈: 프로세스가 작업을 하다가 주어진 시간 안에 완료를 못 하면 큐의 맨 뒤로 감
5. SRT: 라운드로빈을 사용하지만 실행 시간이 짧은 것부터 할당함
디스크 스케줄링: 데이터를 접근하기 위해 디스크 헤드가 움직이는 경로를 결정하는 기법
디스크 스케줄링 동작 방식 비교
1. FCFS: 큐에 들어온 순서대로 서비스를 하는 방법
2. SSTF: 탐색거리가 가장 짧은 트랙 먼저 서비스를 하는 방법
3. SCAN: 탐색거리를 내림차순으로 정렬하고, 현재 진행 방향으로 끝까지 가고, 다시 역으로 끝까지 가는 방법
4. C-SCAN: SCAN 방법에서 방향을 바꾸고 이동할 때 서비스하지는 않는 방법
5. LOOK: 더이상 서비스할 트랙이 없으면 중간에서 방향을 바꾸는 방법
6. C-LOOK: LOOK 방법에서 방향을 바꾸고 이동할 때 서비스하지는 않는 방법

SHA Computing

How Sunghyun handles computer

AI/CS 대학원 입시 질문 준비 모음

Leave a Reply Cancel reply