Detection모델은 영상의 물체(object)를 Bbox(Bounding_Box)라는 직사각형으로 지정한다. 이때, Box마다class와 confidence를 출력한다.
PASCAL VOC대회, COCO 대회 등에서 성능을 주로 mAP로 측정한다. IoU→AP→mAP 순으로 계산이 되기에 IoU부터 알아보고자 한다. 추천 Survey 논문: [Padilla 2020]
1.1IoU (Intersection Over Union)
AP(Average Precision)는 IoU를 기반으로 계산되므로 IoU에 대해 알아보자. 아래 식은 IoU에 대한 식을 정의한다. IoU는 Jaccard Similarity, Jaccard Index라고도 불리는데, 이는 기본적으로 prediction과 target간의 percent overlap을 정량화하는 방법이다.
실제로는 Object에 Bbox가 여럿 나타나 복잡한 상황이 된다. ∙ 참값 하나가 여러 예측과 겹치거나 ∙ 예측이 여러 참값과 겹치고 겹침이 없거나.
1.2AP. & mAP
AP (Average Precision)
AP는 위와 같은 상황(Bbox가 여럿 나타나는 상황)에서 계산한다. AP계산을 위해 TP, FP, FN을 세야한다. cf) True = 맞춘것을 의미
AP 계산알고리즘: ① 신뢰도 임계값을 넘는 Bbox만 선택, 예측목록을 생성 ② 예측목록에 있는 Bbox를 신뢰도로 정렬 ③ Confidence값이 큰 순서대로 처리. 현재 Bbox가 IoU 임계값을 넘으면 TP로 판정, 아니면 FP로 판정
❗️이때, 2개 이상의 물체에 하나의 Bbox가 겹치게 된다면? IoU가 최대인 쌍을 사용한다. TP발생 시, 참값목록에서 TP_Bbox를 제거, 이중의 쌍을 맺는 것을 방지한다. 이때, 예측목록에 있는 Bbox를 모두처리후, 쌍을 맺지못한 채 남아있는 TP_Bbox는 FN으로 판정한다.
mAP (mean Average Precision)
AP를 각 물체 class에 대해 계산 → 이 AP를 모든 class에 대해 평균한 값이다.
아래 예시를 살펴보자. 먼저, Precision과 Recall은 아래수식처럼 구할 수 있다.
즉, True = 맞춘것을 의미하므로 Precision과 Recall은 아래처럼 설명할 수 있다. ∙ Precision = (맞춘것=TP) / (예측한 것 중 = ?P) ∙ Recall = (맞춘것=TP) / (실제 중)
먼저 mAP를 구하는 순서에 대해 설명해보겠다.
⓪ Confidence=0.6 & IoU=0.5 로 설정
① Confidence임계값을 넘긴 Bbox로 예측목록 {a,b,d}를 생성
② 예측목록을 Confidence순으로 정렬 → {b,d,a}
③ 신뢰도가 가장 높은 b먼저 처리.
∙ b는 2,3과 겹침 → IoU가 더 큰 2와 쌍을 맺음
∙ b-2쌍을 TP로 판정 후, 2는 참값(Ground_Truth)목록에서 제외.
④ 2번째 신뢰도를 갖는 d를 처리
∙ d는 4와 IoU가 0.12(<임계IoU)이므로 FP로 판정
⑤ 마지막 Bbox예측목록원소 a를 처리
∙ a는 1과 IoU가 0.6(=임계IoU)이므로 TP로 판정
⑥ Bbox로 생성한 예측목록을 모두 처리하였다.
⑦ 예측 Bbox 처리 후, 쌍을 못맺은 3과 4는 FN으로 판정.
⑧ 최종적인 Precision과 Recall은 다음과 같다.
∙ TP=2 , FP=1 , FN=2
∴ Precision = 2/3
∴ Recall = 2/4
⑨ Confidence임계값을 0.5로 낮추면, Precision과 Recall은 다음과 같다.
∙ TP=3 , FP=2 , FN=1
∴ Precision = 3/5
∴ Recall = 3/4
1.4 ROC / PR-Curve
PR-Curve
위의 PR-Curve에서 알 수 있는 사실은 Precision과 Recall은 서로 반비례 관계를 보인다는 점이다. 이때, PR곡선 아래부분면적이 의미하는 바가 바로 AP(Average Precision)이다. AP는 [0,1]의 범위를 가지며, 1에 가까울수록 좋은 성능을 가짐을 의미한다.
추가적으로, class별로 AP를 구하고, 모든 class에 대한 평균(mean)을 계산한 것이 바로 mAP이다.
ROC-curve
ROC Curve는 양성 클래스와 음성 클래스의 비율이 균형적일 때 성능을 평가하는 데 유용하다. 즉, 클래스 불균형이 낮을 때, ROC Curve는 민감도와 특이도의 trade-off를 측정하여 모델의 성능을 평가한다. 좀 더 자세한 설명은 아래 필기로 대체한다.
2. Traditional Detection Method
Detection의 초기연구는 사람얼굴에 국한되어 진행되어왔다. PASCAL VOC대회 시작 이후, 여러 class로 확장되어 연구가 진행되어왔다. [Everingham2010]
Object Detection은 물체의 위치와 class를 모두 알아내야 해결이 가능한데, 어떤 물체가 어디에 있는지 한번에 알아내기 어렵다. 따라서 가능성이 있는 후보영역을 많이 생성하고, 영역을 classification algorithm으로 걸러내는 two-stage 접근방법을 주로 사용해왔다. 여기서 주의할 점은, two-stage 접근방법을 제대로 구현하려면 "후보영역을 가급적 적게 생성"하고, "실제 물체를 놓치지 않아야하며", "후보영역을 높은 정확률로 분류"할 수 있어야 한다.
HOG
Viola Algorithm. with. HOG(Histogram Of Gradients) 2004년, 성공적인 얼굴검출방법으로 Viola Algorithm이 있다. 여기서, Dalal은 HOG Feature Extraction을 제안하였다. 아래는 Dalal은 HOG Feature Extraction을 간단히 설명한 그림이다.
좀 더 자세한 사례로 예시를 들어보자.
먼저 위처럼 후보크기를 128×64로 변환한다. 이후 이 영역을 8×8크기로 나누면, 16×8개의 타일이 생성된다. 이후 각 타일에서 특징을 추출한다.
타일에 있는 64개의 화소에 각 수평방향과 수직방향의 edge연산자를 적용해 gradient방향을 계산하고 9개의 구간을 양자화한다. 이후, 양자화된 gradient방향으로 histogram을 구하면 9차원 feature vector가 된다. 이때, 명암변화에 둔감히 하기 위해 feature vector를 정규화한다. 정규화과정에서 4개타일의 특징벡터를 이어붙여 36차원의 벡터를 생성하고, 36개요소의 제곱을 합하면 1이 되도록 한다.
이때, 4개타일=window라 하는데, 가로방향으로 7번, 세로방향으로 15번 이동한다. (sliding_window방식) 결국 7×15×36 = 3780차원의 특징벡터를 얻는데, 이를 HOG Feature라 한다.
이후 HOG Feature를 SVM에 입력해 사람일 확률을 출력한다.
DPM
DPM (Deformable Part Model) 이후 등장한 DPM은 파트를 이용해 물체를 모델링한다. 그렇기에 part-based model로 불리기도 한다.
Object는 자세와 모양이 심하게 변하기에, DPM은 이런 특성을 반영하기위해 물체를 몇개의 부품으로 모델링한다.
위의 그림은 5개 part로 모델링을 한다. ∙ 좌측은 물체전체 ∙ 중앙은 5개의 part ∙ 우측은 part가 발생할 위치에 대한 확률분포 이때, Feature Extraction으로는 HOG를 사용한다.
또한, DNN도입 이전이기에
Detection Model은 위의 그림처럼 학습으로 알아낸다.
3. R-CNN 계열 (RCNN, Fast R-CNN, Faster R-CNN)
3.1 R-CNN
R-CNN은 후보영역을 생성하는단계와 후보영역을 분류하는 단계로 구성된다 [Girshick 2014]. R-CNN은 후보영역을 영역제안[Region Proposal]이라한다.
2-stage를 순차적으로 처리하기에 RCNN계열방법들을 2-stage방법이라 부른다. 아래 그림은 영역제안과 영역분류의 2-stage를 거치는 RCNN처리과정이다.
∙ 영역제안과정
물체가 있을 가능성이 높은 영역을 찾는단계. RCNN은 Selective Search Algorithm으로 image에서 2000여개의 후보영역을 생성한다. Selective Search는 image를 super pixel로 분할 후, clustering과정으로 영역을 생성. 생성된 영역을 227×227크기로 정규화하고, CNN에 입력해 4096차원의 특징벡터를 추출한다.
Pascal VOC는 20개 class가 있으므로 21개 SVM이 각 클래스확률을 계산해 그림처럼 맨 오른쪽에 있는 클래스확률벡터를 출력한다. cf) 21번째 SVM은 물체가 아닌 클래스를 의미.
최종적으로 2000여개 후보영역에 대해 위치와 클래스정보를 확보한 후, 21번 클래스를 버리고 나머지에대해 후처리를 거쳐 위치와 클래스를 최종적으로 출력한다.
즉, "Selective Search알고리즘 → RoI 생성 → CNN으로 특징벡터 추출→ SVM" 순이다. 다만, RCNN은 분류에 SVM을 사용하고 영역제안을 위해 고전방법을 사용하는 등 속도가 느리다는 결정적 단점이 있다. 이로인해 RCNN의 한계를 극복하는 fast RCNN과 faster RCNN이 등장했다.
input image를 Conv에 통과시켜Conv특징맵을 얻는다. Conv특징맵에서후보영역에 해당하는곳을 RoI(Region Of Interest)로 지정하는,RoI투영을 진행한다. 그림에서 좌측선수에 해당하는 RoI가 노란색인데,RoI에 RoI풀링층을 적용해 고정크기맵(녹색 7×7맵)을 출력한다.
∙ RoI 특징벡터추출
이 특징맵을 2개의 FC층을 통과시켜 4096차원의 RoI특징벡터로 변환한다. RoI특징벡터는 2갈래로 나뉜다.
∙ 분류 및 회귀과정을 모든 RoI에 적용
한곳은 분류를 담당하는 FC층을 통과, 클래스확률벡터를 출력하고 한곳은 회귀를 담당하는 FC층을 통과, 클래스별 박스정보(x,y,h,w)가 된다.
즉,"RoI투영 → RoI 특징벡터추출 → 분류 및 회귀과정을 모든 RoI에 적용"한다. 물체없음으로 판정된 RoI는 버리고, 나머지는 후처리 후 박스정보와 클래스정보를 최종 Detection결과로 출력한다.
Fast-RCNN은 박스정보를 알아내는 회귀와 클래스를 알아내는 classification을 동시에 수행하기 때문에 하나의 Loss function으로 두 task를 달성해야한다. ∙ 손실함수:J=Jclassification+λ∙Jregression형식 이런 손실함수를 다중과업손실함수(Multi-task Loss function)라 한다. λ는두 task의 비중을 결정하는 hyper-parameter로 논문에서는 1로 설정했다.
다만, 여전히 영역제안단계에서 고전알고리즘(Selective Search)을 사용하기에 한장의 이미지처리에 CPU로 2초가량 걸린다 알려져있다.
3.3 Faster-RCNN
아래그림은 Faster-RCNN의 처리과정으로 Fast-RCNN에 비해 정확도와 속도를 획기적으로 개선하였다 [Ren 2015]. 오직 CNN신경망으로만 Object Detection을 수행하는 지평을 열어버렸기에 매우 기념비적이라 할 수 있다. ∙ 영역제안단계: 영역제안모듈, RPN(Region Proposal Network)신경망 사용. ∙ 영역분류단계: Fast R-CNN 사용.
∙ RPN
Pre-Trained VGG16을 앞에 배치해 특징맵을 추출(노란색 H×W맵)한다. RPN은 이 특징맵의 각 pixel에서 3×3 filter로 512차원의 특징벡터를 추출한다.
이 특징맵에 서로 다른 2개의 1×1 convolution을 적용해 6개의 값들을 추출한다. ∙ 물체여부를 나타내는 2개의 값 ∙박스정보를 나타내는 4개의 값.
위의 연산을 9번 적용해 크기와 가로세로비율이 다른 9개의 박스 (= Anchor)를 생성. Anchor: 여러크기의 물체를 표현하는 Anchor를 생성함으로써 다중크기의 물체탐지능력을 갖춘다.
결과적으로 H×W의 pixel마다 9개의 Anchor가 생성되므로 H×W×9개의 Anchor가 생성된다. 여기서 NMS를 적용해 2,000여개의 Anchor만 남긴다.
즉, CNN으로 특징맵 추출 → 1×1 conv로 6개값 추출 9회 진행 → Anchor Box생성 순이다.
∙ Fast R-CNN
이 Anchor들을 RoI으로 간주해 위 그림의 신경망의 뒷부분에 있는 Fast-RCNN으로 입력한다. Fast-RCNN은 후보영역 각각에 대해 RoI투영 → RoI 특징벡터추출 → 분류 및 회귀과정을 적용한다.
물체없음으로 판정된 후보영역은 버리고, 나머지 후처리 후, 박스정보와 클래스정보를 최종 Detection결과로 출력한다.
4. YOLO 계열
YOLO는 RCNN계열에 비해 정확도는 떨어지나 속도가 월등히 빠른 장점이 있다. (물론, 이도 옛날얘기로 최근에는 YOLOv8, YOLOX계열 등으로 충분히 RCNN을 뛰어넘는 성능을 보이고 있으며, 정확도가 높은 모델을 필요로 하는 경우, InternImage나 DETR계열을 사용한다.)
2016년 최초 발표된 YOLO v1은 Titan X GPU에서 45FPS를 처리한다.[Redmon2016] YOLO는 물체의 위치와 클래스정보를 Regression으로 한번에 알아내는, End-to-End방식을 고수한다.
YOLO v1의 특징
image를 s×s격자로 나눈다. (실제 구현은 아래그림의 노란격자처럼 s=7로 설정해 총 49개의 칸이 존재한다; 빨간박스는 dataset에 라벨링된 참값이다.)
아래그림에서 검은칸을 예로들어 90차원의 벡터로 표현해보자. 빨간색의 좌측선수를 표시한 빨간박스의 중심은 검은칸에 놓이기에 검은칸이 이 박스를 책임진다. 벡터는 90차원인데 앞의 5개요소(x1, y1, w1, h1, o1)는 이 박스의 위치와 크기, 신뢰도를 의미한다.
박스의 위치와 크기는 영상좌표계를 [0,1]사이로 정규화하고 정규화좌표를 중심으로 표현한다. x2,y2,w2,h2,o2는 또다른 박스를 표현할 수 있기에 한칸은 박스를 2개까지 책임질 수 있다.
p0~p80은 해당박스가 어떤객체클래스에 속하는지 나타내는 one-hot코드이다. YOLO가 물체의 위치와 클래스를 표현하는 방식 YOLO는 RCNN계열에 비해 상당히 단순한데, 아래 그림은 YOLO가 사용하는 CNN의 구조이다. ∙ Conv층: 24개 / MaxPool층: 4개 / FC층: 2개 로 구성되며 - input은 448×448크기로 변환되어 입력되고 - output은 7×7×90의 출력텐서를 갖는다. YOLO가 사용하는 Convolution신경망 구조
위 그림에서 신경망은 image를 입력으로 받아 7×7×90의 출력텐서를 참값으로 주어 통째로 학습한다.
참값텐서에 [float으로 표시되는 Bbox정보], [OneHot코드로 표현되는 클래스정보]가 섞여있기에 classification과 regression이 동시에 일어난다.
YOLO의 Loss function
YOLO의 Loss function은 5개의 항으로 구성된 조금 복잡한 식을 갖는다. ∙ 1, 2항은 각 박스의 위치오류와 크기오류를 측정하는 Regression Loss이다. ∙ 3항은 물체가 있지만 없다고한FN오류를 측정하는 Confidence Loss이고, ∙ 4항은 물체가 없지만 있다고한FP오류를 측정하는 Confidence Loss이다. ∙ 5항은 class를 나타내는 OneHot코드의 오류를 측정하는 Classification Loss이다.
YOLO v3
YOLO v3는 여러 scale을 표현해 다양한 크기의 물체를 탐지하는 능력이 향상되었다 [Redmon 2018]. YOLO v3은 (object, class)의 85차원 벡터를 추출하는 층을 신경망 3곳에 배치한다. ∙ yolo_82층에서는 14×14격자로 나눠 14×14×85×3텐서를 출력한다. 따라서 14×14의 각 요소는 박스를 3개까지 출력한다. ∙ yolo_94층에서는 28×28격자로 나눠 28×28×85×3텐서를 출력한다. ∙ yolo_106층에서는 56×56격자로 나눠 56×56×85×3텐서를 출력한다.
이 층들이 출력한 텐서를 객체정보로 변환하면, 다양한 크기의 객체를 탐지할 수 있다.
5. Transformer : DETR , SETR
고안 배경)
Image에서 객체를 탐지하는 신경망은 여러 Bbox를 예측해야해서 집합예측모델이라 할 수 있다. 모델의 예측과 정답에 해당하는 라벨이 모두 Box집합이기에 Hungarian Algorithm으로 최적의 매칭쌍을 알아내 손실함수를 계산한다. 고전방법과 딥러닝 모두 후보영역을 충분히 많이 생성한 후, 후보영역 각각에 대해 어떤 물체인지 분류하는 접근방법을 사용한다. 이후, 여러 Bbox가 중복검출되는 현상이 발생하면, 중복해소를 위해 비최대억제(NMS)로 후처리를 적용한다. 고안 배경)Transformer를 사용하면, ∙ 후보영역(RoI)을 생성하는 중간단계없이 Box집합을 직접예측할 수 있을까? ∙ 중복현상이 아예 일어나지 않게 할 수 있을까? ∙ Convolution기반의 Faster-RCNN이나 YOLO보다 좋은 성능을 얻을 수 없을까? CNN은 유연하기에 Faster-RCNN과 YOLO v3의 구조를 자유자재로 설계가능하였다.
하지만 Transformer는 다소 고정적인데, 이유는 아래와 같다. ∙ T × dmodel 크기의 tensor가 여러 encoder블록과 decoder블록을 흐르며 연산이 진행 Encoder만 사용되는 ViT와 달리(https://chan4im.tistory.com/163) DETR는 영상을 입력으로 박스집합을 출력해야하기에 Encoder와 Decoder 모두 사용한다. Decoder에 붙은 출력층은 T × dmodel tensor를 Box집합으로 변환해야한다.
손실함수는 Transformer가 예측한 Box집합과 label박스집합이 일치하는 정도를 측정하는 능력을 가져야한다. Box는 직사각형을 표현하는 4개의 좌표(coordinate)와 물체 클래스를 나타내는 Class확률벡터(softmax)로 표현된다.
5.1 DETR (DEtection TRansformer)
Faster-RCNN같은 CNN기반 신경망은 Box집합을 바로 예측하기 어렵기에 RoI를 생성 후, 영역을 분류하는 일종의 우회하는 방식을 사용한다. 즉, 기존문제를 대리문제로 바꾸고 대리문제를 푸는 셈이라 볼 수 있다. [Carion 2020]은 transformer를 이용해 집합예측을 하는 DETR모델을 제안한다.
DETR은 RoI생성단계가 없고, NMS라는 후처리단계가 없다. 즉, End-to-End 학습이 가능하다.
위의 그림은 DETR모델구조로 DETR은 ①~③로 표시한 3가지 모듈로 구성된다.
∙모듈①
CNN을 통해 Feature Extraction을 진행. 또한, 1×1 convolution을 적용해 channel을 C에서 dmodel로 줄여 h×w×dmodel의 tensor로 변환한다. 이후 Flatten으로 pixel을 이어붙여 행에 배치한 hw×dmodel행렬을 얻는다. 위 그림에서는 hw를T로 표기하는데, 이는 최종적으로 transformer의 input으로 입력할T×dmodel행렬을 얻음을 의미한다.
이 행렬의 각 행은 축소된 image의 pixel에 해당하며, Self-Attention계산 시 행이 Query로 참여하기에 축소된 pixel(= patch)간의 attention정보를 추출하는 셈이다. 즉, DETR은 Self-Attention을 반영한다 볼 수 있다.
∙모듈 ②
Encoder-Decoder로 구성된 Transformer로 모듈 ①에서 입력된 T×dmodel행렬에 Position Encoding을 적용해 Encoder블록1에 입력한다.
Encoder블록1, ... , Encoder블록M을 통해 변환된 행렬은
Decoder의 MHA에 입력되어 Key와 Value의 역할을 한다.
Decoder를 좀 더 살펴보자.
기존 Transformer에서는 Decoder가 Auto-Regressive방식으로 작동한다. 즉, NLP에서 <SOS>토큰을 주면 첫번째 단어가 생성되고 <SOS>토큰과 첫번째 단어를 주면 두번째 단어가 생성된다. 이런 AR방식을 객체탐지에 적용할 수 있을까?? → ❌ (Bbox는 순서없이 집합으로만 표현하기 때문.)
Decoder 입력을 보면 object queries라 표시된K개 벡터가 있다. K×dmodel크기의 행렬이 입력된다는 의미로K는 탐지가능한 물체의 최대개수이다. 출력층은물체가 아닌경우,∅를 출력할 수 있기에가변개수의 객체탐지가 가능하다.
그림의 예시에서는 2개의 박스와 3개의∅를 출력했다. Decoder의 최초 입력인 object queries는 Box에 대한 아무런 정보❌ Position Encoding,P를 갖고 출발해야하는데, DETR은 학습을 통해 알아낸P를 사용한다.
∙ 모듈③
Decoder블록이 출력한K×dmodel행렬의 각 행을Feed-Foward에 통과시켜 박스정보로 변환한다. 이렇게 모델이 예측한 박스집합을ŷ라 하고 정답에 해당하는 Ground_Truth Box집합을 y라 하자.
y에 ∅박스를 추가해 ŷ처럼 K개 박스를 갖게 한다. ŷ과 y에 Hungarian Algorithm을 사용해 최적매칭쌍을 구한다.
📌 Loss Function 매칭된 참값박스 i와 예측박스 j쌍을 이용해 아래 처럼 손실함수를 정의한다.
첫번째 항은 class를 맞췄는지 측정한다. (p̂j(ci)는 class확률벡터에서 참값class에 해당하는 확률.) 두번째, 세번째 항은 물체위치를 얼마나 정확히 맞혔는지 측정한다. (2번째항: IoU ; 3번째항: L1 Distance)
Self-Attention Matrix식 = softmax(QKT/√dkey). 이 행렬은 image를 구성하는 여러 Q벡터가 상호주목하는 정도를 표현.
위의 그림에서 주황색 표시된 코끼리의 경우, 코와 발, 등, 꼬리에 주목하고 있는데, 이는Bbox의 경계에 주목하고 있다는 사실을 확인할 수 있다.
이 사실을 바탕으로Decoder의 역할을 추론해보면, Decoder는 Bbox를 제대로 알아내기위해Self-Attention Matrix를 통해 물체의 상하좌우 경계에 주목한다고 할 수 있다.
5.2 SETR(SEgmentation TRansformer)
DETR는 Object Detection의 목적으로 고안되었다. 이때, Transformer의 특성으로인해 분할을 할 수 있도록 쉽게 확장할 수 있다. DETR Architecture위의 DETR모델의 모듈 ③은 출력행렬을 해석해 Box정보로 변환하는, Detection용도의 Head이다. 따라서, Segmentation용도의 Head를 붙이면, 분할용도의 Transformer모델인, SETR이 된다. 즉, 요약하면 SETR은Encoder(Transformer) - Decoder(CNN)의 구조를 띈다. Segmentation Head는 축소된 해상도를 원래 해상도로 복구하기위해 UpSampling을 위한 Convolution층이 포함된다. SETR Architecture(a). 먼저 image(m×n×3)를 고정된 크기의 patch로 나누고 각 patch를 선형 임베딩한 다음 Position Embedding을 추가한 후, 결과 벡터 시퀀스를 표준 트랜스포머 인코더에 공급한다. (이때, 픽셀 단위 분할을 수행하기 위해 다양한 디코더를 도입한다)
(b) Decoder는 점진적 UpSampling(resulting in a variant called SETRPUP)으로 여러 단계의 Convolution층을 쌓아 피라미드 형태로 쌓은 Decoder를 제안한다.
(c) multi-level feature aggregation (a variant called SETR-MLA).
6. Backbone Transformer : Swin Transformer
6.1 Backbone Transformer
CNN transfer learning은 DNN의 큰 이점이다. 보통 전이학습(transfer learning)에 널리 사용되는 Backbone model로는 VGG, GoogLeNet, ResNet, DenseNet121 등이 있었으며, 최근에는 EfficientNet 등이 있다.
Backbone model은 주로 input data에서 feature map을 추출하는 역할을 한다. 주로 pretrained model을 사용하며, 다양한구조(CNNs, Transformers, ResNets)를 사용할 수 있다.
기존 NLP에서 Transformer가 사용이 되었기에(GPT, BERT), 초반에는 transformer도 transfer learning을 위한 Backbone model로 쓸 수 있을까?라는 의문에서 출발했다.
지역정보를 추출하는 Convolution연산에 의존하는 CNN에 비해 Self-Attention에 의존하는 Transformer가 Transfer Learning에 훨씬 유리하다는 실험적 입증이 많이 발표되었는데, Backbone으로 쓸 수 있는 Vision Transformer를 제작할 수 없을까? 라는 의문에서 Swin Transformer로 답을 해준다. Backbone이 되려면 image의 feature를 충분히 반영한 구조를 설계해야한다. 기존 transformer는 문장처리목적으로 설계되었기에, 조금의 변형이 필요하다. Backbone모델이 되려면 아래의 특성들을 잘 반영해 처리할 수 있어야 한다. (문장을 구성하는 단어는 scale변화가 없으나 image를 구성하는 Object는 아주 다양한 크기로 나타나기에 scale변화가 심한편.) (또한, 한 문장을 구성하는 단어는 수십∙수백개에 불과하지만, image를 구성하는 pixel은 수만~수백만 개이다.) (문장의 단어는 띄어쓰기로 잘 분할되어있지만, image는 Object끼리 혹은 배경이 심하게 섞여있다.)
6.2 Hierarchical Feature map. &. Shifted Window
Swin Transformer는 image특성을 반영하기위한 핵심아이디어를 2가지로 설명한다.
∙Hierarchical ViT
아래 그림(a)은 Hierarchical ViT(= Hierarchical Featuremap)을 사용해 객체의 scale변환에 대응하는 방법을 설명한다. 모든 window는 M×M개의 patch로 구성된다. (여기서 M=4) 맨 아래층은 작은 patch_size로 window가 4×4개가 있다. 가운데 층은 patch_size가 2배로 커져 2×2개의 window가 있고, 맨 윗층은 1개의 window가 있다. 이렇게 작은 patch부터 큰 patch로 구분해 처리하면, 여러 크기의 객체를 분류하거나 탐지할 수 있다.
그림 (b)의 ViT의 경우, 영상을 분류하는데 사용할 수는 있지만 객체탐지 및 분할에는 한계가 있다.
계층적 특징맵은 계산효율상에도 큰 이점이 존재한다.
단일해상도를 사용하는 ViT의 경우) 224×224 image를 16×16 patch(= 14×14개)로 나눈다 가정하자. 이 경우,T= 196인 행렬이 입력되는데, MHA는T개 patch끼리 Self-Attention을 계산하기에 T2번 연산을 수행한다. 이때, 연산은 QKT의 행렬곱으로 이뤄진다. Q와 K가T×dkey행렬이므로 T2×dkey만큼 곱셈이 수행된다.
다중해상도를 사용하는 Swin의 경우) window별로 self-attention을 적용한다. window는 M×M개의 patch로 구성되기에 한 window는 M2×dkey만큼 곱셈을 수행한다.
즉, ViT에비해(T×T) / (M×M×window개수)배빠르게 계산된다. 예를 들면 그림(a)의 맨 아래층에서는 window가 16개이므로 49배 빠르다.
∙Shifted Window
Swin Transformer의 이름이ShiftedWINdow에서 유래되었을 정도로 핵심아이디어이다. ℓ번째 layer에서 이전처럼 window를 나누는데, 그 다음 ℓ+1층에서는 window를 절반크기만큼 수평과 수직방향으로 이동해 나눈다.
shifted window를 사용하면 window간의 연결성강화 및 다양한 크기의 객체를 처리할 수 있고, 객체의 상대적인 위치정보를 저장하는 등 이를 통한 성능향상이 가능하다.
6.3 Swin Transformer Architecture
아래그림은 Swin Transformer의 구조이다. 좌측에서 우측으로 흐르는 단계 1~4는 좌측그림의 (a)의 아래에서 위로 진행하며 patch는 커지고 window개수는 작아지는 방향에 해당한다.
위 그림의 (a)는 이런 tensor변환을 어떻게 수행하는지 설명한다.
단계 2에서 patch합치기 적용시, 맨 아래층에서 맨 위층으로 진행하는 과정에 해당하는 것으로 단순히 이웃한 4개 patch를 하나의 patch로 합치는 과정을 의미한다.
모든 단계를 거쳐 얻은 특징맵에 classification을 위한 head를 붙이면 classifier가 되고, Detection을 위한 head를 붙이면 detector가, Segmentation을 위한 head를 붙이면 segmentor가 된다. 이런 방식으로 Swin Transformer는 Backbone 모델로 작용한다.
이제 단계 1~4에 노랜색 표시된 Swin Transformer Block의 동작을 그림 (b)를 통해 살펴보자. (b)는 Encoder Block을 2개 쌓은 상황으로 현재 Block ℓ은 ℓ-1번째 Block에서 xℓ-1 tensor를 받아 Layer Normalization을 거쳐 W-MHSA층으로 Self-Attention을 적용한다. 이후, Add와 Norm, FF, Add를 적용해 xℓ을 출력한다.
ℓ+1번째 Block은 xℓ을 입력으로 받아 같은 과정을 거쳐 xℓ+1 tensor를 출력한다. ℓ Block과 ℓ+1 Block의 Self-Attention을 W-MHA, SW-MHA로 표기했다. W-MHA는 window를 분할하고 SW-MHA는 Shifted Window로 분할한다.
Backbone모델로써의 Swin Transformer
Swin Transformer는 Backbone으로 쓰이는 CNN인 ResNet등과 호환되도록 tensor모양을 설정했기에 기존 딥러닝모델에서 CNN-Backbone을 들어내고 Swin-Transformer로 쉽게 대치할 수 있다.
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로 구현한다면 더 좋은 결과를 얻을수도 있다. 이를 기반으로 다른 모델들을 참고한다면, 긴문장이나 어려운 텍스트에서도 더 높은 성능을 낼 수 있을 것이다.
🤔Algorithm 과정 1. s와 string 리스트에 입력에 해당하는 각각의 문자열을 넣음 2. for문으로 string을 돌면서 string에 있는 문자열과 일치하는 단어가 s에 있다면? 3. cnt값 1 증가 (= 일치하는 문자열이 있다는 것) 4. 최종적으로 cnt값 출력
🤫solution_14425
N, M = map(int, input().split())
s = [input() for _ in range(N)]
string = [input() for _ in range(M)]
cnt = 0
for i in string:
if i in s:
cnt += 1
print(cnt)
🧐 백준 10815, 10816(이진탐색)
🤔Algorithm 과정 1. 중복되어 입력되어도 비교만 하면 되기에 n이라는 set과 m이라는 리스트를 생성 2. 이후 m안의 원소를 돌면서 만약 m의 원소가 n에 있다면 1을 출력, 아니면 0을 출력해주면 된다. 3. 물론 위의 경우 m 리스트의 원소에 순서대로 접근하기 때문에 순서를 상관쓰지 않아도 된다.
🤫solution_10815
# cf. n을 list로 했더니 시간초과가 났음.
# 즉, 중복된 결과가 들어가게 되어 set보다 시간복잡도가 더 걸리게 되는 것.
N, n = input(), set(map(int, input().split()))
M, m = input(), list(map(int, input().split()))
m_set = list(set(m))
for i in m:
print(1, end = " ") if i in n else print(0, end = " ")
# 리스트를 실제로 분할해서 새로 저장하는 것은 O(N)으로 매우 무거운 연산
🤫해결의 실마리(10816): 이진탐색
🤔 count 함수를 무턱대고 쓰면 안된다?? count함수는 시간복잡도가 O(n)시간이 걸려서 for문과 같이 쓰면 시간초과가 발생할 확률이 높다.
🤔Algorithm 과정 1. cnt = {}로 딕셔너리를 생성한다. 2. cnt라는 비어있는 딕셔너리에 i 즉, n의 원소가 없다면 cnt[i] = 1로 원소와 개수를 맵핑 3. 만약 i in cnt라면 원소의 개수를 증가시켜줘야 하므로 cnt[i] += 1을 통해 value(원소의 개수)를 증가 4. 이후 m 안의 어떤 원소 i에 대해 cnt에 i가 있으면 value를 출력, 없으면 0을 출력한다.
🤫solution_10816(시간초과 ∵ count함수의 사용)
N, n = int(input()), list(map(int, input().split()))
M, m = int(input()), list(map(int, input().split()))
for i in m:
print(n.count(i), end = " ") if i in n else print(0, end = " ")
🤫solution_10816
N, n = int(input()), list(map(int, input().split()))
M, m = int(input()), list(map(int, input().split()))
cnt = {}
for i in n:
if i in cnt:
cnt[i] += 1
else:
cnt[i] = 1
# 딕셔너리 생성
# print(cnt) => {6: 1, 3: 2, 2: 1, 10: 3, -10: 2, 7: 1}
for i in m:
if i in cnt:
print(cnt[i], end = " ")
else:
print(0, end = " ")
🧐 백준 11478
🤔사실 문제에서 말하는 바는 등수를 출력하는 것과 동일! 🤔Algorithm 과정 1. s에 바로 문자열을 입력받는다. 이때, s에 "abcde"라는 문자열이 들어왔을때, s[1:3]으로 bc에 접근할 수 있다.]
2. set_s = set()를 통한 set을 생성해주고 3. 이중 for문에서 위의 인덱스 슬라이싱원리를 이용해 부분문자열을 구한다. 4. 이때, set_s에 넣어주는데, 중복된 문자열은 추가되지 않는다.
🤫solution_11478
s = input()
# print(s[1:3]) ba출력
set_s = set()
# 이중 for문을 돌면서 부분 문자열을 구하고 set_s에추가한다.
# 이때, set_s는 집합이기 때문에 중복된 문자열을 추가되지 않는다.
for i in range(len(s)):
for j in range(i, len(s)):
set_s.add(s[i:j+1])
print(len(set_s))
※vector(std::vector) _가변배열 / 가장 기본이 되는 컨테이너 (★★★★★)
#include <vector>
using namespace std;
vector<자료형> 변수명(숫자) //숫자만큼 벡터 생성 후 0으로 초기화
vector<자료형> 변수명(숫자, 변수1); //숫자만큼 벡터 생성 후 변수1으로 모든 원소 초기화
vector<자료형> 변수명{숫자, 변수1, 변수2, 변수3, ...}; // 벡터 생성 후 오른쪽 변수 값으로 초기화
vector<자료형> 변수명[]={ {변수1, 변수2}, {변수3, 변수4}, ...} //2차원 벡터생성 (열은 고정, 행 가변)
vector<vector <자료형>> 변수명 //2차원 벡터생성 (열, 행 가변)
ex);
vector<int> vec1; // 크기가 0인 벡터 선언
vector<int> vec2(10); // 크기가 10인 벡터 선언
vector<int> vec3(10, 3); // 크기가 10이고 모든 원소가 3으로 초기화된 벡터
vector<int> vec4 = { 1,2,3,4,5 }; // 크기가 지정한 초기값으로 이루어진 벡터
vector<int> vec5[] = { {1,2},{3,4} }; // 벡터 배열 생성(행은 가변인지만, 열은 고정)
vector<vector<int>> vec6; // 2차원 벡터 생성(행과 열 모두 가변)
- set은 연관 컨테이너로 삽입, 삭제, 검색의 시간복잡도가O(logn) 인 Binary Search Tree로 구현되어 있다.
- key라는 원소들의 "집합"으로 key값은 중복되지 않는다!
- insert()를 통한 자동적으로 오름차순 정렬이 가능하다.
∴중복을 피하면서 정렬까지 사용할 때 매우 유용하다!
insert(k): 원소 k 삽입 begin(): 맨 첫번째 원소를 가리키는 iterator를 반환 end():맨 마지막 원소를 가리키는 iterator를 반환 find(k): 원소 k를 가리키는 iterator를 반환 size(): set의 원소 수 empty():비어있는지 확인
※algorithm
※ STL 알고리즘의 분류
find()는 2개의 입력 반복자로 지정된 범위에서 특정 값을 가지는 첫 번째 요소를 가리키는 입력 반복자를 반환
for_each()는 2개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입한 후, 대입한 함수 객체를 반환
copy()는 2개의 입력 반복자로 지정된 범위의 모든 요소를 출력 반복자가 가리키는 위치에 복사
swap()은 2개의 참조가 가리키는 위치의 값을 서로 교환
transform()은 2개의 입력 반복자로 지정된 범위의 모든 요소를 함수 객체에 대입후, 출력 반복자가 가리키는 위치에 복사
sort()는 2개의 임의 접근 반복자로 지정된 범위의 모든 요소를 비교, 오름차순정렬.
stable_sort()는 2개의 임의 접근 반복자로 지정된 범위의 모든 요소를 비교, 값이 같은 요소들의 상대적인 순서는 유지, 오름차순으로 정렬합니다.
binary_sort()는 정렬되어있는 경우(오름차순)에 한해서 탐색효율이 매우 좋고 적은 시간에 소요된다.
accumulate()는 두 개의 입력 반복자로 지정된 범위의 모든 요소의 합을 반환합니다.
※ 벡터의 오름차순과 내림차순 정렬 (feat. greater<int> 키워드)
§ sort() 함수 형식
단, custom_func()은 0 또는 1이 나오도록 해야해서 보통 bool형 함수를 많이 넣는다.
