데이터마이닝연구세미나 과목에서는 선형대수학(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, \[\begin{cases} 𝑏̅𝑟=0 & \mbox{⇒the present row is redundant (0=0)} \\ 𝑏̅𝑟≠0 & \mbox{⇒the original system is inconsistent (0≠𝑏̅𝑟)} \end{cases} \] 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, \[\begin{cases} & \mbox{∄ nonbasic variable(독립 변수) ⇒unique solution} \\ & \mbox{∃ nonbasic variable(부정-해가무수히많다) ⇒infinite number of solutions} \end{cases} \] 소거법 최종 형태(예시)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 𝑅ⁿ (𝑛 차원 실수 공간의 표준 기저) \[ 𝑆=\{𝑒_1,⋯,𝑒_n\} \] - 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 (벡터 공간의 차수) \[ \eqalign{ dim V & = \mbox{num(} \# \mbox{) of vector in any basis for }V. \\ &= \mbox{num(} \# \mbox{) of vector in any minimal spanning set for }V. \\ &= \mbox{num(} \# \mbox{) of vector in any maximal linear independent subset of }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 (만약, 차수가 같으면 벡터 공간은 같다고 본다.)
