DataManyo

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

Relief-F는 데이터 마이닝 및 머신러닝에서 특징 선택을 위해 사용되는 알고리즘입니다. Relief 알고리즘의 확장판으로, 멀티 클래스 문제를 처리할 수 있고, 불완전하거나 잡음이 많은 데이터에 대한 강건성을 향상시킵니다. 

Relief-F 알고리즘의 주요 아이디어는 원래 클래스와 가장 가까운 인스턴스(이웃)와 가장 가까운 인스턴스 중 다른 클래스를 각각 찾는 것입니다. 이를 통해 각 특징이 클래스 구분에 얼마나 중요한지 평가하고, 중요도에 따라 특징을 선택합니다.

Relief-F 알고리즘의 기본적인 단계는 다음과 같습니다:

1. 각 특징의 가중치를 0으로 초기화합니다.
2. 지정된 횟수만큼 다음 과정을 반복합니다:
    - 무작위로 인스턴스를 선택합니다.
    - 선택한 인스턴스와 같은 클래스의 가장 가까운 이웃을 찾습니다.
    - 선택한 인스턴스와 다른 클래스의 가장 가까운 이웃을 찾습니다.
    - 각 특징에 대해, 선택한 인스턴스와 같은 클래스의 이웃과의 차이를 계산하고 가중치에서 빼줍니다.
    - 각 특징에 대해, 선택한 인스턴스와 다른 클래스의 이웃과의 차이를 계산하고 가중치에 더해줍니다.
3. 모든 특징의 가중치를 확인하고, 가중치가 높은 특징부터 낮은 특징까지 순서대로 나열합니다.

위의 방법을 통해 Relief-F 알고리즘은 특징 선택을 위한 중요도 순서를 제공하게 됩니다. 이 알고리즘은 특히 특징 간의 상호작용이 예측 성능에 영향을 미치는 경우 유용합니다.

Relief 알고리즘을 직접 코드로 구현하는 것은 조금 복잡할 수 있지만, 이해를 돕기 위해 기본적인 아이디어를 파이썬 코드로 표현해 보겠습니다.

다음 코드는 실제 Relief 알고리즘의 간략화 된 버전이며, 실제로 작동하려면 입력 데이터와 함께 조정 및 추가 구현이 필요합니다.

또한, 이 코드는 scikit-learn 라이브러리의 K-Nearest Neighbors(KNN) 알고리즘을 사용하여 가장 가까운 이웃을 찾습니다.

import numpy as np
from sklearn.neighbors import NearestNeighbors

def relief(X, y, m):
    """
    X : Data instances
    y : Class labels
    m : Number of sampled instances
    """

    # Initialize a weight vector to zeros
    weights = np.zeros(X.shape[1])
    for i in range(m):
        # Randomly select an instance
        idx = np.random.randint(0, X.shape[0])

        # Split the data into same and different class
        same_class = X[y==y[idx]]
        diff_class = X[y!=y[idx]]

        # Find the nearest neighbor from the same class
        nn_same = NearestNeighbors(n_neighbors=1).fit(same_class)
        distances_same, indices_same = nn_same.kneighbors(X[idx].reshape(1, -1))
        near_same = same_class[indices_same[0][0]]

        # Find the nearest neighbor from the different class
        nn_diff = NearestNeighbors(n_neighbors=1).fit(diff_class)
        distances_diff, indices_diff = nn_diff.kneighbors(X[idx].reshape(1, -1))
        near_diff = diff_class[indices_diff[0][0]]

        # Update the weights
        weights -= np.square(X[idx] - near_same)
        weights += np.square(X[idx] - near_diff)

    return weights

위의 코드는 Relief 알고리즘의 간략화 된 버전이기 때문에, 실제 데이터세트에 적용하려면 추가적인 사전 처리 단계와 최적화가 필요할 수 있습니다. 예를 들어, 코드는 현재 수치형 속성에만 적용됩니다. 범주형 속성이 있는 경우, 해당 속성을 적절하게 처리해야 할 것입니다. 또한, 거리 메트릭에 따라 결과가 크게 달라질 수 있으므로, 문제에 가장 적합한 메트릭을 선택하는 것이 중요합니다.

DBSCAN의 기본 정의에 기반해, x가 핵심 대상이라면 x 밀도에 의해 커버되는 모든 샘플로 구성된 집합을 X라 한다. X는 연속성(식 9.39)과 최대성(식 9.40)을 만족한다는 사실을 증명하라.

문제 정의에 의해 최대성은 만족.

연속성 만족 증명:

x_i를 핵심 대상이라고 가정한다면, x_j는 x_i밀도에 의해 density-reachable이다. 따라서 핵심 대상 x_k가 존재하고, 이는 x_i와 x_k에 direct density reachable이고, x_k와 x_j 의 direct density reachable이다.

x_k는 핵심 대상이기 때문에 x_k와 x_i는 direct density reachable이다. 

또한 direct density reachable 은 density reachable의 부분집합이기 때문에,

x_k와 x_j는 density reachable이다. 그리고 x_k와 xi는 density reachable이고 x_i와 x_j는 density connected 관계이다.

참고:

• Direct density reachable : 점 p가 점 q의 반경에 들어오고, 점 q가 코어점일 때, "점 p가 점 q로부터 직접적으로 밀도(기반)-도달가능한 관계에 있다"고 한다. 반대의 경우는 성립하지 않음.

• Density reachable : 점 p와 점 q 사이에 p1,p2,⋯,pn,p1=q,pn=pp1,p2,⋯,pn,p1=q,pn=p 들이 있고, 점 pi+1pi+1이 점 pipi로 부터 직접적으로 밀도(기반)-도달가능하다면, "점 p는 점 q로부터 밀도(기반)-도달가능한 관계에 있다."고 한다. 

• Density connected : 만약 두 점 p와 q가 모두 어떤 점 O로 부터 반경 내 MinPts 조건 하에 밀도(기반)-도달가능(density-reachable)하다면 "점 p는 점 q와 반경 내 MinPts 조건 하에 밀도(기반)-연결되었다."고 합니다.
  => (다르게 말하면, p가 O의 친구이고, q도 O의 친구이면, p와 q는 친구 O를 통해 서로 연결되었다고 보면 된다.)

설명 출처:

https://syj9700.tistory.com/40#:~:text=Direct%20density%20reachable%20%3A%20%EC%A0%90%20p,%EA%B4%80%EA%B3%84%EC%97%90%20%EC%9E%88%EB%8B%A4%22%EA%B3%A0%20%ED%95%9C%EB%8B%A4.