🍺 매일매일 맥잔잔 🍺

• 신호처리, 머신러닝, 통계, 로봇, 그래픽스등 다양한 분야와 관련이 있음
• 2000년대에 와서야 대중화됨
• 컴퓨터비전은 레벨별로 분류할 수 있음
• 로우레벨: stereopsis, optical flow, image segmentation
• 미드레벨: object tracking, human motion analysis
• 하이레벨: object recognition, event detection

• 보통의 인간은 trichromacy(원추세포가 r,g,b 세개있음. 세가지 원추세포로 물체의 색깔을 인식함)
• monochromacy~pentachromacy의 다양한 생물들이 있음
• cone(원추세포)가 있는 영역은 안구 내부에서 극히 일부(fovea)를 차지함. 나머지는 rod(명암, 형태 등을 인식하는 세포)
• perceptual organization(지각적 조직화)
• subjective contour(주관적 윤곽)
• stomatopod: 특이한 눈을 가졌음

• 선형대수
• p-norm
• 내적
• 외적은 쓸일없음
• 행렬(합, 곱, transpose)
• rank: number of linearly independent rows/columns
• linearly independent: 다른 row/column의 linear combination으로 만들 수 없는것

• 이미지 프로세싱이란?
• I -> I’
• 하나의 이미지를 넣어서 새로운 이미지를 뽑음
• PIL: Python Imaging Library
• box 나타내는 방법 두가지
• (left, upper, right, lower)
• (left, upper, width, height)
• Image Operations
• array(Image.open(’images/empire.jpg’).convert(’L’)) 
• 불러온 image 객체를 배열로 변환
• Displaying Images
• contour(im, origin=’image’)
• 밝기 구간을 나눠서 보여줌
• Image Histogram
• hist(im.flatten(), 128) 
• flatten(): 2차원 배열을 1차원 배열로 바꿈
• 해당 값을 가지고 있는 픽셀이 몇개인지 보여줌(a distribution of pixel values) 
• Array Image Representation
• print im.shape, im.dtype # (800, 569, 3) uint8
• im이 Image 객체의 배열일 경우
• (width, height, depth)
• Pixel Value Transforms
• im2 = 255 - im
• 흑백 반전
• im4 = 255.0 * (im/255.0)**2 
• pixel value를 제곱함(밝은 부분을 더 밝게 보여줌)
• Histogram Equalization
• Flattens the histogram so that all intensities are as equally common as possible. (histogram의 분포를 고르게 함)
• def histeq(im, num_bins=256)
• cdf = imhist.cumsum() # cumulative distribution function
• histogram의 누적분포함수를 이용하여 normalize -> 원래 이미지에 linear interpolation
• 밝기조정기능(너무 밝거나 어둡게 찍힌 사진을 적당하게 바꿀 수 있음)
• 하지만 화질구지가될수있음
• Image Filtering
• f(x, y) * h(x, y) = g(x, y) 
• 어떤 n*n patch(=kernal=mask)를 가지고 원본 image에 convolution함
• correlation operator, convolution operator가 있음
• Padding
• filtering을 할 경우 가생이에 예외상황이 발생함(convolution할 픽셀값이 존재하지 않는 문제)
• 따라서 padding을 설정해줌 (zero padding, wrap padding, clamp padding, mirror padding등)
• 패딩을 설정해서 하나의 이미지로 만들어서 convolution할수도 있고 아니면 그때그때 값을 가져와서 convolution할 수도 있다(memory issue임)
• Blurring Images
• 보통 가우시안 커널을 사용
• 시그마 값이 클 수록 블러효과 증가
• Image Derivative
• = Image gradient
• gradient angle = arctan2(Ix, Iy)
• Filter 종류: Prewitt/Sobel/Gaussian 등등
• 투디 linear filter는 separable함(n*n => (n*1)*(1*n))
• 나눌 수 있으면 무조건 나누어 하는 것이 빠름(n^2 operations > 2n operations)
• morphology
• binary image로 만드는것(모양이 중요)
• convert(’L’): Luminance
• original/dilation(확장)/erosion(축소)/majority(kernel 내에 max(|0|, |1|))/opening(erosion->dilation)/closing(dilation->erosion)
• connected components
• 4-neighbor(상하좌우)/8-neighbor(+대각선)
• 구하는 방법
• two-pass algorithm: horizontal run -> connect vertically adjacent runs
• recursive algorithm
• distance transform
• 중심축 구할때 사용
• forward sweep: 왼쪽과 위의 픽셀을 보고 둘중에 작은거 선택
• backward sweep: 오른쪽 + 아래 + (자신의 픽셀 + 1)을 보고 작은것 

• Origin of Edges
• edge: discontinuity가 존재하는 부분
• surface normal discontinuity/depth discontinuity/surface color discontinuity/illumination discontinuity
• human boundary detection과 최대한 비슷하게 하는것이 목표
• edge의 재정의: intensity의 rapid한 변화가 발생하는 부분 -> gradient operator를 이용
• 실제 data에는 noise가 많기 때문에 smoothing을 먼저 한다
• canny edge detector
• 여러 방향으로 잘라본 후 기울기가 가장 큰것을 선택
• hysteresis thresholding
• local max에서 시작해서 양쪽 방향을 따라 진행
• threshold: edge의 최소 기준
• threshold를 두개 설정 
• Thigh, Tlow: Thigh에서 시작하여 Tlow까지만 따라감
• scale selection
• gaussian filtering의 정도
• 요즘은 가능할 경우 다 딥러닝으로 함. 속도가 중요할 경우 빼고
• Line Detection
• successive approximation
• 두 점을 골라서 line을 만듬 -> 두 점 사이의 점들에서 line까지의 거리를 잼 -> 모든 거리가 threshold보다 작을 때까지 가장 먼 점을 찾아 두개로 나눔
• hough transform
• 어떤 이미지에서 x, y를 지나는 모든 line을 r, 세타 좌표계에서 나타냄 -> voting
• 문제점: 시간 + 메모리(3d가 넘어가면 좀 힘들어짐), 짧은 edge는 detection이 어려움
• 해결책: 모든 line말고 실제 edge와 비슷한 방향의 line만 고려

• 서로 다른 이미지(e.g. 다른 각도에서 같은 장소를 찍은 사진)에서 대응되는 점/지역을 찾는 것
• invariant local feature
• geometric invariance: translation, rotation, scale … => 회전, 이동, 확대/축소 등을 감안하여 판단(회전하더라도 같은 feature가 뽑힘)
• photometric invariance: brightness, exposure, contrast => 밝기, 노출, 대비를 감안하여 판단
• advantages of local features
• locality: robust to occlusion and clutter
• distinctiveness: should differentiate a large set of images(장점보다는 local feature가 가져야 할 덕목…)
• quantity: hundreds of thousands in a single image(많을수록 좋음)
• efficiency: real-time performance 
• generality
• what makes a good feature?
• uniqueness: 한 이미지 내에서 unique해야 한다. 나랑 비슷한 feature가 많으면 좋은 feature라고 할 수 없음
• 그럼 uniqueness는 어떻게 판단하는가? 이미지를 다 scan할 수는 없잖아
• 근처에서 shift해서 비슷한게 나올 경우 x. 안나올 경우 좋은 feature
• corner detection: compare the changes of pixels by summing up the squared differences(SSD)
• 2차원에서 나오는 두 eigenvector는 서로 수직임
• n차원에서 eigenvector는 n개 => 모두 수직
• Shi-Tomasi corner detector: 람다 마이너스를 기준으로 corner를 판단
• Harris and Stephens: 더 복잡한 공식
• harris는 scale invariant하지 않음(왜냐하면 patch 사이즈가 바뀌니까) + translation invariant함
• gaussian filtering을 할 경우에는 rotation invariant함
• 가장 적절한 scale을 찾는 방법
• scale을 바꿔가면서 local maximum cornerness response를 가지는 scale을 찾음!
• 하지만 시간이 너무 많이 걸림
• automatic scale selection
• FAST
• 어떤 점을 중심으로 반지름이 r인 원을 그림 -> 중심에서 원의 둘레까지의 벡터가 r^2만큼 생김 -> 벡터들의 밝기가 연속적으로 몇개 이상일 경우 corner라고 판단
• 빠름
• SIFT
• very popular “high-end” detection/ description algorithm
• high-end: 오래 걸림
• 하나의 물체를 다른 각도에서 찍었을 때는 어느정도 이상이면 잘 안됨(3d invariant)
• 시그마가 다른, 가우시안 처리된 이미지의 차 -> Difference of Gaussian(DOG)
• 라플라시안 함수랑 비슷하게 생겨먹음 => 비슷한 효과를 얻을 수 있음
• MOPS(Multiscale Oriented Patches)
• 다양한 scale에서 방향을 고려해서 뽑음
• 잘안됨
• SURF
• Speed-Up Robust Features
• image를 integral image로 만들어서 계산 -> computation time 감소
• 커널사이즈에 시간이 영향 받지 않음(계산 열여섯번 하는건 항상 같음) -> scale space building을 할 필요가 없음
• Binary Descriptors
• pixel value를 이용하지 않고 두 value의 대소만 비교함
• BRIEF, BRISK, ORB
• 정확도가 중요할 경우: SIFT, SURF, KAZE
• 속도가 중요할 경우: BRIEF, ORB
• feature matching(패치 비교)
• ncc: normalized cross-correlation
• one-sided
• 각각의 i에 대해서 어떤 j와 가장 잘 맞는지
• two-sided
• one-sided + 각각의 j에 대해서 어떤 i와 가장 잘 맞는지

• 2d image transformations
• translation, euclidean, similarity, affine, projective
• forward warping
• 원본 이미지를 그대로 warp하는 것
• 확대할 경우 비어있는 픽셀이 발생하는 등 문제가 생김
• inverse warping
• f의 역함수 이용
• linear interpolation
• 결과로 정수가 아닌 값이 나올 경우 가장 가까운 pixel을 선택
• DoF(Degree of Freedom)
• 해당 transformation을 표현하기 위해 필요한 parameter 개수
• svd(singular value decomposition)
• A=USV^T
• A: n*m, U: n*m, S: n*m, V^T: m*m
• U는 orthonormal, S는 diagonal(대각선 빼고 0)
• feature를 모두 쓸 수 없음. outlier/noise가 있을 때 결과가 제대로 안나옴
• RANSAC(Random Sample Concensus)
• 잘못된 feature(outlier)를 거르기 위함
• 여러개의 feature중 랜덤으로 샘플을 뽑아서 여러번 맞추어 보고 inlier(outlier의 반댓말. 일치하는 feature를 의미)의 갯수가 최대가 되는 p를 구함
• 93쪽: h.o.t = high order term은 무시한다
• Levenberg-Marquadt Algorithm(LM)
• 에러가 감소하는 방향으로 움직일 때 step size를 줄여줌 => minimum을 지나쳐버리는 경우인 overshooting을 방지
• Summary: noise-free data의 경우 DLT, outlier/noise를 filter해야 할 경우 RANSAC, 추가적으로 optimization이 필요할 경우 robust norm

• camera: 빛을 재는 도구
• cx, cy => center 좌표
• 사람 눈의 focal length는 대략 50mm
• focal length가 길면 화각이 감소 -> 좁은 범위를 정밀하게 측정
• 짧으면 화각 증가 -> 넓은 범위
• crop body: 필름보다 작은 ccd -> 같은 렌즈라도 작은 범위가 찍힘
• full body: 필름만한 ccd
• camera intrinsics: 카메라 자체의 parameter(focal length, image center등)
• camera extrinsics: 카메라의 위치
• pinhole camera에서 pinhole이 너무 클 경우 빛이 너무 많아서 흐릿함. 너무 작을 경우 빛의 파동성때문에 회절이 일어나서 흐릿함
• 렌즈가 필요한 이유: 빛의 양을 키우기 위함, 한 점에서 출발한 빛을 정확히 한 점으로 모을 수 있음
• 단점: 거리가 정확히 맞지 않으면 정확히 한 점으로 모아지지 않음 => circle of confusion
• depth of field: pinhole camera에는 없는 개념. 렌즈가 있기 때문에 생긴 개념임
• lens model의 geometrical aberrations
• distortion
• spherical aberration
• astigmatism
• coma
• chromatic aberrations: 여러 파장의 빛이 들어올 경우 모두 굴절률이 다르기 때문에 발생

• 한 물체에 대한 여러장의 이미지를 통해 해당 물체에 대한 structure를 알아냄
• Triangulation, P3P, Epipolar Geometry
• Triangulation: 두 장 이상의 이미지가 있고, 카메라의 pose(Rt), image(2d)에서의 물체의 pixel 좌표가 주어졌을 때 해당 물체의 3d 공간에서의 위치를 알아냄
• P3P: 3개의 3차원 좌표 + 좌표들의 image에서의 좌표가 주어졌을 때 카메라의 pose를 알아냄
• Epipolar Geometry: 두개의 카메라가 3d 공간의 좌표를 관찰
• epipolar plane: 3d공간상의 세 점(3d공간의 한 좌표, 카메라 1의 위치, 카메라 2의 위치)을 포함하는 평면

• stereo rectification
• original image pair에서의 epipolar lines를 horizontally & vertically correspond 하도록 이미지 자체를 transform함
• disparity(시차)
• 두 카메라에서부터 무한대의 거리에 있는 물체에 대한 두 카메라의 disparity는 0
• 항상 0이상의 값을 가짐
• depth estimation
• 빛을 직접 쏘는지 여부에 따라 active/passive로 나뉨
• time-of-flight의 경우 빛을 쏘니까 active 방식
• stereo의 경우 passive
• lens array(integral imaging)
• 한 점을 통과하는 빛을 capture하는 pinhole camera와 달리 평면을 지나는 모든 빛(light field)을 capture함 => focus를 자유롭게 바꿀 수 있음
• normal sensor
• surface의 normal을 구할 수 있음
• structured light
• 가장 많이 쓰이는 기술. stereo 원리와 비슷하지만 카메라 하나에 projector 하나를 사용한다는 점
• baseline(카메라-projector간 거리)이 넓을수록 측정할 수 있는 depth range가 깊어짐
• time-of-flight
• 빛을 쐈을 때 ~ 반사되어 돌아올 때까지의 시간을 계산하여 거리를 도출해냄
• kinect

• image 내에서 해당 object가 있을 확률이 가장 높은 곳을 선택
• mean-shift algorithm
• search window의 mean계산 -> 계산한 mean을 중심으로 search window를 옮김 -> converge 할 때까지 반복
• camshift
• window size도 조절
• tracking vs detection
• tracking: time-continuous estimation of object states
• detection: finding the targets from scratch in a given scene
• prediction-correction
• 이전까지의 object tracking한 결과를 이용해서 해당 object가 어디에 있을 지 prediction한 후 현재 상태를 반영하여 correction함
• kalman filtering
• estimates the internal states of a linear dynamic system from a series of noisy measurements
• 기계등 다른 분야에서 많이 씀
• particle filtering
• condensation: particle filtering의 implementation 중 하나

—

• spectral clustering
• cluster마다 크기가 어느정도 일정하기 때문에 배경이 필요 이상으로 쪼개질 수 있음
• minimum cut
• normalized cut

• PCA(Principal Component Analysis) & FLD(Fisher Linear Discriminant)
• Generative model: 타겟으로 최적의 모델을 만듦
• Discriminative model: classifier를 학습하여 타켓을 구분함
• PCA: orthogonal linear transform. the greatest variance by any projection of the data comes to lie on the first coordinate, the second greatest on the second coordinate, and so on
• FLD: linear discriminant analysis
• maximizes the distinctness between classes of data
• approximation(PCA, max. variance) vs. classification (LDA)
• AdaBoost
• 여러개의 weak classifier(vertical/horizontal half plane)를 합쳐 하나의 final classifier를 만듬
• Cascaded Classifier
• 10배 빠름 - only positive examples are considered이기 때문

• algorithms that try to mimic the brain
• activation functions
• sigmoid, ReLU, Leaky ReLU, tanh, Maxout, ELU
• sigmoid: 미분가능, x의 domain이 무한함 하지만 vanishing gradient problem 발생
• Deep NN
• hidden layer가 여러개

1-1

• oriC: DNA에서 복제의 시작점
• k-mer: mer은 polymer할 때 mer
• most frequent k-mer: 길이 k의 text중 가장 frequent한 text
• kmer 찾는것이 실제로 hidden message를 찾는것에 의미가 있는가? (15p)
• polymerase: polymer를 만드는 애
• dnaA: replication initiater
• dnaA box

• 19p: 초록색과 빨간색은 complementary한 관계에 있다
• 염기서열의 첫부분은 5’ end 끝부분은 3’ end라고 함
• 5’ end가 항상 왼쪽으로 오게 쓴다
• genome(또는 생물 종류)에 따라 hidden message가 다를 수 있다

• oriC가 주어질 때는 hidden message를 찾을 수 있지만 전체 genome에서 oriC를 찾으려면?
• oriC크기의 window를 잡아서 해당 window내의 frequent word를 찾아서 window끼리 비교한다

1-2

Probabilities of Patterns in a String

• Pr(4, 2, “11”, 2) > Pr(4, 2, “01”, 2) 인 이유는 11은 overlap이 가능하기때문이다 (111이면 11이 두번 있는셈)
• 6쪽의 공식은 overestimate임. 왜냐하면 예로 0101011이라는 string은 0101xxx, xx0101x 등 중복되어 counting 될 수 있기 때문이다
  

Finding Frequent Words

• brute force
• less time: frequency array
• patternToNumber, NumberToPattern -> O(k)
• findingFrequentWordsBySorting -> O(1)
• total -> O(text * k)
• 4의 k승만큼의 메모리를 사용
• sorting을 추가한다면? findingFrequentWordsBySorting -> 단어길이만큼의 메모리를 사용
• k가 길경우에는 sorting을 사용하고 짧을경우에는 sorting없이 그냥 하는것이 나음

Finding Clumps

• index를 integer로 바꾸는것 -> text * k

1-3

• dna 복제는 2개 방향으로 밖에 진행될 수 없다(bidirectional)
• 갈라지는동안 okazaki fragment가 부분적으로 복제된다
• 그리고 마지막에 합쳐짐
• 방향(forward, backward)에 따라 mutation rate가 다름
• single-stranded DNA has a much higher mutation rate than double-stranded DNA
• cytosine rapidly mutates into thymine through deamination & deamination rates rise 100-fold when DNA is single stranded
• skew diagram
• skew(k): |G| - |C| for the first k nucleotides of genome(누적함수)
• skew 함수가 감소하다가 증가하는 부분이 oriC라고 추측할 수 있다

1-4

• Hamming Distance Problem
• hamming distance: number of mismatches between string p and q
• d-neighborhood: hamming distance가 d보다 작거나 같은 k-mer들
• skew diagram에서 감소-증가 바뀌는 부분이 반드시 oriC라고 할 수 없다. reversal때문에 genome이 부분적으로 바뀔 수 있기 때문

//Assignment 1

Rosalind - bioinformatics problems - overlap graphs

• fasta format: 헤더와 스트링이 있는 포맷

• Searching for Tyrocidine B1
• Translation은 genome의 어느 부분에서든 시작해도 된다
• Cyclic
• DNA->RNA
• Transcription 과정
• RNA Polymerase에 의해 진행됨
• RNA->Protein
• Translation 과정
• Ribosome에 의해 진행됨
• 하지만 ribosome이 억제됐을 때 합성되는 단백질도 있음. NRP synthetase에 의해 합성되는 tyrocidine
• Mass Spectrometer로 분자의 질량을 계산 -> 어떤 단백질인지 알아냄
• 1 Dalton = mass of proton/neutron
• mass of molecule = sum of protons/neutrons
• 단, 20개 아미노산 중 정수로 따질 경우 같은 질량을 가진 애들이 2쌍 있음 -> 18가지의 질량을 구분할 수 있음
• Mass Spectrometer
• 1. Theoretical spectrum을 구함
• 길이 n의 주어진 peptide를 순서에 따라 쪼개서 가능한 모든 subpeptide(1~n-1)의 mass를 구함
• 2. spectrum에 해당하는 peptide를 찾는다(Cyclopeptide Sequencing Problem)

—

• A Brute Force Algorithm for Cyclopeptide Sequencing
• 주어진 mass를 가지는 모든 가능한 peptide sequence를 생성하여 비교함
• 결론적으로 불가능하다. 왜냐하면 가능한 sequence의 수가 exponentially 증가하기 때문에
• 해결책: branch-and-bound
• Cyclopeptide Sequencing with Branch-and-Bound
• 주어진 spectrum중 57~186에 해당하는 mass를 골라 가능한 1-mer들을 구한다 -> 해당 1-mer들로 만들 수 있는 가능한 2-mer를 만든다 -> 2-mer들 중 spectrum과 일치하는 것들만 남긴 후 3-mer를 만든다 -> 반복
• 어떤 dataset에 대해서는 exponential 할 수 있지만 보통의 상황에서는 굉장히 빠름(증명되지는 않음)
• Adapting Sequencing for Spectra with Errors
• 실제 spectrum에는 error가 있을 수 있음. 있어야 할 mass가 없거나 없어야 할 mass가 있을 수 있음
• false masses: present in experimental spectrum, absent from theoretical spectrum
• missing masses: present in theoretical spectrum, absent from experimental spectrum
• 해결책: theoretical, experimental spectrum에 공통적으로 해당하는 mass만 추림 + LeaderboardCyclopeptideSequencing
• LeaderboardCyclopeptideSequencing
• 주어진 spectrum에서 정확한 1-mer들을 추려낼 수 없기 때문에(에러 가능성) 18개의 아미노산 mass 모두에 대해 따짐
• low-scoring peptide를 쳐냄(단, keep top N with ties)
• candidate이 없을 때까지 extend, cut 반복
• heuristic한 방법이기 때문에 precise하지 않고 correct solution을 miss할 가능성이 있음(진작에 쳐내진 branch 중 정확한 솔루션이 존재할 가능성)
• 실제 실험 결과 10%의 error가 있을 경우 제대로 찾았지만, 25%의 error가 있던 경우에는 정확한 답을 찾지 못함
• From 20 to More than 100 Amino Acids
• 실제 아미노산 중에서는 mass가 일정하지 않은 non-standard amino acid가 존재한다(Ornithine)
• 따라서 18가지의 mass말고 그냥 57-186에 해당하는 정수로 따지면 리더보드 알고리즘으로 10%의 에러가 있을 경우에도 제대로 답을 찾지 못함
• The Spectral Convolution Saves the Day
• 주어진 spectrum에서 어떤 mass pair의 차는 1-mer의 mass에 해당할 수 있음. 물론 아닐 수도 있음 => Spectral Convolution!
• 모든 mass pair의 차를 구해서 테이블에 나타냄
• 테이블을 보면 여러번 나오는 mass가 있을 것. 실제 spectrum에 해당하는 1-mer일 가능성이 높다
• ConvolutionCyclopeptideSequencing
• 주어진 sequence에 대해 spectral convolution을 진행 -> M most frequent mass에 대해 LeaderboardCyclopeptideSequencing을 진행
• 실험 결과 M=10일 경우 10%의 error, 25%의 error 두 경우에 대해 모두 제대로 나옴
• The Truth About Spectra
• 실제 mass spectrometer에서는 25%보다도 더 많은 에러 가능성이 있다…실제 스펙트럼은 100개인데 1000개가 나올수도 있음
• Beltway and Turnpike Problems
• 두 문제 모두 polynomial한 알고리즘이 밝혀지지 않음
• turnpike의 경우에는 pseudo-polynomial한 알고리즘은 증명된 바 있음
• 점의 개수에 대해 polynomial한게 아니라 segment의 길이에 대해 polynomial함

• From Sequence Comparison to Biological Insights
• sequence alignment의 중요성
• 길이가 다른 여러개의 sequence를 앞/뒤나 중간에 띄워놓아서 sequence간의 공통 부분을 찾아내는 것
• Cystic Fibrosis
• The Alignment Game and the Longest Common Subsequence
• dynamic programming을 이용하여 해결해야 함. genome의 크기가 크기 때문에
• 두개의 스트링을 비교하며 맞을 경우 match, 안 맞을경우 mismatch, 빈 공간을 넣을 경우 insertion 처리
• 하나의 스트링 입장에서 insertion은 다른 스트링에서의 deletion
• Longest Common Subsequence Problem이 됨.
• Input: 두개의 스트링
• Output: A longest common subsequence of these strings(unique 하지 않음)
• The Manhattan Tourist Problem
• Longest Path in a Directed Graph Problem(irregular grid)
• The Change Problem
• Input: integer money & array of positive integers(돈의 단위)
• Output: minimum number of coins with denominations(단위) that changes money
• Greedy 알고리즘을 사용하면 최적의 해가 되는 경우가 있음(우리나라 단위 시스템의 경우)
• 안되는 경우 Recursive한 방법을 쓰면 됨. 하지만 이 경우에는 동일한 항목에 대한 계산을 여러번 하게 된다는 문제점이 있음
• 해결책: 다이나믹 프로그래밍 - 한번 계산한 항목을 저장
• biology에서는 평균적으로 alignment가 잘 맞는것 보다 local하게 alignment가 완벽하게 맞는것이 더 중요할 때가 많다
• homeobox genes
• gap penalty
• multiple sequence alignment
• 비교해야 하는 sequence의 개수가 증가할수록 시간이 exponential하게 늘어나기 때문에 exact한 답을 구하기는 거의 불가능하고 approximation 할 수밖에 없음 - suboptimal solution
• profile을 이용
• asymptotic: 점근선의

• Which Yeast Genes Are Responsible for Wine Making
• diauxic shift: yeast가 자신의 metabolism을 바꾸는것(glucose를 먹고 살다가 주변에 없으면 ethanol을 먹고삼)
• diauxic shift가 발생하기 이전, 당시, 이후에 yeast의 gene expression을 관찰 -> 비슷한 behavior의 gene들을 clustering함
• clustering
• k-center clustering problem
• noise에 민감함
• 해결방법: maximal distance 기준으로 center를 정하던 것을 squared error distortion 기준으로 수정 => k-means clustering problem
• 하지만 k-means의 문제점 -> NP-Hard for k>1임 따라서 approximation을 하여 suboptimal solution을 구함
• lloyd algorithm
• k-means clustering 알고리즘
• 항상 converge함
• hard/soft clustering
• soft clustering: clustering with responsibility
• stiffness parameter를 통해 hard clustering-soft clustering의 정도를 조절할 수 있음
• From Coin Flipping to k-means Clustering
• clustering은 em(expectation-maximization) 알고리즘의 일종
• Hierarchical clustering
• k가 주어질 필요 없음

02 Motif finding

• greedy approach
• randomized approach
• gibbs sampling
• expectation-maximization

03 Graph for string reconstruction: Assembly

• overlap graph
• de Bruijin graph
• hidden Markov model for gene finding

04 Structural variations

• insertion/deletion
• translocation

—

• metagenomics
• string match
• genotype(유전형) vs phenotype(표현형)
• DNA sequencing
• sequencer를 이용하여 할 수 있다
• 실제 dna에서 ACGT string을 얻어내는 과정
• Assembly
• 100~200개 되는 base pair를 이어 붙이는 과정
• 현재 기술으로는 sequencer가 모든 dna를 처음부터 끝까지 읽지 못하기 때문에 조각조각 읽어 붙이는것임
• Motif finding
• Text mining for biomedical literature
• 실제 literature를 train하여 어떤 term과 어떤 term이 관련 되어 있는지 알아냄.

<How do we find motifs?>

• motif: 반복되는 string
• k-mer = k-word = k-gram
• (k, d)-motif: k-mer that appears in each sequence with at most d mismatches
• consensus: 각 인덱스에서 가장 빈도수가 높은 애들의 string
• consensus의 conservation 정도를 측정하기 위해 entropy를 사용한다
• entropy가 높을수록 conservation 감소
• EM(expectation maximization)
• k-means와 방식이 비슷함: 실제 데이터를 반영한 모델을 만듬 -> 모델과 데이터를 비교 -> 업데이트 -> 반복
• 20쪽: 그대로 implement하면 두가지 문제가 발생
• 0이 하나라도 있으면 0이 됨 => pseudocount 개념 도입
• 확률에 로그를 취해줘야함
• randomised motif search
• global max를 보장할 수 없기 때문에 여러번 시행함(local max를 여러번 구해서 비교)

<Expectation Maximization>

• 어떤 데이터가 어디에 속하는지(classification)하기 위해서는 모델을 만들어야 한다
• 모델을 만드는 가장 간단한 방법 -> normal distribution
• class 정보가 주어지지 않을 경우: EM을 사용하여 hidden variable/parameter를 estimate
• naive bayesian classifier
• 한 개체가 하나의 cluster를 정하는 데에만 사용되는 것을 hard clustering이라고 함 => 결과가 extreme해질 가능성이 존재
• 하나의 개체에 대해 어떤 cluster가 될 “확률”을 계산하면 됨 = soft clustering
• 20쪽 k-means clustering은 hard clustering의 예이다
• soft clustering: EM for Gaussian mixture

<Gibbs Sampling>

• randomized motif search와 다른점
• randomized motif search may replace all k-mers in a single iteration
• gibbs sampling replaces a “single” k-mer at each iteration -> sampling with more caution
• relative entropy
• background probability 개념을 이용
• minimize the entropy of a motif matrix
• maximize the relative entropy
• “은/는”, “~이다” 와 같이 많이 등장하지만 중요한 의미를 갖지 않는 string을 처리하기 위함

<Assembly Problem>

• overlap graph를 만들면 쉽게 해결할 수 있음
• a의 prefix와 b의 suffix가 같으면 edge로 연결
• 모든 node를 딱 한번씩만 방문하는 path를 찾는 문제가 됨(Hamiltonian path problem)
• k-mer 자체를 node에 대응시키지 않고 edge에 대응시킴 => de Bruijn graph
• node는 edge의 prefix(TAA일 경우 앞의 노드는 TA, 뒤의 노드는 AA)
• 노드의 중복을 허락하지 않음(중복이 나올 경우 합침)
• Eulerian path problem이 됨(모든 edge를 한번씩 거침)
• Eulerian graph: eulerian cycle이 존재하는 graph
• Eulerian cycle: balanced & strongly connected
• 실제로는 k를 보통 50으로 잡아서 해결한다
• 너무 짧을 경우: 중복 edge가 많이 발생
• 너무 길 경우: 한 node의 크기가 너무 커짐 -> 메모리 이슈
• edge 여러개일 경우 해결법
• node간 edge가 여러개일 경우에 어떤 edge를 선택할까 하는 문제가 발생하게 됨. 그런 경우에는 k+1 mer 그래프를 그림. unique path가 생길 때까지 k를 늘려간다
• paired composition
• 방향을 양쪽으로 해서 읽으면 뒷부분에 대한 정보가 추가적으로 생김 => 어떤 edge로 이동할 지 priority를 정해줄 수 있음
• maximal non-branching path
• 노드간 edge가 여러개인 경우 그냥 그래프를 따로 나눈다. => 결과로 나온 여러가지 그래프를 실험적으로 맞춰봄

<Hidden Markov Model(HMM)>

• Markov chain
• trainsition probability를 고려한 모델
• inhomogenous Markov chain
• different distributions at different positions in the sequence
• ex) DNA sequence에서 맨 처음 위치에는 A가 올 확률이 높고 두번째 위치에는 낮고… 등등 이러한 정보를 반영
• MLE(Maximum Likelihood Estimators)
• CpG island
• ~ island: ~가 많이 있는 부분을 비유적으로 의미함
• dna 서열에서는 보통 gene이 등장하기 전에 CpG island가 많이 있음
• Hidden Markov Model
• state, state 내의 symbol, transition probability, emission probability를 정의한다. 어떻게? 데이터를 학습시켜야함!
• 어떤 종류의 problem을 해결할 수 있을까
• how likely is a given sequence?(forward algorithm)
• 길이가 같은 sequence들의 모든 조합 중 특정 sequence가 나올 확률(결론적으로 state를 고려함)
• what is the most probable path for generating a given sequence?(viterbi algorithm)
• 어떤 sequence가 주어졌을 때 그 sequence의 state 변화를 예상
• how can we learn the hmm parameters given a set of sequences?(forward-backward(baum-welch) algorithm)
• viterbi algorithm은 꽤 fair하게 state변화를 감지 할 수 있지만 정확하게는 감지할 수 없을수도 있다. 따라서 이런 경우에는 state 모델을 잘 설계하는것이 효율/성능을 높일 수 있다.

<How Do We Locate Disease-Causing Mutations?>

• Combinatorial Pattern Matching
• genotype-phenotype(표현형)간 관련성을 연구하는 것이 중요
• read mapping: reference genome에서 어떤 부분이 read와 대응되는지 찾는 것
• Trie: 그래프 자료구조의 일종
• store pairs of keys and data
• represent a collection of strings whose edge has a character
• suffix tree: trie를 compression한 것
• burrows-wheeler transform
• genome을 run-length encoding이 가능한 형태로 만드는 transform
• run-length encoding: aaaabbbccc -> 4a3b3c

• assignment 0:  virtualbox랑 ubuntu(14.04) 다운받기

OS Basics

• Von Neumann architecture = CPU + Memory + Storage
• CPU = Register + PC + ALU 

“Three Easy Pieces” -  Virtualization, Concurrency, Durability

• Virtualization: The OS takes the physical resources and transforms into virtual form of itself(OS is often referred as virtual machine)
• Concurrency: multi-thread
• Durability: surviving failure(persistence)

When a program runs:

Fetch -> Decode -> Execute

• c에서 volatile을 쓰면 해당 변수에 접근할 때 마다 캐시 대신 메모리에 접근한다
• SSD: solid-state drives

• data abstraction 
• procedural abstraction
• lazily: on demand = not executed unless necessary
• memory load를 on demand로 한다
• 48쪽 memory 그림 사실은 거꾸로임 code(text)맨 아래, 그 위에 data, heap, 맨 위에 stack. stack은 밑으로 쌓이고 heap은 위로 쌓인다
• 49쪽 64bit architecture. 
• bss segment: guard page. 
• kernal space에는 접근할 수 없다
• process는 3개의 state를 가지고 있다 - running/ready/blocked
• 53쪽 실제 register context used by the xv6 kernel
• 54쪽 proc에서 중요한 것: mem, proc_state, parent, context, tf
• 57쪽에서 return value빼고 parent에서 child로 모두 복사됨. child의 return value(address)는 0임! -> parent와 child 구분법
• %>/.program의 parent: bash

OS는 physical CPU를 time sharing을 이용해서 공유해야 한다. 이 때 고려해야할 것 두가지는:

1. performance
2. control

68쪽의 경우 run이라는 행위가 언제 끝날지 모르기 때문에 문제이다. (ex)infinite loop

+ 다른 프로그램에서 io를 access할 수 없음

kstack - kernel의 stack. 8kb

1. esp는 stack, eip는 code(text)를 가리키고 있다.
2. write()를 실행하면
3. eip는 kernel space, esp는 kernel stack을 가리킨다.

• 자원을 필요로 하는 프로세스에 자원을 배정해주는 것
• 스케줄링의 성능을 판단하는 기준:  turnaround time, fairness
• FIFO(FCFS)
• Convoy effect때문에 문제가 생김: 맨 처음 도착한 것이 엄청나게 오래걸릴경우
• SJF(Shortest Job First)
• 짧은 job들이 긴 job 실행 중에 도착할 경우 문제가 생김
• STCF(Shortest Time-to-Completion First)
• A가 실행되던 중 더 짧은 것이 도착하면 짧은것을 먼저 실행하고 A의 나머지는 그 다음에 실행함
• 스케줄링 성능 판단의 새로운 기준! response time
• 처음 schedule된 시간 - 도착한 시간
• 앞에 job이 있을 때 현재의 job이 길다고 맨 나중에 실행해버리면 답답할것이다. 적은 amount의 response라도 해야함
• 이전의 스케쥴링들은 response time이 안좋음
• RR(Round Robin)
• 하나의 job을 time slice로 잘라서 실행
• response time 훌륭
• 어떤 system이냐에 따라 적절한 size의 time slice가 필요
• 너무 작을 경우 response time은 좋지만 context switching 할 때 오버헤드 발생
• 너무 클 경우 반대의 장단점.
• real-time system의 경우 슬라이스를 작게하는것이 좋다 ex)미사일
• Incorporating I/O
• I/O가 개입될 경우 CPU 활용도를 최대한으로!
• Multi-Level Feedback Queue(MLFQ)
• priority마다 queue를 만듦. 내부에서는 rr실행
• 예) 어떤 job이 CPU를 오래 점령하고 있으면 priority를 낮춤
• CPU를 오래 사용하지 않는 interactive job은 priority를 높은곳에 둠
• 만약 interactive job이 엄청 많다면 long running job은 실행되지 못할것이다 -> starvation
• 90%정도 완료될 경우 yield하면 됨
• rule 5: 주기적으로 boost 진행(모든 프로세스를 맨 위의 queue로 이동)
• Proportional Share
• job이 필요로 하는 resource를 수치로 나타낸 후 퍼센트를 부여한다(CPU 점유 시간의 비율)
• Stride Scheduling(보폭 스케줄링)
• (A large number)/(the number of tickets of the process)
• 보폭은 스케줄링 대상을 의미한다

//과제2 String Scheduling + MLFQ 

• OS가 각 프로세스에게 가상의 memory space를 제공 -> 각각의 프로세스마다 CPU를 가지고 있다고 볼 수 있음
• 이전에는 메모리에 한번에 하나의 프로세스만 할당될 수 있었음. 효율성 .. 참담
• 그래서 Multiprogramming과 time sharing이라는 것이 나옴.
• 메모리에 여러개의 프로세스를 조금씩 할당하는 것
• 하지만 protection issue를 초래할 수 있음..
• 자기가 아닌 프로세스에 접근 가능할 수 있어서 다른 프로세스를 손상시킬 수 있다
• protection issue를 어떻게 resolve 하느냐
• 프로세스마다 address space를 만듬
• 실행되고 있는 프로세스에 관한 모든 정보를 포함하고 있는 애(program code, heap, stack 등)
• 힙은 아래를 향해 쌓이고 스택은 위를 향해 쌓이는 이유
• 둘 다 dynamic하게 쌓이거나 없어지기 때문에 딱딱 나누어 같은 방향으로 쌓이게 하면 비효율적일 수 있다
• Memory API
• malloc()
• system call이 아닌 library function이다
• free()
• new()
• delete()
• 포인터는 스택에 저장됨
• string을 allocate할 때는 \0자리까지(1byte) 해서 malloc해야함. 안그러면 string의 끝이 어딘지 알수 없으니까
• Memory Leak
• “valgrind”: 메모리 leak되는 곳을 찾아주는 프로그램
• unused code를 free해주지 않으면 메모리에 계속 쌓여서 메모리가 다 차면 프로세스가 죽어버림
• malloc은 brk라는 system call을 사용한다
• 그래서 직접 brk/sbrk를 사용하면 안됨! malloc이나 free 자신이 스스로 하기 때문에 따로 하면 충돌할 수 있다
• brk는 프로그램의 break를 확장할 때 쓰인다
• break: address space내의 heap의 끝 주소
• good memory allocation -> jemalloc.so 또는 tcmalloc.so  (so: shared object)
• LD_PRELOAD = “/usr/(local/)lib/libjemalloc.so._
• 이렇게 하면 lib.c가 아닌 저기에 define 되어있는 function들을 대신 사용함
• main호출 전에 실행하고 싶은 것이 있을경우 library에 정의하고 LD_PRELOAD에 메인함수 전의 directory에 해당 library를 정의해놓으면 된다
• LD_PRELOAD는 굉장히 고급스킬임
• Address Translation
• 프로세스가 가진 address space안의 local address(0~16kb)는 실제 physical memory안의 address(0~64kb내의 어떤 16kb만큼의 space)와 다르기 때문에, 두개의 address를 서로 바꿀 수 있어야함
• OS는 이 작업에 최대한 관여를 안하는 것이 좋음. 하드웨어로 처리하는 것이 가장 빠르기 때문에
• Assumptions
• 1) user의 address space는 memory에 연속적으로 위치해 있다
• 2) address space의 크기는 memory의 크기보다 작다
• 3) 모든 address space의 크기는 같다
• Hardware-based Address Translation(Dynamic Relocation)
• 하드웨어가 virtual address를 physical address로 번역한다
• 소프트웨어(운영체제)만을 이용하여 번역하면 아주 오래걸리기 때문에 하드웨어의 도움이 필요하다
• 34쪽에서 5번 번역해야함. 아주 비효율적.
• base and bounds register를 이용!
• address space에서 bounds register라는 것을 가지고 있게 한다
• bounds register: 내 address space의 크기 (or +base)
• physical memory에서 base register라는 것을 가지고 있게 한다
• base register: 해당 address space가 시작하는 위치 
• base부터 bound만큼의 address space가 있다는 것을 알 수 있다. (Virtual Address + base = Physical Address)
• 이렇게 하면 translation 자체에는 OS가 관여할 필요가 없게됨. base만 CPU가 알아서 더하면 되니까
• 단, OS가 꼭 관여해야 하는 부분이 있음
• process가 시작할 때: physical memory에서 address space를 위한 공간을 확보할 때 -> free list를 찾음(사용되지 않고 있는 physical memory의 범위)
• process가 끝났을 때: 
• context switch가 발생할 때: PCB에 base-and-bounds pair를 저장해야 함
• process당 하나의 base and bound를 쓰는 것의 단점
• 비효율적이다 왜냐하면 heap과 stack사이에 free(unused) space chunk가 생기게 됨
• Segmentation: 따라서 한 process의 code, heap, stack마다 각각의 base and bound를 생성!
• virtual address를 두 파트로 나눔: segment와 offset으로.
• segment: address space내의 code인지, heap인지, stack인지 indicate하는 부분
• 왜 segmentation fault라고 하냐: 나에게 허용된 segment의 base와 bound를 넘었기 때문에
• hardware support
• 각 segment가 어떤 방향으로 자라는지 알고있어야 함
• read/write/execute등 각 segment가 어떤 작업에 허용될 수 있는지 알아야 함
• bound를 absolute값으로 잡으면 메모리를 더 차지하게 됨

• finding a free chunk of memory that can satisfy the request and splitting it into two: when request for memory allocation is smaller than the size of free chunks
• 링크드리스트를 이용하여 관리
• 실제 메모리의 bound말고 주소공간의 heap을 증가시키고싶다. 그것이 미덕
• Coalescing
• free list의 여러 node들을 하나의 node로 합치는 것
• free list의 node들이 contiguous할 때만 coalescing할 수 있음. 만약 떨어져있으면 안 free한것들까지 포인터를 다 바꿔줘야하는데 이건 불가능에 가깝다
• free(void *ptr)
• 어떻게 free해 줄 포인터의 size를 아느냐???
• malloc으로 메모리 할당해줄 때 요구한것보다 조금 더 해서 size 정보 등을 저장해놓기 때문에 거기서 알 수 있음
• magic number: 현재 사용되고 있는 process인지?
• Segregated List
• Slab Allocator
• on demand하게(free list에서) 말고 같은 size의 cache를 미리 allocate하여 요청이 있을때 바로바로 제공 (kmem_alloc/ kmem_cache)
• Buddy Allocation
• Binary Buddy Allocation
• free space를 계속 반으로 나누어 요청된 메모리를 수용할 수 있는 최소한의 space를 제공
• coalescing할 때 나의 buddy만 check하면 됨

• essence of memory virtualization
• Segmented Architecture
• 장점: address translation이 빠르다(하나의 adder logic이면 가능)
• 단점: 
• 외부단편화(요청한 메모리 양에 비해 segment가 너무 작아서 안들어가는 경우)
• 내부단편화(제공된 메모리 양이 모두 사용되지 않아 낭비될 경우)
• Swapping 옵션 제한
• segment가 작을수록 fragmentation이 적게 일어남. 그럼에도 불구하고 엄청 작게 하지 않는 이유는 process에 대해 segment를 관리하기가 어려워지기 때문이다
• Page: multiple fixed-size segments with mapping table
• process의 address만을 나누지 말고(segmentation) physical memory space도 나누자
• page table은 process마다 생성됨 -> context switch가 일어날 때마다 base-bound pair도 저장해야하기 때문에
• 장점: flexibility + 
• free space를 squeeze 할 필요가 없음. 그냥 사용할 수 있는 페이지를 보고 제공하면 됨.
• Address Translation
• page number + offset
• Page Table은 handle 하기 어려울 만큼 커질 수 있음
• 그걸 address space에 저장??? 안돼…
• Physical memory에 저장하고 process마다 어디에 저장했는지 기억한다.
• PTBR(Page Table Base Register)(=CR3) 레지스터는 자신의 페이지 테이블의 base(처음)를 가리킨다.
• 뭘 하려면 PTBR이 가리키는 곳에 가서 어딘지 보고 그 주소의 메모리에 가서 정보를 가져옴..50 cycles…too much memory reference->MMU(Memory Management Unit)로 해결!
• MMU에는 TLB라는 것이 있어서 mapping table의 cache로 작용한다. Memory-Address간 translating 없이 아주 적은 cycle로 해결 가능
• 실제 주소 = CR3 + VP# * 4byte
• page table을 효율적으로 만들어야한다. 모든 page에 대해 64bit 안에 맵핑할 수 있도록
• code, stack, heap에 page 하나씩 세개의 페이지면 충분하다
• 페이지 테이블에 존재하는 flag:
• valid/protection/present/dirty/reference bit
• 페이징의 문제점:
• extra memory access
• memory utilization for page table
• 46, 47쪽:
• edi -> &array[0]
• edx -> i
• 4 -> &(array + i * sizeof(int))
• array는 위쪽 주소에 있다(4만) 왜냐하면 function 내부(stack)에 정의되어있기때문에
• 그래프의 의미: paging때문에 memory access를 한번 더해야한다(page table 한번+실제 값을 fetch하기 위해 한번)

• 프로그램 실행 시간은 clock cycle 속도보다 cache에 의해 결정된다
• vpn: virtual page number

• multiple execution flows within a process
• 실행 단위: thread
• 각자의 program counter와 register를 가지고 있다
• address space가 바뀌지 않기 때문에 process간의 context switching 보다 빠르다

• race condition(=data race)
• 여러개의 스레드/프로세스를 동시에 돌릴 때 같은 변수를 수정하면 그 여러개만큼 수정되지 않을 때
• atomicity를 보장하기 위해 lock을 이용하여 임계 영역을 지정해주어야 함

• performance가 증가했다가 유지되지 않고 감소하는 이유(spinlock에서)
• 1. convoy effect
• t1이 락을 가지고있으면 다른 스레드들도 cpu를 사용(burn)하고 있지만 t1락이 풀릴때까지 뭔가를 process 할 수 없다. 따라서 이 경우에 멀티쓰레드 상황은 performance를 worsen할 뿐이다
• 그래서 critical section는 적으면 적을수록 좋다
• lock holder인 t1에게 cpu시간을 많이 주어서 언락을 빨리 할 수 있게 하면 좋다
• 2. cache invalidation
• 락홀더가 캐쉬에 있는 값을 바꾸면 다른 쓰레드들에게 값을 똑같이 바꾸라고 보내는 메시지. 메시지가 있는 동안에는 process를 할 수 없음
• 하드웨어의 메시지 (메모리 버스)
• moesi, mesi protocol
• Thread API
• process의 시작은 fork. thread의 시작은 start_routine
• join: 어떤 스레드가 끝났는지 안끝났는지 알 수 있는 방법
• BSP(Bulk Synchronous Processing): 한 태스크를 여러 스레드로 돌리고, 다음 태스크로 갈 땐 이전 스레드들이 모두 끝났는지 확인해야함
• trylock(lock이 되어있으면 failure, 안되어있으면 락 - opportunistic locking), timelock(일정시간 이후 락을 풀음)
• condition variables: thread의 상태를 나타냄(wait(=sleep)/signal(=wake))
• 락 안에서 자면 안됨. 아무도 깨울수가 없음…
• 그래서 락 안에서 잘 경우 바로 락을 풀어야함

• 두가지 상태가 있다: available = unlocked, acquired = locked
• pthread는 lock에 관련한 여러 api를 제공한다
• interrupt는 현재 execution flow를 방해할 수 있는 최상의 priority를 가진다
• lock에서 interrupt를 disable한다? 안됨. 다양한 문제가 발생한다
• atomic instruction을 사용하는 애와 안사용하는 애가 shared variable을 사용하기 원하면 atomicity를 보장할 수 없음. 따라서 모든 instruction이 atomic하도록 주의해야함!!
• 만약 어떤 variable이 발생하는 곳에 락을 걸면 그 variable이 나오는 모든 코드 부분에 똑같이 락을 걸어야함
• ticket lock에서 발생할 수 있는 문제: 같은 번호의 티켓이 두개의 프로세스에 발급될 경우(티켓 발급이 atomic하지 않을 경우)
• spinlock 해결방법
• spin하려고 할 때 yield한다
• context switch 비용 발생
• 따라서 critical section이 작을 때는 spin waiting 하고 클 때는 yield하면 좋다
• sleeping
• 이것도 주의할점이 있음. 영원히 잠드는 애가 발생할 수 있다
• futex
• 영원히 잠드는것을 방지
• two-phase locks
• lock을 두 단계(phase)로 나눔

• file = named permanent storage
• data와 metadata를 포함하고 있다
• directory
• collection of files/directories
• file system은 logically continuous하고 physically spread하다. process에서의 page table처럼
• file allocation table(FAT)
• “direct” mapping table
• allocation 작업이 O(1)이기 때문에 아주 빠르다는 장점이 있다
• direct하기 때문에 search는 오래걸림(linear time)
• 따라서 general purpose에 적절하지 않음
• Inode
• fat와 달리 direct하지 않기 때문에 서치가 비교적 빠름(logarithmic time)
• mmap: system call로 하지 않고 memory operation으로 실행. a few cycle 뿐이기 때문에 시간이 아주 절약된다
• file system을 durable하게 만드는 방법
• write하는 것을 자주 저장(survive in short term)
• 데이터를 오래 저장할 수 있게 함
• 데이터를 여기저기 복제해놓아서 independence of failure를 보장

• RAID(Redundant Arrays of Inexpensive Disks)
• level이 올라갈수록 redundancy가 증가
• level 0: striping
• 라운드로빈을 이용하여 여러 디스크에 block을 나누어 저장
• performance와 capacity가 훌륭함
• 그림에서 (0,1,2,3)을 하나의 stripe set이라고 한다
• 실제 field에서 아주 기본적이고 중요한 technique
• no redundancy
• level 1: mirroring(=replication)
• redundancy가 존재하기 때문에(같은 data를 여러번 저장) 시간이 오래 걸린다
• level 4: saving space with parity
• 하나의 디스크를 추가하여 같은 stripe set에 있는 정보를 해당 디스크에 저장
• level 5: rotating parity
• parity block을 하나의 디스크가 아니라 전체 디스크에 돌아가며 저장
• 보통 0+1을 합쳐서 사용한다

The Turing test is a test, developed by Alan Turing in 1950, of a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human.

• Unintelligent human behavior - 기대값이 -임에도 불구하고 복권을 사는 행위
• AI는 어떻게 보면 moving target이다 - OS가 AI로 불리던 시절도 있다.
• lisp: programming language
• 여러 technology의 collaboration 결과가 바로 deep learning이라고 할 수 있다 - 소프트웨어, 하드웨어..
• Modeling -> Algorithms의 두 단계로 real-world task를 tackle한다.
• 무엇을 풀지 정하고, 어떻게 풀지 정한다. 그 과정에선 어느 정도의 abstraction이 필요함.
• reflex-based model < state-based model < variable-based model < logic-based model 등 여러가지 모델이 있다 (low-level -> high-level 순)
• 각 모델마다 풀 수 있는/풀기 쉬운 문제의 종류가 다름
• what을 정할 때 computing이 가능할 지 안할지 고려해야 함. 따라서 how보다는 what이 대개 더 어려운 문제이다
• Learning algorithm내에서 example을 학습하고 generalization을 해야 의미가 있다. 그냥 예시만 학습(단순 암기)하면 머신러닝이 아님. 의미가없다.
• 31쪽 그림에서 node 하나하나를 각각의 state라고 한다
• 하나의 state에서 다음 state로 가는 순서가 중요한 경우에 state-based model을 사용한다. sudoku의 경우에는 그렇지 않음. 그래서 variable 측면에서 문제를 해결하는 것이 바람직함.
• 37쪽 hard constraints의 의미: 반드시 만족해야 하는 것으로 하나라도 만족하지 않으면 solve된 것이 아님.
• 반면 Bayesian network에서 soft dependencies의 의미: H1을 1분마다 차의 위치라고 하면, 여기서 위치는 반드시 만족하는 것이 아닌 단지 확률의 문제일 뿐이다
• 40쪽: 해당 문제를 variable-based 모델로 해결하려면 student를 하나하나를 variable로 표현해야하기 때문에 비효율적이다.
• 모델끼리 concept을 합쳐서 구현하는 경우도 있다

• feature를 어떻게 설계하느냐에 따라 전체 설계의 성능이 달라진다. 가장 중요한 부분
• raw data보다 feature를 더 크게 사용하는 경우는 없다 왜냐하면 raw data가 주어진 데이터의 총량이기 때문
• production system: production rules로 이루어진 시스템.
• if-then으로 이루어져있다

• 숫자판 문제에서 가능한 9!개의 상태를 하나의 노드로 생각 하면 9!개의 노드를 가진 그래프라고 생각해서 풀면 됨 - 스테이트 마다 각각 연결할 수 있기 때문 - 하지만 여기서 문제는 3*3, 4*4는 가능하지만 5*5는 불가능하다. 너무 크기 때문에
• 숫자가 움직이느냐/blank가 움직이느냐 의 차이: 32개의 액션/ 4개의 액션
• 9!개 노드가 있는 그래프를 스태틱하게 계속 가지고 있으면 비효율적임. 다이내믹하게 그때그때 필요한 부분만 빌드해서 쓰는게 중요하다 -> implicit representation
• start state는 주어질 수도 아닐수도 있다. 따라서 알고리즘 내에서 start state를 정의할 수 있어야 함
• state를 expand한다: 하나의 상태에서 다음 상태로 가능한 상태들을 계산하는 것
• 15쪽의 수도코드는 expand만 하고 지우는게 없음. 
• 20쪽의 수도코드는 좀 더 refined된 버전
• fringe: expand되지 않았지만 expand되기 위해 대기하고 있는 노드들의 집합
• goal인지 아닌지는 fringe에 들어갈 때가 아닌 dequeue 될 때(해당 노드를 expand 할 때) 판단한다
• state와 node를 혼용해서 쓰는 경우가 많다. 
• “node는 어떤 state를 나타내기 위한 것”
• search stretegy의 평가 기준
• time complexity: 만들어지는 노드의 총 수
• space complexity: 어느 한 “순간”에 메모리에 있는 최대 노드의 수. 전체 프로세스에서 만드는 총 노드의 수가 아님
• 두가지 complexity는 b,d,D의 세가지 변수로 계산할 수 있다
• b는 트리의 차수
• 23~ 26쪽 fringe의 queue (breadth-first search)
• A
• BC
• CDE
• DEFG
• 같은 레벨의 노드들(successor)간의 순서는 상관 없다
• 28쪽 
• time?: b(b^d-1) 은 트리의 d레벨의 마지막노드가 goal일 경우이다.
• 그럼 goal test를 fringe에 들어갈 때 하면 안되냐? 된다. 더 효율적임 breadth-first search에서만. 일반적인 경우에는 fringe에서 dequeue될 때 goal test를 해야 편하다 => exponential
• space?: 각 레벨에서의 노드들만 저장하고 있으면 된다. 부모 노드들(goal test가 끝난 노드들)은 잊어도 됨 => exponential
• optimal?: 가장 shallow한 노드에 대해 goal test를 먼저하기 때문에 yes.
• 29~40쪽 fringe의 stack (depth-first search)
• A
• BC
• DEC
• HIEC
• IEC
• EC
• JKC
• KC
• C
• so on
• 같은 레벨 노드 순서 역시 상관 없다
• 레벨을 계속 내려가다가 더 이상 갈 곳이 없으면 다음꺼… 반복
• 그림상에는 모든 노드가 있지만 까만색으로 색칠된 노드들은 스택에서 빠져나갔기 때문에 실제 메모리상에는 존재하지 않는다.
• 41쪽
• complete?: infinite loop에 빠질 가능성 존재
• time?: 최적의 경우 한번에 찾을수도 있지만 최악의 경우 모든 노드를 찾아봐야 할수도 => exponential
• space?: 최악의 경우 - 하나의 경로(D) * 나의 sibling(b-1) (가장 깊은 레벨의 첫번째 노드에서) => linear
• depth-first의 장점(메모리)을 살리며 단점(optimality)을 보완하는 방법: depth-limited search
• 42쪽
• limit l을 optimal depth로 정하는 것이 가장 좋다
• 하지만 optimal depth는 항상 알려진 것이 아니기 때문에 그런 경우에는 l을 작게 해보고 점점 늘려나가면 찾을 수 있다 -> iterative deepening
• limited search를 할 때 l의 범위 내에서 찾지 못하면 맨 위의 노드부터 (맨 처음부터) 다시 한다. overhead가 발생할 수도 있지만 overhead를 방지하기 위해 그 레벨의 노드를 모두 저장하면 결국 depth-first의 장점인 linear 메모리의 의미가 없어짐
• 43쪽 
• 이 그림에도 역시 스택에서 빠져나간 노드들이 그려져 있음. 실제 메모리에는 없다!
• backtracking: 하는것 처럼 보이지만, 실제 메모리는 그렇지 않음
• 44쪽
• chronological backtracking: 완전히 expand되지 않았지만 시간상 가장 최근에 만들어진(스택에 들어간) 노드로 backtrack하는 것

• 50쪽 Nids = O(b^(d+1))
• time에서 11%의 오버헤드가 발생하지만 그만큼 메모리라는 장점을 안고간다는 것에 의미를 둔다

• 51쪽 expand할 때 goal test를 해야하는 이유. link마다 cost가 있으면 더 깊은 node가 optimal goal일 수 있기 때문
• complete?: step cost가 양수나 0인 이유는 0인 루프가 있으면 infinite loop가 생길 수 있기 때문이다
• time?: C*/e 인 이유는 link 그대로 따지지 않고 step cost로 나누어서 단위 단계로 생각. (5면 1+1+1+1+1 이런식)

• 54쪽 기존 알고리즘과 다른 점은 closed에 기존 노드들을 저장. 이전 알고리즘들에선 지나간 노드들은 기억할 필요가 없었음

• heuristic function: 내가 얼마나 빨리 goal에 도달할 수 있는지 나타내는 함수. cost가 얼마나 남았는지. 지나온 길은 생각하지 않음. 
• 넓은 의미의 heuristic function은 evaluation function이라고 할 수 있다. 
• 숫자판 예시에서의 heuristic은 단지 추정값이고 정확하게 실제 “앞으로 얼마 남았는지”는 알 수 없다. 실제로 보면 7쪽에서 보면 5에서 6으로 간다. 따라서 그걸 따라가서 반드시 goal을 찾는다는 보장은 없다.
• 8쪽에서의 fringe는 min heap라고 생각하면 됨
• 9쪽 Greedy best-first search
• goal에 가장 가까운것 같은 node를 따라감
• Not complete라는 말 무시. 뒤에 보면 complete하다고 나와있음!
• 여태까지 본것중에 가장 비효율적인 알고리즘 같아 보인다. time과 cost를 보면
• A* search
• gb-f search가 왜 비효율적이냐면 여태 온거에 대해서는 다 까먹기 때문. 따라서 그것도 계산에 포함하면 꽤 효율적인 알고리즘을 찾을 수 있을것이다 그게 바로 a*: f = g + h
• h를 0으로 잡으면 UFS와 동일 => heuristic search라고 안한다
• 11쪽 마지막 조건: h*는 실제거리. 이 조건을 만족하는 그래프를 admissible heuristic이라고 한다
• 9쪽의 그래프에서 오른쪽애(h=4) 때문에 a* search를 쓸 수 없음
• 19쪽 앞의 핖티와 같은 알고리즘인데 expand부분이 좀 더 복잡
• successor가 처음 만드는 애면 값을 그대로 저장
• 이미 있으면 새로 계산해서 minimum한 것을 저장
• goal state의 h*값은 항상 0
• 21쪽 G는 9+0이고 C는 8+3=11이므로 둘을 비교함. G를 먼저 expand하려고 하던 중 goal test를 했는데 goal이니까 C는 expand 안하고 끝남
• h*는 우리가 아는 값. h는 정확히 알지 못하고 단지 추정하는 값일 뿐이다
• g는 expand하면서 구하는것이다. 처음부터 알려진게 아님
• 23쪽은 gbf서치를 이용하여 optimal path를 찾지 못한 예이다
• 24쪽은  a*를 이용하여 optimal path를 찾음
• 25쪽의 OPEN은 fringe임
• 둘째줄에서 h가 admissible(h* >= h)하다고 f* >= f라고 할 수 없음.
• 저렇게 말할 수 있는 이유는 f가 단조증가 하기 때문 
• admissible하면 단조증가한다(삼각형 공식)
• 어떤 노드든 expand할 때(fringe에서 뽑힐 때)에는 그 노드의 g가 optimal하다. 
• 28쪽 IDA*는 cutoff(limit)을 f로 한다
• A*는 좋아보이는데로 가면서 다 펼쳐본다면 RBFS는 가다가 아닌것같으면 backtrack해서 그 경로에 대한 정보를 기록함
• RBFS는 IDA*보다 시간을 조금 더 많이 쓰는 대신 메모리를 적게 쓴다
• SMA*: simple memory bounded a* 
• 내가 사용할 수 있는 메모리를 다 ㅏ사용함. 단 그 이상이 되면 RBFS처럼 backtrack함(가장 메모리를 많이 차지하는것을)

• 그럭저럭 괜찮은 알고리즘
• 3쪽에서 hill의 가장 높은 곳(evaluation 값이 큰 곳)으로 올라가는 것이 목표 
• 지금보다 낮은 곳으로는 가지 않고, 경사가 가장 높은 곳으로 감
• 따라서 내 주변에 낮은 곳만 있을 때 종료됨 -> local optimal은 찾을 수 있지만 global optimal은 못찾을 수도 있음.
• random restart: 한번 search가 끝나면 random한 위치에서 다시 search를 진행함 (존재할 수도 있는 global optimal를 찾기 위해)
• 7쪽 simulated annealing search
• hill climbing search처럼 낮은 곳은 아예 제외하는게 아니라 확률적으로 낮은 곳으로 갈 수도 있음
• T = f(t)
• T는 temperature, t는 time, f(x)는 정하는 것
• next 위치를 랜덤으로 설정하여 현재보다 높으면 가고, 낮으면 확률을 따져서 가거나 가지 않음 
• 확률 공식을 보면 온도가 낮을수록 optimal에서 멀어질 확률이 적게 설계되어있음. 그리고 e에 대해 exponential하니까 처음에는 많이 헤메고 확 떨어져서 오랫동안 조금씩 헤매게 함 (꼭 나와있는 공식대로 쓸 필요는 없음. design issue!)
• 온도를 천천히 낮추면 global optimal을 찾을 확률이 높음
• 이론상 온도를 무한히 천천히 낮추면 global optimal을 찾을 수 있다
• 너무 복잡한 문제가 있을 때 어려운 솔루션을 찾는 대신 지푸라기 잡는 심정으로 아주 단순한 위의 알고리즘을 이용할 수 있다
• propositional satisfiability: 주어진 논리식에 0 또는 1을 대입하여 결과가 1이 나올수 있게 할 수 있는지 여부 -> SAT solver를 이용해서 해결할 수 있음 

• 앞에서 배운것들과 달리 예측 불가능한 요소가 존재한다: 상대의 움직임, chance
• ply: 플레이어 하나의 차례. 2 ply = 1 move. move가 하나의 의미있는 단위임
• utility: 하나의 terminal state마다의 효용성(승리/패배 혹은 얻은 돈/잃은 돈)
• 보통 첫 플레이어를 max라고 함. utility를 max의 입장에 따라 정하기 때문
• Minimax: min과 max 모두 best play를 한다고 가정. 즉 max의 입장에서 상대인 min은 가장 불리한 play를 함
• dfs
• b: branching factor/m: maximum depth
• ab pruning
• 18쪽 doubles solvable depth의 의미: depth는 m, branching factor를 루트b로 줄어듬. 그냥 minimax와 같은 시간(b^m)으로 계산 한다면 depth를 2m만큼 search할 수 있다.
• random ordering은 같은 시간 안에 (4/3)m만큼 search할 수 있다
• heuristics: 같은 depth의 node들에 대해서 해당 레벨에서의 max/min한 해를 기억하고 있다
• DFID할 때 이전 iteration에서의 max/min값을 기억하고 있음
• 19쪽: quiescence search - eval값이 dynamic하게 변하는 상황 말고 잠잠한 상황에서 cut off를 한다. (병사 잡히고 다음에서 말을 먹을 수 있는 상황/병사를 먹고 다음에서 말을 잡히는 상황)
• 정확한 값일 필요 없음
• Expectiminimax
• 정확한 값이 필요
• TDGammon은 알파고같은 백개먼 게임 프로그램임. 두 수 앞을 내다본다
• Games of imperfect information
• 카드게임처럼 상대의 패를 모르는 경우에는 모든 가능성에 대한 확률을 구할 수 있다. 

• CSP가 아닌 constraint가 없는 일반적인 dfs에서는 pruning을 하지 않음
• CSP는 dfs의 중간 단계에서 constraint를 만족하는지 여부를 통해 pruning이 가능하다는 점이 기존의 일반적인 dfs와 비교해서 하나의 장점이 될 수 있다
• expand하지 않고 constraint를 만족하는 애들만 자식으로 삼는다
• optimization을 할 때 주로 local search를 쓴다
• 10쪽에서 root노드에 4개의 자식을 다 하지 않는 이유: symmetric하기 때문에 두개만 해보면 된다
• 밑의 예시에서는 땅이 variable, color가 value
• Minimum remaining values
• 앞에서 배운 heuristic처럼 value를 선택하는 것이 아니라 MRV를 가진 “variable”을 선택함
• 가장 남은 값이 적은 variable을 선택
• Most constraining variable
• 다른 variable에 대해 가장 많은 영향을 미치는 애를 우선적으로 선택
• 13쪽의 예에서는 다른 면과 가장 많이 맞닿아 있는 애
• Least constraining value
• 남은 variable이 최대한 다양한 value를 가질 수 있게 하는 값을 가진 애
• variable은 failure를 빨리 찾는 방향(까다롭게), value는 constraint를 만족하는 방향으로 이동
• Backtracking 효율적으로 하기 위한 것들
• Forward checking
• 남은 variable이 가질 수 있는 value들을 기록함 -> 어느 하나라도 공집합이 되면 backtrack함(가장 최근에 한 assignment를 undo)
• Constraint propagation: 공집합이 되지는 않았지만 인접한 두개가 같은 색(파랑)이 남았으므로 failure를 detect하게 함
• Arc consistency: 모든 vi에 대해 어떤 vj가 constraint를 만족한다면  vi->vj는 consistent하다고 한다
• preprocessor이나 postprocessor로 이용될 수 있음
• 따라서 assignment가 발생하면 나를 쳐다보는 unassigned된 애들이 constraint를 만족하는지 모두 살펴봐서 아니면 안되는 value를 지워서 consistent하게 만들어야한다. 
• time complexity: O(n^2 * d^3) -> 최대 n^2개의 edge가 있을 수 있음 * edge는 queue에 최대 d번 들어감 * value하나에 대해 constraint를 만족하는지 확인하는 횟수(RM-Inconsistent-Values)는 d^2
• SAT는 가장 대표적인 CSP문제이다: variable이 가질 수 있는 value는 0또는 1, constraint는 식의 결과가 1이어야 한다는 것
• 경로문제에서 어떤 경로에 대해 consistent하다는 것(path consistency)은 보장할 수 없음. pair-wise로 계산하기 때문에.
• map coloring의 경우에는 preprocessor의 의미가 없음: 맨 처음에 아무것도 색칠되지 않은 상태에서는 inconsistent한 값이 없으니까
• chronological backtracking: 가장 최근에 했던 것을 undo하는 방식
• 26쪽: local search와 비슷해 보이지만 backtracking을 하면 heuristic repair이고 현 상태만 가지고 있으면 local search임
• CSP로 풀 수 있는건 대부분 local search로 풀 수 있음

//중간고사 CSP까지

1. TF

2. A* 수도코드 잘못된 것

3. 확률 Minimax

4. NQueens forward checking + Arc consistency

5. Forward Checking + Arc Consistency

• 예전의 번역기: 어떤 언어를 하나의 언어로 바꾼후 그것을 목표 언어로 바꿈
• 현재의 번역기: 목표 언어로 바로 바꿈
• 어떤 독립적인 기능을 수행하는 단위를 agent라고 한다. 사람일수도 로봇일수도
• 3쪽
• Performance Standard는 고정하는것이 일반적.
• Problem generator: 실제 문제가 아닌 자기가 스스로 문제를 만들어보고 풀기위한 노력을 함. 여기서는 무시
• 4쪽
• representation: 어떤 알고리즘을 이용하여 학습할 것인가의 문제
• 피드백의 종류 세가지: supervised - 각각의 예제에 대해 정답이 주어짐, unsupervised - 예제에 대한 답이 없음, reinforcement - 예제에 대해 상과 벌을 줌 occasionally

• supervised learning은 대부분 inducted learning이다
• data의 pair(입력과 출력)을 보고 f에 최대한 근접하는 함수(h)을 알아내는 것이 목표
• f를 정확히 알아내려면 모든 x에 대해서 y가 일치해야 하는데 실제 상황에서 x가 유한하지 않기 때문에 모든 x에 대해서 확인할 수 없음
• training set에 없는 x에 대해서도 결과를 내는것 -> generalization
• 뭐가 중요하다고 생각하느냐(outlier가 있다고 생각하느냐 없다고 생각하느냐 등)에 따라 8쪽의 세가지 그래프 중 어떤식으로 하는게 바람직한지 달라질 수 있다. 파란색이 100% 다 맞췄다고 무조건 좋다고 할 수 없음

• linear predictor에 대해 배움 -> neural network
• 10쪽에서 0일경우에는 +1/-1 중 하나로 붙이면 된다
• 2차원: 직선, 3차원: 평면, n차원: hyperplane

Loss minimization

• optimization
• margin = (w*phi)*y
• 똑같이 positive라도 0.5와 1의 confidence는 다르다고 생각한다.
• 음수값이면 틀림, 양수값이면 맞음. 절대값이 클수록 얼마나 맞았고 얼마나 틀렸는지 알 수 있음
• 16쪽: 1[어쩌구]는 어쩌구가 맞으면 0, 틀리면 1을 리턴하는 함수
• residual: 실제값과 예측값과의 차이
• square loss: residual 제곱
• classification할때랑 regression할 때 무엇을 중심으로 error를 정할지 달라짐(margin/residual)
• 22쪽에서 squared loss를 사용하면 y가 최소가 되는 w값은 0, 2, 1000의 평균이고 absolute deviation을 사용하면 y가 최소가 되는 w값은 2(0, 2, 1000의 median)

Stochastic gradient descent

• squared loss를 사용할 경우 w가 하나일때는 미분해서 0되는값 찾으면 됨. 여러개일때는 변수 하나당 편미분해서 0되는값 찾음
• gradient: 기울기
• gradient descent: continuous space에서 하는 경우가 많음.
• initialize의 의미: 다 0으로 하라는게 아니라 랜덤값 넣으라는말
• hill climbing과 다른점은 모든 방향을 고려하는게 아니라 training data가 알려주는 방향으로 감
• step size가 크면 클수록 학습을 얼마나 과감하게 진행하느냐가 달라짐 -> learning rate라고 부르기도 함
• 27쪽 공식에서 변수는 w뿐이다(x, y는 주어지는것) 따라서 objective function을 w에대해 미분한 것이 gradient임
• gradient descent의 문제점: data가 엄청 많으면 한 iteration을 할 때 data를 한번 스캔해야하는데 엄청 오래걸린다. 따라서 모두 계산한 뒤에 iteration을 하지 않고 tuple하나하나 볼 때마다 iteration을 함(결과가 똑같지는 않음) -> stochastic gradient descent
• decreasing step size: simulated annealing에서 temperature과 비슷한 개념
• zero-one loss
• gradient가 항상 0이기 때문에 SGD를 이용할 수 없음. optimization은 loss에 비례해서 진행되니까
• 위의 문제를 해결하기 위해 hinge loss function을 이용
• hinge loss는 zero-one loss의 upper bound이므로 zero-one과 추구하는 방향은 같음
• 0<x<1 구간에서도 학습이 발생함
• loss가 클수록 loss를 줄이려는 노력을 더 많이함. zero one의 경우에는 줄이려는 노력이 같음 항상 1이니까
• logistic regression
• 모든 구간에서 미분 가능함
• 항상 upper bound는 아니지만 전체적으로 문제는 없음
• margin이 1을 넘어도 학습을 진행함
• SGD의 terminal condition
• 고정된 iteration 횟수를 넘길 경우
• weight update가 멈출 경우(미미할 경우)

• 여러가지 linear predictor를 합쳐서 하나의 predictor를 만드는 것. 단 합친 것이 nonlinear할 수 있게 하는 요소를 추가
• 2쪽에서 한단계로 학습하던 것(x -> y)을 3쪽에서는 두단계로 학습함(x -> h1 + h2 -> y)
• >=가 바로 NN을 nonlinear하게 만드는 요소(thresholding)
• NN에서만 할 수 있는 일이 있음. XOR은 단일 linear classification으로 학습할 수 없다
• sigmoid함수: zero-one함수를 모든 점에서 미분가능하게 흉내낸 것
• 8쪽: 1.5, -0.5, 0.5는 threshold value를 나타낸다. 1, -1은 weight.
• NN에서는 gradient descent를 backpropagation method라고 부른다
• d: desire (원하는 값)
• s: weighted sum
• f: sigmoid 함수
• ε: error
• error가 원하는값과 실제값의 차의 제곱이라고 하면 error를 s에 대해 미분한 것은 -2(d-f)
• 결과적으로 gradient만큼의 error를 고침
• 10쪽: layer간의 connection은 모두 complete bipartite하다
• k-layer feedforward network라고 함(feedback 되지 않음)
• 회색부분은 hidden layer이다
• j번째 레이어의 i번째 unit을 나타내려면 j를 위에 i를 밑에 쓴다
• threshold함수를 정하기 위해 dimension을 하나 추가하여 1로 둠 -> 11쪽에서 m(j-1)+1에서 플러스 1이 되는 이유. 1을 위해 unit이 따로 만들어주는건 아님
• 14: j+1번째 레이어의 unit들의 델타를 이용하여 j번째 레이어의 i번째 unit의 델타를 구함
• 뒤에서부터 앞으로 가면서 델타값을 결정 => backpropagation
• 15: 0인 이유는 같은 레이어의 unit들은 서로에게 영향을 끼치지 않기 때문
• train instance 하나에 대해서 각 unit별로 결과를 계산 -> backpropagation으로 weight를 업데이트
• generalization: 유한한 train set을 통해 나온 네트워크로 무한한 경우에 대한 추정값을 구할 수 있다
• 18: 일곱개의 점에 대해 함수를 구한다고 가정
• 무조건 에러가 적은 경우(high-degree)가 좋은가?
• 아님. noise가 존재할 수 있고, train data는 일부에 불과하기 때문. 따라서 train set으로 함수의 accuracy를 측정하는 것은 잘못된것.
• 그럼 전체를 모르는 상황에서 어떤 함수가 바람직한지 알수 있는가?
• 주어진 training set을 두개로 나눔: training set과 validation set -> cross validation
• k-fold cross validation: 적어도 몇번 이상을 해야 의미가 있다. 한번 하는건 의미 없음
• overfitting: 비슷한 에러를 낸다면 낮은 차수의 함수(2차원보다는 1차원 함수)를 이용하여야 방지할 수 있다
• underfitting: 데이터의 복잡도를 충분히 보장하지 않아 너무 낮은 차수의 함수로 나타내려고 하는것
• 21: validation set error 감소하는 부분은 언더피팅에서 정상으로 가는 부분, 증가하는 부분은 정상에서 오버피팅으로 가는 부분
• 앞의 모델(NN, decision tree, linear predictor…)은 parametric model(데이터에 알맞은 파라미터를 찾는 학습).
• nearest neighbor은 non-parametric
• regression이 아닌 classification에 사용
• 그냥 내가 가진 train set중 가장 가까운 애의 class를 리턴
• generalization을 한다기 보다는 storage의 문제