DataManyo

유도식 12.1 정리

유도식 12.1은 다음과 같습니다:

\[
E(h; \mathcal{D}) = P_{x \sim \mathcal{D}}(h(x) \neq y)
\]

이를 통해 \( E(h; \mathcal{D}) \)를 정의하고 정리해보겠습니다.

정리

1. **정의에 따라, 일반화 오차 \( E(h; \mathcal{D}) \)는 가설 \( h \)가 데이터 분포 \( \mathcal{D} \)로부터 샘플링된 입력 \( x \)에 대해 실제 레이블 \( y \)와 일치하지 않는 확률을 의미합니다:**

\[
E(h; \mathcal{D}) = P_{x \sim \mathcal{D}}(h(x) \neq y)
\]

2. **데이터 세트 \( D \)가 독립적이고 동일한 분포(i.i.d.)에서 샘플링된 경우, 경험 오차 \( \hat{E}(h; \mathcal{D}) \)는 다음과 같이 정의됩니다:**

\[
\hat{E}(h; \mathcal{D}) = \frac{1}{m} \sum_{i=1}^{m} \mathbf{1}(h(x_i) \neq y_i)
\]

여기서 \( \mathbf{1} \)은 지시 함수(indicator function)로, \( h(x_i) \)가 \( y_i \)와 일치하지 않으면 1, 일치하면 0의 값을 가집니다.

3. **큰 수의 법칙에 따라, 샘플 크기 \( m \)이 커질수록 경험 오차는 일반화 오차에 수렴합니다:**

\[
\hat{E}(h; \mathcal{D}) \rightarrow E(h; \mathcal{D}) \quad \text{as } m \rightarrow \infty
\]

4. **따라서, 유도식 12.1을 다시 정리하면 다음과 같은 결론에 도달합니다:**

\[
E(h; \mathcal{D}) = P_{x \sim \mathcal{D}}(h(x) \neq y)
\]

이는 가설 \( h \)가 주어진 데이터 분포 \( \mathcal{D} \)에 대해 얼마나 잘 일반화하는지를 나타내는 지표입니다.

보조 정리 12.1 증명

보조 정리 12.1의 내용은 다음과 같습니다:

\[
E(h; \mathcal{D}) = P_{x \sim \mathcal{D}}(h(x) \neq y)
\]

이를 증명해보겠습니다.

증명

1. **정의에 따라 일반화 오차는 다음과 같이 정의됩니다:**

   \[
   E(h; \mathcal{D}) = P_{x \sim \mathcal{D}}(h(x) \neq y)
   \]

2. **경험 오차는 다음과 같이 정의됩니다:**

   \[
   \hat{E}(h; \mathcal{D}) = \frac{1}{m} \sum_{i=1}^{m} \mathbf{1}(h(x_i) \neq y_i)
   \]

   여기서 \( \mathbf{1} \)은 지시 함수(indicator function)로, 조건이 참일 때 1, 거짓일 때 0의 값을 갖습니다.

3. **확률적 관점에서 일반화 오차와 경험 오차의 차이는 데이터를 무작위로 샘플링한 결과로 나타날 수 있습니다. 이는 크게 두 가지 요소로 설명될 수 있습니다:**

   • **샘플의 크기 \( m \):** 샘플의 크기가 클수록, 경험 오차는 일반화 오차에 가까워집니다.
   • **샘플링 분포 \( \mathcal{D} \):** 샘플이 독립적이고 동일한 분포(i.i.d.)에서 추출된 경우, 경험 오차는 일반화 오차의 좋은 추정치가 됩니다.

4. **독립적이고 동일한 분포(i.i.d.)에서 샘플링된 경우, 큰 수의 법칙에 따라 경험 오차는 일반화 오차로 수렴합니다:**

   \[
   \hat{E}(h; \mathcal{D}) \rightarrow E(h; \mathcal{D}) \quad \text{(as \( m \rightarrow \infty \))}
   \]

5. **이를 바탕으로, 다음이 성립함을 보일 수 있습니다:**

   \[
   \hat{E}(h; \mathcal{D}) = \frac{1}{m} \sum_{i=1}^{m} \mathbf{1}(h(x_i) \neq y_i) \rightarrow P_{x \sim \mathcal{D}}(h(x) \neq y) = E(h; \mathcal{D})
   \]

따라서, 보조 정리 12.1은 증명되었습니다.

젠센 부등식 증명 (Jensen's Inequality)

젠센 부등식은 모든 컨벡스 함수(convex function)에 대해 다음과 같은 식을 만족합니다.

\[
f(\mathbb{E}(x)) \leq \mathbb{E}(f(x))
\]

이를 증명해보겠습니다.

증명

컨벡스 함수 \( f \)의 정의에 따르면, \( f \)는 다음 조건을 만족합니다.

\[
f(\theta x_1 + (1-\theta) x_2) \leq \theta f(x_1) + (1-\theta) f(x_2)
\]
여기서 \( 0 \leq \theta \leq 1 \)입니다.

이를 수학적 기댓값을 이용하여 일반화하면,

\[
f\left(\sum_{i=1}^{n} \theta_i x_i\right) \leq \sum_{i=1}^{n} \theta_i f(x_i)
\]
여기서 \(\sum_{i=1}^{n} \theta_i = 1\)이고, 각 \(\theta_i \geq 0\)입니다.

이제, \( x \)가 확률 변수이고, \(\theta_i\)가 확률 변수 \( x \)가 \( x_i \) 값을 가질 확률이라고 가정합니다. 그러면 \(\mathbb{E}(x) = \sum_{i=1}^{n} \theta_i x_i\)입니다.

따라서, 컨벡스 함수의 정의에 따라,

\[
f\left(\mathbb{E}(x)\right) = f\left(\sum_{i=1}^{n} \theta_i x_i\right) \leq \sum_{i=1}^{n} \theta_i f(x_i) = \mathbb{E}(f(x))
\]

즉, 젠센 부등식이 성립함을 알 수 있습니다.

\[
f(\mathbb{E}(x)) \leq \mathbb{E}(f(x))
\]

따라서, 젠센 부등식은 증명되었습니다.

사전 학습(pretraining)과 압축 센싱(compressed sensing) 모두 머신러닝과 신호 처리 분야에서 중요한 개념이며, 각각 희소성(sparsity)을 활용하는 방법이지만, 그 활용 방식과 목표에는 중요한 차이가 있습니다.

1. 사전 학습: 이는 일반적으로 딥 러닝 모델에서 사용되는 방법으로, 모델의 초기 가중치를 설정하는 방법입니다. 사전 학습은 주로 큰 데이터셋에서 먼저 모델을 학습시킨 후, 이를 더 작은 특정 작업에 맞게 미세 조정하는 방식으로 사용됩니다. 이때 희소성의 개념은 모델의 가중치 또는 표현이 희소해질 수 있도록 학습 과정을 제어하는데 사용될 수 있습니다. 예를 들어, 오토인코더의 은닉층을 희소하게 만드는 것이 여기에 해당합니다. 이 방식은 노이즈에 강하고 중요한 특징을 잡아내는 능력을 향상시킬 수 있습니다.

2. 압축 센싱: 이는 신호 처리 분야에서 발견된 방법으로, 희소한 신호를 샘플링하고 재구성하는 프로세스입니다. 희소성은 이 방법의 핵심이며, 신호의 대부분이 0 또는 0에 가까운 값으로 구성되어 있을 때 신호를 효과적으로 샘플링하고 압축할 수 있습니다. 이렇게 샘플링된 신호는 후에 원래의 신호로 복구될 수 있습니다. 이 방법은 원래의 신호를 효과적으로 복구하기 위해 필요한 샘플 수를 크게 줄일 수 있어, 매우 효율적인 방법입니다.

결국, 사전 학습과 압축 센싱 모두 희소성을 활용하지만, 그 목적과 사용 방식에는 큰 차이가 있습니다. 사전 학습은 모델의 성능을 향상시키고, 압축 센싱은 신호를 효과적으로 샘플링하고 복구하는 데 중점을 두고 있습니다.

L1 노름 최소화 문제는 다음과 같습니다:

minimize ||y - Xw||^2_2 + λ||w||_1

여기서 y는 응답 변수, X는 설명 변수, w는 가중치, ||.||_2는 L2 노름 (유클리드 거리), ||.||_1은 L1 노름 (맨해튼 거리), λ는 정규화 파라미터입니다.

이 최적화 문제는 일반적으로 닫힌 형태의 해를 가지지 않습니다. L1 노름은 절대값 함수를 포함하므로, 그레디언트를 계산하거나 표준 최적화 기법을 적용하기 어렵습니다. 따라서, 이 문제는 수치적 최적화 방법, 예를 들어 좌표 하강법, 경사 하강법, 또는 더 복잡한 최적화 방법 (예: 내부점 방법)을 사용하여 해결됩니다.

그러나, 이 최적화 문제의 부분 최적화 문제는 닫힌 형태의 해를 가질 수 있습니다. 예를 들어, w의 한 요소를 고정하고 나머지 요소로 최적화하는 문제는 닫힌 형태의 해를 가집니다. 이 사실은 좌표 하강법의 구현에 사용됩니다.

L0 노름은 벡터의 0이 아닌 요소의 수를 측정하는 노름입니다. 머신러닝과 통계에서, L0 노름은 변수 선택이나 피처 선택에 자주 사용되며, 이는 모델의 복잡성을 줄이고 과적합을 방지하는 데 효과적입니다.

그러나 L0 노름 정규화의 해를 직접 구하는 것은 계산적으로 매우 어려운 문제입니다. 그 이유는 다음과 같습니다.

1. 비볼록(non-convex) 최적화 문제: L0 노름은 비볼록 함수이기 때문에 전역 최적해를 찾는 것이 어렵습니다. 이 문제는 지역 최적해에 빠지기 쉬워, 그레디언트 기반의 최적화 방법이 잘 작동하지 않습니다.

2. 조합 최적화 문제:L0 노름 최적화는 본질적으로 조합 최적화 문제입니다. 가능한 모든 피처의 부분 집합을 검토해야 하므로, 피처의 수가 많아질수록 계산 복잡도가 기하급수적으로 증가합니다.

3.희소(sparse) 해: L0 노름은 정확히 0인 가중치를 강조하므로, 최적의 해는 일반적으로 많은 피처 가중치가 0인 '스파스' 해가 됩니다. 이는 모델의 해석 가능성을 높이지만, 모델의 예측 성능을 저하시킬 수 있습니다.

이러한 이유로, 실제로는 계산적으로 용이하며 비슷한 속성을 가진 L1 노름 (Lasso) 또는 L2 노름 (Ridge) 정규화를 L0 노름의 대안으로 사용하는 경우가 많습니다.

릿지 회귀(Ridge Regression)와 서포트 벡터 머신(SVM)은 모두 머신러닝 알고리즘으로, 선형 및 비선형 패턴을 찾아내는 데 사용됩니다. 그러나 두 방법 간에는 몇 가지 중요한 차이점이 있습니다.

1. 목표 함수: Ridge 회귀는 오차 제곱의 합 (즉, 잔차 제곱의 합)을 최소화하고자 합니다. 이는 모든 관찰치를 고려한 모델을 만듭니다. 이와 대조적으로, SVM은 마진을 최대화하는 결정 경계를 찾습니다. 마진은 클래스 사이의 거리로, SVM은 이를 최대화하여 최적의 결정 경계를 찾으려고 합니다. 이로 인해 SVM은 모든 데이터 포인트를 고려하지 않고, 결정 경계 근처의 '서포트 벡터'라는 특정 데이터 포인트만 고려합니다.

2. 과적합 방지: Ridge 회귀는 L2 정규화 방식을 사용하여 모델의 복잡성을 제한하고 과적합을 방지합니다. 이는 모든 가중치를 약간씩 축소시킴으로써 모델을 단순화합니다. 반면, SVM은 소프트 마진 분류를 통해 일부 오분류를 허용함으로써 과적합을 방지합니다.

3. 비선형 패턴: Ridge 회귀는 선형 패턴을 가정하지만, SVM은 비선형 패턴을 캡처할 수 있습니다. SVM은 '커널 트릭'을 사용하여 고차원 공간에서 분리 가능한 결정 경계를 찾을 수 있습니다.

이러한 차이점들로 인해, Ridge 회귀는 오차를 최소화하는 선형 회귀 모델이 필요한 경우 유용하며, SVM은 복잡하고 비선형적인 데이터 패턴을 처리해야 하는 복잡한 분류 문제에 더 적합할 수 있습니다.

그림 11.2는 L1 정규화(Lasso)와 L2 정규화(Ridge)가 어떻게 파라미터를 제한하는지를 보여주는 대표적인 그림입니다. L1 정규화의 경우 diamond-shaped 등치선을 가지며, L2 정규화의 경우 circular 등치선을 가집니다.

L1 정규화는 가중치 벡터의 L1 norm (즉, 가중치의 절대값의 합)을 최소화하려는 성질을 가집니다. 이는 특정 가중치가 0이 되는 희소한 해를 생성하는 경향이 있습니다. 이는 diamond-shaped 등치선이 w1, w2 축과 만나는 지점(즉, 축의 교차점)에서 최적화 문제의 해를 찾는 경향이 있기 때문입니다. 이러한 지점에서 가중치 중 하나가 0이 됩니다.

그러나 L1 정규화가 항상 희소한 해를 생성하는 것은 아닙니다. 예를 들어, L1 정규화의 등치선과 평균 오차 등치선이 교차하는 지점이 축의 교차점이 아닌 경우에는 희소한 해를 생성하지 않을 수 있습니다. 이런 상황은 오차 등치선이 가중치 축에 거의 수직인 경우 등에서 발생할 수 있습니다. 

이 경우, L1 정규화의 등치선이 오차 등치선을 더 큰 각도로 교차하는 위치에서 최적의 해를 찾게 되고, 이는 가중치가 0이 아닌 값을 가지는 경우가 됩니다. 따라서, 이러한 특정 상황에서는 L1 정규화가 희소한 해를 생성하지 않게 됩니다.

Relief 알고리즘의 변형으로는 ReliefF, SURF, SURFStar, MultiSURF 등이 있습니다. 이들은 Relief 알고리즘을 기반으로 하되, 문제의 특성에 맞게 속성 중요도를 더 효과적으로 계산하는 방법을 제공합니다.

LVW (Local-Valued-Relief) 는 Relief 알고리즘의 변형 중 하나로, 가장 가까운 이웃을 이용하지 않고 모든 이웃의 영향을 고려해 속성 중요도를 계산하는 방식입니다. 

기본적인 아이디어는 각 속성에 대해 그 속성의 값을 기반으로 모든 이웃을 가중치를 주어 평가하는 것입니다. 이는 각 속성에 대해 "로컬" 값 (즉, 각 인스턴스에서 해당 속성의 값)을 사용하는 Relief 알고리즘의 일반화입니다.

제한 시간에 상관없이 해를 구하는 것은 알고리즘의 최적화와 관련된 문제입니다. 대부분의 머신러닝 알고리즘은 반복적인 프로세스를 통해 모델을 훈련시키므로, 어느 정도의 시간 제약이 있습니다. 이러한 시간 제약을 완화하기 위해 병렬 컴퓨팅, 분산 컴퓨팅, GPU 가속 등의 기술을 활용할 수 있습니다.

그러나 이러한 방법들이 늘 최적의 해를 보장하는 것은 아닙니다. 결국, 최적의 해를 찾는 것은 문제의 복잡도, 사용 가능한 계산 자원, 그리고 알고리즘의 효율성에 크게 의존합니다. 따라서 특정한 해를 무제한 시간 안에 찾는 것을 보장하기 위해서는 문제의 복잡도를 줄이거나, 계산 자원을 늘리거나, 더 효율적인 알고리즘을 사용하는 등의 방법을 고려해야 합니다.

속성의 중요성을 고려하는 다른 개선 알고리즘을 구상하면 다음과 같을 수 있습니다:

Entropy-Based Feature Selection 알고리즘:

1. 데이터셋의 각 속성에 대한 엔트로피를 계산합니다. 엔트로피는 데이터의 불확실성을 측정하는 방법으로, 낮은 엔트로피는 예측 가능성이 높은 것을 의미하며, 높은 엔트로피는 예측이 어려운 것을 의미합니다.

2. 각 속성을 기준으로 데이터를 분할합니다. 그 후, 이 분할에 대한 정보 이득(전체 엔트로피와 분할 후 엔트로피의 차이)을 계산합니다. 

3. 가장 높은 정보 이득을 가진 속성을 최상위 노드로 선택합니다. 이렇게 선택된 속성은 클래스 분류에 가장 중요하다고 간주됩니다.

4. 데이터셋을 선택된 속성에 따라 분할하고, 각 하위 데이터셋에 대해 위의 과정을 반복합니다. 이 과정을 모든 속성이 사용되거나, 모든 데이터 포인트가 동일한 클래스에 속할 때까지 반복합니다.

5. 마지막으로, 각 속성의 중요도는 그들이 트리에서 얼마나 높은 위치에 있는지(즉, 얼마나 일찍 선택되는지)에 따라 결정됩니다.

이 알고리즘은 Relief 알고리즘과는 달리 각 속성을 개별적으로 고려하는 대신, 그들이 전체적으로 클래스 분류에 어떤 영향을 미치는지를 고려합니다. 이 방식은 특히 속성 간의 상호 작용이 중요하지 않은 문제에 적합합니다.