데이터마이닝연구세미나 과목에서는 선형대수학(Linear Algebra) 및 벡터(Vectors) 학습을 통해 머신러닝에 필요한 볼록해석학(Convex Analysis) 및 최적화 이론(Nonlinear Programming)에 대해 다룬다.
① 선형대수학(Linear Algebra) for Machine Learning
머신러닝을 이해하기에 앞서 선형대수학의 연립방정식, 선형생성, 선형독립과 관련 된 내용을 학습한다.
· 선형연립방정식 풀이(System of Linear Equations) - Tableau Form
1) A𝑥 = b (𝑛-columns, 𝑚-rows)
"Ax = b" to the Tableau Form
선형연립방정식의 해는 총 3가지의 형태가 나온다. (유일 해, 부정_일반해-해가무수히많다, 불능-해가없다)
먼저, 복잡한 연립방정식의 나열을 위와 같은 심플렉스 표로 옮겨 사용하도록 한다.
[𝑚×𝑛] 행렬일 경우,
[𝑚×𝑛] 형태의 matrix A 와 [𝑛×1] 형태의 variable 𝑥 및 [𝑚×1] 형태의 class b 로 나뉘게 된다.
이후, 대표적인 풀이 방법인 가우스 조던 소거법(GJ Pivot Method)을 통해 해를 구해보도록 한다.
The GJ Pivot Method Step 1: Put the System in Tableau Form Select the first row as the pivot row in the original tableau and go to Step 2. Step 2: General Step Let 𝑟 denote the number of the present pivot row in the current tableau. If the coefficients of all the variables in the pivot row are 0, ̅̅̅ If at least on of the variables has a nonzero coefficient(pivot element) in the pivot row, perform GJ Pivot Step. Step 3: Checking Uniqueness of Solution, and Writing the General Solution At termination, 독립변수부정해가무수히많다 소거법 최종 형태(예시)GJ Pivot Step - Pivot element 1 만들고 나머지 컬럼은 모두 0 으로 한다. 피벗 스텝을 수행해보자. Pivot row, column, and element계산이 간단한 피봇 요소를 잡고 행 연산한다. Ex. Three Solution Types • basic variable: any variable that corresponds to a pivot column in the augmented matrix of a system. • free variable: all nonbasic variables.
case 1) 일반 해(general solution) - 해가 무수히 많을 때, 5차원 공간에 2차원 평면의 서브 셋을 가진다. (𝑥2, 𝑥5 에 대한 식으로 표현 됨) number of nonbasic variable means dimension case 2) 유일 해(unique solution), RC(중복제약식, 0=0) 생략 가능 계단형(에첼론 폼) 행렬로 해가 떨어짐(no free variables) case 3) 해가 없을 때(no solution), - 1 개 이상의 IE row 가 나오면 해가 없다. 불능(Inconsistent Equation)
· 사다리꼴행렬(에첼론 폼) 만들기 - Reduced Row Echelon Form (rref)
Reduced Row Echelon Form (rref) [Definition] 기본 행 연산(Elementary Row Operations) (E1) Row Interchange - 행 간 교환 가능 (E2) Row multiplication - 행 에 상수 곱 가능 (0 이 아니어야 함) Each element in a row can be multiplied by a non-zero constant. (E3) Row addition - 행 에 다른 행의 상수 곱을 더할 수 있음 A row can be replaced by the sum of that row and a multiple of another row.
[Definition] Reduced Row Echelon Form (rref) A 𝑚×𝑛 matrix 𝑅 is called rref if there exists a positive integer r, 1≤𝑟≤𝑚 and positive integers 𝑘₁,⋯,𝑘𝑟 such that (a) 𝑅(𝑖,∙)=0,∀𝑖≥𝑟+1 모든 값이 0 인 RC(중복 제약식) 값은 맨 밑에 배치한다. (b) 𝑅(𝑖,𝑗)=0,if 𝑗<𝑘𝑖 앞의 Column 들이 모두 0 이 되게 한다. (c) 𝑅(𝑖,𝑘𝑗)=𝛿𝑖𝑗,1≤𝑖≤𝑟,1≤𝑗≤𝑟 위의 Row 들이 모두 0 이 되게 한다. (d) 𝑘₁<⋯< 𝑘𝑟≤𝑛. 𝑘₁⋯𝑘𝑟 까지는 모두 순차적이어야 한다 (계단식, 사다리꼴 형태)
[Proposition] The rref of a matrix is unique. 에첼론 폼의 규칙에 따라 유일한 형태여야 한다. Basic & Nonbasic colums 컬럼의 앞 부분은 basic, 뒷 부분은 nonbaic 그리고 k 순서는 순차적으로 유니크한 형태가 된다. nonbasic 컬럼들은 basic 에 대한 역행렬 형태로, D-bar 를 계수로 표현할 수 있다.
② 벡터(Vectors) for Machine Learning
머신러닝에서의 벡터와 선형 부분공간에 대한 동작을 학습한다.
• 벡터 공간(Vector Space) - A Vector Space involves four things; - two sets V and F, and two operations vector addition and scalar multiplication. 1)V : a nonempty set of objects, called vectors (보통 set of 𝑛-tuples (𝑥₁,⋯,𝑥𝑛) ∈ 𝑅ⁿ, 또는 set of matrix) 2)F : scalar 가 정의되는 공간 (실수:real, 복소수:complex) 3)Vector Addition : 𝑥+𝑦, ∀ 𝑥,𝑦 ∈ V 4)Scala Multiplication : F 와 V 간의 operation : α𝑥, α ∈ F, 𝑥 ∈ V
[Definition] The set V is called a vector space over F. When the vector addition and scalar multiplication operation satisfy the following properties.
• 벡터 합(Vector Addition) A1) 벡터 공간에 대한 닫힘 성질(Closure Property)을 만족한다. 𝑥+𝑦 ∈ V, ∀ 𝑥,𝑦 ∈ V ∶ closure property of vector addition A2) 결합 법칙(Associative)이 성립한다. (𝑥+𝑦)+𝑧 = 𝑥+(𝑦+𝑧), ∀ 𝑥,𝑦,𝑧 ∈ V ∶ associative A3) 교환 법칙(Commutative)이 성립한다. ※ 매트릭스 곱에서는 교환 법칙 성립 X (중요) 𝑥+𝑦 = 𝑦+𝑥, ∀ 𝑥,𝑦 ∈ V ∶ commutative A4) 원점을 포함하는 공간이 벡터 공간이다. 원점이 존재하지 않으면 벡터 공간이 될 수 없다. (必 Zero Vector) ∃ !0 ∈ V, 𝑥+0 = 𝑥, ∀𝑥 ∈ V
• 스칼라 곱(Scalar Multiplication) M1) 스칼라 곱으로써 닫힘 성질을 만족한다. α𝑥 ∈ V, α ∈ F, 𝑥 ∈ V ∶ closure property for scalar multiplication M2) 스칼라 곱에 대한 부분은 결합 법칙이 성립한다. (αβ)𝑥 = α(β𝑥), ∀ α,β ∈ F, 𝑥 ∈ V ∶ associative M3) 스칼라에 대한 분배 법칙도 성립한다. α(𝑥+𝑦) = α𝑥+α𝑦, ∀ α ∈ F, 𝑥,𝑦 ∈ V ∶ distributive M4) 스칼라 합에 대한 분배 법칙도 성립한다. (α+β)𝑥 = α𝑥+β𝑥, ∀ α,β ∈ F, 𝑥 ∈ V M5) 곱에 대한 항등원 1의 결과는 자기 자신이다. 1𝑥 = 𝑥, ∙∋∙ ∀ 𝑥 ∈ V
[Definition] 부분 공간(Subspace) Let V is a vector space over F. A Subspace of V is subset W of V which it reself a vector space over F with operations of vector addition and scalar multiplication on V.
[Proposition] A subset W of V is a subspace of V⇔ ⋯ 부분 공간이 되는 필요충분조건 (선형 결합이 만족하면 됨) ∀ 𝑥,𝑦 ∈ W, α𝑥+β𝑦(선형 결합:linear combination) ∈ W, ∀ α,β ∈ F
Ex. with function addition and scalar multiplication defined by (𝑓+𝑔)(𝑥) = 𝑓(𝑥)+𝑔(𝑥) (𝛼𝑓)(𝑥) = 𝛼𝑓(𝑥)
1) the set of function : [0, 1] -> 𝑅 (0과 1사이의 값이 실수인 함수 집합) 2) the set of all real-valued continuous function over [0-1] (0과 1사이의 연속함수의 부분 공간도 연속함수) 3) the set of all real-valued function that are diffentation on [0-1] (미분 가능한 함수도 역시 벡터 공간) ⇒ vector space. 그 밖에도 다항식의 합 역시 다항식 이므로 선형 결합을 만족한다.
기저(Basis)를 설명하기에 앞서, 생성 집합(Spanning Set) & 선형 독립(Linear Independence) 정의하고 가도록 한다.
[Definition] 생성 집합(Spanning Set) 1) For a set of vectors 𝑆 = {𝑣₁, ⋯, 𝑣𝑟}
the subspace span(𝑆) ≜ {𝛼₁𝑣₁+ ⋯+ 𝛼𝑟𝑣𝑟 : 𝛼𝑖 ∈ F, ∀𝑖} : the set of all linear combination of S: 모든 선형 결합의 집합 is called the subspace spanned by 𝑆
2) V = span(𝑆) → We say that 𝑆 is a spanning set for V. In other words, 𝑆 spanned V whenever each vector in V is a linear combination of vector from 𝑆
Ex. ① 2-dim, y=x spanning. 감마에 대한 스칼라 곱으로 치환(2차원) ② 3-dim, unit vector(standard basis) e1, e2, e3 spanning. 스탠다드 베이시스(3차원) ③ n-dim, all polynomials spanning. n차 이하의 모든 다항식을 스팬한다.
[Definition] 선형 독립(Linear Independence) A set of vectors 𝑆 = {𝑣₁, ⋯, 𝑣𝑛} is said to be a linearly independent set whenever the only solution for the scalar 𝛼𝑖 in the equation. 𝛼₁𝑣₁+ ⋯+ 𝛼𝑛𝑣𝑛 = 0 ⋯ 유일 해 in the trivitial solution, ⋯ 자명한 해 𝛼₁ = 𝛼₂ = ⋯ = 𝛼𝑛 = 0 whenever there is a nontrivial solution for 𝛼𝑖(i.e., at least one 𝛼𝑖 ≠ 0), the set 𝑆 is said to be a linearly dependent set.
* 독립, 종속 ⇒ 집합(Set)에만 적용, Linearly independent vector X Ex. Determine whether the set. Basic Column(Red) → 따라서, {A.₁, A.₂, A.₃} linearly dependent.
• Remark 1) 선형 종속 집합을 포함하는 임의의 집합은 선형 종속이다. - Any set which contained a linearly dependent set is linearly dependent. 2) 선형 독립 집합의 부분 집합 역시 선형 독립이다. - Any subset of linearly independent set is linearly independent. 3) 제로 벡터를 포함하는 임의의 집합도 선형 종속이다. - Any set which contained the 0 vector is linearly dependent. ∃ 1∙0 = 0, {0} is linearly dependent. 4) 공 집합은 선형 독립이다. (임의의 집합의 부분 집합이기 때문에) - Empty set linearly independent.
[Definition] 기저(Basis) Let V are a vector space. A basis of V is a linealy independent set of vector in V which spans V. The space V is finite dimensional if it has a finite basis.
* basis of V : 기저의 필수조건 2 가지 ① Linearly independent ② Spaned V
[Proposition] If V is a finite dimensional vector space, then any two basis of V have the same number of elements.
① V가 n개로 span 되면 n개보다 많은 set은 독립일 수 없다. ② V의 basis는 같은 수의 element를 가진다. 이 숫자를 V의 dimension 이라하고 dim V로 나타낸다. ③ dim V = n 이면, n보다 작은 수의 vector로는 V를 span 못한다. ④ zero subspace S = span{0} (제로 벡터로 span 되면), dim V = 0 으로 정의한다.
[Definition] Maximally linear independent subset Δ of Γ Γ = {𝑣₁, ⋯, 𝑣𝑘} ⊂ V Δ ⊂ Γ i) Δ is linearly independent. ii) ∀ 𝑣𝑗 ∈ Γ/Δ, ⋯ Γ 에서 Δ 제외한 부분의 원소 벡터 𝑗 Δ ⋃ {𝑣𝑗} is linearly dependent. (그림 참조) 그림 1 감마에서 델타만큼 잡아내면 인디펜던트한데, 여기에 vj 벡터 1개만 집어넣으면 그 영역은 디펜던트하게 되고, 이를 맥시멀리 인디펜던트 서브셋이라고 부른다.
※ Maximally linear independent subset 이 span 하다는 것을 증명(독립은 이미 증명 됨) [Proposition] Any maximal independent subset Δ of Γ is a basis of L = span Γ. (맥시멀리 인디펜던트 셋은 하나의 베이시스를 갖는다는 이야기) Df> We must show that Δ = {𝑣₁, ⋯, 𝑣𝑟} span L Let 𝑣 ∈ L = span Γ. then, {𝑣, 𝑣₁, ⋯, 𝑣𝑟} is linearly dependent. ⋯ maximal ⇒ ∃ 𝛼, 𝛼₁, ⋯, 𝛼𝑟 (𝛼 ≠ 0) 𝛼𝑣, 𝛼₁𝑣₁, ⋯, 𝛼𝑟𝑣𝑟 = 0 ⇒ 𝑣 = -(𝛼₁/𝛼)𝑣₁ -(𝛼₂/𝛼)𝑣₂ ⋯ -(𝛼𝑟/𝛼)𝑣𝑟 ⇒ {𝑣₁, ⋯, 𝑣𝑟} span L. (MLIS is span 하다.)
* span Δ is called a minimal representation of L. 최소한의 수로 L을 나타낼 수 있다. 그림을 참고하면, (L = span Γ = span Δ) L 을 나타내는 다양한 방법 미니멀하지만, 독립으로 볼 때는 맥시멀리 인디펜던트 서브셋으로 볼 수도 있다.
※ Summary of Basis 1) All maximal linearly independent subset of a set Γ always contained the same number of vector. 집합 감마의 모든 최대 선형 독립 부분 집합은 항상 동일한 수의 벡터를 포함하고 있다. 2) A linearly independent and spanning set for a vector space V is called a basis for V. 벡터 공간 V 에 대한 기저의 필요충분조건은 선형 독립이면서 생성 집합이어야 한다. 3) Every vector space V possess a basis. A space can have many different basis. 모든 벡터 공간은 기저를 가지고, 공간은 다양한 기저가 존재할 수 있다. - Standard basis for 𝑅ⁿ (𝑛 차원 실수 공간의 표준 기저) - The set {1, 𝑥, 𝑥², ⋯, 𝑥ⁿ} is a basis for the vector space of polynomial having degree n of set. 𝑛 차 이하의 모든 다항식에 대한 집합의 기저는 다음과 같다. 4) Characterization of a Basis (기저의 특징) - Let V is a vector space. and Let 𝐵 = {𝑣₁, ⋯, 𝑣𝑛} < V. The following statement are equiation. ⅰ) 𝐵 is a baise for V ⅱ) 𝐵 is a minimal spanning set for V ⅲ) 𝐵 is a maximal linear independent subset of V 5) Dimension of a vector space V (벡터 공간의 차수) 6) Subspace dimension (부분 공간 차수) - For vector space W and V. (W ⊆ V) ⅰ) dim W ≤ dim V (W 차수는 V 보다 작거나 같다.) ⅱ) If dim W = dim V, then W = V (만약, 차수가 같으면 벡터 공간은 같다고 본다.)
