주어진 점들 중 최대 맨해튼 거리(Manhattan Distance)를 빠르게 찾는 방법

https://atcoder.jp/contests/abc178/tasks/abc178_e E - Dist MaxAtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.atcoder.jp   n개의 점이 주어질때, 이들 쌍으로 만들 수 있는 가장 긴 맨해튼 거리는? n이 최대 20만이기 때문에 $O(N^2)$으로 직접 비교할 수는 없다 두 점 (xi,yi), (xj,yj)에 대하여 맨해튼 거리는 |xi - xj| + |yi - yj| = A A는 xi,xj, yi,yj 사이 대소관계에 따라 다음과 같이 풀어낼 수 있다 1) $x_{i} >= x_{j}..

• format_list_bulleted 알고리즘/애드 혹 알고리즘
• · 2024. 10. 23.
• textsms

L1 regularization vs. L2 regularization vs. elastic net 비교하기

1. elastic net 알고리즘 L1 regularization과 L2 regularization을 모두 사용한 regularization loss에 L1 term과 L2 term의 선형결합을 더해서 모델을 학습시키는 알고리즘   2. L1 , L2, elastic net 비교 L1, L2는 모두 계수 $\lambda$가 크면 클수록 parameter를 축소시킨다. L2는 parameter를 0으로 근사시키나 L1은 parameter를 완전하게 0으로 축소시키는 경향이 있다. L1은 무수히 많은 변수들이 있는데 영향력이 강력한 변수들은 별로 없다고 생각이 들면 대부분의 변수를 0으로 축소시켜 일부 변수만 선택하고자할때 유리함 그러나 L1은 covariate가 sample에 비해 충분히 많을 때 상관관..

• format_list_bulleted 딥러닝/딥러닝 기초
• · 2024. 6. 17.
• textsms

Regularization에 대해 꼭 생각해봐야하는 점(L2 regularization, dropout의 단점, early stopping의 단점, data augmentation의 단점)

모델이 validation set에 성능을 내지 못할때, training data에 overfitting이 되었을때 데이터를 더 많이 얻는 것은 좋은 방법이지만 항상 그럴 수는 없다. 그럴때 시도하면 좋은 것이 regularization L2 regularization은 가중치 W의 L2 norm, L1 regularization은 가중치 W의 L1 norm을 더해주는데... 1. 여기서 하나 bias도 parameter인데 왜 가중치 W 항만 더해주는것인가? 모델의 거의 모든 parameter가 W에 집중되어 있기 때문에 bias를 더할수도 있지만 계산비용 대비 거의 차이가 없다고 한다 2. L2 regularization을 일반적으로 많이 사용한다. L1 regularization을 사용하면 가중치 ..

• format_list_bulleted 딥러닝/Deep Learning Specialization
• · 2024. 1. 13.
• textsms

벡터 사이의 거리 norm

벡터의 norm은 벡터 사이 거리로 정의된다. 그런데 벡터 사이 거리를 어떻게 정의할까? 일반적으로 유클리드 거리를 생각하지만 사실 거리를 정의하는 방법은 다양하다 임의의 n차원에서 거리를 정의한다는 것이 중요하다. 첫번째는 L1 norm, 두번째는 L2 norm이라고 부른다 1. L1 norm의 기하학적인 의미 L1 norm이란 원점에서 x까지의 거리를 위 그림에서 빨간 선분의 총 길이로 정의하는 것이다. 2. L2 norm의 기하학적 의미 L2 norm은 x까지의 거리를 위와 같이 직선거리로 정의하는 것이다. 3. norm에 따른 원 원은 원점에서 거리가 r인 점의 집합이라는 사실로부터 3-1) L1 norm을 사용한 원 robust 방법, lasso 회귀 등에서 사용 3-2) L2 norm을 사용한..

• format_list_bulleted 선형대수학
• · 2022. 1. 3.
• textsms

여러가지 regularization 기법

1. regularization generalization이 잘 되게하고자 학습을 방해하는 요소를 추가하여 학습뿐만 아니라 test에도 잘 동작하는 모형을 만드는 방법 여러가지 방법들 모두 시도해보면서 잘 되면 좋고 아님 말고… 2. Early stopping Early stopping은 iteration이 증가할 수록 test error는 증가하니 증가하기 전에 멈추자는 원리 특히 test data는 학습 과정에서 사용하면 안되니까 train data의 일부인 validation set으로 평가했다는 점이 주목할만 하다. 3. Parameter norm penalty Parameter norm penalty는 네트워크의 parameter가 크기면에서 너무 커지지 않았으면 하는 바람에서 나온 것 L1, ..

• format_list_bulleted 딥러닝/딥러닝 기초
• · 2021. 12. 26.
• textsms

L1(Lasso)과 L2 regularization(Ridge)에 대한 고찰

1) L1(절댓값 함수)과 L2(제곱 함수) regularization 항을 그래프로 그려보면 weight parameter중 하나가 0으로 가까이 가면 L2 regularization은 나머지 하나도 0으로 가까이 가는 듯 하지만 0은 아닌데 L1 regularization은 확실하게 0으로 가려고 한다 결론은 L1 regularization은 많은 weight를 0으로 만들어낼 수있는데 L2 regularization은 0에 가까운 weight들을 만들어낸다. 2) 이 사실을 다른 그림을 통해 직관적으로 살펴보면 2개의 paramete $W _{1},W _{2}$가 있다고 가정하고 2가지 regularization에 대하여 regularization 항이 최소한 $s$이내에 있어야한다고 하면 $$\l..

• format_list_bulleted 딥러닝/딥러닝 기초
• · 2021. 12. 17.
• textsms