본문 바로가기

Research114

P, NP, NP-Complete, NP-Hard, 시간 복잡도 # 아주 직관적인 설명P: 폴리노미얼 타임으로 완전한 정답을 구할 수 있는 쉬운 문제 NP: 임의의 값 하나에 대해서만 그것이 정답인지 아닌지 폴리노미얼 타임이하로 계산가능한 검산만 쉬운 문제보통 NP를 풀때는 휴리스틱 탐색 등의 계산적인 접근법을 사용한다. 위의 정의에서 P 문제는 애초에 폴리노미얼 타임으로 정답을 구할 수 있으므로, 당연 그 시간내에 검산도 가능하다. 따라서 P ⊂ NP이다. NP-Hard: NP-Hard는 계산복잡도가 NP일 수도 있고, 그보다 더 어려울 수도 있다. NP-Hard >= NP영어로는 이렇게 표현한다. "at least as hard as the hardest problems in NP". 그런데 여기서 어렵다의 의미가 조금 복잡하다. 어떤 NP문제를 다른 문제로 다항.. 2014. 7. 22.
[NeuroScience] New born neurons 사이언티픽 아메리칸에 올라온 글.간단히 요약하면, 뉴런은 성인이 되어서도 계속해서 새로 생겨나며, 이 새로 생겨난 뉴런은 기존의 뉴런들에대해 억제 시그널을 생성해 새로운 환경에대한 패턴 인식을 더 잘하게끔 도와준다.관련해서 불안 장애 또한 새로운 환경과 위험한 환경을 잘 구분하지 못해서 생기는 것이며, 이것을 새로 태어난 뉴런들이 죽지않게끔 유도해 해결할 수 있을 것이라고 제안한다. 2014. 7. 22.
Dimension Reduction, Curse Of High Dimensionality 고차원의 저주 (Curse Of High Dimensionality) : 고차원에서는 다음과 같은 현상이 일어나 기계학습에서 여러 문제가 발생한다.1) 차원이 무한으로 갈 수록 임의의 두 점간의 거리가 무한대로 발산한다. 그러므로 당연히 임의의 두점에 대한 거리의 비가 1로 수렴한다.(즉 임의의 점 4개를 뽑고, 2점들 간의 거리의 비가 1로 수렴한다) 2) 데이터의 instance가 고차원의 공간에서는 보다 희소(Sparse)해진다. 따라서 특정한 차원(Feature)를 충분히 설명할 수 없어지고, 부족한 데이터는 곧 모델의 Generalization Ability를 약화시켜 Overfitting이 일어난다. 차원 축소 (Dimension Reduction) :차원 축소는 고차원의 저주를 비롯해 여러가.. 2014. 7. 18.
Linear Discriminant Analysis (Latent Dirichlet Allocation 과 약자가 똑같으니 주의하자.) 선형판별분석법은 PCA와 그 원리가 거의 유사하다. PCA는 label 즉, 데이터의 클래스에대한 정보를 쓰지 않는 unsupervised learning인데비해, LDA는 클래스에대한 정보를 갖고 분석하는 supervised learning이다. 원리는 각 데이터들을 분리하는 최적의 정사영을 계산하는 것이다. 클래스가 2개가 있다면, 각각을 eigen vector를 이용해서 대각화 시켜, 서로 직교하도록 만드는 것이라고 한다. http://funnypr.tistory.com/36 2014. 7. 18.
라그랑지 승수법, KKT condition 라그랑지 승수법(Lagrange multiplier) : 어떤 함수(F)가 주어진 제약식(h)을 만족시키면서, 그 함수가 갖는 최대값 혹은 최소값을 찾고자할 때 사용한다. L(x,λ) = F(x) + λ*h(x) 으로 표기하며, (x,λ)변수들로 각각 편미분 한 식이 0이 되는 값으로 해를 구한다. 이러한 계산의 원리는, 사실 두 함수의 기울기가 같아지는 공통접선을 구하는 것이다.(위 수식이 가능한 이유는, F(x) = F(x) 에서 양변에 0에 해당하는 제약식( 0=h(x) )을 더해서 F(x) + 0= F(x) + λ*h(x) 으로 놓고 문제를 푼것이라 생각해볼 수 있다.) http://blog.naver.com/mindo1103/90154212128이글에 원리가 아주 잘 설명되어 있다. * 부연 설.. 2014. 7. 18.
Eigenvalue, Eigenvector, PCA, SVD # 아이겐 벡터와 아이겐 벨류의 의미 : 3*3으로된 행렬에 일련의 값들이 들어있다고 하자. 이 값들은 3차원 공간상에 점들로 표현될 수 있다. 그런데 만약 이 점들에 전부 x,y위에만 존재한다면, 이는 사실 x,y 2개의 차원만으로 표현될 수 있는 데이터였던 것이다. 이러한 n*n행렬에서의 핵심 차원을 알아내는 것이 바로 아이겐 벡터와 아이겐 벨류이다. # 정의 : 임의의 정방행렬(n*n) A에대해, AB=λB를 만족하는 (단, B는 0이 아닌 벡터) B를 eigenvector, 상수 λ를 eigenvalue 라고 한다. - 직관적 해석 : A라는 행렬에 벡터 B를 곱하여 선형 변환(프로젝션)시켰을 때, B 벡터가 그리는 직선(상수 λ가 미지수이므로)위에 행렬 A가 놓여지는 것을 의미한다. 즉, 임의의.. 2014. 7. 18.
RNN 학습 알고리즘, BPTT BPTT(Backpropagation Through Time) : RNN의 recurrent한 부분을 시간에 대해서 펼치면 2개의 feedforward neural network로 이루어진 구조로 생각할 수 있다. 이렇게 리커런트 노드를 time step에 대해 k 번만큼 펼친 다음, 그대로 백프로퍼게이션 알고리즘을 적용한다.이 때 한가지 헷갈리는 점은, 시간에 대해 펼친 recurrent layer가 각 layer마다 동일한 weight를 가져야한다는 조건이다. 이부분이 조금 어려운데 사실은 하나의 리커런트 엣지를 인위적으로 시간에 대해 펼쳐서 해석한 것이기 때문에, 실제로 모든 layer는 같은 edge인 것이라 weight가 같아야 한다.따라서 똑같이 forward pass로 activation값을.. 2014. 7. 8.
Naive Bayse, Bayesian Network, HMM Naive Bayse : bayes theorem 에 모든 변수들이 C라는 클래스에대해 conditionally independent 라고 가정하고 모델링 한것. 위 그림에서처럼 단순한 구조로만 모델링이 됨. Bayesian Network(=bayesian belief network, belief network) : bayes theorem 에서 변수들간에 다양한 conditionally independent이 존재한다고 가정하고 모델링 한 것. 위 그림에서처럼 복잡한 구조가 모델링 될 수 있음.DBN = deep BN conditionally independent 조건을 많이 가정할 수록 계산해서 구해야하는 확률 변수의 개수를 확 줄일 수 있다. HMM(Hidden Markov Model) : 은 BN.. 2014. 7. 7.
딥러닝과 FIR, IIR, LPF, HPF, BPF Impulse responseImpulse response(IR), 혹은 impulse response function(IRF)라고 불리운다. 좀 더 직관적인 의미는 후자가 더 와닿는다. 이는 쉽게 말하면 어떠한 신호를 처리하는 system이 있을 때, input signal을 받아서 어떻게 output signal로 변형시키는지에 대한 함수(시간에 대한 함수)를 가리키는 말이다. 만약 우리가 어떤 공연장의 IR 데이터를 갖고 있으면, 어떠한 소리든지 그 공연장에서 나오는 소리처럼 변형시킬 수 있게 된다. # 용어 - Impulse: input signal을 의미함 - response: output signal을 의미함 Impulse(unit impulse)출처: https://en.wikipedia.o.. 2014. 7. 1.
Markov Chain, Markov Matrix Markov Chain(MC) : 메모리를 갖지않는, 즉 직전 상태에의해서만 다음상태가 결정되는 이산적 시간에따른 확률적인 변화 모델 그냥 Markov Chain 은 Markov Matrix를 적용하는 방법을 의미한다고 이해할 것. Markov Matrix가 훨씬 직관적임 (MC의 그래프는 당연히 Markov Matrix 와 1:1 대응되어 표현가능함.) Markov Matrix : 그냥 Markov Chain 을 행렬로 표현 한 것. Markov Chain 은 오히려 Markov Matrix로 이해하는게 더 적합해보임. 단순히 Ut+1 = A*Ut 항 에서의 행렬 A가 바로 Markov Matrix임. (단, row의 합은 1이고, 각 성분은 0보다 같거나 커서 row stochastic matrix .. 2014. 6. 24.
Perceptron, TLU TLU : Threshold Logic Unit / TLU의 다른이름은 Perceptron, Threshold neuron 이라고 함. input의 합(=weighted summation)이 Threshold 이상이면 1을 출력, 그렇지 않으면 0을 출력하는 유닛. if(Sum(input) => Threshold) return 1; if(Sum(input) 0 {0,1} -> 0 {1,0} -> 0 {1,1} -> 1 OR gate : threshold를 0.5로 잡으면 {0,0} -> 0 {0,1} -> 1 {1,0} -> 1 {1,1} -> 1 XOR gate : threshold를 어떻게.. 2014. 6. 17.
Neural Network의 학습 방법, Gradient Descent, Back-Propagation Gradient descent : 에러를 미분하여 weight를 업데이트 하는 방법. Back-propagation : Hidden node에서 에러를 미분하여 weight를 업데이트 하는 방법. Neural Network 학습 방법 1) Hebbian Learning (Hebbian Rule) 2) Perceptron Rule 3) Gradient Descent (Delta Rule, Least Mean Square) 4) Back propagation 5) 그 이외 응용기법 1) Hebbian Learning 기본 신경망 학습 규칙으로, 원래 무감독 학습 방법에 쓰는 것이었다. * 아이디어 -> 만일 어떤 신경세포의 활성이 다른 신경세포가 활성하는 데 계속적으로 공헌한다면, 두 신경세포 간의 연결 가.. 2014. 6. 17.
Activation Function - Sigmoid 함수 (시그모이드 함수) 대표적인 활성 함수(Activation Function)이다. 뉴럴넷에서 Activation Function 이란, x=Weighted Sum 에대해, y=F(x) 로 output y를 다음 레이어로 보내는 함수 F를 의미한다. 단순히 계단식으로 활성화 함수를 사용할 경우, output이 무조건 0과 1로만 나와, 미분이 불가능하고, 중간 값이 존재하지 않는다.그러나 시그모이드 함수를 쓸 경우, output을 0과 1만이 아니라 [0,1]의 범위로 feature를 나타낼 수 있다. 여기서 분자분모에 e^x 를 곱하면로 바꾸어 표현할 수 있다.(두 표현 다 자주 쓰임) 정확히 이런 모양을 가진 함수를 Sigmoid 함수라고 부름.(logistic 함수라고도 부름).. 2014. 6. 12.
Gaussian Distribution, Gaussian Mixture Model Gaussian Distribution : 다른말로 정규 분포라고도 부른다.(자연계에서 많은 현상이 이 분포를 따르기 때문)가우시안 분포의 수식 유도는 링크된 다른 블로그에서 잘 설명되어 있다.여기서는 직관적인 이해를 시도해보겠다. 우선 정규분포의 모형을 보면 가운데를 중심으로 좌우가 대칭이다. 따라서 (x-u)^2 의 의미가 여기에 있다. 좌우가 대칭되도록 하기 위해 x의 제곱을 한 뒤, 평균 값인 u를 중심으로하게끔 평행이동 시킨 것이다.그 앞에 있는 -(1/2sigma^2)은 x^2식의 계수이다. 일단 부호가 음수인 이유는, 종모양으로 바꾸기 위해서 y축 대칭을 시킨 것이다. 그러면 1/2sigma^2의 값은 y=-ax^2 에서 a에 해당하는 것이 되고, 이것은 y=-ax^2 그래프의 좌우 크기를 .. 2014. 6. 11.
큰 수의 법칙, 중심 극한의 정리 # 큰 수의 법칙 : 표본집단들의 평균과 분산에 대한 법칙 어떤 모집단에서 표본집단들을 추출할 때, 각 표본집단의 크기가 커지면 그 표본집단들의 평균은 모집단의 평균과 같아지고, 표본집단들의 분산은 0에 가까워 진다. http://dermabae.tistory.com/146http://blog.daum.net/gongdjn/114 # 중심극한의 정리(Central limit theorem) : 표본집단들의 평균이 갖는 분포에 대한 법칙 그 어떠한 모양의 임의의 분포에서 추출한 표본집단들의 평균(표본평균)의 분포는 정규분포를 이룬다. (심지어 모집단이 정규분포를 따르지 않더라도. 단 각각의 표본의 크기가 적당히 커야한다. 30이상) http://blog.naver.com/PostView.nhn?blogId.. 2014. 6. 11.
Clustering, GMM, K-means, EM, DBSCAN 케이민즈 - 케이니얼니스트의 클러스터링 버젼 k means랑 gmm이랑 거의 비슷함. 차이는 가우시안분포에대한 가정이 있는가 없는가 / 둘다 클러스터의 개수를 지정하고, EM 식으로 둘다 이터레이티브하게 클러스터링을 함. Centroid : 무게 중심, 질량 중심 (정확히는 질량 중심인데 해석하는데 큰차이는 없어 보임.) K-means : K개의 클러스터를 묶어내는 것 (K-means가 EM(Expectation Maximization)의 전형적인 예라고 함.) Step 1) K개 만큼의 랜덤한 점을 정한다. Step 2) 각 클러스터의 점들을 계산해서 각각의 Centroid 를 구한다. Step 3) 입력받은 X1에대해 가장 가까운 Centroid 쪽의 클러스터에 할당한다. -> 다시 Step 2)로 .. 2014. 6. 11.
Nominal, Ordinal, Interval, Ratio Nominal : 각 데이터마다 Label이 정해져 있는 것 (Name) / Classification 문제ex) 어떤 (R,G,B) 값으로 구성된 색상을 보고, 이건 무슨색이다라고 이름을 맞추는 것 Ordinal : 어떤 데이터를 보고 랭킹을 정하는 것 (Order) / Regression 문제, 그러나 각 랭킹 사이의 거리가 일정하지 않을 수 있음. (즉 1등하고 2등하고의 실제 맞은 점수 차이는 엄청 작을 수도 있다는 것) ex) 영화 10개를 보고, 1~10등 까지 정하는 것. (이 때 1등과 2등은 근소한 차이일 수 있음) Interval : 어떤 데이터를 보고 자유롭게 평점을 정하는 것 / Regression 문제. Ordinal에서 보다 거리 정보를 고려한 것 ex) 영화를 보고 0.0 ~ .. 2014. 6. 11.
거리, Distance # 유클리드 거리(Euclidean Distance): 유클리드 공간에서의 기하학적 최단 거리(직선 거리)2차원상에서보면, 두점사이의 직선거리(고차원 상에서도 그릴 수는 없지만, 직선거리 or 최단라고 정의는 가능 할듯.) # 마할라노비스 거리(Mahalanobis Distance): 정규분포에서 특정 값 X가 얼마나 평균에서 멀리있는지를 나타내는 거리관측된 X가 , 얼마나 일어나기 힘든 일인지 즉 평균과 표준편차를 고려했을때 얼마나 중심에서 멀리 떨어져 있는가를 구하는 값. 주로 관측된 데이터의 신뢰성? 또는 적합성을 판단하는데 쓰인다고함.(에러인지를 판단한다)ex) 평균이 20, 표준편차가 3인 분포에서 26의 데이터가 관측 -> 이때 26의 마할라노비스 거리는 (26-20)^2/3 = 12가 됨. .. 2014. 6. 11.
공분산, 상관계수, 왜도, 첨도 Variance: 편차제곱의 평균 = X제곱의 평균 - X평균의 제곱 즉 편차의 정도를 제곱내서 측정하는 것.(제곱을 안하면 부호가 양수와 음수가 있어서 평균내면 항상 0이 됨) Covariance: X편차 * Y편차 = X*Y의 평균 - X평균*Y평균 두 편차 random variable가 같이 변하는 방향성이 있는지 측정또는 N차원 공간 상에서, 각각의 차원들이 서로 상관성을 갖는지를 측정하는 것임. 즉 어떤 dim과 어떤 dim은 서로 100%의 상관성을 갖는다라고 하면, 이 dim은 하나로 합쳐질 수 있는 것임. 왜도 (Skewness) : 이 분포가, 좌우로 얼마나 치우쳐져 있는가를 나타낸다. 첨도 (Kurtosis) : 이 분포가 얼마나 뾰족한가를 나타낸다. (컬토시스 -> 칼의 뾰족함) 공분.. 2014. 6. 11.
벡터의 내적과 외적 벡터의 내적 :해석-> B벡터를 A벡터로 정사영한다음 두 길이를 곱한다. 두백터의 같은 방향으로의 길이 곱을 구한 느낌. 벡터의 외적 :해석-> B벡터의 A벡터로의 sin값, 즉 A백터에 수직한 B성분의 길이로 곱한다. 두벡터의 서로 수직인 방향으로의 길이 곱을 구한 느낌.(왠지 두 벡터로 넓이를 구하는 느낌이다)그로 인해 외적의 결과는 새로운 벡터가 나오며, 그것은 A와 B벡터에 모두 수직인 벡터이다. 따라서 어떤 순서로 곱하냐가 중요.A와 B벡터로 하나의 평면을 찾을 수 있고, 그 평면에 수직인것이 바로 A,B벡터의 외적이다.(따라서 방향이 2가지 존재) 2014. 6. 11.

티스토리툴바