Affine and Convex

1. Basic concepts

1) line and segment

two points x1, x2 -> y=wx1 + (1-w)x2

for 0<w<1: y is segment

for w<0, w>1: y is line

 

2) affine set and convex set

affine set: the set C that contains line wx1 + (1-w)x2 or, w1x1 + w2x2 + w3x3 +...+ wnxn (Sigma(wi)=1)

-> affine combination: (w1,w2,...,wn) that belong to set C 

-> meaning: combination of weights that make y lies on x1~xn points

 

convex set: the set C that contains segment wx1 + (1-w)x2 

-> convex combination: (w1,w2,...,wn) that belong to set C 

-> meaning: combination of weights that make y lies on x1~xn points

 

3) hyperplane

set of x that fits {x|w^T x = b} -> {x|w^T (x-x0) = 0}  (w: vector, x,x0: point)

hyperplane: the space that all possible x lies on -> space vertical to vector w

-> space is divided to two halfspaces by hyperplane: {x|w^T x > b} and {x|w^T x < b}

-> dividing feature space into a number of subspaces

<-> classification problem: finding appropriate hyperplane

 

2. Convex function

f(w x1 + (1-w) x2) <= w f(x1) + (1-w) f(x2)

-> function that satisfies upper condition

=> f(x') (x1<x'<x2)가 x1, x2를 잇는 선분보다 밑에 있어야 한다

=> 볼록함수

(concave function: -f that satisfies convex condition)

(affine function: convex and concave function)

 

 

* Jansen's inequality: expand of convex condition

f(w1x1 + w2x2 + ... + wnxn) <= w1 f(x1) + w2 f(x2) +...+ wn f(xn) (Sigma(wi)=1)

n개의 f(xi) 함숫값의 어떠한 내분/외분 선형 조합을 찾아도 f값이 더 작다. (볼록)

-> f(E(x)) <= E(f(x)) 

 

* if f is convex function, composite function using f is also convex