Text Classification이란, 텍스트∙문장∙문서를 입력으로 받아 사전에 정의된 클래스중 어디에 속하는지 분류(classification)하는 과정으로 아래와 같이 응용분야가 다양하다.
문제
클래스 예시
감성분석 (Sentiment Analysis)
긍정 / 중립 / 부정
스팸메일 탐지 (Spam Detection)
정상 / 스팸
사용자 의도 분류 (Intent Classification)
명령 / 질문 / 잡담 등
주제 분류 (Topic Classification)
각 주제
카테고리 분류 (Category Classification)
각 카테코리
딥러닝 이전에는 Naïve Bayes Classification, Support Vector Machine 등 다양한 방법으로 Text Classification을 진행하였다. 이번시간에는 딥러닝 이전의 가장 간단한 분류방식인 Naïve Bayes방식을 비롯, 여러 딥러닝 방식을 알아보자.
2. Naïve Bayes 활용하기
Naïve Bayes는 아주 강력한("각 feature는 independent하다!"라는 강력한 가정을 가짐) 분류방식으로
성능은 준수하지만 단어라는 불연속적인 symbol을 다루는 NLP에서는 아쉬운 면이 존재한다.
2.1 MAP (Maximum A Posterior)
❗️Bayes Theorem 이때, 대부분의 문제에서 evidence, P(D)는 구하기 어렵기에 P(c | D) ∝ P(D | c)∙P(c) 식으로 접근하기도 한다. 앞의 성질을 이용하면, 주어진 data D에 대해 확률을 최대로 하는 클래스 c를 구할 수 있는데,
❗️MAP 이처럼 사후확률을 최대화하는 클래스 c를 구하는 것을 MAP(사후확률최대화)라 한다.
❗️MLE 이와 마찬가지로 가능도를 최대화하는 클래스 c를 구하는 것을 MLE(최대가능도추정)이라 한다.
MLE는 주어진 data D와 label C에 대해 확률분포를 근사하기 위한 parameter θ를 훈련하기위한 방법으로 사용된다.
MLE. vs. MAP MAP가 경우에 따라 MLE보다 더 정확할 수 있다. (∵ 사전확률이 포함되어있어서)
2.2 Naïve Bayes Naïve Bayes는 MAP를 기반으로 작동한다. 가정: 각 feature는 independent하다! 라는 강력한 가정을 바탕으로 진행된다. 대부분의 경우, 사후확률을 구하기 어렵기에 가능도와 사전확률의 곱으로 클래스를 예측한다.
만약 다양한 특징으로 이루어진 data의 경우, feature가 희박하기에 가능도를 구하기 또한 어렵다. 이때, Naïve Bayes가 매우 강력한 힘을 발휘하는데, 각 특징이 독립적이라는 가정을 통해 사전확률이 실제 data corpus에서 출현한 빈도를 통해 추정이 가능해지는 것이다.
이처럼 간단한 가정으로 데이터의 희소성문제를 해결하는 쉽고 강력한 방법으로 MAP의 정답클래스라벨예측이 가능해지는 것이다.
상세예시 및 식은 아래 2.3을 참고
2.3 Sentiment Analysis 예제
위와 같이 class와 data가 긍정/부정과 document로 주어질 때, 'I am happy to see this movie' 라는 문장이 주어진다면, 이 문장이 긍정인지 부정인지 판단해보자! Naïve Bayes를 활용해 단어의 조합에 대한 확률을 각각 분해할 수 있다. 즉, 각 단어의 출현확률을 독립적이라 가정 후, 결합가능도확률을 모두 각각의 가능도확률로 분해한다. 그렇게 되면 데이터 D에서의 출현빈도를 구할 수 있다.
이처럼 corpus에서 단순히 각 단어의 class당 출현빈도를 계산하는 것만으로도 간단한 sentiment analysis가 가능하다.
2.4Add-One Smoothing Naïve Bayes가정을 통해 corpus에서 출현확률을 독립으로 만들어 출현횟수를 적극적으로 활용할 수 있게 되었다. 여기서 문제점이 발생하는데, 만약 Count(happy, neg)=0이라면? P(happy | neg)=0이 되어버린다.
아무리 data corpus에 존재하지 않더라도 그런 이유로 해당 sample의 출현확률을 0으로 추정해버리는 것은 매우 위험한 일이 되어버리기에 아래처럼 분자(출현횟수)에 1을 더해주면 쉽게 문제해결이 가능하다.(물론 완벽한 해결법은 아님)
2.5 장점 및 한계 장점: 단순히 출현빈도를 세는 것처럼 쉽고 간단하지만 강력!! 딥러닝을 활용하기에 label랑 문장 수가 매우 적은 경우, 오히려 복잡한 딥러닝방식보다 더 나은 대안이 될 수 있다.
한계: 'I am not happy'와 'I am happy'에서 not의 추가로 문장은 정반대뜻이 된다. 수식으로는 P(not, happy) ≠ P(not)∙P(happy)가 된다. 단어간 순서로 인해 생기는 정보도 무시할 수 없는데, "각 특징은 서로 독립적이다."라는 Naïve Bayes의 기본가정은 언어의 이런 특징을 단순화해 접근해 한계가 존재한다.
3. 흔한 오해 2
표제어추출(lemmatization), 어간추출(stemming)을 수행해 접사등을 제거한 이후 Text Classification을 진행해야하는가?? 예를들어, "나는 학교에 가요"라는 원문이 있다면, [나 학교 가] 처럼 어간추출이 진행된다.
이는 적은 corpus에서 효과를 발휘하여 희소성문제에서 어느정도의 타협점이 존재할 수 있게된다. 특히, DNN이전 전통적 기계학습방법에서 불연속적 존재인 자연어에 좋은 돌파구를 마련해주었다.
하지만, DNN시대에서는 성공적으로 차원축소(https://chan4im.tistory.com/197#n2)를 수행할 수 있게 되면서 희소성문제는 더이상 큰 장애물이 되지는 않기에 lemmazation, stemming등은 반드시 정석이라 하긴 어렵다.
또한, "나는 학교에 가요" / "나만 학교에 가요" 라는 두 문장은 서로 긍정 / 부정이라는 다른 class를 갖기에 lemmazation이나 stemming을 한 후 Text Classification에 접근하는 것은 바람직하지 못한 방법일 수도 있다. 따라서 이후 설명될 신경망모델을 사용해 text classification을 시도하는것이 훨씬 바람직하다.
만약, 성능향상을 위해 tuning 및 여러 시도에서 corpus의 부족이 성능저하의 원인이라 생각될 때, 추가적인 실험으로는 괜찮은 시도가 될 수 있다.
4. RNN 활용하기
이제 DNN을 통한 text classification문제를 살펴보자. 가장 간단한 방법은 RNN을 활용하는 것으로 sequential data라는 문장의 특징을 가장 잘 활용가능한 신경망 구조이다.
n개의 단어로 이루어진 문장 x에 대해 RNN이 순전파 시, n개의 hidden_state를 얻는다. 이때, 가장 마지막 은닉층으로 text classification이 가능하며 RNN은 입력으로 주어진 문장을 분류문제에 맞게 encoding할 수 있다. 즉, RNN의 출력값은 문장임베딩벡터(sentence embedding vector)라 할 수 있다.
4.1 Architecture 알다시피, text에서 단어는 불연속적 값이기에 이들이 모인 문장 또한, 불연속적값이다. 즉, 이산확률분포에서 문장을 sampling한 것이므로 입력으로는 one-hot벡터들이 여러 time-step으로 주어진다.
mini-batch까지 고려한다면, 입력은 3차원 tensor (n×m×|V|)가 될 것이다. ∙ n : mini_batch size (= 한번에 처리할 문서의 개수) ∙ m : sentence length (= feature vector의 차원수 = 텍스트 문서의 단어의 개수) ∙|V| : Vocabulary size (= Dataset내의 고유한 단어/토큰의 총 수)
하지만 원핫벡터는 주어진 |V| 차원에 단 하나의 1과 |V|-1개의 0으로 이루어진다. 효율적 저장을 위해 굳이 원핫벡터 전체를 가지고 있을 필요는 없기에 원핫벡터를 0 ~ |V|-1 사이 정수로 나타낼 수 있게 된다면, 2차원 matrix (n×m)으로 충분히 나타낼 수 있다.
이렇게 원핫인코딩된 (n×m) tensor를 embedding층에 통과시키면, word embedding tensor를 얻을 수 있다.
이후 word_embedding tensor를 RNN에 통과시키면 된다. 이때, 우린 RNN에 대해 각 time-step별, 계층별로 구분해 word_embedding tensor나 hidden_state를 넣어줄 필요가 없다.
최종적으로 제일 마지막 time-step만 선택해 softmax층을 통과시켜 이산확률분포 P(y | x;θ)로 나타낼 수 있다. 이때 제일 마지막 time-step은 H[:, -1]과 같은 방식으로 index slicing을 통해 도출할 수 있다.
모델구조로 보면 아래와 같다.
마지막으로 원핫벡터 y이기에 인덱스의 로그확률값만 최대화하면 되므로 CE Loss 수식은 NLL(음의 로그가능도)를 최소화하는 것과 동치이다.
Pytorch 구현예제 앞의 수식을 pytorch로 구현한 예제코드로 여러계층으로 이뤄진 LSTM을 사용했다. ∙ LSTM에는 각 층마다 Dropout이 사용되며 ∙ NLL(음의 로그가능도)손실함수로 최적화하기 위해 logsoftmax로 로그확률을 반환한다.
5.3 Text Classification with CNN CNN은 RNN과 달리 순차적 정보보다는 패턴인식 및 파악에 중점을 두는 구조를 갖는다. CNN은 classification에 중요한 단어들의 조합에 대한 패턴을 감지하기도 하는데, 해당 클래스를 나타내는 단어조합에 대한 pattern의 유무를 가장 중시한다.
예를들어, 'good'이라는 단어는 긍정/부정 분류에 핵심이 되는 중요한 signal로 작동한다. 그렇다면, 'good'에 해당하는 embedding vector의 pattern을 감지하는 filter를 모델이 학습한다면? → 'better', 'best', 'great'등의 단어들도 'good'과 비슷한 벡터값을 갖게 될 것이다. → 더 나아가 단어들의 조합 패턴(word sequence pattern)을 감지하는 filter도 학습이 가능할 것이다.
모델 구조에 대해 간단히 설명하자면, 아래와 같다. 먼저 one-hot벡터를 표현하는 인덱스값을 단어임베딩벡터(1차원)로 변환한다. 그 후 문장 내 모든 time-step의 단어임베딩벡터를 합치면 2차원 행렬이 된다. 그 후 Convolution Operation을 수행하면 CNN이 효과를 발휘한다.
Pytorch 구현예제 RNN의 text classification처럼 NLL(음의 로그가능도)손실함수로 최적화하기 위해 logsoftmax로 로그확률을 반환한다.
import torch
import torch.nn as nn
class CNNClassifier(nn.Module):
def __init__(
self,
input_size,
word_vec_size,
n_classes,
use_batch_norm=False,
dropout_p=.5,
window_sizes=[3, 4, 5],
n_filters=[100, 100, 100],
):
self.input_size = input_size # vocabulary size
self.word_vec_size = word_vec_size
self.n_classes = n_classes
self.use_batch_norm = use_batch_norm
self.dropout_p = dropout_p
# window_size means that how many words a pattern covers.
self.window_sizes = window_sizes
# n_filters means that how many patterns to cover.
self.n_filters = n_filters
super().__init__()
self.emb = nn.Embedding(input_size, word_vec_size)
# Use nn.ModuleList to register each sub-modules.
self.feature_extractors = nn.ModuleList()
for window_size, n_filter in zip(window_sizes, n_filters):
self.feature_extractors.append(
nn.Sequential(
nn.Conv2d(
in_channels=1, # We only use one embedding layer.
out_channels=n_filter,
kernel_size=(window_size, word_vec_size),
),
nn.ReLU(),
nn.BatchNorm2d(n_filter) if use_batch_norm else nn.Dropout(dropout_p),
)
)
# An input of generator layer is max values from each filter.
self.generator = nn.Linear(sum(n_filters), n_classes)
# We use LogSoftmax + NLLLoss instead of Softmax + CrossEntropy
self.activation = nn.LogSoftmax(dim=-1)
def forward(self, x):
# |x| = (batch_size, length)
x = self.emb(x)
# |x| = (batch_size, length, word_vec_size)
min_length = max(self.window_sizes)
if min_length > x.size(1):
# Because some input does not long enough for maximum length of window size,
# we add zero tensor for padding.
pad = x.new(x.size(0), min_length - x.size(1), self.word_vec_size).zero_()
# |pad| = (batch_size, min_length - length, word_vec_size)
x = torch.cat([x, pad], dim=1)
# |x| = (batch_size, min_length, word_vec_size)
# In ordinary case of vision task, you may have 3 channels on tensor,
# but in this case, you would have just 1 channel,
# which is added by 'unsqueeze' method in below:
x = x.unsqueeze(1)
# |x| = (batch_size, 1, length, word_vec_size)
cnn_outs = []
for block in self.feature_extractors:
cnn_out = block(x)
# |cnn_out| = (batch_size, n_filter, length - window_size + 1, 1)
# In case of max pooling, we does not know the pooling size,
# because it depends on the length of the sentence.
# Therefore, we use instant function using 'nn.functional' package.
# This is the beauty of PyTorch. :)
cnn_out = nn.functional.max_pool1d(
input=cnn_out.squeeze(-1),
kernel_size=cnn_out.size(-2)
).squeeze(-1)
# |cnn_out| = (batch_size, n_filter)
cnn_outs += [cnn_out]
# Merge output tensors from each convolution layer.
cnn_outs = torch.cat(cnn_outs, dim=-1)
# |cnn_outs| = (batch_size, sum(n_filters))
y = self.activation(self.generator(cnn_outs))
# |y| = (batch_size, n_classes)
return y
6. 쉬어가기) Multi-Label Classification
Mutli-Label Classification: 기존 softmax 분류와 달리 여러 클래스가 동시에 정답이 될 수 있는것
6.1 Binary-Classification sigmoid. &. BCELoss를 사용한다. (이진분류상황은 Bernoulli Distribution이기 때문)
수식은 아래와 같은데, BCE Loss는 이진분류에 특화된 기존 CE Loss의 한 종류이다. 이 수식에서 y는 0또는 1을 갖는 불연속적인 값이고 y_hat은 sigmoid를 통과한 0~1사이의 연속적인 출력값이다.
6.2 Multi-Binary Classification 그렇다면, Multi-Label문제에서 Binary Classification를 어떻게 적용할까?
n개의 항목을 갖는 분류에 대해 신경망의 마지막 계층에 n개의 노드를 주고, 모두 sigmoid함수를 적용한다. 즉, 하나의 모델로 여러 이진분류작업이 가능하다.
그렇다면 최종 손실함수는? 다음과 같다.
6.3ETC 이진분류가 아닐 때는, sigmoid가 아닌 softmax를 사용하고, Loss도 Cross-Entropy로 바꾸면 된다.
마치며...
이번시간에는 text classification에 대해 다루었다. text classification은 모델의 구조의 복잡도나 코드작성난도에 비해 활용도가 매우 높은 분야이다. 다만, 신경망사용이전, 불연속적값에 대한 희소성문제해결을 하지 못한 채, Naïve Bayes방식과 같이 매우 간단하고 직관적인 방법을 사용했다. 다만, Naïve Bayes방식은 "각 feature는 independent하다!"라는 강력한 가정으로인해 classification의 정확도가 떨어질 수 밖에 없었다. 하지만 딥러닝의 도입으로 매우 효율적이고 정확하게 text classification이 가능해졌는데, RNN은 단어들을 순차적으로 받아 가장 마지막 time-step에서 classification을 예측하고 CNN은 classification에 중요한 단어들의 조합에 대한 패턴을 감지하기도 한다.
∙RNN의 경우, 문장전체의 맥락과 의미에 더 집중해 classification을 수행하며 ∙CNN의 경우, 해당 클래스를 나타내는 단어조합에 대한 pattern의 유무를 가장 중시한다.
따라서 RNN과 CNN을 조합해 Ensemble Model로 구현한다면 더 좋은 결과를 얻을수도 있다. 이를 기반으로 다른 모델들을 참고한다면, 긴문장이나 어려운 텍스트에서도 더 높은 성능을 낼 수 있을 것이다.
CNN, Convolutional Neural Network은 기존 딥러닝 신경망이었던 Fully-Connected Layer를 대체하기 위해 나왔다.
CNN은 Locally-Connected Layer로 Fully-Connected Layer에 비해 정보손실이 발생할 수 있다.
하지만 CNN은 이런 정보손실에 대해 channel을 많이 줌을 통해 정보손실을 방지할 수 있다.
또한 CNN은 FC보다 훨씬 weight수 즉, param#이 더 줄어든다
weight의 개수 = input_channel수 x kernel개수 x kernel개수 x output_channel
(단, padding='same')
filter를 weight로 하며, 이때 model은 weight를 조정하여 filter를 모델이 '알아서' 만들도록 한다.
(filtering을 모델에게 맡겨 상황에 따라 필요한 filter를 자체적으로 만들 수 있게 하는 것이다.)
[Auto-Encoder]
[본 목적]
input의 압축 => 스스로 압축 알고리즘을 학습할 수 있는, input에 근사한 압축값을 뽑아낼 수 있음. - 특정 분야에서 정상적으로 동작한다.
(글자->강아지로 클래스가 변하게 된다면? 특징을 못뽑을 수도 있는, 특정 dataset에서만 가능한 비범용적 방법이다.)
- 주로 언어모델, segmentation 등등에서 사용됨.)
Encoding
- 코드화 시키는 것 = 어떠한 코드로 1:1 매칭시키는 것 - 암호화 즉, 용량 압축의 효과 및 일반화도 가능하다.
bottleneck
- 정보가 embedding되어 있음(= 필요 정보만 모여있는 것)
Decoding
- decoding은 사람이 이해하도록 바꿔주는 것으로 encoding과 반대 개념이다. - 이때, input image에 비해 손실이 발생한다.
[Curse of Dimensionality., 차원의 저주]
- 차원이 늘어날수록 문제를 풀기 쉬워지는것은 어느 정도까지이다! - 즉, 역효과가 발생가능하다. → 도리어 학습이 안될 수 있다는 것!
[ERF (Effective Receptive Field)]
- 학습이 되면서 점점 receptive field가 Gaussian distribution 형태에 가까워지는데, 이를 effective receptive field라 한다. - (가장 최외각의 patch는 뒤로 갈수록 영향력이 줄고, 가운데 patch의 영향력이 커져 뒤로갈수록 정규분포와 비슷해져버림) - 이러한 문제로 인해 CNN이 깊게 쌓을 수 없게 된다. → attention을 이용한 transformer, ViT가 나오게 된 배경이 되어 버림!
- 심층신경망은 "over-parameterized"되거나 "weight_decay. &. dropout"같은 엄청난 양의 noise와 regularize로 훈련될 때, 종종 잘 작동하곤한다. 비록 Dropout이 FC.layer층에서 매우 포괄적으로 사용되는 regularization기법이지만, conv.layer에서 종종 덜 효과적이다. 이런 Conv.layer에서의 Dropout기법의 성공의 결핍은 conv.layer의 activation unit이 "dropout에도 불구하고 공간적 상관관계"가 있기에 정보가 여전히 conv.layer를 통해 흐를 수 있다는 점이다. ∴ CNN의 정규화를 위해 구조화된 형태의 dropout기법이 필요하다!
- 이 구조화된 형태의 dropout기법을 본 논문에서 소개하는데, 바로 Dropout이다. Dropout기법은 특징맵의 인접영역에 있는 units를 함께 Drop시키는 방법을 채택한다. 우린 "skip-connection"에 DropBlock을 적용함으로써 정확도의 향상을 이룩했다. 또한, training시 Drop의 수를 점차 늘리면서 2가지 이점을 얻었다. i) 더 나은 accuracy ii) hyperparameter의 선택의 확고성(robust)
- 수많은 실험에서 DropBlock은 CNN을 규제화하는 데 Dropout보다 더 잘 작동한다. ImageNet에서 DropBlock을 사용하는 ResNet-50 아키텍처는 78.13%의 정확도를 달성하여 기존보다 1.6% 이상 향상되었다. COCO Detection에서 DropBlock은 RetinaNet의 평균 정밀도를 36.8%에서 38.4%로 향상시킨다.
1. 서론 (Introduction)
- 심층신경망은 "over-parameterized(= parameter수가 많은)"되거나 "weight_decay. &. dropout"같은 엄청난 양의 noise와 regularize로 훈련될 때, 종종 잘 작동하곤한다. CNN에서 dropout의 첫등장으로 막대한 성공에도 불구하고, 최근 연구에서 convolutional architectures에서 dropout이 사용되는 경우는 극히 드물다. [BN, ResNet,...등 논문] 대부분의 경우, dropout은 CNN에서 주로 "Fully-Connected layer"에서 메인으로 사용된다.
- 우린 Dropout의 핵심결점이 "drops out featurerandomly"라고 주장한다. 특징을 무작위로 제거하는 것이 FC.layer에서는 좋을 수는 있으나, "공간적 상관관계"가 존재하는 Conv.layer에서는 덜 효과적이다. dropout에도 불구하고, 특징간의 상관관계가 존재한다는 것은 "input정보가 다음층에도 전달된다는 것"이며 이는 신경망의 "overfitting"을 야기할 수 있다. 이런 직관은 CNN의 규제화를 위해 더 구조화된 dropout이 필요하다는 것을 시사한다.
- 본 논문에서, (dropout을 구조화하여 CNN규제화에 부분적으로 효과가 있는) DropBlock에 대해 소개한다. DropBlock에서 block내의 특징, 즉 특징맵의 인접영역이 함께 drop된다. DropBlock은 상관영역의 특징을 폐기(discard)하므로 신경망은 data에 적합한 증거를 다른 곳에서 찾아야한다. (그림 1 참조).
- 우리 실험에서, DropBlock은 다양한 모델과 dataset에서 dropout보다 훨씬 낫다. ResNet-50 에 DropBlock을 추가하면 ImageNet의 Image Classification의 정확도가 76.51%에서 78.13%로 향상된다. COCO detection에서 DropBlock은 RetinaNet의 AP를 36.8%에서 38.4%로 향상된다.
2.Related work
- 서론에서 말했듯, Dropout은 DropConnect, maxout, StochasticDepth, DropPath, ScheduledDropPath, shake-shake regularization, ShakeDrop regularization같은 신경망에 대한 여러 정규화 방법에서 영감을 받었다. 이런 방법들의 기본 원칙은 training data에 overfitting되지 않기위해 신경망에 noise를 추가한다. CNN의 경우, 전술한 대부분의 성공적 방법은 noise가 구조화되어야 한다는 것이다. 예를 들어, DropPath에서 신경망의 전체 계층은 특정 단위뿐만 아니라 훈련에서 제외된다. 이러한 dropping out layer의 전략은 입출력 branch가 많은 계층에 잘 적용될 수 있지만 branch가 없는 계층에는 사용할 수 없다. cf) "block"을 conv.layer내의 인접한 특징맵의 집합으로 정의하고 "branch"를 동일한 공간 해상도를 공유하는 연속된 block의 집합으로 정의한다.
우리의 방법인 DropBlock은 CNN의 모든 곳에 적용할 수 있다는 점에서 더 일반적이다. 우리의 방법은 전체 channel이 특징맵에서 drop되는 SpatialDropout과 밀접한 관련이 있기에 우리의 실험은 DropBlock이 SpatialDropout보다 더 효과적이라는 것을 보여준다.
- Architecture에 특정된 이런 noise주입 기술의 개발은 CNN에만 국한되지 않는다. 실제로 CNN과 유사하게 RNN은 자체적인 noise의 주입방식을 필요로 한다. 현재, Recurrent Connections에 noise를 주입하는 데 가장 일반적으로 사용되는 방법 중 두 가지가 있는데, 바로 Variational Dropout과 ZoneOut이다.
- 우리의 방법은 입력 예제의 일부가 영점 처리(zeroed out)되는 데이터 증강 방법인 Cutout에서 영감을 얻었다. DropBlock은 CNN의 모든 특징맵에서 Cutout을 적용하여 Cutout을 일반화한다. 우리의 실험에서, training 중 DropBlock에 대해 고정된 zero out비율을 갖는 것은 훈련 중 zero out비율이 증가하는 schedule을 갖는 것만큼 강력하지 않다. 즉, 교육 중에는 초기에 DropBlock 비율을 작게 설정하고, 교육 중에는 시간이 지남에 따라 선형적으로 증가시키는 것이 좋으며, 이 scheduling 체계는 ScheduledDropPath와 관련이 있다.
3. DropBlock
- DropBlock은 dropout과 비슷한 간단한 방법이지만, dropout과의 주된 차이점은 Dropout: dropping out independent random unit DropBlock: drops contiguous regions from a feature map of a layer DropBlock은 2가지의 주요 parameter가 있다. i) block_size : drop할 block의 크기 ii) 𝛾 :얼마나 많은 activation units를 drop할 것인지 우리는 서로 다른 feature channel에 걸쳐 공유된 DropBlock mask를 실험하거나 각 feature channel에 DropBlock 마스크를 지니게 한다. Algorithm 1은 후자에 해당하며, 이는 우리의 실험에서 더 잘 작동하는 경향이 있다.
Dropout과 유사하게 우리는 추론시간중 DropBlock을 적용하지 않는데, 이는 기하급수적으로 크기가 큰 하위신경망의 앙상블에 걸쳐 평균예측을 평가하는 것으로 해석된다. 이런 하위신경망은 각 신경망이 각 특징맵의 인접한 부분을 보지 못하는 Dropout으로 커버되는 특별한 하위신경망의 하위집합을 포함한다.
• Setting the value of block_size
•Setting the value of 𝛾
•Scheduled DropBlock
4. Experiments
다음 Section에서는 Image Classification, Object Detection 및 Semantic Segmentation에 대한 DropBlock의 효과를 경험적조사를 진행한다. Image Classification을 위한 광범위한 실험을 통해 ResNet-50에 DropBlock을 적용한다. 결과가 다른 아키텍처로 전송가능여부의 확인을 위해 최첨단 모델인 AmoebaNet에서 DropBlock을 수행하고 개선 사항을 보여준다. Image classification 외에도, 우리는 DropBlock이 Object Detection 및 Semantic Segmentation을 위한 RetinaNet을 훈련하는 데 도움이 된다는 것을 보여준다.
4.1 ImageNet Classification
ILSVRC 2012 classification dataset - train: 1.2M , valid: 5만 , test: 15만, 1000-class label 이미지에는 1,000개의 범주가 레이블로 지정됩니다. [GoogLeNet, DenseNet]처럼 training하기 위해 horizontal flip, scale, 종횡비율확대를 사용했다. evaluation에서 multiple crop대신, single crop을 적용했다. 일반적 관행에 따라 검증 세트에 대한 분류 정확도를 보고한다.
우리는 모든 모델에 대해 - 기본 image size (ResNet-50의 경우 224 x 224,AmebaNet의 경우 331 x 331) - batch size (ResNet-50의 경우 1024,AmebaNet의 경우 2048) - 및 하이퍼 파라미터 설정을 적용했다. 우린 단지 ResNet-50 아키텍처에 대한 training epoch을 90개에서 270개로 늘렸을 뿐이다. 학습률은 125, 200, 250 epoch마다 0.1배 감소했다.
AmebaNet 모델은 340epoch 동안 훈련되었으며 학습률스케줄링을위해 지수decay체계가 사용되었다. 기존의 모델은 일반적으로 더 긴 training scheme으로 인해 overfitting되어서 훈련이 종료되면 validation accuracy가 낮다. 따라서 공정한 비교를 위해 전체 training과정에 걸쳐 가장 높은 validation accuracy를 보고한다
4.1.1 DropBlock in ResNet-50
ResNet-50은 이미지 인식을 위해 널리 사용되는 CNN아키텍처이다. 다음 실험에서, 우리는 ResNet-50에 다른 규제화 기술을 적용하고 결과를 DropBlock과 비교한다. 결과는 표 1에 요약되어 있다.
•Where to apply DropBlock ResNet에서 building block은 몇 개의 conv.layer와 identity mapping을 수행하는 별도의 skip-connection으로 구성된다. 모든 conv.layer는 Batch Normalizatoin layer 및 ReLU activation에 따른다. building block의 출력은 convolution building block의 출력은 convolution branch의 출력과 skip connection 출력의 합이다.
ResNet은 활성화함수의 공간적 해상도에 기초하여 그룹을 구축하여 나타낼 수 있는데, building group은 여러 building block으로 구성된다. 우리는 그룹 4를 사용해 ResNet의 마지막 group(즉, conv5_x의 모든 layer)을 나타낸다.
다음 실험에서는 ResNet에서 DropBlock을 적용할 위치를 연구한다. ① conv.layer이후에만 DropBlock을 적용하거나 ② conv.layer와 skip-connection 둘 모두 뒷부분에 DropBlock을 적용하는 실험을 했다. 다양한 특징 그룹에 적용되는 DropBlock의 성능을 연구하기 위해 그룹 4 또는 그룹 3과 그룹 4 모두에 DropBlock을 적용하는 실험을 했다.
•DropBlock. vs. dropout 원래 ResNet 아키텍처는 모델의 Dropout을 적용하지 않는다. 다만 논의의 용이성을 위해 기존 ResNet의 Dropout을 convolution branch에만 dropout을 적용하는 것으로 정의한다. 기본적으로block_size= 7로 그룹 3과 4 모두에 DropBlock을 적용한다. 우리는 모든 실험에서 그룹 3에 대해 parameter𝛾를4만큼감소시켰다. 그림 3-(a)에서, 우리는 top-1 accuracy에서 DropBlock이 1.3%로 Dropout을 능가한다는 것을 보여준다. reservedkeep_prob는 DropBlock을keep_prob의 변경에 더 강력하게 만들고 keep_prob(3-(b))의 가장 많은 값에 대한 개선을 추가한다.
그림 3에서 최고의keep_prob를 통해 발결한 점은 바로block_size가 1에서 전체 특징맵을 포함하는block_size로 바뀌었다는 것이다. 그림 4는 일반적으로 1의block_size를 적용하는 것보다 큰block_size를 적용하는 것이 더 낫다는 것을 보여주며 최상의 DropBlock 구성은block_size= 7을 그룹 3과 4에 모두 적용하는 것입니다.
모든 구성에서 DropBlock과 Dropout은 유사한 추세를 공유하며 DropBlock은 최상의 Dropout 결과에 비해 큰 이득을 보입니다. 이것은DropBlock이Dropout에 비해 더 효과적인 규제화 도구라는 증거를 보여준다.
•DropBlock. vs. SpatialDropout 기존의 Dropout과 유사하게, 우리는 기존의 SpatialDropout기법이 convolution branch에만 적용하는 것으로 정의한다. SpatialDropout기법은Dropout기법보다는 낫지만 DropBlock다는 떨어진다. (즉, DropBlock >SpatialDropout > Dropout) 그림 4에서 그룹 3의 고해상도 특징맵에 적용할 때,SpatialDropout기법이 너무 가혹할 수 있음을 발견했다. DropBlock은 그룹 3과 그룹 4 모두에서 일정한 크기의 Block을 Drop하여 최상의 결과를 달성합니다.
•Comparision withDropPath Scheduled DropPath기법에서 "skip-connection"을 제외한 모든 연결에 Scheduled DropPath를 적용했습니다. 우리는keep_prob매개 변수에 대해 다른 값으로 모델을 훈련시켰으며, 모든 그룹에서 DropPath를 적용하고 그룹 4 또는 그룹 3과 그룹 4에서만 다른 실험과 유사한 모델을 훈련시켰다. keep_prob= 0.9인 그룹 4에만 적용했을 때 77.10%로 최상의 validation accuracy를 달성했다.
•Comparision with Cutout 또한 데이터 증강 방법 중 하나인 Cutout기법과 비교하여 입력 이미지에서 고정 크기 블록을 무작위로 떨어뜨렸다. Cutout기법은 Cutout논문에서 제안한 대로 CIFAR-10 dataset의 정확도향상을 되지만, 우리 실험에서 ImageNet dataset의 정확도를 향상시키지는 않는다.
•Comparision with other regularization techniques 우리는 DropBlock을 일반적으로 사용되는 2가지 regularization기술(data augmentation, label smoothing)과 비교한다. 표 1에서 DropBlock은data augmentation, label smoothing에 비해 성능이 우수하다. DropBlock과 label smoothing 및 290epoch training을 결합하면 성능이 향상되어 규제화 기술이 더 오래 훈련할 때, 보강이 될 수 있음을 보여준다.
4.1.2DropBlock in AmoebaNet
-또한 진화적구조의 search를 사용하여 발견된 최신 architecture는AmoebaNet-Barchitecture에서 DropBlock의 효과를 보여준다. 이 모델은 0.5의 keep probability로 dropout하지만 최종 softmax층에서만 dropout된다.
- 우린모든 Batch Normalization층 후에 DropBlock을 적용하고 또한마지막셀의 50%에 Skip-Connection에도 적용한다. 이러한 셀에서 특징맵의 해상도는 331x331 크기의 입력 이미지에 대해 21x21 또는 11x11이다. 마지막 Section의 실험을 기반으로, 우리는0.9의keep_prob를 사용하고 마지막 특징맵의 width인block_size= 11을 설정했다. DropBlock은AmoebaNet-B의 top-1 accuracy를 82.25%에서 82.52%로 향상시킨다(표 2).
4.2 Experimental Analysis
DropBlock은드롭아웃에비해ImageNet classification정확도를 향상시키는 강력한 경험적 결과를 보여준다.
우리는conv.layer의 인접 영역이 강하게 상관되어 있기 때문에Dropout이충분하지 않다고 가정한다. unit을임의로 떨어뜨려도 인접 unit을 통해 정보가 흐를 수 있기 때문이다.
이Section에서는DropBlock이 semantic정보를 삭제하는 데 더 효과적이라는 것을 보여주기 위해 분석을 수행한다.
결과적으로,DropBlock에 의해 규제화된모델은Dropout에의해규제화된모델에 비해 더 강력하다.
우리는추론 중,block_size가1과7인DropBlock을 적용하고 성능의 차이를 관찰하여 문제를 연구한다.
• DropBlock drops more semantic information
먼저 규제화 없는 훈련된 모델을 가져와서block_size= 1및block_size = 7을 사용하여DropBlock으로테스트했다. 그림5의 녹색 곡선은 추론 중에keep_prob가 감소함에 따라 validation accuracy가 빠르게 감소함을 보여준다.
이것은DropBlock이 semantic정보를 제거하고 분류를 더 어렵게 한다는 것을 시사한다.
정확도는 DropBlock이dropout보다 semantic정보를 제거하는 데 더 효과적이라는 것을 시사하는block_size= 7과 비교하여block_size= 1에 대해keep_prob가 감소할수록 더 빠르게 떨어진다.
• Model trained with DropBlock is more robust
다음으로 우리는 더 많은 의미 정보를 제거하는 큰 블록 크기로 훈련된 모델이 더 강력한 정규화를 초래한다는 것을 보여준다.
우리는추론 중에block_size= 7과 적용된block_size= 1로 훈련된 모델을 취함으로써 그 사실을 입증하고 그 반대도 마찬가지이다.
그림5에서block_size= 1과block_size = 7로 훈련된 모델은 모두 추론 중에block_size = 1이 적용된 상태에서 견고하다.그러나block_size = 1로 훈련된 모델의 성능은 추론 중에block_size = 7을 적용할 때keep_prob가 감소함에 따라 더 빠르게 감소했다.
결과는block_size = 7이 더 강력하고block_size = 1의 이점이 있지만 그 반대는 아님을 시사한다.
DropBlock으로훈련된 모델은DropBlock이 인접한 영역에서 semantic정보를 제거하는 데 효과적이다. 따라서 공간적으로 분산된 표현을 학습해야 한다고 가정한다.
DropBlock에 의해규제화된모델은 하나의 독자적 영역에만 초점을 맞추는 대신 여러 독자적 영역을 학습해야 한다.
우리는ImageNet validation set에서ResNet-50의conv5_3클래스 activation을 시각화하기 위해 클래스 활성화 맵(CAM)을 사용한다.
그림6은block_size = 1및block_size = 7인DropBlock으로훈련된 기존모델과 모델의 클래스 activation을 보여준다.
일반적으로DropBlock으로훈련된 모델은 여러 영역에서 높은 클래스 activation을 유도하는 공간적으로 분산된 표현을 학습하는 반면,규제화가 없는 모델은 하나 또는 매우적은 수의 영역에 초점을 맞추는 경향이 있다.
4.3 Object Detection in COCO
DropBlock은 CNN을 위한 일반적인 regularization 모듈이다. 이 Section에서는 DropBlock이 COCO dataset의 training object detector에도 적용될 수 있음을 보여준다. 우리는 실험에 RetinaNet을 사용하며, image에 대한 single label을 예측하는 image classification과 달리, RetinaNet은 multi-scale Feature Pyramid network(FPN)에서 convolution으로 실행되어 다양한 스케일과 위치에서 object를 localizatoin하고 분류한다. [Focal loss for dense object detection]의 모델 아키텍처와 anchor 정의를 따라 FPN과 classifier/regressor의 branch들을 구축했다.
• Where to apply DropBlock to RetinaNet model RetinaNet 모델은 ResNet-FPN을 백본 모델로 사용한다. 단순성을 위해 ResNet-FPN의 ResNet에 DropBlock을 적용하고 ImageNet classification 훈련에 대해 찾은 최상의keep_prob를 사용한다. DropBlock은 지역 제안(region proposal)의 특징에 구조화된 패턴을 drop하는 방법을 배우는 최근 연구[A-Fast-RCNN]과는 다르다.
• Training object detector from random initialization 무작위 초기화에서 object detector를 훈련하는 것은 어려운 작업으로 간주되어 왔다. 최근, 몇몇 논문들은 새로운 모델 아키텍처, 큰 mini-batch size 및 더 나은 normalization layer를 사용하여 이 문제를 해결하려고 시도했다. 우리의 실험에서, 우리는 모델의 규제화 관점에서 문제를 살펴본다. training image classification model과 동일한 hyper parameter인keep_prob = 0.9로 DropBlock을 시도하고 다른 block_size로 실험했다. 표 3에서 무작위 초기화에서 훈련된 모델이 ImageNet으로 사전 훈련된 모델을 능가한다는 것을 보여준다. DropBlock을 추가하면 1.6%의 AP가 추가되는데, 그 결과는 모델 규제화가 Object Detector를 처음부터 훈련시키는 중요한 요소이며 DropBlock은 물체 감지를 위한 효과적인 규제화 접근법임을 시사한다. • Implementation details 우리는 실험을 위해 RetinaNet3의 오픈 소스 구현을 사용한다. 모델은 64개의 이미지를 한 batch동안 처리하여 TPU에 대해 훈련되었다. 교육 중에 multi-scale jittering을 적용해 scale간의 image sizewhwjd gn ekdma image를 최대차수 640으로 padding/crop을 진행. 테스트하는 동안 최대 차수는 640의 singel-scale image만 사용되었다. Batch Normalization층은 classifier/regressor branch를 포함한 모든 conv.layer 이후에 적용되었다.
모델은 150 epoch(280k training step)을 사용해 훈련되었다. 초기 학습률 0.08은 처음 120 epoch에 적용되었고 120 epoch과 140epoch에 0.1씩 감소했다. ImageNet 초기화를 사용한 모델은 16 및 22 epoch에서 learning decay와 함께 28 epoch에 대해 훈련되었다. 초점 손실에는 α = 0.25와 𝛾 = 1.5를 사용했다. weight_decay =0.0001. &. 0.9의 momentum = 0.9 이 모델은 COCO train 2017에서 훈련되었고 COCO val 2017에서 평가되었다.
4.4 Semantic Segmentation in PASCAL VOC
-우리는 DropBlock이 semantic segmentation모델도 개선한다는 것을 보여준다. PASCAL VOC 2012 데이터 세트를 실험에 사용하고 일반적인 관행을 따라 증강된 10,582개의 training이미지로 훈련하고 1,449개의 testset 이미지에 대한 mIOU를 보고한다. 우리는semantic segmentation를 위해 오픈 소스 RetinaNet 구현을 채택한다. 구현은 ResNet-FPN backborn 모델을 사용하여 multi-scale feature를 추출하고 segmentation을 예측하기 위해 Fully-Convolution Network를 상단에 부착한다. 우리는 훈련을 위해 오픈 소스 코드의 default hyper-parameter를 사용한다.
- Object Detection실험에 이어 random initialization에서 훈련 모델에 대한 DropBlock의 효과를 연구한다. 우리는 45개의 epoch에 대해 pre-trained ImageNet 모델로 시작한 모델과 500개의 epoch에 대해 무작위 초기화된 모델을 훈련시켰다. ResNet-FPN backborn 모델과 Fully-Convolution Network에 DropBlock을 적용하는 실험을 수행했으며Fully-Convolution Network에 DropBlock을 적용하는 것이 더 효과적이라는 것을 발견했다. DropBlock을 적용하면 처음부터 교육 모델에 대한 mIOU가 크게 향상되고 ImageNet 사전 교육 모델과 무작위로 초기화된 모델의 교육 간 성능 격차가 줄어든다.
5. Discussion
- 이 논문에서, CNN의 training regularize기법인 DropBlock을 소개한다. DropBlock은 공간적으로 연관된 정보를 drop하는 구조화된 dropout기법이다. ImageNet, COCO detection에 dropout과 DropBlock을 비교함으로써 더욱 효과적인 규제화기법임을 증명하였다. DropBlock은 광범위한 실험 설정에서 지속적으로 드롭아웃을 능가한다. 우리는 DropBlock으로 훈련된 모델이 더 강력하고 드롭아웃으로 훈련된 모델의 이점을 가지고 있음을 보여주기 위해 분석을 수행하였으며, class activation mapping은 모델이 DropBlock에 의해 정규화된 더 많은 공간적으로 분산된 표현을 학습할 수 있음을 시사한다.
- 우리의 실험은 conv.layer외에 "skip-connection"에 DropBlock을 적용하면 정확도가 증가한다는 것을 보여준다. 또한 훈련 중에 삭제된 unit의 수를 점진적으로 증가시키면 정확도가 향상되고 hyper-parameter선택에 더욱 강력해진다.
🧐 논문 감상_중요개념 핵심 요약
"DropBlock: A regularization method for convolutional networks"
[핵심 개념]
Dropout은 딥러닝에서 널리 사용되는 regularization방법이지만 구조적 특성으로 인해 CNN에서는 제대로 작동하지 않을 수 있다.
DropBlock은 CNN용으로 특별히 설계된 정규화 방법이다. 개별 단위 대신 교육 중에 기능 맵의 전체 연속 블록을 무작위로 삭제하여 작동합니다.
DropBlock 방법은 개별 픽셀 대신 인접한 블록을 드롭(contiguous block drop)하는 공간적 드롭아웃 방법의 일반화로 볼 수 있다.
DropBlock은 CIFAR-10, CIFAR-100 및 ImageNet을 포함한 여러 dataset에서 CNN의 일반화 성능을 향상시켰다.
DropBlock은 기존 CNN구조에 쉽게 통합될 수 있으며 "weight_decay" 및 "data augmentation"같은 다른 "regularization"방법과 함께 사용할 수 있다.
또한 학습 중 신경망에서 연결의 전체 경로를 무작위로 drop하는 유사한 정규화 방법인 "drop-path"의 개념을 도입했다.
전반적으로 DropBlock 방법은 CNN을 위해 특별히 설계된 강력하고 효과적인 정규화 기술로 여러 벤치마크dataset에서 네트워크의 일반화 성능을 개선하는 것으로 나타났으며 기존 아키텍처에 쉽게 통합할 수 있다.
🤫 CNN, 합성곱 신경망이란? 여러 분야, 특히나 image classification에서 좋은 성능을 보여주는 방법이다. 이런 합성곱 신경망에서 합성곱의 연산은 정의 자체에 가중치를 flip하는 연산이기에 아래와 같은 수식으로 표현한다. i와 j시점에서 input x와 kernel(= weight)의 합성곱에 편향(bias)를 각 pixel에 더해 output y를 도출한다. 이때, 아래와 같은 연산식을 Cross-Correlation이라 부른다.
🤫 CNN이 등장하게 된 이유는 무엇일까? MLP vs CNN ▶ image classification에서 MLP보다 CNN이 더 선호된다.
1.MLP는 각 input(한 image의 pixel)에 대해 하나의 퍼셉트론만 사용하고 large한 image에 대해 weight가 급격하게 unmanageable해진다. 이는 너무 많은 parameter들이 fully-connected되어 있기 때문이다. 따라서 일반화를 위한 능력을 잃는, 과적합(overfitting)이 발생할 수 있다.
2. MLP는 input image와 shift된 image가 다르게 반응한다는 점이다. (translation invariant(불변)가 아니기 때문)
예를 들어 고양이 사진이 한 사진의 이미지 왼쪽 상단에 나타나고 다른 사진의 오른쪽 하단에 나타나면 MLP는 자체 수정을 시도하고 고양이가 이미지의 이 섹션에 항상 나타날 것이다.
즉, MLP는 이미지 처리에 사용하기에 가장 좋은 아이디어가 아니다. 주요 문제 중 하나는 이미지가 MLP로 flatten(matrix -> vector)될 때 공간 정보가 손실된다.
∴고양이가 어디에 나타나든 사진에서 고양이를 볼 수 있도록 image features(pixel)의 공간적 상관 관계(spatial correlation)를 활용할 방법이 필요.
∴ 이를 위한 해결책으로 등장한 것이 바로 CNN 이다!
좀 더 일반적으로, CNN은 공간적 상관관계가 있는 data에 잘 반응할 수 있다. 따라서 CNN은 input으로 image data를 포함하는 문제에 대한 prediction의 한 방법이다.
이런 CNN의 사용은 2차원 이상의 image의 내부적 표현에 대한 좋은 이점을 갖는다. 즉, image작업 시, 가변적인 구조의 data안에서의 position과 scale을 model이 배우기 쉽게 해준다.
🧐 Padding, Stride, Pooling
🤫 Padding 예를들어 4x4차원이 input에 2x2의 kernel로 합성곱을 하게되면 output 차원은 3x3으로 차원이 줄어든다. 이렇게 차원이 줄어드는 현상을 방지하기 위해서 padding이라는 방법을 사용한다. 위 사진처럼입력 데이터는 3x3이지만zero-padding을 통해 차원의 축소가 일어나지 않게 할 수 있다.
🤫 Stride 한 번의 합성곱연산 이후 다음 계산영역으로 이동을 해야하는데, 이때 얼마나 이동할 것인지 간격을 정하는 값이며 이때 output 데이터 행렬의 차원이 더 작아지는 것을 알 수 있다. 그렇다면, padding과 stride를 해도 output data의 크기를 미리 계산할 수는 없을까?
🤫 Pooling CNN에서 feature의 resolution을 줄일 때, 사용하는 방식으로 아래와 같이 작동한다.
그렇다면, 이쯤에서 드는 생각이 있을 것이다. Question? 왜 굳이? pooling을 사용하는거지? 그냥 convolution layer를 stride = 2로 줄여서 작동하면 같은작업이지 않나?
Answer!
convolution layer를 이용하여stride = 2로 줄이면학습 가능한 파라미터가 추가되므로 학습 가능한 방식으로 resolution을 줄이게 되나 그만큼 파라미터의 증가 및 연산량이 증가하게 됩니다.
반면pooling을 이용하여 resolution을 줄이게 되면 학습과 무관해지며 학습할 파라미터 없이 정해진 방식 (max, average)으로 resolution을 줄이게 되어 연산 및 학습량은 줄어든다. 다만convolution with stride방식보다 성능이 좋지 못하다고 알려져 있습니다. 따라서,layer를 줄여서 gradient 전파에 초점을 두려고 할 때 pooling을 사용하는게 도움이
🤔 딕셔너리 key, value에 대한 접근-2. (key로 value얻기, value로 key얻기)
dict_a.get(key) # key에 해당하는 "value값 출력"
for i in dict_a # 기본적으로 for문에서 i를 통해 key값을 사용할 수 있음
for i in dict_a.values() # 기본적으로 for문에서 i를 통해 value값을 사용할 수 있음
for key, value in dict_a.items(): # key와 value를 한번에 사용
for key, value in dict_a: # 위와 동일한 사용법
😶 활용
for i in construct.keys():
if construct[i] == n: # key의 어떤 값이 n과 같다면
ans.append(i) # {construct[i] : i} key에 해당하는 value, i를 추가
🧐 백준 2798 (딕셔너리 활용)
🤫해결의 실마리 1. brute force (완전탐색)
처음부터 끝까지 모두 탐색하는 방법의 brute force를 사용한다,.
🤫해결의 실마리 2. 딕셔너리와 set
cf. 딕셔너리 객체의 get()함수
dict.get(key, default = None)
# 매개변수로 넘긴 값 (괄호 안의 값)이 키에 속하지 않으면? None 출력
get함수의 return값은 첫번째 인자의 키값이다.
🤔Algorithm 과정 1. 입력받은 숫자 리스트들에서 3개의 숫자를 골라 더한 값을 set에 집어넣는다. 2. 이 sum_set에 대해 입력된 M을 넘지 않는 것들에 대해 딕셔너리 형태로 세 숫자의 합과 m과의 차이를 저장한다. 3. 이때, 저장한 m과의 차이가 가장 작은 것이 m과 가장 가까운 것이므로 답임을 알 수 있다.
🤫solution_2798
n, m = map(int, input().split())
num = list(map(int, input().split()))
sum_set = set()
sum_dict = {}
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
sum_set.add(num[i] + num[j] + num[k])
for i in sum_set:
if m - i >= 0:
sum_dict[i] = m - i
else:
pass
print(min(sum_dict, key = sum_dict.get))
🧐 백준 2231 (딕셔너리 활용)
🤫해결의 실마리 1. 자연수의 자릿수에 해당하는 숫자 구하기.
# 각 자릿수의 숫자의 합을 출력하는 함수
def digit(n):
if n < 10:
return n
else:
return digit(n // 10) + digit(n % 10)
🤫해결의 실마리 2. 딕셔너리의 사용
construct = {}
for i in range(n+1):
construct[i] = i + digit(i)
ans = []
for i in construct:
if construct[i] == n:
ans.append(i)
🤔Algorithm 과정
216 => 198 + 1 + 9 + 8 ... 이런 방식은 거의 불가 (역추적 진행 시 생성자가 여러개임을 도출할 수 없음)
맵핑을 통해 1~N까지 똑같은 value들 중 최소 key를 찾는 방식으로 문제를 해결해 나갈 것이다.
{1:1}
{2:2}
...
{13:17}
{14:19}
{15:21}
...
{198:216}
...
{N:N'}
🤫solution_2231
n = int(input())
# 각 자릿수의 숫자의 합을 출력하는 함수
def digit(n):
if n < 10:
return n
else:
return digit(n // 10) + digit(n % 10)
construct = {}
for i in range(n+1):
construct[i] = i + digit(i)
ans = []
for i in construct:
if construct[i] == n:
ans.append(i)
print(0) if len(ans) == 0 else print(min(ans))
🤔Algorithm 과정 1. 각각 받은 w, h에 대해 등수는 1부터 시작하므로 rank = 1로 초기화해준다. 2. 입력한 변수들을 저장한 person리스트에 대해 0번째 인덱스(몸무게)와 1번째 인덱스(키)가 모두 큰 경우에 rank를 1 증가시켜준다.
🤫solution_7568
person = []
for _ in range(int(input())):
w, h = map(int, input().split())
person.append((w, h))
# print(person) => [(55, 185), (58, 183), (88, 186), (60, 175), (46, 155)]
for i in person:
rank = 1
for j in person:
if i[0] < j[0] and i[1] < j[1]:
rank += 1
print(rank, end = " ")
🧐 백준 1436
🤔Algorithm 과정 1. 처음 666인 수를 terminal변수에 저장 2. n이 0이 아닐 때 까지 반복하는데, 문자열 terminal을 update하는 방식으로 문제를 해결할 것이다. 3. terminal 문자열 안에 666이 들어있다면, n을 1만큼 감소시키고 4. 만약 n이 0이라면 반복문을 탈출한다. 5. 이후 terminal의 값을 1만큼 증가시킨다.
🤫solution_1436
n = int(input())
terminal = 666
while n != 0:
if '666' in str(terminal):
n -= 1
if n == 0:
break
terminal += 1
print(terminal)
CNN에서 filter를 이용해 합성곱 계층의 동작처럼 8X8의 정답 체스판을 만들고 CNN알고리즘처럼 입력받은 체스판을 스캔하면서 틀린 경우를 카운팅해서 틀린경우의수가 최소를 출력한다.
🤔 CNN_Algorithm 과정 https://wikidocs.net/164823
🤫solution_1436
n, m = map(int, input().split())
chess = [list(input()) for _ in range(n)]
ans_chess_W , ans_chess_B = [], []
for i in range(4):
ans_chess_W.append('WBWBWBWB')
ans_chess_W.append('BWBWBWBW')
ans_chess_B.append('BWBWBWBW')
ans_chess_B.append('WBWBWBWB')
def wrongcount_W (x, y):
cnt = 0
for i in range(8):
for j in range(8):
if chess[x+i][y+j] != ans_chess_W[i][j]:
cnt += 1
return cnt
def wrongcount_B (x, y):
cnt = 0
for i in range(8):
for j in range(8):
if chess[x+i][y+j] != ans_chess_B[i][j]:
cnt += 1
return cnt
# CNN처럼 8x8 size로 체스판 자르기
cnt = []
for i in range(n-8 +1):
for j in range(m-8 +1):
cnt.append(wrongcount_W(i, j))
cnt.append(wrongcount_B(i, j))
print(min(cnt))
