DETR 논문 리뷰

Introduction

Object Detection의 목표는 bounding box의 좌표와 카테고리 레이블을 예측하는 것입니다. 기존 인공지능 모델은 이러한 set prediction task를 regression과 classification 문제로 나누어서 간접적으로 접근했습니다. 기존 인공지능 모델과 달리 DETR은 CNN과 트랜스포머 아키텍처를 결합하여 집합을 한 번에 예측합니다.

집합은 이미지 내에서 감지된 모든 객체의 모음을 의미합니다. 각 객체는 일반적으로 바운딩 박스(bounding box)와 카테고리 레이블(category label)로 표현됩니다.

Related work

집합 예측(set prediction)은 멀티레이블 분류(multilabel classification) 문제의 일종으로, 이 문제에서 가장 큰 도전은 서로 거의 동일한 예측이나 중복된 예측을 피하는 것입니다. 기존의 객체 탐지 모델들은(Faster RCNN, YOLO) 비최대 억제(Non-Maximum Suppression, NMS)라는 후처리 과정을 사용하여 중복된 예측을 제거합니다.

반면에 글로벌 추론(global inference)은 이미지 안의 모든 객체를 한 번에 인식하고 분석합니다. DETR은 이미지 전체를 종합적으로 보고 객체를 탐지합니다. 이 모델은 이미지 전체의 정보를 사용하여, 강아지의 머리와 몸통이 서로 연결되어 있다는 것을 이해하고 한 마리의 강아지로 정확히 인식할 수 있습니다.

이러한 글로벌 추론은 Transformer 모델과 병렬 디코딩(parallel decoding) 방식을 사용하여 구현됩니다. Transformer는 self-attention 메커니즘을 사용하여 데이터의 전체적인 context을 한 번에 파악하고, 병렬 디코딩을 통해 모든 예측을 동시에 수행합니다.

손실 함수는 Hungarian algorithm을 기반으로 한 bipartite matching loss을 사용합니다. 이는 각각의 실제 대상 요소가 예측과 일대일로 매칭되도록 하여 중복을 효과적으로 방지합니다.

Transformers (Perfect Memory): 트랜스포머 모델은 모든 입력 정보를 기억하고, 이를 기반으로 전체적인 추론을 수행할 수 있는 "완벽한 기억" 능력을 가집니다.

Auto-Regressive Models (Prohibitive Inference Cost): 자동회귀 모델은 한 번에 하나의 출력만을 생성하기 때문에, 병렬 처리가 불가능하고 추론 비용이 높습니다.

Parallel Decoding (Simultaneously): 트랜스포머는 모든 객체를 동시에 병렬로 디코드할 수 있어, 추론 시간을 대폭 단축시키고 효율성을 높입니다.

The DETR model

Object Detection set prediction loss

1. Bipartite Matching (이항 매칭): 먼저, 모델의 예측과 실제 객체 사이의 최적 매칭을 찾아야 합니다. 이를 위해 모든 가능한 매칭 조합을 고려하여, 예측과 실제 데이터 사이의 매칭 비용 L_match을 최소화하는 최적의 매칭 σ을 찾습니다. 이 과정에서 헝가리안 알고리즘이 사용됩니다.
2. Matching Cost (매칭 비용): 매칭 비용은 예측된 객체와 실제 객체 사이의 비용을 측정합니다. 클래스 레이블에 대한 예측이 정확하면 비용이 낮아지고, 바운딩 박스의 위치가 실제와 정확히 일치하면 또한 비용이 낮아집니다. 만약 예측된 객체가 "no object" 클래스라면, 이에 대한 비용은 계산되지 않습니다.
3. Loss Function (손실 함수): 이항 매칭을 통해 결정된 최적의 매칭을 바탕으로, 모델의 전체 손실을 계산합니다. 이 손실은 모든 예측된 객체에 대해 계산되며, 클래스 레이블에 대한 예측 손실과 바운딩 박스의 손실을 모두 포함합니다.
4. Bounding Box Loss (바운딩 박스 손실): 각 예측된 바운딩 박스와 실제 바운딩 박스 사이의 차이를 측정합니다. 이 손실은 일반적으로 IoU 손실과 L1 거리 손실을 포함하여 계산되며, 이러한 각각의 손실에는 가중치 λ가 적용됩니다.

이러한 4단계를 통해, DETR 모델은 이미지 내의 각 객체에 대해 정확한 클래스 레이블을 할당하고, 각 객체의 위치를 정확하게 예측하는 방법을 학습합니다. 손실 함수는 모델이 잘못된 예측을 할 때마다 페널티를 부여하여, 모델이 실제 객체의 정확한 클래스와 위치를 더 잘 예측하도록 돕습니다. 전체 학습 과정에서 모델은 이 손실을 최소화하는 방향으로 파라미터를 조정합니다.

The DETR model Architecture

1. Backbone (CNN): DETR은 이미지에서 고차원 특징을 추출하기 위해 전통적인 CNN 백본을 사용합니다. 이 백본은 2차원 이미지를 입력으로 받아 처리합니다.
2. Positional Encoding: Transformer 구조는 입력 embedding의 순서와 상관없이 같은 출력값을 생성하기 때문에 encoder layer 입력 전에 입력 embedding에 positional encoding을 더해줍니다.
3. Transformer Encoder: 포지셔널 인코딩이 추가된 특징들은 트랜스포머 인코더를 거치게 됩니다. 인코더는 이 특징들 사이의 관계를 이해하고, 이미지 전체의 컨텍스트를 포착하기 위해 자기 주의(self-attention) 메커니즘을 사용합니다.
4. Object Queries: Object query features는 이미지 내의 객체를 식별하기 위한 초기 prediction을 제공하고, object query positional embeddings는 디코더가 해당 객체의 위치에 attention할 수 있도록 도와줍니다.
5. Transformer Decoder: 디코더는 인코더의 출력과 오브젝트 쿼리를 기반으로 하여, 각 객체의 위치와 클래스에 대한 예측을 생성합니다.

Experiments

Comparison with Faster R-CNN

1. GFLOPS: Giga Floating Point Operations Per Second의 약자로, 모델이 수행하는 부동소수점 연산의 수를 기가 단위로 나타냅니다. 낮은 GFLOPS는 모델이 더 적은 계산으로 동작한다는 것을 의미합니다. 즉, 모델이 더 효율적이라는 것을 뜻합니다.
2. FPS: Frames Per Second의 약자로, 모델이 초당 처리할 수 있는 이미지 프레임 수입니다. 높은 FPS는 더 빠른 추론 속도를 의미합니다.
3. #params: 모델이 가진 파라미터의 총 수로, 모델의 크기와 복잡성을 나타냅니다.
4. AP (Average Precision): 모델이 객체 탐지 작업을 수행하는 정확도를 나타냅니다. AP는 PR-curve 그래프 아래 면적입니다.
5. AP50, AP75: 이는 IoU(Intersection over Union)가 0.5 또는 0.75일 때의 AP입니다. IoU는 예측된 바운딩 박스와 실제 바운딩 박스의 오버랩 정도를 측정하며, AP50과 AP75는 이러한 IoU 임계값에서 모델의 정확도를 나타냅니다.
6. AP_S, AP_M, AP_L: 이는 각각 작은(Small), 중간(Medium), 큰(Large) 크기의 객체에 대한 모델의 AP를 나타냅니다. 이 지표들은 모델이 다양한 크기의 객체를 얼마나 잘 탐지하는지를 보여줍니다.

표에 따르면, DETR 모델은 기존의 Faster R-CNN 모델들과 비교하여 상대적으로 낮은 GFLOPS와 높은 FPS를 가지며, 적은 수의 파라미터로도 높은 AP 점수를 달성했습니다. 특히, 큰 객체(AP_L)에 대해서는 Faster R-CNN 모델들보다 높은 성능을 보여준 것으로 나타납니다. 이는 DETR이 효율적인 모델 구조를 가지면서도 높은 정확도를 제공할 수 있음을 의미합니다.

Comparison with UPSNet and Panoptic FPN

1. PQ (Panoptic Quality): Panoptic Segmentation 작업에 대한 성능을 측정하는 지표로, 물체 탐지(object detection)와 세그멘테이션(segmentation)의 정확성을 모두 고려합니다. PQ는 높을수록 모델의 성능이 좋다는 것을 의미합니다.
2. SQ (Segmentation Quality): 탐지된 각 객체의 세그멘테이션 마스크의 정확성을 평가합니다. SQ는 주로 세그멘테이션의 정밀도를 나타냅니다.
3. RQ (Recognition Quality): 얼마나 많은 객체가 정확하게 분류되었는지를 측정합니다. RQ는 객체 인식의 정확도를 평가합니다.
4. PQ^th (Things Panoptic Quality): ‘things’ 클래스(일반적으로 이산적인 객체를 의미함)에 대한 PQ를 나타냅니다.
5. SQ^th (Things Segmentation Quality): ‘things’ 클래스에 대한 SQ를 나타냅니다.
6. RQ^th (Things Recognition Quality): ‘things’ 클래스에 대한 RQ를 나타냅니다.
7. PQ^st (Stuff Panoptic Quality): ‘stuff’ 클래스(일반적으로 연속적인 영역 또는 배경을 의미함)에 대한 PQ를 나타냅니다.
8. SQ^st (Stuff Segmentation Quality): ‘stuff’ 클래스에 대한 SQ를 나타냅니다.
9. RQ^st (Stuff Recognition Quality): ‘stuff’ 클래스에 대한 RQ를 나타냅니다.
10. AP (Average Precision): 객체 탐지에서 사용되는 지표로, 모델이 객체의 클래스와 위치를 얼마나 잘 예측하는지를 평가합니다.

표에 따르면, DETR 모델은 다양한 백본(ResNet-50, ResNet-101)과 결합하여, ‘things’와 ‘stuff’ 카테고리 모두에서 괜찮은 PQ를 달성하며, 특히 ‘things’ 카테고리에서 높은 SQ와 RQ를 보여줍니다. DETR은 상대적으로 적은 파라미터로 이러한 성과를 달성하여, 모델의 효율성과 성능의 균형을 잘 보여줍니다.

Conclusion

DETR: Transformers와 bipartite matching loss를 활용하여 직접적인 set prediction을 가능하게 하는 Object Detection System입니다. COCO 데이터셋에서 최적화된 Faster R-CNN과 비슷한 수준의 성능을 보이며, 유연한 아키텍처를 바탕으로, 경쟁력 있는 결과를 제공하면서 panoptic segmentation까지 확장할 수 있습니다. Self-attention을 통한 전역 정보 처리로 인해 Large Objects에 대한 성능이 향상되었으나, Training, optimization, 그리고 Small Objects에 대한 성능은 향후 개선이 필요합니다.

1. Voting Classifiers

Suppose you have trained a few classifiers, each one achieving about 80% accuracy.

A very simple way to create an even better classifier is to aggregate the predictions of each classifier and predict the class that gets the most votes.

• This majority-vote classifier is called a hard voting classifier

Similarly, suppose you build an ensemble containing 1,000 classifiers that are individually correct only 51% of the time (barely better than random guessing).

However, this is only true if all classifiers are perfectly independent, making uncorrelated errors, which is clearly not the case because they are trained on the same data.

• They are likely to make the same types of errors, so there will be many majority votes for the wrong class, reducing the ensemble’s accuracy.

Ensemble methods work best when the predictors are as independent from one another as possible.

You can tell Scikit-Learn to predict the class with the highest class probability, averaged over all the individual classifiers.

• This is called soft voting.
• All you need to do is replace voting="hard" with voting="soft" and ensure that all classifiers can estimate class probabilities.
• This is not the case for the SVC class by default, so you need to set its probability hyperparameter to True (this will make the SVC class use cross-validation to estimate class probabilities, slowing down training, and it will add a predict_proba() method).

  2. Bagging and Pasting

  Another approach is to use the same training algorithm for every predictor and train them on different random subsets of the training set.

When sampling is performed with replacement, this method is called bagging (short for bootstrap aggregating). When sampling is performed without replacement, it is called pasting.

Each individual predictor has a higher bias than if it were trained on the original training set, but aggregation reduces both bias and variance.

• Generally, the net result is that the ensemble has a similar bias but a lower variance than a single predictor trained on the original training set.

With bagging, some instances may be sampled several times for any given predictor, while others may not be sampled at all.

Since a predictor never sees the oob instances during training, it can be evaluated on these instances, without the need for a separate validation set.

3. Random Patches and Random Subspaces

The BaggingClassifier class supports sampling the features as well. Sampling features results in even more predictor diversity, trading a bit more bias for a lower variance.

4. Random Forests

The Random Forest algorithm introduces extra randomness when growing trees; instead of searching for the very best feature when splitting a node, it searches for the best feature among a random subset of features.

• The algorithm results in greater tree diversity, which (again) trades a higher bias for a lower variance, generally yielding an overall better model.

Another great quality of Random Forests is that they make it easy to measure the relative importance of each feature.

• Scikit-Learn measures a feature’s importance by looking at how much the tree nodes that use that feature reduce impurity on average (across all trees in the forest).
• More precisely, it is a weighted average, where each node’s weight is equal to the number of training samples that are associated with it.

Scikit-Learn computes this score automatically for each feature after training, then it scales the results so that the sum of all importances is equal to 1.

5. Boosting

Boosting (originally called hypothesis boosting) refers to any Ensemble method that can combine several weak learners into a strong learner.

• The general idea of most boosting methods is to train predictors sequentially, each trying to correct its predecessor.

AdaBoost

One way for a new predictor to correct its predecessor is to pay a bit more attention to the training instances that the predecessor underfitted.

• This results in new predictors focusing more and more on the hard cases.

Gradient Boosting

Just like AdaBoost, Gradient Boosting works by sequentially adding predictors to an ensemble, each one correcting its predecessor.

However, instead of tweaking the instance weights at every iteration like AdaBoost does, this method tries to fit the new predictor to the residual errors made by the previous predictor.

6. Stacking

Stacking (short for stacked generalization)

• It is based on a simple idea: instead of using trivial functions (such as hard voting) to aggregate the predictions of all predictors in an ensemble, why don’t we train a model to perform this aggregation.

The following regression task: Each of the bottom three predictors predicts a different value (3.1, 2.7, and 2.9), and then the final predictor (called a blender, or a meta learner) takes these predictions as inputs and makes the final prediction (3.0).

To train the blender, a common approach is to use a hold-out set.

• First, the training set is split into two subsets. The first subset is used to train the predictors in the first layer.
• Next, the first layer’s predictors are used to make predictions on the second (held-out) set. This ensures that the predictions are “clean,” since the predictors never saw these instances during training.
• We can create a new training set using these predicted values as input features (which makes this new training set 3D), and keeping the target values.
• The blender is trained on this new training set, so it learns to predict the target value, given the first layer’s predictions

It is actually possible to train several different blenders this way (e.g., one using Linear Regression, another using Random Forest Regression), to get a whole layer of blenders.

1. Decision Tree (Training, Visualizing, Making Predictions)

Like SVMs, Decision Trees are versatile Machine Learning algorithms that can perform both classification and regression tasks, and even multioutput tasks.

A node’s samples attribute counts how many training instances it applies to.

• Ex: 100 training instances have a petal length greater than 2.45 cm (depth 1, right), and of those 100, 54 have a petal width smaller than 1.75 cm (depth 2, left).

A node’s value attribute tells you how many training instances of each class this node applies to

• Ex: the bottom-right node applies to 0 Iris setosa, 1 Iris versicolor, and 45 Iris virginica

A node’s gini attribute measures its impurity: a node is “pure” (gini=0) if all training instances it applies to belong to the same class.

• EX: since the depth-1 left node applies only to Iris setosa training instances, it is pure and its gini score is 0

A Decision Tree can also estimate the probability that an instance belongs to a particular class k. First it traverses the tree to find the leaf node for this instance, and then it returns the ratio of training instances of class k in this node.

• Ex: suppose you have found a flower whose petals are 5 cm long and 1.5 cm wide. The corresponding leaf node is the depth-2 left node, so the Decision Tree should output the following probabilities: 0% for Iris setosa (0/54), 90.7% for Iris versicolor (49/54), and 9.3% for Iris virginica (5/54).

  2. The CART Training Algorithm

Once the CART algorithm has successfully split the training set in two, it splits the subsets using the same logic, then the sub-subsets, and so on, recursively.

CART algorithm is a greedy algorithm. Unfortunately, finding the optimal tree is known to be an NPComplete problem.

• It requires O(exp(m)) time, making the problem intractable even for small training sets.

  3. Regularization Hyperparameters

  Decision Trees make very few assumptions about the training data.
• As opposed to linear models, which assume that the data is linear.

If left unconstrained, the tree structure will adapt itself to the training data, fitting it very closely—indeed, most likely overfitting it.

• Such a model is often called a nonparametric model, not because it does not have any parameters but because the number of parameters is not determined prior to training, so the model structure is free to stick closely to the data.

To avoid overfitting the training data, you need to restrict the Decision Tree’s freedom during training. (=regularization)

• You can at least restrict the maximum depth of the Decision Tree.

The DecisionTreeClassifier class has a few other parameters that similarly restrict the shape of the Decision Tree:

• min_samples_split (the minimum number of samples a node must have before it can be split)
• min_samples_leaf (the minimum number of samples a leaf node must have)
• min_weight_fraction_leaf (same as min_samples_leaf but expressed as a fraction of the total number of weighted instances)
• max_leaf_nodes (the maximum number of leaf nodes)
• and max_features (the maximum number of features that are evaluated for splitting at each node).

❑ Increasing min_* hyperparameters or reducing max_* hyperparameters will regularize the model.

4. Regression

• The main difference is that instead of predicting a class in each node, it predicts a value.
• Ex: x1=0.6, then predicts value =0.111. This prediction is the average target value of the 110 training instances associated with this leaf node, and it results in a mean squared error equal to 0.015 over these 110 instances.

5. Instability

Decision Trees love orthogonal decision boundaries (all splits are perpendicular to an axis), which makes them sensitive to training set rotation.

• On the left, a Decision Tree can split it easily, while on the right, after the dataset is rotated by 45°, the decision boundary looks unnecessarily convoluted.

1. Linear SVM Classification

These instances are called the support vectors (SVM decision boundary). They are circled in Figure 5-1.

SVMs are sensitive to the feature scales. -> scaling is necessary!!

Hard margin classification

Two main issues with hard margin classification:

• First, it only works if the data is linearly separable.
• Second, it is sensitive to outliers.

Soft margin classification

• To avoid these issues, use a more flexible model.
• The objective is to find a good balance between keeping the street as large as possible and limiting the margin violations (i.e., instances that end up in the middle of the street or even on the wrong side).

C = 1 margin increase -> violation increase -> flexible -> not overfitting

C = 100 margin decrease -> violation decrease -> train fitting (noise sensitive) -> overfitting

2. Nonlinear SVM Classification

Polynomial Kernel

Fortunately, when using SVMs you can apply an almost miraculous mathematical technique called the kernel trick.The kernel trick makes it possible to get the same result as if you had added many polynomial features, even with very high-degree polynomials, without actually having to add them.

So there is no combinatorial explosion of the number of features because you don’t actually add any features.

If your model is overfitting, reduce the polynomial degree.

• If your model is underfitting, increase the polynomial degree.
• Hyperparameter coef0 controls how much the model is influenced by high-degree polynomials vs. low-degree polynomials.

Similarity features

let’s define the similarity function to be the Gaussian Radial Basis Function (RBF) with γ = 0.3. This is a bell-shaped function varying from 0 (very far away from the landmark) to 1 (at the landmark).

How to select the landmarks?

• The simplest approach is to create a landmark at the location of each and every instance in the dataset. training data x feature = 100 x 100
• Doing that creates many dimensions and thus increases the chances that the transformed training set will be linearly separable.
• The downside is that a training set with m instances and n features gets transformed into a training set with m instances and m features (assuming you drop the original features).
• If your training set is very large, you end up with an equally large number of features.

Gaussian RBF Kernel

Hyperparameter 𝛾

• Increasing 𝛾 makes bell-shaped curve narrower, so each instance’s range of influence is smaller: the decision boundary ends up being more irregular, wiggling around individual instances. → possibly overfitting
• Decreasing 𝛾 makes bell-shaped curve wider, so each instance has a larger range of influence: the decision boundary ends up smoother. → possibly underfitting

How to choose the kernel?

• As a rule of thumb, you should always try the linear kernel first, especially if the training set is very large or if it has plenty of features.
• If the training set is not too large, you should also try the Gaussian RBF kernel; it works well in most cases.
• Then if you have spare time and computing power, you can experiment with a few other kernels, using cross-validation and grid search.

The LinearSVC class is based on the liblinear library.

• It does not support the kernel trick, but it scales almost linearly with the number of training instances and the number of features. - O(m × n) The SVC class is based on the libsvm library, which implements an algorithm that supports the kernel trick.
• The training time complexity is between 𝑂𝑂(𝑚^2 × 𝑛) and 𝑂(𝑚^3 × 𝑛)
• This means that it gets dreadfully slow when the number of training instances gets large.
• This algorithm is perfect for complex small or medium-sized training sets.

3. SVM Regression

SVM supports linear and nonlinear regression. To use SVMs for regression instead of classification, the trick is to reverse the objective. SVM Regression tries to fit as many instances as possible on the street while limiting margin violations (i.e., instances off the street). The width of the street is controlled by a hyperparameter, 𝜖.

Adding more training instances within the margin does not affect the model’s predictions; thus, the model is said to be ϵ-insensitive.

4. Under the Hood

Hard Margin Objective

1. we want to minimize | 𝐰 | to get a large margin.
2. If we want to avoid any margin violations (hard margin), then we need the decision function to be greater than 1 for all positive training instances and lower than -1 for negative training instances.

Soft Margin Objective

We now have two conflicting objectives

1. make the slack variables as small as possible to reduce the margin violations.
2. 𝐰𝐓𝐰 as small as possible to increase the margin.

-> This is where C hyperparameter comes in: it allows us to define the trade-off between these two objectives

The hard margin and soft margin problems are both convex quadratic optimization problems with linear constraints. Such problems are known as Quadratic Programming (QP) problems.

The dual problem

Given a constrained optimization problem, known as the primal problem, it is possible to express a different but closely related problem, called its dual problem.

• Under some conditions, the dual problem can have the same solution as the primal problem
• Condition: the objective function is convex, and the inequality constraints are continuously differentiable and convex functions

Luckily, the SVM problem happens to meet these conditions, so you can choose to solve the primal problem or the dual problem; both will have the same solution.

The dual problem makes the kernel trick possible, while the primal does not.

4장 에지와 영역

에지(edge)는 물체 경계에 있는 점이다.

4.1 에지 검출

에지 검출 알고리즘은 물체 내부는 명암이 서서히 변하고 물체 경계는 명암이 급격히 변하는 특성을 활용한다.

4.1.1 영상의 미분

$$ f'(x) = \displaystyle \lim_{ \Delta x \to 0} \frac{f(x + \Delta x) - f(x)}{\Delta x} = f(x + 1) - f(x) $$

미분은 변수 x의 값이 미세하게 증가했을 때 함수의 변화량을 측정한다. 미분 연산을 디지털 연상에 어떻게 적용할까? 정수 좌표를 쓰는 디지털 영상에서는 x의 최소 변화량이 1이므로 델타 x = 1로 한다.

4.1.2 에지 연산자

다음 사진은 필터 u = ( -1, 1)로 컨볼루션 한 결과이다. 1차 미분은 에지가 어떤 방향을 향하는지(양수, 음수)에 대한 정보를 제공하지만 에지의 정확한 위치를 정하는 위치 찾기 문제가 생겼다.

u로 컨볼루션한 영상을 u로 한 번 더 컨볼루션하면 원래 영상을 두 번 미분한 2차 미분 영상 f’’로 볼 수 있다.

1차 미분 영상에서는 봉우리가 발생하고 2차 미분 영상은 영교차가 발생한다. 영교차란 왼쪽과 오른쪽에 부호가 다른 반응이 나타나고 자신은 0을 갖는 위치를 뜻한다.

에지 연산자 (-1, 1)은 너무 작고 대칭이 아니다. ( -1, 0, 1)로 확장해서 사용한다.

소벨이 가장 많이 쓰인다.

4.2 캐니 에지

캐니 에지는 에러율이 낮다는 장점이 있지만 구현이 복잡하고 수행 시간이 길다.

import cv2 as cv

img = cv.imread('soccer.jpg')
gray = cv.cvtColor(imag, cv.COLOR_BGR2GRAY)

canny1 = cv.Canny(gray, 50, 150)
canny2 = cv.Canny(gray, 100, 200)

cv.imshow('Canny1', canny1)
cv.imshow('Canny2', canny2)

다음은 예시 코드이다. 캐니 알고리즘은 거짓 긍정을 줄이기 위해 2개의 이력 임곗값 T(low), T(high)를 이용한 에지 추적을 추가로 적용한다. 거짓 긍정이란 실제 에지가 아닌데 에지로 검출된 화소를 뜻한다. 캐니는 T(high)를 T(low)의 2~3배로 설정할 것을 권고했다.

4.3 직선 검출

앞에서 에지로 검출된 에지 화소는 1, 에지가 아닌 화소는 0으로 표시한다. 이들을 연결하여 경계선으로 반환하고 경계선을 직선으로 변환하면 이후 단계인 물체 표현이나 인식에 무척 유리하다.

4.3.1 경계선 찾기

에지 맵에서 이웃한 에지를 연결하여 경계선을 검출한다.(p.128 ~ 129)

4.3.2 허프 변환

허프변환은 이미지에서 모양을 찾는 가장 유명한 방법이다. 에지를 연결하여 경계선을 검출하는 방법은 에지가 자잘하게 끊겨 나타나는 경우 문제가 발생한다. 이런 상황에 허프 변환을 적용하여 끊긴 에지를 모아 선분 또는 원 등을 검출할 수 있다.

한 점을 지나는 직선은 다음과 같이 표현할 수 있습니다.

$$ r = x\cos\Theta + y\sin\Theta $$

그럼 각 점(x,y)에 대해서 삼각함수를 이용하여 𝜃 값을 1 ~ 180까지 변화를 하면서 원점에서 (x,y)까지의 거리(r)을 구합니다. 그러면 (𝜃, r)로 구성된 180개의 2차원 배열을 구할 수 있다. 동일한 방법으로 두번째 점에 대해서도 𝜃값을 변화해 가면서 2차원 배열을 구한다.

허프 변환 — gramman 0.1 documentation

위 설명을 참고했습니다.

4.3.3 RANSAC

데이터 분포로부터 현저히 벗어난 점을 outlier라고 한다. 허브 변환, 최소제곱평균오차(MSE)는 outlier가 섞여 있는 데이터셋에서는 좋은 성능을 발휘하지 못한다.

Hypothesis - 가설 단계

전체 데이터에서 N개의 샘플을 선택하고, 선택된 샘플을 통해 모델을 예측한다.

Verification - 검증단계

데이터셋에서 모델과 일치하는 데이터의 수를 센 후, 최대 값일 경우 모델 파라미터를 새롭게 저장한다.

4.4 영역 분할

영역 분할은 물체가 점유한 영역을 구분해주는 작업이다. 에지가 완벽하다면 영역 분할이 필요하지 않지만 명암 변화가 낮은 곳에서 뚫려 폐곡선을 형성하지 못하는 경우 많다.

4.4.1 배경이 단순한 영상의 영역 분할

Watershed는 비가 오면 오목한 곳에 웅덩이가 생기는 현상을 모방하는 연산이다. 워터세드를 확장해 영역 분할에 활용할 수 있다.

[Image Processing] Watershed(워터쉐드) 적용하기

4.4.2 슈퍼 화소 분할

때론 영상을 아주 작은 영역으로 분할해 다른 알고리즘의 입력으로 사용하는 경우가 있다. 작은 영역은 화소보다 크지만 물체보다 작기 때문에 슈퍼 화소라 한다.

SLIC 알고리즘

k-means clustering과 유사하게 작동한다. (R, G, B, x, y)로 5차원 벡터를 형성하고 군집 중심 C(n)을 군집 중심이 물체 경계에 놓이지 않도록 그레디언트가 가장 낮은 이웃 화소로 이동시킨다. 화소 각각에 대해 주위 4개 군집 중심(k=8인 경우)과 자신까지 거리를 계산해서 가장 유사한 군집 중심에 할당한다. 화소 할당이 끝나면 각 군집 중심은 자신에게 할당된 화소를 평균해 군집 중심을 갱신한다. 모든 군집 중심의 이동량의 평균을 구하고 평균이 임계치보다 작으면 수렴했다고 판단하고 알고리즘을 멈춘다.

[머신러닝] K-평균(K-Means) 알고리즘

4.4.3 최적화 분할

앞선 알고리즘은 지역적 명암 변화만 살핀다. 배경색과 물체의 색이 비슷한 경우 경계가 형성되지 않을 수 있다. 이 문제를 해결하기 위해 지역적 명암 변화를 보되 전역적 정보를 같이 고려하는 방법을 사용한다. 이 방법을 사용하기 위해서는 주로 영상을 그래프로 표현하고 분할을 최적화 문제로 푼다.

앞서 언급한 5차원 벡터 v = (R, G, B, x, y) 사이의 거리가 사용자가 지정한 r 이내면 참이다.

$$ d_{pq} = \begin{cases} ||f(v_p) - f(v_q)|| & \text{if } v_q\in neighbor(v_p) \ inf. & \text{if not}
\end{cases} $$

$$ \text{similarity s } = \begin{cases} D - d_{pq}& \text{if } v_q\in neighbor(v_p) \ 0 & \text{if not } \end{cases} $$

정규화 절단 알고리즘: cut(C1, C2)라는 함수를 사용해 영역 분할의 좋은 정도를 측정한다.

4.5 대화식 분할

지금까지 다룬 분할 알고리즘은 영상 전체를 여러 영역으로 나눈다. 한 물체의 분할에만 관심이 있는 경우 초기 정보를 가지고 사용자의 의도에 맞게 물체를 분할한다.

4.5.1 능동 외각선

사용자가 물체 내부에 초기 곡선을 지정하면 곡선을 점점 확장하면서 물체 외곽선으로 접근하는 방법이다. 곡선이 꿈틀대면서 에너지가 최소인 상태를 찾아가기 때문에 스네이크라는 별명을 얻었다.

4.5.2 GrabCut

GrabCut 알고리즘은 이미지에서 배경이 아닌 전경에 해당하는 이미지를 추출해 내는 방법이다. 이미지에서 한번에 전경을 추출해 내는 것이 아닌 사용자와의 상호 작용을 통해 단계적으로 전경을 추출한다. 이 상호작용은 크게 2가지 단계로 진행되는데, 첫번째는 이미지에서 전경이 포함되는 영역을 사각형으로 대략적으로 지정한다. 그리고 두 번째는 첫 번째에서 얻어진 전경 이미지의 내용중 포함되어진 배경 부분은 어디인지, 누락된 전경 부분은 어디인지를 표시하면 이를 이용해 다시 전경 이미지가 새롭게 추출된다.

4.6 영역 특징

텍스처 특징

텍스처는 영상의 질감(반복되는 일정 패턴)이다. 텍스처가 세밀하면 많은 에지가 발생하고 거칠면 적게 발생한다. busy는 에지 화소 수를 전체 화소 수로 나누어 세밀함을 측정한다. mag는 에지 강도를 q 단계로 양자화하여 구한 히스토그램이고 dir은 에지 방향을 8단계로 양자화해 구한 히스토그램이다.

$$ T_{edge} = (busy, mag(i), dir(j)) $$

LBP(local binary pattern)는 빨간색 화소보다 큰 화소는 1 작은 화소는 0으로 표시한다.

LTP(local tenary pattern) (빨간색 화소 - 임계값 t)보다 작은 화소 -1 큰 화소 1

머신러닝 모델과 그들의 훈련 알고리즘을 대부분 black box처럼 취급했습니다. ch03을 통해 어떻게 했는지 모르고도 회귀 시스템을 최적화하고, 숫자 이미지 분류기를 개선하고, 심지어 스팸 분류기를 처음부터 구축할 수 있었던 것이 놀라웠습니다. 실제로 많은 상황에서는 구현 세부 사항을 알 필요가 없다고 합니다.

그러나 어떻게 작동하는지 이해하는 것이 적절한 모델, 사용할 훈련 알고리즘 및 작업을 위한 좋은 하이퍼파라미터 세트를 빠르게 찾을 수 있게 도와줍니다. 내부 작동 원리를 이해하면 문제를 디버깅하고 오류 분석을 더 효율적으로 수행하는 데도 도움이 됩니다. 마지막으로 이 장에서 논의되는 대부분의 주제는 신경망을 이해하고, 구축하고, 훈련시키는 데 필수적일 것입니다.

1. Linear Regression

선형 모델은 입력 특성의 가중합을 계산함으로써 예측을 수행하며, 이때 상수항인 편향 항을 더합니다. Linear model prediction formula: $$ y = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \ldots + \theta_n x_n $$ Vectorized form of Linear model prediction formula: $$ y = h_\theta(\mathbf{x}) = \theta^T \cdot \mathbf{x} $$

모델을 훈련시키는 것은 모델이 훈련 세트에 최적으로 적합하도록 그 파라미터를 설정하는 것을 의미합니다. 우리는 먼저 모델이 훈련 데이터에 얼마나 잘 (또는 얼마나 나쁘게) 적합하는지 측정할 필요가 있습니다.

루트 평균 제곱 오차 (Root Mean Square Error, RMSE) 따라서, 선형 회귀 모델을 훈련시키려면 RMSE를 최소화하는 θ의 값을 찾아야 합니다. 실제로는 RMSE를 최소화하는 것보다 평균 제곱 오차 (Mean Squared Error, MSE)를 최소화하는 것이 더 간단하며, 이는 동일한 결과를 이끌어냅니다.

The Normal Equation

Normal Equation은 비용 함수를 최소화하는 θ의 값을 직접 찾아주는 수학적 방정식입니다.

$$ \boldsymbol{\theta} = (\mathbf{X}^T \mathbf{X})^{-1} \mathbf{X}^T \mathbf{y} $$ 하지만 역행렬이 없는 행렬도 있습니다. 그런 경우 pseudo inverse를 사용하여 역행렬을 계산합니다. $$ \boldsymbol{\theta} = \mathbf{X}^+ \mathbf{y} $$ 유사 역행렬 자체는 특이값 분해(Singular Value Decomposition, SVD)라는 표준 행렬 분해 기법을 사용하여 계산됩니다.

Computational Complexity

정규 방정식은 X^T * X의 역행렬을 계산합니다. 이는 (n + 1) × (n + 1) 행렬입니다 (여기서 n은 특성의 수입니다). 이러한 행렬의 역행렬을 구하는 계산 복잡도는 대략 ( O(n^{2.4}) )에서 ( O(n^3) ) 사이로, 구현에 따라 달라집니다. 다시 말해, 특성의 수를 두 배로 늘리면, 계산 시간은 대략 ( 2^{2.4} = 5.3 )에서 ( 2^3 = 8 )까지 곱해집니다.

• Scikit-Learn의 LinearRegression 클래스에서 사용하는 SVD(특이값 분해) 접근법은 대략 ( O(n^2) )입니다.
  • 특성의 수를 두 배로 늘리면, 계산 시간은 대략 4배가 됩니다.
• 특성의 수가 많아질 때 (예: 100,000개), 정규 방정식과 SVD 접근법 모두 매우 느려집니다.
  • 긍정적인 측면으로, 두 방법 모두 훈련 세트의 인스턴스 수에 대해 선형적이므로 (즉, O(m), 메모리에 맞는 한 큰 훈련 세트를 효율적으로 처리할 수 있습니다.

2. Gradient Descent

이제 선형 회귀 모델을 훈련시키는 매우 다른 방법을 살펴볼 것입니다. 이 방법은 특성의 수가 많거나 메모리에 맞지 않을 정도로 많은 훈련 인스턴스가 있는 경우에 더 적합합니다.

경사 하강법은 다양한 문제에 대한 최적의 해를 찾을 수 있는 일반적인 최적화 알고리즘입니다. 경사 하강법의 일반적인 아이디어는 비용 함수를 최소화하기 위해 매개변수를 반복적으로 조정하는 것입니다. 이 방법은 매개변수 벡터 θ에 대한 오류 함수의 지역 기울기를 측정하고, 기울기가 감소하는 방향으로 진행합니다. 기울기가 0이 되면 최솟값에 도달한 것입니다!

먼저 θ를 랜덤 값으로 채웁니다(이것을 랜덤 초기화라고 합니다). 그런 다음 점진적으로 개선하며, 한 번에 한 걸음씩 걸으며, 각 단계에서 비용 함수(예: MSE)를 줄이려고 시도합니다, 알고리즘이 최소값에 수렴할 때까지 이어집니다. 학습률(Learning Rate)

걸음의 크기를 나타냅니다. 학습률이 너무 작으면 알고리즘이 수렴하기 위해 많은 반복을 거쳐야 하며, 이는 시간이 많이 걸립니다. 반면에, 학습률이 너무 높으면 계곡을 건너뛰어 반대편에 도달하게 되어 알고리즘이 발산할 수 있습니다.

구멍, 가장자리, 고원 및 모든 종류의 불규칙한 지형이 있을 수 있어 최소값에 수렴하는 것이 어렵게 만듭니다. 랜덤 초기화가 알고리즘을 왼쪽으로 시작하면 지역 최소값에 수렴하게 되며, 이는 전역 최소값만큼 좋지 않습니다.오른쪽에서 시작하면 고원을 가로질러 가는 데 매우 오랜 시간이 걸립니다. 그리고 너무 일찍 멈추면 전역 최소값에 도달하지 못합니다.

선형 회귀 모델의 MSE 비용 함수는 볼록 함수(bowl)라는 것이 밝혀졌습니다, 이는 곡선 상의 어떤 두 점을 선택하더라도 그들을 연결하는 선분이 곡선을 건너지 않는다는 것을 의미합니다.

이는 지역 최소값이 없고 단 하나의 전역 최소값만 있다는 것을 의미합니다. 또한 갑작스럽게 변하지 않는 기울기를 가진 연속 함수입니다.비용 함수가 볼록할 때, 경사 하강법은 긴 시간동안 기다리고 학습률이 너무 높지 않다면 전역 최소값에 임의로 접근할 것이 보장됩니다.

실제로, 비용 함수는 그릇의 형태를 가지고 있지만, 특성들의 스케일이 매우 다르다면 길쭉한 그릇의 형태를 가질 수 있습니다.

경사 하강법을 사용할 때, 모든 특성이 유사한 스케일을 가지도록 확인해야 합니다(예: Scikit-Learn의 StandardScaler 클래스를 사용함), 그렇지 않으면 수렴하는 데 훨씬 더 오랜 시간이 걸립니다.

Batch Gradient Descent

Gradient Descent에 Dataset 전체를 넣는 것을 Batch Gradient Descent라고 합니다. 경사 하강법을 구현하기 위해서는 각 모델 파라미터 Θ에 대한 비용 함수의 그래디언트를 계산해야 합니다. 다시 말해, Θ를 조금 변경하면 비용 함수가 얼마나 변할지 계산해야 합니다. 이것을 편미분이라고 합니다.

이 공식은 각 경사 하강법 단계에서 전체 훈련 세트 X에 대한 계산을 포함하고 있습니다. 이것이 알고리즘이 배치 경사 하강법(Batch Gradient Descent)이라고 불리는 이유입니다: 이 알고리즘은 각 단계에서 훈련 데이터의 전체 배치를 사용합니다.

이 알고리즘은 매우 큰 훈련 세트에서 무척 느립니다. 그러나 경사 하강법은 특성의 수에 대해 잘 확장되므로, 수십만 개의 특성이 있을 때 선형 회귀 모델을 훈련시키는 것은 정규 방정식(Normal Equation)이나 SVD 분해를 사용하는 것보다 경사 하강법을 사용하여 훈련시키는 것이 훨씬 빠립니다.

학습률이 너무 낮으면 알고리즘이 중지될 때 최적 해에서 여전히 멀리 떨어져 있을 것입니다. 너무 높으면 모델 매개변수가 더 이상 변경되지 않는 동안 시간을 낭비하게 됩니다.

간단한 해결책은 반복 횟수를 매우 크게 설정하지만, 기울기 벡터가 아주 작아질 때 즉, 아주 작은 수 ϵ보다 작아질 때 알고리즘을 중단시키는 것입니다. 이것은 경사 하강법이 (거의) 최소값에 도달했을 때 발생합니다. 배치 경사 하강법의 주요 문제점은 각 단계에서 기울기를 계산하기 위해 전체 훈련 세트를 사용한다는 사실로, 훈련 세트가 클 때 이것이 매우 느려집니다.

Stochastic Gradient Descent

확률적 경사 하강법(Stochastic Gradient Descent)은 각 단계에서 훈련 세트에서 무작위로 인스턴스를 선택하고 그 단일 인스턴스에만 기반하여 기울기를 계산합니다.

분명히 한 번에 하나의 인스턴스만 처리하면 알고리즘이 훨씬 더 빨라집니다. 왜냐하면 각 반복에서 조작할 데이터가 매우 적기 때문입니다. 또한 매 반복에서 메모리에 하나의 인스턴스만 있어야 하므로 거대한 훈련 세트에서 훈련시킬 수 있게 됩니다.

반면에, 그 확률적(즉, 무작위) 특성 때문에 이 알고리즘은 배치 경사 하강법보다 훨씬 덜 규칙적입니다: 최소값에 도달할 때까지 부드럽게 감소하는 대신 비용 함수는 위아래로 튀어 오르며 평균적으로만 감소하게 됩니다.

학습률을 점차 줄여나가기

스텝은 처음에 크게 시작하여(빠른 진행을 돕고 지역 최저점에서 벗어날 수 있도록 돕습니다) 점점 작아져서 알고리즘이 전역 최저점에 정착할 수 있게 됩니다. 각 반복에서 학습률을 결정하는 함수를 학습 일정(learning schedule)이라고 합니다.

학습률을 너무 빨리 줄이면 지역 최저점에 갇히게 되거나 최저점까지 도달하다가 중간에 멈출 수 있습니다. 학습률을 너무 천천히 줄이면 최저점 주변을 오랫동안 돌게 되고, 너무 일찍 훈련을 중단하면 최적이 아닌 해결책에 도달하게 될 수 있습니다.

주의할 점은 인스턴스들이 무작위로 선택되기 때문에, 어떤 인스턴스들은 에포크당 여러 번 선택될 수 있으며, 반면에 다른 인스턴스들은 전혀 선택되지 않을 수 있습니다.

알고리즘이 각 에포크에서 모든 인스턴스를 거치도록 하려면, 다른 접근 방법은 훈련 세트를 셔플하고, 인스턴스별로 거쳐가며, 다시 셔플하고, 계속해서 진행하는 것입니다. 확률적 경사 하강법을 사용할 때, 훈련 인스턴스들은 독립적이고 동일하게 분포되어야(IID) 평균적으로 매개변수가 전역 최적점을 향해 당겨질 것을 보장합니다.

Mini-batch Gradient Descent

미니 배치 경사 하강법(Mini-batch GD)은 미니 배치라고 불리는 작은 무작위 인스턴스 집합에 대해 기울기를 계산합니다. 미니 배치 경사 하강법의 주요 장점은 행렬 연산의 하드웨어 최적화로부터 성능 향상을 얻을 수 있으며, 특히 GPU를 사용할 때 유용하다는 것입니다. 이 알고리즘의 매개변수 공간에서의 진행은 확률적 경사 하강법(Stochastic GD)보다 덜 불규칙적이며, 특히 상당히 큰 미니 배치에서 그러합니다.

배치 경사 하강법(Batch GD)의 경로는 실제로 최소값에서 정지합니다. 확률적 경사 하강법과 미니 배치 경사 하강법은 계속해서 최소값 주변을 돌아다닙니다.

그러나 좋은 학습 스케줄을 사용해도 배치 경사 하강법은 각 단계를 수행하는 데 많은 시간이 소요됩니다.

3. Polynomial Regression

당신의 데이터가 직선보다 복잡하다면 어떻게 될까요?

비선형 데이터에 선형 모델을 사용하여 적합시킬 수 있습니다. 이를 수행하는 간단한 방법은 각 특성의 거듭제곱을 새로운 특성으로 추가하고, 이 확장된 특성 세트에 선형 모델을 학습시키는 것입니다.

여러 특성이 있을 때, 다항 회귀는 특성 간의 관계를 찾을 수 있습니다.

이는 PolynomialFeatures가 주어진 차수까지의 모든 특성 조합을 추가하기 때문에 가능합니다. 예를 들어, 두 특성 𝑎와 𝑏가 있다면, degree=3인 PolynomialFeatures는 𝑎^2, 𝑎𝑎^3, 𝑏^2, 𝑏^3 특성만 추가하는 것이 아니라 조합된 특성인 𝑎^1𝑏𝑏, 𝑎^2𝑏, 𝑎𝑏^2도 추가합니다. PolynomialFeatures(degree=d)는 𝑛개의 특성을 포함하는 배열을 (𝑛 + 𝑑) !/ 𝑑! 𝑛!의 특성을 포함하는 배열로 변환합니다. 특성의 조합 수가 조합적으로 폭발할 수 있으므로 주의해야 합니다!

underfitting

모델이 과소적합되었을 때, 초기에는 제대로 일반화하지 못해 validation error가 큽니다. 모델에 더 많은 데이터를 제공하면 오류가 줄어들지만, 데이터를 올바르게 모델링하는 데는 한계가 있습니다. 이러한 과소적합의 특징은 두 곡선이 높은 곳에서 고원을 이루는 것으로 나타납니다.

overfitting

새로운 모델은 훈련 데이터에 대한 오류가 선형 회귀 모델보다 낮고, 훈련 데이터와 검증 데이터 간의 성능 차이가 나타나는데, 이는 과대적합의 특징입니다.

5. Regularized Linear Models

Regularization

A good way to reduce overfitting is to regularize the model (Fewer degree of freedom) 1. reducing training data error 2. simple model with fewer error

• A simple way to regularize a polynomial model is to reduce the number of polynomial degrees.
• For a linear model, regularization is typically achieved by constraining the weights of the model.

Ridge Regression

$$ J(\theta) = MSE(\theta) + \alpha \sum_{i=1}^{n} \theta_i^2 $$ alpha increase -> flatten

It is important to scale the data (e.g., using a StandardScaler) before performing Ridge Regression

Lasso Regression

$$ J(\theta) = MSE(\theta) + \alpha \sum_{i=1}^{n} |\theta_i| $$

Add a regularization term to the cost function, but it uses the ℓ1 norm of the weight vector instead of half the square of the ℓ2 norm. An important characteristic of Lasso Regression is that it tends to eliminate the weights of the least important features (i.e., set them to zero).

Elastic net

Elastic Net is a middle ground between Ridge Regression and Lasso Regression. $$ J(\theta) = MSE(\theta) + \alpha \rho \sum_{i=1}^{n} |\theta_i| + \frac{\alpha (1-\rho)}{2} \sum_{i=1}^{n} \theta_i^2 $$

Early Stopping

A very different way to regularize iterative learning algorithms such as Gradient Descent is to stop training as soon as the validation error reaches a minimum.

6. Logistic Regression

Commonly used to estimate the probability that an instance belongs to a particular class

Just like a Linear Regression model, a Logistic Regression model computes a weighted sum of the input features (plus a bias term), but instead of outputting the result directly like the Linear Regression model does, it outputs the logistic of this result

Training and cost function

-log(t) grows very large when t approaches 0, so the cost will be large if the model estimates a probability close to 0 for a positive instance, and it will also be very large if the model estimates a probability close to 1 for a negative instance.

The bad news is that there is no known closed-form equation to compute the value of θ that minimizes this cost function (there is no equivalent of the Normal Equation). The good news is that this cost function is convex, so Gradient Descent (or any other optimization algorithm) is guaranteed to find the global minimum (if the learning rate is not too large and you wait long enough).

Softmax Regression

The Logistic Regression model can be generalized to support multiple classes directly, without having to train and combine multiple binary classifiers.

When given an instance x, the Softmax Regression model first computes a score 𝑠𝑘(𝐱) for each class k, then estimates the probability of each class by applying the softmax function (also called the normalized exponential) to the scores.

1. MNIST

a set of 70,000 small images of digits handwritten by high school students and employees of the US Census Bureau.

often called the “hello world” of Machine Learning

There are 70,000 images, and each image has 784 features.

This is because each image is 28 × 28 pixels, and each feature simply represents one pixel’s intensity, from 0 (white) to 255 (black).

2. Training a Binary Classifier

Let’s simplify the problem for now and only try to identify one digit

from sklearn.linear_model import SGDClassifier
sgd_clf = SGDClassifier(random_state=42)
sgd_clf.fit(X_train, y_train_5)

3. Performance Measures

Let’s use the cross_val_score() function to evaluate our SGDClassifier model, using K-fold cross-validation with three folds.

>>> from sklearn.model_selection import cross_val_score
>>> cross_val_score(sgd_clf, X_train, y_train_5, cv=3, scoring="accuracy")
array([0.96355, 0.93795, 0.95615])

Let’s look at a very dumb classifier that just classifies every single image in the “not-5” class:

• over 90% accuracy even a dumb classifier.
• This is simply because only about 10% of the images are 5s, so if you always guess that an image is not a 5, you will be right about 90% of the time.

Confusion Matrix

A much better way to evaluate the performance of a classifier is to look at the confusion matrix.

from sklearn.metrics import confusion_matrix

confusion_matrix(y_train_5, y_train_pred)

array([[53057, 1522],
             [1325, 4096]])

Precision and Recall

Precision

$$ precision = \frac{TP}{TP + FP} $$

Recall

$$ recall = \frac{TP}{TP + FN} $$

from sklearn.metrics import precision_score, recall_score

>>> precision_score(y_train_5, y_train_pred) # == 4096 / (4096 + 1522)
0.7290850836596654
>>> recall_score(y_train_5, y_train_pred) # == 4096 / (4096 + 1325)
0.7555801512636044

When it claims an image represents a 5, it is correct only 72.9% of the time. Moreover, it only detects 75.6% of the 5s.

It is often convenient to combine precision and recall into a single metric called the F1 score.

$$ F_1 = \frac{2}{\frac{1}{precision} + \frac{1}{recall}} = 2 *\frac{precision * recall}{precision + recall} = \frac{TP}{TP + \frac{FN + FP}{2}} $$

This is not always what you want: in some contexts you mostly care about precision, and in other contexts you really care about recall.

• Ex1: if you trained a classifier to detect videos that are safe for kids, you would probably prefer a classifier that rejects many good videos (low recall) but keeps only safe ones (high precision), rather than a classifier that has a much higher recall but lets a few really bad videos show up in your product.
• Ex2: Suppose you train a classifier to detect shoplifters in surveillance images: it is probably fine if your classifier has only 30% precision as long as it has 99% recall (sure, the security guards will get a few false alerts, but almost all shoplifters will get caught).

ROC Curve

• ROC curve plots the true positive rate (another name for recall) against the false positive rate (FPR).
• Once again there is a trade-off: the higher the recall (TPR), the more false positives (FPR) the classifier produces.
• The dotted line represents the ROC curve of a purely random classifier; a good classifier stays as far away from that line as possible (toward the top-left corner).

4. Multiclass Classification

one-versus-the-rest (OvR) strategy (also called one-versus-all)

• Classify the digit images into 10 classes (from 0 to 9) is to train 10 binary classifiers, one for each digit (a 0-detector, a 1-detector, a 2- detector, and so on).
• Then when you want to classify an image, you get the decision score from each classifier for that image and you select the class whose classifier outputs the highest score

one-versus-one (OvO) strategy

• Train a binary classifier for every pair of digits: one to distinguish 0s and 1s, another to distinguish 0s and 2s, another for 1s and 2s, and so on.
• If there are N classes, you need to train N × (N – 1) / 2 classifiers.
• When you want to classify an image, you have to run the image through all 45 classifiers (for MNIST problem) and see which class wins the most duels.

5. Error Analysis

• The column for class 8 is quite bright, which tells you that many images get misclassified as 8s.
• As you can see, the confusion matrix is not necessarily symmetrical. You can also see that 3s and 5s often get confused (in both directions).

6. Multilabel Classification

In some cases you may want your classifier to output multiple classes for each instance.

ex) train classifier(Kneighbors) → measure(F1 score)

If you wish to use a classifier that does not natively support multilabel classification, such as SVC, one possible strategy is to train one model per label.

To solve this issue, the models can be organized in a chain: when a model makes a prediction, it uses the input features plus all the predictions of the models that come before it in the chain

7. Multioutput Classification

Generalization of multilabel classification where each label can be multiclass

i.e., it can have more than two possible values

우리는 실제 부동산 회사에 최근에 고용된 데이터 과학자라고 가정합시다. 그리고 이 머신 러닝 프로젝트를 처음부터 끝까지 살펴봅시다!!

1. Look at the big picture

Frame the problem

최종 목표 주택 가격 예측(머신러닝 모델)을 통해서 해당 지역이 투자할 가치가 있는지 파악하고, 투자를 통해 수익을 얻는 것이 최종 목표입니다.

현재 상황 현재 지구의 주택 가격은 전문가들에 의해 수동으로 추정되고 있습니다: 팀은 지구에 관한 최신 정보를 수집하고, 주택 가격을 얻을 수 없을 때 복잡한 규칙을 사용하여 추정합니다. 이것은 비용이 많이 들고 시간이 많이 걸리며, 그들의 추정치는 그리 좋지 않습니다. 실제 주택 가격을 알아낼 수 있는 경우에 종종 그들의 추정치가 20% 이상 벗어났음을 깨달았습니다.

Q1. 먼저 문제를 설정해야 합니다: 지도 학습, 비지도 학습, 또는 강화 학습 중 어떤 것인가요?

주어진 dataset에 레이블이 붙어 있기 때문에, 이것은 전형적인 지도 학습 작업입니다 (각 인스턴스는 예상 출력값, 즉, 주택 가격과 함께 제공됩니다).

Q2. 분류 작업, 회귀 작업, 또는 다른 것인가요? multiple regression, univariate regression

Q3. 배치 학습이나 온라인 학습 기법 중 어떤 것을 사용해야 하나요? 시스템으로 지속적으로 데이터가 들어오지 않으며, 빠르게 변화하는 데이터에 적응할 특별한 필요성이 없고, 데이터가 메모리에 충분히 들어갈 만큼 작기 때문에, 단순한 배치 학습이 잘 맞을 것입니다.

Select a performance measure

RMSE(L2) vs MAE(L1) RMSE(평균 제곱근 오차)가 MAE(평균 절대 오차)보다 이상치(outliers)에 더 민감합니다. 그러나 이상치가 지수적으로 드물게 발생하는 경우 (예: 종 모양의 곡선에서처럼), RMSE는 매우 잘 작동하며 일반적으로 선호됩니다.

2. Get the data

일반적인 환경에서 데이터는 관계형 데이터베이스(또는 다른 일반적인 데이터 저장소)에 저장되어 있을 것이며 여러 테이블/문서/파일에 분산되어 있을 것입니다. 그러나 이 프로젝트에서는 상황이 훨씬 간단합니다: 당신은 단순히 하나의 압축 파일인 housing.tgz를 다운로드할 것입니다. 이 파일 안에는 모든 데이터가 포함된 쉼표로 구분된 값(CSV) 파일인 housing.csv가 있습니다.

fetch the data

import os
import tarfile
from six.moves import urllib

DOWNLOAD_ROOT = "https://raw.githubusercontent.com/ageron/handson-ml2/master/"
HOUSING_PATH = os.path.join("datasets", "housing")
HOUSING_URL = DOWNLOAD_ROOT + "datasets/housing/housing.tgz"
def fetch_housing_data(housing_url=HOUSING_URL, housing_path=HOUSING_PATH):
 if not os.path.isdir(housing_path):
 os.makedirs(housing_path)
 tgz_path = os.path.join(housing_path, "housing.tgz")
 urllib.request.urlretrieve(housing_url, tgz_path)
 housing_tgz = tarfile.open(tgz_path)
 housing_tgz.extractall(path=housing_path)
 housing_tgz.close()

Load the data

import pandas as pd

def load_housing_data(housing_path=HOUSING_PATH):
 csv_path = os.path.join(housing_path, "housing.csv")
 return pd.read_csv(csv_path)

Take a quick look at data structure

이 히스토그램에서 주목해야 할 몇 가지 사항들이 있습니다:

첫째, 중앙 소득 특성이 미국 달러(USD)로 표현된 것처럼 보이지 않습니다. 데이터는 스케일링되어 있고, 높은 중앙 소득에 대해 15에서, 낮은 중앙 소득에 대해 0.5에서 상한을 설정했습니다. 숫자는 대략 수만 달러를 나타냅니다 (예: 3은 $30,000을 의미합니다). 주택 중앙 연령 및 중앙 주택 가치도 상한을 설정했습니다. 중앙 주택 가치는 당신의 목표 특성(당신의 레이블)이므로, 이것은 심각한 문제가 될 수 있습니다. $500,000 이상에서도 정확한 예측이 필요하다면 두 가지 옵션이 있습니다: • 상한을 설정한 지역의 적절한 레이블을 수집합니다. • 해당 지역을 훈련 세트와 테스트 세트에서 제거합니다. 이러한 속성들은 매우 다른 스케일을 가지고 있습니다. 마지막으로, 많은 히스토그램이 끝이 무거워 보입니다. 이것은 일부 기계 학습 알고리즘이 패턴을 감지하는 데 어려움을 겪을 수 있습니다. 나중에 이러한 속성을 더 종 모양의 분포를 가지도록 변환해 볼 것입니다.

Create a test set 데이터셋의 일반적으로 20% (데이터셋이 매우 크다면 그보다 적게)를 무작위로 선택하고, 그것들을 따로 빼놓습니다.

3. Discover and visualize the data to gain insights

먼저, 테스트 세트를 따로 빼놓았는지 확인하고 훈련 세트만 탐색하고 있는지 확인하세요. 또한, 훈련 세트가 매우 크다면, 조작을 쉽고 빠르게 하기 위해 탐색 세트를 샘플링하는 것이 나을 수 있습니다.

해변가에 위치한 집들이 높은 가격을 형성하고 있다는 것을 알 수 있습니다.

Looking for Correlations

데이터셋이 너무 크지 않기 때문에, standard correlation coefficient (also called Pearson’s r)를 쉽게 계산할 수 있습니다. standard correlation coefficient는 선형 상관 관계만을 측정합니다.

전체 침실 수보다 전제 방 수 보다는 bedrooms_per_room이 더 좋은 correlation 값을 보입니다. 이런 식으로 feature를 만들어 사용할 수 있습니다.

4. Prepare the Data for Machine Learning Algorithms

Data Cleaning

• Separate the predictors and the labels

• Take care of missing features Ex: total_bedrooms attribute has some missing values, so let’s fix this.

  1. Get rid of the corresponding districts.
  2. Get rid of the whole attribute.
  3. Set the values to some value (zero, the mean, the median, etc.).

Handling Text and Categorical Attributes

이전에 우리는 ocean_proximity라는 범주형 속성을 제외했습니다. 왜냐하면 이것은 텍스트 속성이기 때문에 중앙값을 계산할 수 없기 때문입니다. 우리는 이 텍스트로 이루어진 카테코리를 숫자로 바꾸어 주려고 합니다.

이 표현법의 문제점은 기계 학습 알고리즘이 가까운 두 값이 먼 두 값보다 더 유사하다고 가정한다는 것입니다.

해결책: 각 카테고리별로 이진 속성을 하나씩 생성합니다. 이것을 one-hot encoding이라고 합니다.

Feature Scaling and Transformation

Feature Scaling

데이터에 적용해야 할 가장 중요한 변환 중 하나는 특성 스케일링입니다. 소수의 예외를 제외하고, 입력 수치 특성의 스케일이 매우 다를 때 기계 학습 알고리즘은 잘 수행되지 않습니다. 주택 데이터의 경우: 전체 방의 수는 대략 6에서 39,320까지 범위를 가지며, 중앙 소득은 0에서 15까지의 범위만을 가집니다. (목표값을 스케일링할 필요는 일반적으로는 없습니다!!)

모든 속성이 같은 스케일을 갖게 하는 두 가지 일반적인 방법:

• 최소-최대 스케일링 (=정규화)
• 표준화

최소-최대 스케일링 (=정규화)

• 값들이 0에서 1의 범위로 끝나도록 이동하고 재조정됩니다.

표준화

• 먼저 평균 값을 뺀 다음 (따라서 표준화된 값은 항상 평균이 0입니다), 결과 분포가 단위 분산을 가지도록 표준 편차로 나눕니다.
• 최소-최대 스케일링과는 달리, 표준화는 값들을 특정 범위로 제한하지 않습니다. 이는 일부 알고리즘들 (예: 신경망은 종종 0에서 1의 범위로 입력 값을 기대합니다)에 문제가 될 수 있습니다. 그러나, 표준화는 이상치에 훨씬 덜 영향을 받습니다.

모든 변환과 마찬가지로, 스케일러를 훈련 데이터에만 적합시키는 것이 중요합니다. 전체 데이터셋 (테스트 세트 포함)에는 아닙니다. 그런 다음에만 훈련 세트와 테스트 세트 (그리고 새로운 데이터)를 변환할 수 있습니다.

** Transformation **

5. Select and Train a Model

RMSE 값이 크게 나오므로 underfitting입니다.

RMSE값이 너무 작게 나오므로 overfitting이 되었을 가능성이 큽니다!!

validation에서 RMSE 값이 매우 크므로 overfitting임을 확인할 수 있습니다. RMSE 값이 적절히(너무 크지도 작지도 않게) 나와야 훈련이 잘 되었음을 의미합니다.

6. Fine-Tune Your Model

Grid Search

수동으로 하이퍼파라미터를 조절하여, 하이퍼파라미터 값의 훌륭한 조합을 찾을 때까지 조정하는 것입니다.

이 중에서 RMSE가 49682일 때가 가장 좋은 성능을 보입니다.

Randomized Search

그리드 검색 접근법은 상대적으로 적은 조합을 탐색할 때 괜찮습니다만, 하이퍼파라미터 검색 공간이 큰 경우 대신 RandomizedSearchCV를 사용하는 것이 종종 바람직합니다. 모든 가능한 조합을 시도하는 대신, 각 반복마다 모든 하이퍼파라미터에 대해 무작위 값을 선택하여 주어진 횟수의 무작위 조합을 평가합니다.

주요한 두 가지 이점이 있습니다: 무작위 검색을, 예를 들어, 1,000번의 반복으로 실행하면, 이 접근법은 각 하이퍼파라미터에 대해 1,000개의 다른 값을 탐색합니다 (그리드 검색 접근법을 사용할 때 하이퍼파라미터 당 몇 개의 값만 탐색하는 것에 비해). 반복 횟수를 설정함으로써, 하이퍼파라미터 검색에 할당하고 싶은 컴퓨팅 예산에 대해 더 많은 통제를 가질 수 있습니다.

Ensemble Methods

시스템을 미세 조정하는 또 다른 방법은 가장 잘 수행되는 모델들을 결합하는 것입니다. 그룹 (또는 "앙상블")은 종종 최고의 개별 모델보다 더 나은 성능을 보입니다 (개별 결정 트리에 의존하는 랜덤 포레스트가 그렇듯이), 특히 개별 모델들이 매우 다른 유형의 오류를 만들 때 특히 그렇습니다.

Evaluate Your System on the Test Set

일반화 오류에 대한 95% 신뢰 구간을 계산할 수 있습니다.

• 하이퍼파라미터 튜닝을 많이 했다면, 성능은 교차 검증을 사용하여 측정한 것보다 약간 나쁠 것입니다 (시스템이 검증 데이터에서 잘 수행되도록 미세 조정되기 때문에 알려지지 않은 데이터셋에서는 그렇게 잘 수행되지 않을 가능성이 높습니다).
• 이런 상황이 발생하면, 테스트 세트에서 숫자가 좋아 보이게 하이퍼파라미터를 조정하는 유혹을 저항해야 합니다. 개선점은 새로운 데이터에 일반화될 가능성이 낮습니다.

7. Launch, Monitor, and Maintain Your System

Deploy

훈련된 Scikit-Learn 모델을 저장합니다 (예: joblib 사용), 전체 전처리 및 예측 파이프라인을 포함하여. 이 훈련된 모델을 생산 환경에서 로드합니다.

• predict() 메서드를 호출하여 예측을 수행합니다. 클라우드에 모델 배포하기 (예: Google Cloud AI Platform) joblib을 사용하여 모델을 저장하고 Google Cloud Storage(GCS)에 업로드합니다.
• Google Cloud AI Platform으로 이동하여 GCS 파일을 가리키는 새로운 모델 버전을 생성합니다.
• 장점: 이를 통해 부하 분산 및 스케일링을 처리하는 간단한 웹 서비스를 얻게 됩니다.

Monitoring

시스템의 실시간 성능을 정기적으로 확인하고 성능이 감소할 때 알림을 trigger하는 모니터링 코드를 작성해야 합니다.

이는 오랜 시간 동안 쉽게 눈치채지 못할 수 있는 서서히 이루어지는 감소일 수 있습니다. 모델이 시간이 지남에 따라 "부식"되는 경향이 있기 때문에 이러한 현상은 꽤 흔합니다.

• 데이터가 계속 변화한다면, 데이터셋을 업데이트하고 모델을 정기적으로 다시 학습해야 합니다.
• 또한 모델의 입력 데이터 품질을 평가하는 것이 중요합니다. 때로는 신호의 질이 떨어져서 성능이 약간 저하될 수 있습니다.
• 마지막으로, 생성한 모든 모델의 백업을 유지하고, 어떠한 이유로 새로운 모델이 크게 실패하기 시작할 경우 이전 모델로 빠르게 롤백할 수 있는 프로세스와 도구를 갖추고 있어야 합니다

Overfitting이란?

머신 러닝 모델이 공원 밖에서 찍힌 개가 포함된 사진만을 훈련 데이터(training data)로 사용하면, 모델은 개를 분류하기 위한 특성으로 잔디와 같은 공원의 요소를 학습할 수 있습니다. 그러나 이렇게 훈련된 모델은 방 안에서 찍힌 개의 사진을 제대로 인식하지 못할 수 있고, 이로 인해 특정 상황에서만 작동하는 한계를 가질 수 있습니다.

💡 모델은 training data에서는 잘 수행되지만, test data에 대해 잘 수행되지 않음을 의미합니다.

Overfitting 원인

1. 적은 traning data

훈련 데이터가 적으면 모델은 모든 가능성을 탐색할 기회를 얻지 못하게 됩니다. 이로 인해 모델은 주어진 데이터에만 적합하게(fitting) 되지만, 이전에 보지 못한 데이터를 도입하면 예측의 정확도가 떨어지고 분산도 증가하게 됩니다.

cf) 풀었던 문제(아는 문제)를 계속 푸는 학생과 틀렸던 문제, 새로운 문제, 아는 문제 모두 골고루 푸는 학생 중 누가 성적이 잘 나올까요?

1. model의 복잡성

다음 그림은 Decision Tree입니다. 네모와 세모를 복잡하게(정밀하게) 분리하려고 해서 경계가 매끄럽지 않은 모습입니다.

Overfitting 해결법

Early stopping, Pruning, Regularization, Ensembling, Data augmentation

Regularization

Dropout

모든 훈련 단계에서 모든 뉴런(입력 뉴런은 포함되지만 출력 뉴런은 제외)은 일시적으로 "드롭아웃"될 확률 p를 가지며, 이는 해당 훈련 단계 동안 완전히 무시될 것임을 의미합니다. 테스트 중에는 다시 활성화됩니다.

model = keras.models.Sequential([
 keras.layers.Flatten(input_shape=[28, 28]),
 keras.layers.Dropout(rate=0.2),
 keras.layers.Dense(300, activation="elu", kernel_initializer="he_normal"),
 keras.layers.Dropout(rate=0.2),
 keras.layers.Dense(100, activation="elu", kernel_initializer="he_normal"),
 keras.layers.Dropout(rate=0.2),
 keras.layers.Dense(10, activation="softmax")
])

코드에서 rate가 p이고 계층을 지나갈 때마다 드롭아웃을 합니다.

💡 Dropout은 효과가 뛰어나다고 알려져 있습니다. 왜 효과가 뛰어날까요?

🙋 회사 직원들에게 매일 아침 동전을 던져 출근 여부를 결정하라고 한다면 성과가 좋아질까요?

회사는 당연히 조직 구조를 조정해야 할 것이며, 커피 머신을 채우거나 다른 중요한 업무를 수행할 특정 인원에 의존할 수 없게 될 것입니다. 따라서 이러한 전문 업무는 여러 사람에게 분산되어야 할 것입니다. 직원들은 소수의 동료와만 협력하는 것이 아니라 많은 동료와 협력할 수 있어야 할 것이며, 회사는 그 결과로 훨씬 더 유연해질 것입니다. 한 사람이 퇴사한다 해도 크게 문제가 되지 않을 것입니다. 이런 방식이 회사에게 실제로 적용될지는 알 수 없지만, 신경망에는 확실히 통용됩니다. 드롭아웃을 통해 훈련된 뉴런은 이웃 뉴런과 공동으로 적응할 수 없으므로, 개별적으로 최대한 유용해져야 합니다. 또한 소수의 입력 뉴런에 지나치게 의존할 수 없으므로, 모든 입력 뉴런을 고려해야 합니다. 그 결과로, 입력의 약간의 변화에 덜 민감한, 더욱 견고하고 일반화 능력이 높은 네트워크가 만들어집니다.

07-01 Perceptron

인공신경망은 수많은 머신러닝 방법 중 하나입니다. 초기의 인공 신경망인 퍼셉트론(Perceptron)에 대해서 살펴보겠습니다.

1. Perceptron

x는 입력값을 의미하며, w는 가중치(Weight), y는 출력값입니다. 그림 안의 원은 인공 뉴런에 해당됩니다. 각각의 인공 뉴런에서 보내진 입력값 x는 각각의 가중치 w와 함께 종착지인 인공 뉴런에 전달되고 있습니다.

각 입력값이 가중치와 곱해져서 인공 뉴런에 보내지고, 각 입력값과 그에 해당되는 가중치의 곱의 전체 합이 임계치(threshold)를 넘으면 종착지에 있는 인공 뉴런은 출력 신호로서 1을 출력하고, 그렇지 않을 경우에는 0을 출력합니다. 이러한 함수를 계단 함수(Step function)라고 하며, 아래는 그래프는 계단 함수의 하나의 예를 보여줍니다.

이렇게 뉴런에서 출력값을 변경시키는 함수를 활성화 함수(Activation Function)라고 합니다. 초기 인공 신경망 모델인 퍼셉트론은 활성화 함수로 계단 함수를 사용하였지만, 그 뒤에 등장한 여러가지 발전된 신경망들은 계단 함수 외에도 여러 다양한 활성화 함수를 사용하기 시작했습니다.

2. Single-Layer Perceptron

위에서 배운 퍼셉트론을 단층 퍼셉트론이라고 합니다. 퍼셉트론은 단층 퍼셉트론과 다층 퍼셉트론으로 나누어지는데, 단층 퍼셉트론은 값을 보내는 단계과 값을 받아서 출력하는 두 단계로만 이루어집니다. 이때 이 각 단계를 보통 층(layer)이라고 부르며, 이 두 개의 층을 입력층(input layer)과 출력층(output layer)이라고 합니다.

3. MultiLayer Perceptron

다층 퍼셉트론과 단층 퍼셉트론의 차이는 단층 퍼셉트론은 입력층과 출력층만 존재하지만, 다층 퍼셉트론은 중간에 층을 더 추가하였다는 점입니다. 이렇게 입력층과 출력층 사이에 존재하는 층을 은닉층(hidden layer)이라고 합니다. 즉, 다층 퍼셉트론은 중간에 은닉층이 존재한다는 점이 단층 퍼셉트론과 다릅니다. 다층 퍼셉트론은 줄여서 MLP라고도 부릅니다.

위와 같이 은닉층이 2개 이상인 신경망을 심층 신경망(Deep Neural Network, DNN) 이라고 합니다. 심층 신경망은 다층 퍼셉트론만 이야기 하는 것이 아니라, 여러 변형된 다양한 신경망들도 은닉층이 2개 이상이 되면 심층 신경망이라고 합니다.

인공지능이 가중치를 스스로 찾아내도록 자동화시켜야하는데, 이는 머신 러닝에서 말하는 훈련(training) 또는 학습(learning) 단계에 해당됩니다. 학습 단계에서는 손실 함수(Loss function)와 옵티마이저(Optimizer)를 사용합니다. 그리고 만약 학습을 시키는 인공 신경망이 심층 신경망일 경우에는 이를 심층 신경망을 학습시킨다고 하여, 딥 러닝(Deep Learning)이라고 합니다.

1. Feed-Forward Neural Network, FFNN

다층 퍼셉트론(MLP)과 같이 오직 입력층에서 출력층 방향으로 연산이 전개되는 신경망을 피드 포워드 신경망(Feed-Forward Neural Network, FFNN)이라고 합니다.

위의 그림은 FFNN에 속하지 않는 RNN이라는 신경망을 보여줍니다. 이 신경망은 은닉층의 출력값을 출력층으로도 값을 보내지만, 동시에 은닉층의 출력값이 다시 은닉층의 입력으로 사용됩니다.

2. Fully-connected layer, FC, Dense layer

다층 퍼셉트론은 은닉층과 출력층에 있는 모든 뉴런은 바로 이전 층의 모든 뉴런과 연결돼 있었습니다. 그와 같이 어떤 층의 모든 뉴런이 이전 층의 모든 뉴런과 연결돼 있는 층을 전결합층(Fully-connected layer) 또는 완전연결층이라고 합니다. 줄여서 FC라고 부르기도 합니다. 위의 그림에서는 다층 퍼셉트론의 모든 은닉층과 출력층은 전결합층입니다.

3. Activation Function

(1) 활성화 함수의 특징 - 비선형 함수(Nonlinear function)

인공 신경망에서 활성화 함수는 비선형 함수여야 합니다. 인공 신경망의 능력을 높이기 위해서는 은닉층을 계속해서 추가해야 합니다. 그런데 만약 활성화 함수로 선형 함수를 사용하게 되면 은닉층을 쌓을 수가 없습니다. 예를 들어 활성화 함수로 선형 함수를 선택하고, 층을 계속 쌓는다고 가정해보겠습니다. 활성화 함수는 y = wx라고 가정합니다. 여기다가 은닉층을 두 개 추가한다고하면 출력층을 포함해서 y = w^2x입니다. k = w^2이라고 정의하면 y = kx로 다시 표현이 가능합니다. 이 경우, 선형 함수로 은닉층을 여러번 추가하더라도 1회 추가한 것과 차이가 없음을 알 수 있습니다.

(3) 시그모이드 함수(Sigmoid function)와 기울기 소실

** 학습 과정 ** 순전파(forward propagation) 연산 -> loss function -> gradient 구하기 -> 가중치, 편향 업데이트(역전파)

주황색 구간에서는 미분값이 0에 가까운 아주 작은 값입니다. 초록색 구간에서의 미분값은 최대값이 0.25입니다. 다시 말해 시그모이드 함수를 미분한 값은 적어도 0.25 이하의 값입니다. 시그모이드 함수를 활성화 함수로하는 인공 신경망의 층을 쌓는다면, 가중치와 편향을 업데이트 하는 과정인 역전파 과정에서 0에 가까운 값이 누적해서 곱해지게 되면서, 앞단에는 기울기(미분값)가 잘 전달되지 않게 됩니다. 이러한 현상을 기울기 소실(Vanishing Gradient) 문제라고 합니다.

시그모이드 함수를 사용하는 은닉층의 개수가 다수가 될 경우에는 0에 가까운 기울기가 계속 곱해지면 앞단에서는 거의 기울기를 전파받을 수 없게 됩니다. 다시 말해 매개변수 w가 업데이트 되지 않아 학습이 되지를 않습니다.

sigmoid 외에도 ReLU, softmax, 등 다양한 종류의 활성화 함수가 있습니다. softmax는 각 클래스에 속할 확률을 알기 위해서 사용됩니다.

07-03 행렬곱으로 이해하는 신경망

$$ Y = XW + b $$

07-04 딥 러닝의 학습 방법

1. 손실 함수(Loss function)

손실 함수는 실제값과 예측값의 차이를 수치화해주는 함수입니다. 이 두 값의 차이, 즉, 오차가 클 수록 손실 함수의 값은 크고 오차가 작을 수록 손실 함수의 값은 작아집니다. 회귀에서는 평균 제곱 오차, 분류 문제에서는 크로스 엔트로피를 주로 손실 함수로 사용합니다. 손실 함수의 값을 최소화하는 두 개의 매개변수인 가중치 w와 편향 b의 값을 찾는 것이 딥 러닝의 학습 과정이므로 손실 함수의 선정은 매우 중요합니다.

ex) MSE, Binary Cross-Entropy

2. 배치 크기(Batch Size)에 따른 경사 하강법

배치는 가중치 등의 매개 변수의 값을 조정하기 위해 사용하는 데이터의 양을 말합니다. 전체 데이터를 가지고 매개 변수의 값을 조정할 수도 있고, 정해준 양의 데이터만 가지고도 매개 변수의 값을 조정할 수 있습니다.

1) 배치 경사 하강법(Batch Gradient Descent)

배치 경사 하강법은 옵티마이저 중 하나로 오차(loss)를 구할 때 전체 데이터를 고려합니다. 딥 러닝에서는 전체 데이터에 대한 한 번의 훈련 횟수를 1 에포크라고 하는데, 배치 경사 하강법은 한 번의 에포크에 모든 매개변수 업데이트를 단 한 번 수행합니다.

2) 배치 크기가 1인 확률적 경사 하강법(Stochastic Gradient Descent, SGD)

배치 크기가 1인 확률적 경사 하강법은 매개변수 값을 조정 시 전체 데이터가 아니라 랜덤으로 선택한 하나의 데이터에 대해서만 계산하는 방법입니다. 더 적은 데이터를 사용하므로 더 빠르게 계산할 수 있습니다.

3) 미니 배치 경사 하강법(Mini-Batch Gradient Descent)

전체 데이터도, 1개의 데이터도 아닐 때, 배치 크기를 지정하여 해당 데이터 개수만큼에 대해서 계산하여 매개 변수의 값을 조정하는 경사 하강법을 미니 배치 경사 하강법이라고 합니다. 미니 배치 경사 하강법은 전체 데이터를 계산하는 것보다 빠르며, SGD보다 안정적이라는 장점이 있습니다.

3. 옵티마이저(Optimizer)

1) 모멘텀(Momentum)

모멘텀(Momentum)은 관성이라는 물리학의 법칙을 응용한 방법입니다. 모멘텀 경사 하강법에 관성을 더 해줍니다. 모멘텀은 경사 하강법에서 계산된 접선의 기울기에 한 시점 전의 접선의 기울기값을 일정한 비율만큼 반영합니다.

전체 함수에 걸쳐 최소값을 글로벌 미니멈(Global Minimum) 이라고 하고, 글로벌 미니멈이 아닌 특정 구역에서의 최소값인 로컬 미니멈(Local Minimum) 이라고 합니다. 로컬 미니멈에 도달하였을 때 글로벌 미니멈으로 잘못 인식하여 탈출하지 못하였을 상황에서 모멘텀. 즉, 관성의 힘을 빌리면 값이 조절되면서 현재의 로컬 미니멈에서 탈출하고 글로벌 미니멈 내지는 더 낮은 로컬 미니멈으로 갈 수 있는 효과를 얻을 수도 있습니다.

ex) Adam, Adagrad

5. 에포크와 배치 크기와 이터레이션(Epochs and Batch size and Iteration)

1) 에포크(Epoch)

에포크란 인공 신경망에서 전체 데이터에 대해서 순전파와 역전파가 끝난 상태를 말합니다. 전체 데이터를 하나의 문제지에 비유한다면 문제지의 모든 문제를 끝까지 다 풀고, 정답지로 채점을 하여 문제지에 대한 공부를 한 번 끝낸 상태를 말합니다.

2) 배치 크기(Batch size)

배치 크기는 몇 개의 데이터 단위로 매개변수를 업데이트 하는지를 말합니다. 현실에 비유하면 문제지에서 몇 개씩 문제를 풀고나서 정답지를 확인하느냐의 문제입니다. 인공지능은 실제값과 예측값으로부터 오차를 계산하고 옵티마이저가 매개변수를 업데이트합니다. 여기서 중요한 포인트는 업데이트가 시작되는 시점이 정답지/실제값을 확인하는 시점이라는 겁니다.

사람이 2,000 문제가 수록되어있는 문제지의 문제를 200개 단위로 풀고 채점한다고 하면 이때 배치 크기는 200입니다. 기계는 배치 크기가 200이면 200개의 샘플 단위로 가중치를 업데이트 합니다.

여기서 주의할 점은 배치 크기와 배치의 수는 다른 개념이라는 점입니다. 전체 데이터가 2,000일때 배치 크기를 200으로 준다면 배치의 수는 10입니다. 이는 에포크에서 배치 크기를 나눠준 값(2,000/200 = 10)이기도 합니다. 이때 배치의 수를 이터레이션이라고 합니다.

3) 이터레이션(Iteration) 또는 스텝(Step)

이터레이션이란 한 번의 에포크를 끝내기 위해서 필요한 배치의 수를 말합니다. 또는 한 번의 에포크 내에서 이루어지는 매개변수의 업데이트 횟수이기도 합니다. 전체 데이터가 2,000일 때 배치 크기를 200으로 한다면 이터레이션의 수는 총 10입니다.

위 내용은 아래의 책을 요약한 내용입니다. 자연어처리 입문하기

읽어주셔서 감사합니다~~

머신러닝과 딥러닝

한국어로 직역해보면 “기계 학습”입니다. 머신러닝은 인공지능을 만들기 위해 기계를 학습시키는 다양한 방법에 대한 학문으로 ‘로봇공학’, ‘제어계측공학’과 같이 하나의 학문입니다.

딥러닝(Deep Learning)이란 머신러닝보다 더 작은 개념으로 ‘신경망’을 통해 인공지능을 만드는 머신러닝의 한 종류입니다. 딥러닝은 신경망을 여러 층 쌓아서 만든 것입니다. 신경세포들이 모여 이루어진 신경망을 여러 계층 쌓아서 만든 깊은 신경망을 딥러닝이라고 합니다. 층이 깊어서, ‘심층 학습, 깊은 학습’으로 불리는 학습 방법입니다.

인공지능 > 머신러닝 > 딥러닝 최근에는 경계가 모호해지고 있지만, 머신러닝과 딥러닝의 포함관계를 설명하자면 아래 그림처럼 표현해 볼 수 있습니다.

전통적인 머신러닝, 딥러닝의 차이 : 사람의 개입 여부 머신 러닝은 알고리즘을 사용하여 데이터를 구문 분석하고 해당 데이터에서 학습하며, 학습한 내용에 따라 정보에 근거한 결정을 내립니다.

딥 러닝은 알고리즘을 계층으로 구성하여 자체적으로 배우고 사람처럼 결정을 내릴 수 있는 '인공 신경망'을 만듭니다.

Dataset 구조

인공지능을 개발하기 위해서 필수적으로 갖춰져야 할 것은 많은 데이터입니다. 데이터가 많을수록 학습의 정확도가 높아지고 예측을 더 정확하게 할 수 있습니다. 또한 좋은 인공지능을 만들려면 인공지능에게 학습시키는 데이터의 질이 매우 중요합니다. 특정한 작업을 위해서 데이터를 관련성 있게 모아놓은 것을 데이터셋이라고 합니다. Dataset은 크게 Train, Validation, Test로 구성되어 있습니다.

Training set, Validation set, Test sets 비율 $$ Training set : Validation set : Test sets = 60 : 20 : 20 $$ Training set의 목적 Training set(훈련 데이터)은 모델을 학습하는데 사용됩니다. Training set으로 모델을 만든 뒤 동일한 데이터로 성능을 평가해보기도 하지만, 유효한 평가는 아닙니다.

Validation set의 목적 Validation set(검정 데이터)은 training set으로 만들어진 모델의 성능을 측정하기 위해 사용됩니다. 일반적으로 어떤 모델이 가장 데이터에 적합한지 찾아내기 위해서 다양한 파라미터와 모델을 사용해보게 되며, 그 중 validation set으로 가장 성능이 좋았던 모델을 선택합니다.

Test set의 목적 Test set(테스트 데이터)은 validation set으로 사용할 모델이 결정 된 후, 마지막으로 딱 한번 해당 모델의 예상되는 성능을 측정하기 위해 사용됩니다. 이미 validation set은 여러 모델에 반복적으로 사용되었고 그중 운 좋게 성능이 보다 더 뛰어난 것으로 측정되어 모델이 선택되었을 가능성이 있습니다. 때문에 이러한 오차를 줄이기 위해 한 번도 사용해본 적 없는 test set을 사용하여 최종 모델의 성능을 측정하게 된니다.

실제 모델의 사용 Training set으로 모델들을 만든 뒤, validation set으로 최종 모델을 선택하게 됩니다. 실제 사용하기 전에는 쪼개서 사용하였던 training set, validation set, test set 을 모두 합쳐 다시 모델을 training 하여 최종 모델을 만듭니다. 기존 training set만을 사용하였던 모델의 파라미터와 구조는 그대로 사용하지만, 전체 데이터를 사용하여 다시 학습시킴으로써 모델이 조금 더 튜닝되도록 만듭니다.

2D Geometric Transformation

기본적인 기하 변환

• 이동 변환(평행 이동) Translation: 행렬 덧셈
• 회전변환 Rotation: 행렬 곱셈
• 사이즈변환 Scaling: 행렬 곱셈

  Homogeneous Coordinates

  동차 좌표는 2차원 평면 상의 점을 3차원 공간 상의 직선에 사상(mapping) 시킨 것으로 평면에서의 한 점을 2개의 좌표가 아닌 3개의 좌표를 사용하여 표현합니다. 일반적으로 n차원의 사영 공간을 n+1개의 좌표로 나타낸다고 할 수 있습니다. 동차 좌표계는 직교 좌표계에서 0이 아닌 실수 w를 x,y에 곱한 후 마지막에 w로 요소를 하나 더 추가하는 것으로 표현합니다. 점 (x,y)에 대한 동차 좌표 표현은 3차원의 한 직선 상에 무한히 존재합니다. 즉, 한 점으로 변환되지 않는다. 또, 동차 좌표의 마지막 요소(argument) w를 scale factor로 사용하여 벡터와 점을 구별할 수 있습니다. 동차 좌표계에서 0이 아닌 w로 나누어주고 마지막 argument를 제거하면 직교 좌표계를 구할 수 있습니다. 다시 말해, 동차 좌표계를 직교 좌표계로 변환하는 것은 w의 scale과 상관없이 동차 좌표계 위의 한 직선에 있는 모든 점들을 w=1인 평면의 한 점으로 mapping 하는 것입니다. 선형 변환 vs 위치 변환 (affine) vs 투영 변환(perspective/projective): 선형 변환은 오직 스케일링, 회전 등과 같은 변환만 포함합니다. 이동(translation) 변환은 포함하지 않습니다.
• 위치 변환 (affine 변환)*은 선형 변환에 이동(translation) 변환이 추가된 것입니다. 따라서 회전, 스케일링, 그리고 이동을 포함할 수 있습니다.
• 투영 변환 (perspective/projective 변환)*은 3D 공간에서 2D 이미지 표면으로의 투영을 포함합니다. 이는 3D 객체를 2D 화면에 그릴 때 필요한 변환입니다.

  동차 좌표의 이점

  일반적인 좌표계에서는 위치 변환 및 투영 변환을 단순한 행렬 곱으로 표현하기 어렵습니다. 왜냐하면 이들 변환은 선형적이지 않기 때문입니다. 그러나 동차 좌표계를 도입하면, 이러한 비선형 변환들도 선형 변환처럼 행렬 곱으로 표현할 수 있게 됩니다. 예를 들어, 2D 공간의 점을 이동시키려면 동차 좌표계에서 3x3 행렬을 사용하여 이를 표현할 수 있습니다. 3D 공간의 점을 이동시키려면 4x4 행렬을 사용합니다. 이것은 그래픽스 하드웨어나 알고리즘의 설계에서 큰 이점을 제공합니다. 여러 변환들을 하나의 행렬로 결합하여 연산의 효율성을 크게 향상시킬 수 있기 때문입니다.

그러면 위에서 언급한 기본 변환들은 다음과 같이 변하게 됩니다.

• 이동변환(= 평행이동) Translation: 행렬 곱셈
• 회전변환 Rotation: 행렬 곱셈
• 사이즈변환 Scaling: 행렬 곱셈

3D나 나머지 변환들은 아래 링크를 참고해주세요. 읽어주셔서 감사합니다!! 기하 변환

Intro

컴퓨터 비전과 관련된 여러 애플리케이션, 특히 객체 탐지에서는 모델의 성능을 평가하는 데 중요한 지표들이 필요합니다. 이러한 지표 중에서도 IoU(Intersection over Union)와 mAP(mean Average Precision)은 그중에서도 중요합니다.

IoU는 예측된 경계 상자와 실제 경계 상자 사이의 겹치는 영역을 측정하는 지표로, 객체의 위치와 크기를 얼마나 정확하게 탐지하는지 평가하는 데 사용됩니다. 반면, mAP는 여러 임계값에서 평균 정밀도를 계산하여 객체 탐지 모델의 전반적인 성능을 평가하는 지표입니다.

이 두 지표는 객체 탐지의 정확성과 신뢰성을 평가하는 데 있어 핵심적인 역할을 합니다. 이 글에서는 IoU와 mAP의 정의, 계산 방법에 대해 자세히 알아보겠습니다.

IoU

IoU는 "Intersection over Union"의 약자로, 두 개의 바운딩 박스(또는 일반적인 두 영역) 사이의 겹치는 부분을 측정하는 방법입니다. 객체 탐지 작업에서는 모델의 예측 바운딩 박스와 실제 참값(ground truth) 바운딩 박스 사이의 일치 정도를 판단하는 데 주로 사용됩니다. IoU threshold는 객체 탐지에서 사용되며, 특정 임계값보다 높은 IOU를 가진 예측만을 정확하게 탐지된 것으로 간주합니다. 예를 들어, IOU threshold를 0.5로 설정하면 IOU가 0.5 이상인 Bounding Box만을 "True Positive"로 간주하고 그 미만의 값을 "False Positive"로 간주합니다.

mAP

mAP을 정의하기 위해서는 precision과 recall에 대해 알아야 합니다.

재현율 (Recall)

재현율은 실제 Positive인 결과 중에서 모델이 Positive로 예측한 결과의 비율을 나타냅니다. $$ Recall = \frac{TP}{TP + FN} $$ 여기서,

• TP는 True Positive의 수
• FN는 False Negative의 수

  Average Precision (AP)

  Average Precision은 Precision-Recall 곡선 아래의 영역으로, 객체 탐지 작업에서 특히 중요한 성능 지표입니다. AP는 다양한 임계값에서의 Precision과 Recall 값을 종합하여 계산됩니다. 일반적인 공식은 다음과 같습니다. $$ AP = \int_{0}^{1} p(r) , dr $$

mean Average Precision (mAP)

mean Average Precision는 데이터셋 내 모든 클래스에 대한 AP 값의 평균입니다. 객체 탐지 및 세그멘테이션 작업에서는 클래스별로 AP를 계산한 다음, 그 값들의 평균을 내어 mAP를 계산합니다.

$$ mAP = \frac{\sum_{classes} AP}{number\ of\ classes}

머신러닝이란?

일반적 정의

머신러닝은 컴퓨터가 명시적으로 프로그래밍되지 않아도 학습할 수 있는 능력을 부여하는 연구 분야입니다. —아서 사무엘, 1959

엔지니어링 중심의 정의

어떤 경험 E, 작업 T, 성능 측정 P에 대하여 컴퓨터 프로그램이 경험 E를 통해 작업 T에서 P로 측정한 성능이 향상된다면, 그 프로그램은 학습한다고 말할 수 있습니다. —톰 미첼, 1997

예를 들어, 스팸 필터는 스팸 이메일(예: 사용자가 표시한 것)과 일반 이메일의 예시를 통해 스팸을 표시하는 데 학습할 수 있는 머신 러닝 프로그램입니다. 시스템이 학습하는 데 사용하는 예시를 훈련 세트(training data)라고 하며, 이 경우 작업 T는 새 이메일에 대한 스팸 표시이고, 경험 E는 훈련 데이터이며, 성능 측정 P는 정의해야 합니다. 예를 들어, 올바르게 분류된 이메일의 비율을 사용할 수 있습니다. 이 특정 성능 측정은 정확도라고 하며, 분류 작업에서 자주 사용됩니다.

머신러닝 분류

1. 인간의 감독 하에 훈련되는지 여부 ex) 지도 학습, 비지도 학습, 준지도 학습, 강화 학습

1. 점진적으로 학습할 수 있는지 여부 ex) 온라인 학습 대 배치 학습
2. 새로운 데이터 포인트를 알려진 데이터 포인트와 단순히 비교하는지, 아니면 과학자들이 하는 것처럼 훈련 데이터에서 패턴을 감지하고 예측 모델을 구축하는지 여부 ex) 인스턴스 기반 대 모델 기반 학습

이러한 기준은 배타적이지 않으며 원하는 대로 조합할 수 있습니다. 예를 들어, 머신러닝을 적용한 스팸 필터는 스팸과 햄(비스팸)의 예시를 사용해 훈련된 깊은 신경망 모델을 사용하여 즉석에서 학습할 수 있으며, 이는 온라인, 모델 기반, 지도 학습 시스템으로 만듭니다.

Supervised Learning

지도 학습에서는 알고리즘에 공급하는 훈련 데이터의 context가 포함되어 있으며, 이를 라벨이라고 합니다. 지도학습에서는 라벨을 통해 데이터를 학습합니다. ex) k-Nearest Neighbors, Linear Regression, Logistic Regression, Support Vector Machines (SVMs), Decision Trees and Random Forests, Neural networks

Unsupervised Learning

비지도 학습에서는 짐작할 수 있듯이 훈련 데이터에 레이블이 지정되지 않습니다. 시스템은 선생님 없이 학습을 시도합니다.

Algorithms

• Clustering
  • K-Means
  • DBSCAN
  • Hierarchical Cluster Analysis (HCA)
• Anomaly detection and novelty detection
  • One-class SVM
  • Isolation Forest
• Visualization and dimensionality reduction
  • Principal Component Analysis (PCA)
  • Kernel PCA
  • Locally-Linear Embedding (LLE)
  • t-distributed Stochastic Neighbor Embedding (t-SNE)
• Association rule learning
  • Apriori
  • Eclat

    Semisupervised Learning

    일부 알고리즘은 부분적으로 레이블이 지정된 교육 데이터, 일반적으로 많은 레이블이 지정되지 않은 데이터와 약간의 레이블이 지정된 데이터를 처리할 수 있습니다. 이것을 준지도 학습이라고 합니다.

Reinforcement Learning

에이전트라고 하는 학습 시스템은 환경을 관찰하고, 행동을 선택 및 수행하고, 그 대가로 보상(또는 부정적인 보상 형태의 페널티)을 받을 수 있습니다. 그런 다음 시간이 지남에 따라 가장 많은 보상을 얻기 위해 정책이라고 하는 최상의 전략이 무엇인지 스스로 학습해야 합니다. 정책은 주어진 상황에 있을 때 에이전트가 선택해야 하는 조치를 정의합니다.

Batch Learning

배치 학습에서 시스템은 점진적으로 학습할 수 없으며, 사용 가능한 모든 데이터를 사용하여 훈련해야 합니다. 일반적으로 이것은 많은 시간과 컴퓨팅 자원을 필요로 하므로, 보통 오프라인에서 수행됩니다. 먼저 시스템이 훈련되고, 그런 다음 생산에 투입되어 더 이상 학습하지 않고 실행됩니다; 그저 배운 것을 적용할 뿐입니다. 이것을 오프라인 학습이라고 합니다.

Online Learning

온라인 학습에서는 데이터 인스턴스를 순차적으로 시스템에 공급하여 점진적으로 훈련시킵니다. 이는 개별적으로 또는 미니 배치라고 하는 작은 그룹으로 수행됩니다. 각 학습 단계는 빠르고 저렴하므로, 시스템은 도착하는 새로운 데이터에 대해 즉시 학습할 수 있습니다. 온라인 학습은 데이터를 연속적인 흐름으로 받고 (예: 주식 가격) 빠르게 또는 자동으로 변화에 적응해야 하는 시스템에 좋습니다.

Instance-based Learning

가장 간단한 형태의 학습은 아마도 암기하는 방법일 것입니다. 이 방법으로 스팸 필터를 만든다면, 그것은 사용자가 이미 플래그한 이메일과 동일한 모든 이메일을 플래그할 것입니다 - 최악의 해결책은 아니지만 확실히 최선은 아닙니다.

알려진 스팸 이메일과 동일한 이메일만 플래그하는 대신에, 스팸 필터는 알려진 스팸 이메일과 매우 유사한 이메일을 플래그하도록 프로그래밍될 수 있습니다. 이것은 두 이메일 사이의 유사성을 측정해야 합니다. (아주 기본적인) 두 이메일 사이의 유사성 측정은 그들이 공통으로 가지고 있는 단어의 수를 세는 것일 수 있습니다. 시스템은 알려진 스팸 이메일과 많은 단어를 공유하고 있다면 이메일을 스팸으로 플래그할 것입니다.

이것을 인스턴스 기반 학습이라고 합니다: 시스템은 예시를 외우고 나서 유사성 측정을 사용하여 학습된 예시(또는 그 중 일부)와 비교하여 새로운 경우에 일반화합니다.

Model-based Learning

data들을 일반화하는 또 다른 방법은 이러한 data를 나타내는 모델을 구축하고 그 모델을 사용해 예측을 만드는 것입니다. 이것을 모델 기반 학습이라고 합니다

BFS는 그래프 순회 알고리즘인 Breadth-First Search의 약자입니다. 레벨별로 그래프 또는 트리의 모든 정점을 탐색합니다. 다음 레벨로 이동하기 전에 동일한 레벨의 모든 정점을 방문합니다.

BFS 과정

1. 탐색 시작 노드 정보를 큐에 삽입하고 *방문 처리합니다.
2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리합니다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다.

큐에서 꺼내 처리 중인 노드는 파란색으로, 방문 처리한 노드는 회색으로 표시하겠습니다.

(1) 시작 노드인 노드 1을 큐에 삽입하고 방문 처리합니다. (2) 큐에서 노드 1을 꺼내고 노드 1과 인접한 노드 2, 3을 큐에 삽입하고 방문 처리합니다. (3) 큐에서 노드 2를 꺼내고 노드 2와 인접한 노드 8을 큐에 삽입하고 방문 처리합니다. (4) 큐에서 노드 3을 꺼내고 노드 3과 인접한 노드 4, 5를 큐에 삽입하고 방문 처리합니다. (5) 큐에서 노드 8을 꺼내고 노드 8과 인접한 노드 6, 7을 큐에 삽입하고 방문 처리합니다. (6) 그래프 내 노드에서 방문하지 않은 노드가 없으므로 큐에서 모든 노드를 차례대로 꺼냅니다. 결과적으로 노드의 탐색 순서, 즉 큐에 삽입한 순서는 다음과 같습니다. 1 -> 2 -> 3 -> 8 -> 4 -> 5 -> 6 -> 7

BFS 구현(백준 24444번)

문제

입력

첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.

다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.

출력

첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다. i번째 줄에는 정점 i의 방문 순서를 출력한다. 시작 정점의 방문 순서는 1이다. 시작 정점에서 방문할 수 없는 경우 0을 출력한다.

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M, R;
    cin >> N >> M >> R;
    vector<vector<int>> graph(M + 1);
    for (int i = 1; i <= M; i++)
    {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for (int i = 1; i <= N; i++) 
        sort(graph[i].begin(), graph[i].end());
    vector<int> visited(N + 1, 0);
    BFS(visited, graph, R);
    for (int i = 1; i <= N; i++)
    {
        cout << visited[i] << "\n";
    }
    return 0;
}

"1 2"가 입력으로 주어졌을 때 graph[1]에 원소로 2를 넣고 연결 그래프이므로 graph[2]에도 원소로 1을 넣는다. 인접 정점은 오름차순으로 방문해야 하므로 오름차순으로 정렬해준다.

int cnt = 0;
void BFS(vector<int>& V, vector<vector<int>>& E, int R) 
{
    queue<int> q;
    q.push(R);
    cnt++;
    V[R] = cnt;
    while (!q.empty())
    {
        int element = q.front();
        q.pop();
        for (int i = 0; i < E[element].size(); i++)
        {
            int temp = E[element][i];
            if (!V[temp])
            {
                cnt++;
                V[temp] = cnt;
                q.push(temp);
            }
        }
    }
}

queue q에 시작 정점 R을 넣습니다. 그리고 cnt를 1 증가해주고 방문 여부와 방문 순서를 표시해주는 배열 V의 R번째 원소에 cnt를 넣습니다. 큐가 비어 있지 않다면 시작 정점 R에 인접한 원소도 똑같이 큐가 빌 때까지 진행해 줍니다.

References

• https://heytech.tistory.com/56
• https://namu.wiki/w/%EB%84%88%EB%B9%84%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89

DP란?

DP는 다시 계산할 필요가 없도록 하위 문제의 결과를 저장하는 것입니다. 이 과정은 지수에서 다항식으로 시간 복잡도를 줄입니다.

동적 계획법에는 분할 정복에 아래 개념이 추가됩니다.

• 반복되는 서브 문제(Overlapping Subproblems) 문제를 해결하는 과정에서 동일한 하위 문제가 여러 번 해결되는 문제의 속성입니다.
• 최적 부분 구조(Optimal Substructure) 문제에 대한 최적해는 작은 하위 문제에 대한 최적해를 결합하여 얻을 수 있습니다. cf) 병합정렬의 경우 부분으로 나누어 정렬하고 합칠 때 다시 대소 비교를 통해 정렬을 수행해야 합니다.

예시(fibonacci)

• 재귀(naive approach)

  # Function to find nth fibonacci number
  def fib(n):
    if (n <= 1):
        return n
    x = fib(n - 1)
    y = fib(n - 2)
  
    return x + y
  

n = 5;

Function Call

print(fib(n))

Time Complexity: **O(2^n)**
- **Memoization**(Top-down approach)
메인 문제를 분할하면서 해결하는 방법입니다.
  ![](https://velog.velcdn.com/images/blublue_02/post/27e548d0-d0f4-4783-9fee-9026f3c9006f/image.png)
```python
F = [-1]*50 #array to store fibonacci terms

def dynamic_fibonacci(n):
  if (F[n] < 0):
    if (n==0):
      F[n] = 0
    elif (n == 1):
      F[n] = 1
    else:
      F[n] = dynamic_fibonacci(n-1) + dynamic_fibonacci(n-2)
  return F[n]

if __name__ == '__main__':
  print(dynamic_fibonacci(46))

Time complexity: O(n)

• Tabulation(Bottom-up approach) 가장 작은 문제를 먼저 해결하고 최종적으로 메인 문제를 해결하는 방법입니다.

  F = [0]*50 #array to store fibonacci terms
  

def fibonacci_bottom_up(n): F[n] = 0 F[1] = 1

for i in range(2, n+1): F[i] = F[i-1] + F[i-2] return F[n]

if name == 'main': print(fibonacci_bottom_up(46))

``` Time complexity: O(n)

Memoization & Tabulation

Memoization은 문제를 해결하는 자연스러운 방법이기 때문에, 복잡한 문제를 다룰 때 코딩이 더 쉽습니다. 많은 조건들을 처리하면서 특정 순서를 고안하는 것은 Tabulation에서는 어려울 수 있습니다.

또한, 모든 하위 문제의 해결책을 찾을 필요가 없는 경우에는 Memoization을 사용하는 것이 좋습니다.

그러나 많은 재귀 호출이 필요한 경우, Memoization은 재귀 호출을 스택에 쌓아 더 깊은 재귀 호출의 해결책을 찾는 것으로 인해 메모리 문제가 발생할 수 있습니다. Tabulation에서는 이 문제를 신경쓰지 않아도 됩니다.

한 문제를 둘 이상의 부분 문제(sub-problem)로 나누어 해결하고 이를 합쳐 원래 문제를 해결하는 기법입니다.

분할 정복 알고리즘은 다음과 같이 세 부분으로 나누어서 생각해 볼 수 있습니다.

분할 정복의 단계

① 분할: 동일한 타입의 하위 문제로 큰 문제를 분할합니다. ② 정복: 재귀적으로 하위 문제들을 해결합니다. ③ 병합: 적절히 해결된 결과를 사용해 큰 문제를 해결합니다.

재귀와 차이점

분할 정복이 일반적인 재귀 호출과 다른 점은 거의 같은 크기의 부분 문제로 나누는 것입니다. 재귀는 한 문제씩 푼다면, 분할 정복은 문제를 거의 같은 크기의 두 문제로 나누어서 해결합니다.

재귀를 이용한 수열의 합

int sum(int n)
{
    if(n == 1) 
        return 1;
    return sum(n - 1) + n;
}

분할 정복을 이용한 수열의 합

int sum(int n)
{
    if(n == 1) 
        return 1;
    if(n % 2 == 1) 
        return sum(n - 1) + n;
    return 2 * sum(n / 2) + (n / 2) * (n / 2);
}

분할 정복의 예 - 합병 정렬

① 분할: 전체 데이터를 반으로 지속적으로 분할합니다. 직접 문제가 해결되는 수준까지(데이터가 1개 남을 때까지) 분할합니다. ② 정복: 데이터가 1개가 남으면 그 자체로 이미 정렬된 상태입니다. 분할된 2개의 데이터를 정렬합니다.(하위 문제 해결) ③ 병합: 정렬된 하위 문제를 병합하여 전체 내역을 정렬합니다.

vector<int> sd; // 임시로 숫자를 저장하기 위한 벡터 sd 선언
// merge 쪼개진 벡터 합치기
void merge(vector<int>& li, int p, int k, int q)
{
    int left = p; // 맨 앞 인덱스
    int m = k + 1; // 가운데 인덱스
    int fin = p; // 최종 벡터에 저장하기 위한 인덱스
    // 작은 순서대로 벡터에 삽입
    while (left <= k && m <= q) { // left > k or m > q이면 while문 종료
        if (li[left] <= li[m]) // 2개의 벡터를 합칠 때 맨 앞 원소끼리 비교
        {
            sd[fin] = li[left]; // 벡터 sd에 작은 숫자 저장
            left++; // 다음 숫자를 가리키도록 +1
        }
        else {
            sd[fin] = li[m]; // 벡터 sd에 작은 숫자 저장
            m++; // 다음 숫자를 가리키도록 +1
        }
        fin++; // 다음 공간을 가리키도록 +1
    }
    // 나머지 데이터 저장
    if (left > k) // left>k가 성립하여 while문이 종료되었다면
    {
        while (m <= q) // m>q만족할 때까지 남은 데이터 저장
        {
            sd[fin] = li[m]; // 데이터 저장
            m++;
            fin++;
        }
    }
    else if (m > q) // m>q가 성립하여 while문이 종료되었다면
    {
        while (left <= k) // left>k 만족할 때까지 남은 데이터 저장
        {
            sd[fin] = li[left]; //데이터 저장
            left++;
            fin++;
        }
    }
    // 데이터 복사
    for (int i = p; i <= q; i++)
        li[i] = sd[i]; // li 벡터에 임시 벡터 sd의 원소 그대로 넣기
}
void merge_sort(vector<int>& li, int p, int q)
{
    if (p < q) {
        int k = (p + q) / 2;
        merge_sort(li, p, k);
        merge_sort(li, k + 1, q);
        merge(li, p, k, q);
    }
}

Class 접근 제한자

• default 접근 제한 클래스를 선언할 때 public을 생략했다면 클래스는 default 접근 제한을 가집니다. 클래스가 default 접근 제한을 가지면 같은 패키지에서는 아무런 제한 없이 사용할 수 있지만 다른 패키지에서는 사용할 수 없도록 제한됩니다.

• public 접근 제한 클래스를 선언할 때 public 접근 제한자를 붙였다면 클래스는 public 접근 제한을 가집니다. 클래스가 public 접근 제한을 가지면, 같은 패키지뿐만 아니라 다른 패키지에서도 아무런 제한 없이 사용할 수 있습니다. 클래스를 다른 개발자가 사용할 수 있도록 라이브러리 클래스로 개발한다면 반드시 public 접근 제한을 갖도록 해야 합니다. 인터넷으로 배포되는 라이브러리 클래스도 모두 public 접근 제한을 가지고 있습니다.

생성자 접근 제한자

• public 접근 제한: public 접근 제한은 모든 패키지에서 아무런 제한 없이 생성자를 호출할 수 있도록 합니다.

• protected 접근 제한: protected 접근 제한은 default 접근 제한과 마찬가지로 같은 패키지에 속하는 클래스에서 생성자를 호출할 수 있도록 합니다. 차이점으로 다른 패키지에 속한 클래스가 해당 클래스의 자식(child) 클래스라면 생성자를 호출할 수 있습니다.

• default 접근 제한: default 접근 제한은 같은 패키지에서는 아무런 제한 없이 생성자를 호출할 수 있으나, 다른 패키지에서는 생성자를 호출할 수 없도록 합니다.

• private 접근 제한: private 접근 제한은 동일한 패키지이건 다른 패키지이건 상관없이 생성자를 호출하지 못하도록 제한합니다. 오로지 클래스 내부에서만 생성자를 호출할 수 있고 객체를 만들 수 있습니다.

필드와 메소드의 접근 제한자

• public 접근 제한: public 접근 제한은 모든 패키지에서 아무런 제한 없이 필드와 메소드를 사용할 수 있도록 해줍니다.

• protected 접근 제한: protected 접근 제한은 default 접근 제한과 마찬가지로 같은 패키지에 속하는 클래스에서 필드와 메소드를 사용할 수 있도록 합니다. 차이점으로 다른 패키지에 속한 클래스가 해당 클래스의 자식 클래스라면 필드와 메소드를 사용할 수 있습니다.

• default 접근 제한: 필드와 메소드를 선언할 때 접근 제한자를 생략하면 default 접근 제한을 가집니다. default 접근 제한은 같은 패키지에서는 아무런 제한 없이 필드와 메소드를 사용할 수 있으나 다른 패키지에서는 필드와 메소드를 사용할 수 없도록 합니다.

• private 접근 제한: private 접근 제한은 동일한 패키지이건 다른 패키지이건 상관없이 필드와 메소드를 사용하지 못하도록 제한합니다. 오로지 클래스 내부에서만 사용할 수 있습니다.

Interface vs Abstract

Interface와 Abstract Class는 상속(extends)받거나, 구현(implements)하는 Class가 Interface나 Abstract Class 안에 있는 Abstract Method를 구현하도록 강제하는 공통점을 가지고 있습니다.

Interface

Interface는 부모, 자식 관계인 상속 관계에 얽메이지 않고, 공통 기능이 필요 할때, Abstract Method를 정의해놓고 구현(implements)하는 Class에서 각 기능들을 Overridng하여 여러가지 형태로 구현할 수 있기에 다형성과 연관되어 있습니다.

Interface는 해당 Interface를 구현하는 Class들에 대해 동일한 method, 동작을 강제하기 위해 존재합니다.

Java에서 다중 상속이 안되어 발생하는 Abstract Class의 한계도 보완해줄 수 있다. Interface의 implements에는 제한이 없어 다중 구현이 가능합니다.

하지만 모든 Class가 Interface를 이용한다면, 공통적으로 필요한 기능도 implements하는 모든 Class에서 Overrindg해 재정의해야 하는 번거로움이 존재합니다.

Interface는 각각 다른 Abstract Class를 상속하는 Class들의 공통 기능을 명시할때 사용하면 편리합니다.

Abstract

Abstract Class는 부모와 자식 즉, 상속 관계에서 Abstract Class를 상속(extends)받으며 같은 부모 Class(여기서는 Abstract Class)를 상속받는 자식 Class들 간에 공통 기능을 각각 구현하고, 확장시키며 상속과 관련되어 있습니다. 상속은 SuperClass의 기능을 이용, 확장 하기 위해 사용됩니다.

Abstract Class는 IS - A "이다"이고, Interface는 HAS - A "을 할 수 있는"입니다. cf) IS - A: 일반적인 개념과 구체적인 개념의 관계입니다. cf) HAS - A: 포함 관계

Abstract Class를 상속하며 Class들간의 구분이 가능해집니다.

Java에서는 다중 상속을 지원하지 않기 때문에 Abstract Class 만으로 구현해야하는 Abstract Method를 강제하는데는 한계가 존재합니다.

1. handle_events()
2. update()
3. render()

def handle_events():
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            # Handle quitting the game
            quit_game()
        elif event.type == pygame.MOUSEBUTTONDOWN:
            # Get the position of the mouse click
            mouse_pos = pygame.mouse.get_pos()
            # Check if the mouse click was on a card
            for card in player.hand:
                if card.rect.collidepoint(mouse_pos):
                    # If the mouse click was on a card, play it
                    play_card(card)
        elif event.type == pygame.KEYDOWN:
            # Handle keyboard input (such as pressing the "Draw" button)
            if event.key == pygame.K_SPACE:
                draw_card()

def update():
    # Check if the game is over
    if check_game_over():
        end_game()
        return

    # Update the player's hand
    player.hand.update()

    # Update the game state based on the top card
    top_card = deck.get_top_card()
    if top_card.is_skip():
        skip_player()
    elif top_card.is_reverse():
        reverse_direction()
    elif top_card.is_draw_two():
        draw_two_cards()
    elif top_card.is_wild():
        handle_wild_card()
    elif top_card.is_wild_draw_four():
        handle_wild_draw_four_card()

def render():
    # Clear the screen
    screen.fill(BG_COLOR)

    # Draw the player's hand
    player.hand.draw(screen)

    # Draw the top card
    top_card = deck.get_top_card()
    top_card.draw(screen)

    # Draw the deck and discard piles
    deck.draw(screen)
    discard_pile.draw(screen)

    # Draw the current player's name and turn indicator
    current_player_name = get_current_player().name
    current_player_indicator = "==> "
    player_font = pygame.font.SysFont(None, 32)
    player_text = player_font.render(current_player_name + current_player_indicator, True, BLACK)
    screen.blit(player_text, (10, 10))

    # Update the display
    pygame.display.flip()

def play_card(card):
    # Check if the card can be played
    if can_play_card(card):
        # Remove the card from the player's hand
        player.hand.remove(card)
        # Add the card to the discard pile
        discard_pile.add(card)
        # Apply the effect of the card
        apply_card_effect(card)
        # Advance to the next player
        next_player()
    else:
        # If the card can't be played, do nothing
        pass

turn 관리(for -> while: running)

def print_list(lst, reverse=False):
    if reverse:
        for i in range(10):
            print(lst[-i % len(lst) - 1])
    else:
        for i in range(10):
            print(lst[i % len(lst)])

lst = [1, 2, 3, 4, 5]

print_list(lst, True)
print_list(lst, False)

예외는 프로그램 실행 중에 개발자의 실수로 예기치 않은 상황이 발생했을 때 입니다.예를 들어 배열의 범위를 벗어난(ArrayIndexOutOfBoundsException), 값이 null이 참조변수를 참조(NullPointerException), 존재하지 않는 파일의 이름을 입력(FileNotFoundException) 등이 있습니다.

예외에는 2가지로 나눌 수 있습니다.

• 체크 예외(Checked Exception),
• 언체크 예외(Unchecked Exception)

Checked Exception

체크 예외는 RuntimeException의 하위 클래스가 아니면서 Exception 클래스의 하위 클래스들입니다. 체크 예외의 특징은 반드시 에러 처리를 해야하는 특징(try/catch or throw)을 가지고 있습니다.

존재하지 않는 파일의 이름을 입력(FileNotFoundException) 실수로 클래스의 이름을 잘못 적음(ClassNotFoundException)

Unchecked Exception

언체크 예외는 RuntimeException의 하위 클래스들을 의미합니다. 이것은 체크 예외와는 달리 에러 처리를 강제하지 않습니다. 말 그대로 실행 중에(runtime) 발생할 수 있는 예외를 의미합니다.

배열의 범위를 벗어난(ArrayIndexOutOfBoundsException) 값이 null이 참조변수를 참조(NullPointerException)

DAO

DAO(Data Access Object) 는 데이터베이스의 data에 접근하기 위한 객체입니다. DataBase에 접근 하기 위한 로직 & 비지니스 로직을 분리하기 위해 사용합니다.

DTO

DTO(Data Transfer Object) 는 계층 간 데이터 교환을 하기 위해 사용하는 객체로, DTO는 로직을 가지지 않는 순수한 데이터 객체(getter & setter 만 가진 클래스)입니다. 유저가 입력한 데이터를 DB에 넣는 과정을 보겠습니다. 유저가 자신의 브라우저에서 데이터를 입력하여 form에 있는 데이터를 DTO에 넣어서 전송합니다. 해당 DTO를 받은 서버가 DAO를 이용하여 데이터베이스로 데이터를 집어넣습니다.

VO

VO(Value Object) 값 오브젝트로써 값을 위해 쓰입니다. read-Only 특징(사용하는 도중에 변경 불가능하며 오직 읽기만 가능)을 가집니다. DTO와 유사하지만 DTO는 setter를 가지고 있어 값이 변할 수 있습니다.

JUnit5이란?

JUnit Platform + JUnit Jupiter + JUnit Vintage가 합쳐진 프레임워크로, Java8 부터 사용 가능합니다.

• JUnit Platform
  • JVM에서 테스트 프레임워크를 실행하는데 기초 제공
  • TestEngine API로 테스트 프레임워크 개발
• JUnit Jupiter
  • JUnit 5에서 테스트를 작성하고 확장을 하기 위한 새로운 프로그래밍 모델과 확장 모델의 조합
• JUnit Vintage
  • 하위 호환성을 위해 JUnit3과 JUnit4를 기반으로 돌아가는 플랫폼에 테스트엔진

    Intellij에서 JUnit 사용하기

    src/test/java 하위에 패기지를 생성하고 클래스를 생성한다. Controller의 경로가 src/main/java/web/이라면 테스트 코드를 작성하기 위한 클래스의 경로는 src/main/java/web/이어야 합니다.
• test 생성 단축기 Command + shift + T* ### 성공

실패