이기문. 이 책의 저자이다. 기업 경영에 관심이 있는 나로서, 전 세계 10억 유저가 열광한 배틀그라운드가 있기까지 10년 간 크래프톤이 겪은 질곡과 인고의 시간을 한 권의 책으로 볼 수 있게 해준 저자의 노고에 매우 감사한 마음이 들었다.
기업 경영을 하게 되면 실제로 발생할 문제 상황과 고통들을 여실히 목도할 수 있는 책이다. 이 책을 읽기 전엔 뭣 모르고 시작해도 뭐라도 하니까 어떻게 되겠지 하는 생각이 있었다. 하지만 기실은 절대 그렇지 않다는 것을 느끼게 해주었다. 경영진의 번민과, 사무침과, 방향성에 대한 끝없는 천착과, 이로 말미암은 수 많은 갈등의 배태를 보며 결코 사업에 대한 가벼운 희구나 간절함으론 사업을 영위할 수 없겠다는 것을 느꼈다.
책을 읽는 내내 경영진의 더 나은 의사결정을 위한 끝 없는 사유와 원활한 커뮤니케이션 능력을 보면서 경외심도 느꼈다. 동시에, 더 이상 좋을 수 없어 보이는 커뮤니케이션 능력으로도 상호 갈등이 좁혀지지 않는 것을 보면서, 원하는 바 쟁취를 위해 기치를 내세우고 투쟁하며 썩은 고통의 구덩이에서 몸부림 쳐야한다는 것도 느꼈다. 눈 앞에서 당장 백 보 후퇴할 것 같아도 기꺼이 한 보 전진이 가능하다면 으스러진 다리를 끌고 나아가는 모습을 보며 비전 성취에 대한 의심과 믿음, 그리고 기개와 집념을 느낄 수 있었다. 과연 나는 이를 견딜 수 있겠는가 하는 생각도 함께 들었다.
만물에는 양면성이 깃들어 있다고 하였던가, 전 세계 10억이 열광하는 배틀그라운드를 만들기 위해 있었던 10년간의 믿음, 노력, 헌신, 갈구, 배려 뿐만 아니라 불신, 집착, 유린, 힐난, 결기와 같은 이 모든것이 있었기에 만들어질 수 있었다고 본다. 결국 나는 서로 양립 불가능한 가치들의 공존에서 위대한 창조가 일어난다고 느꼈다. 원하는 미래를 만들 수 있다는 믿음에 대한 의심을 하면서도 끝없는 간절함과 확신으로 버텼던 크래프톤 처럼 말이다. 나는 책을 두 번 세 번 읽지 않는 편인데, 이 책은 향후 다시 한 번 읽을 수 밖에 없겠다는 생각이 들었다. 내가 겪었던 것 처럼 체화하고 싶을 뿐만 아니라 경영진의 대화에서 드러나는 높은 사고력과 책 속에 담긴 풍부한 어휘 또한 마음에 들었기 때문이다.
🍎 마음에 남는 대목 “펍지 초기, 김창한이 ‘바람이 부는데, 그 끝이 어딘지 모르겠습니다’라는 표현을 한 적이 있다. 인생을 살아가며 바람을 느끼고 인식하는 순간은 정말 드물다. 바람이 불어도 대부분 바람인지 모른다. 바람이라 인식해도 평소처럼 살아가는 경우도 많다.”
이진 탐색 알고리즘은 탐색 알고리즘 종류 중 하나로, 이름 그대로 절반씩 나누어 원하는 값을 알고리즘이다. 이진 탐색을 위한 전제 조건으로 배열이 오름차순 또는 내림차순으로 정렬되어 있어야 한다. 동작 방식은 간단하다. 배열의 중앙을 기준으로 원하는 값이 작은지 큰지 비교하여 한 쪽을 배제하고 나머지 부분을 반복해서 탐색하는 방식이다.
가령 예를 들어 아래와 같이 찾고자 하는 값이 5일 경우, 배열의 가운데인 4를 기준으로 삼은 다음 오른쪽에 있다는 것을 알 수 있다. 이후 왼쪽 배열 0~4를 배제하고 오른쪽 배열 5~9 부분을 탐색한다. 찾고자 하는 값이 5~9 부분의 중앙인 7을 기준으로 왼쪽에 있으므로 다시 오른쪽 배열을 배제하고 왼쪽 배열 5~7을 탐색한다. 6을 기준으로 왼쪽에 있으므로 오른쪽 7을 배제하고 왼쪽 5를 찾으며 탐색이 완료되는 방식으로 동작한다.
원하는 값을 찾기 위해 배열의 모든 원소를 탐색하는 순차 탐색의 경우 시간복잡도가 $O(n)$이다. 하지만 이진 탐색의 경우 시간복잡도가 이보다 작은 $O(logN)$이 된다는 것이 특징이다. 조금 덧붙이자면 시간복잡도 $O(logN)$는 배열이 정렬되고 고정된 상태에서 가능하다. 만약 배열에 삽입, 제거, 탐색과 같은 연산이 함께 이뤄진다면 시간복잡도가 $O(n)$까지 떨어질 수 있다. 때문에 삽입, 제거, 탐색과 같은 연산이 함께 이뤄지는 경우 이진탐색 트리를 자료구조로서 사용해야 한다. 이진탐색트리의 경우 삽입, 제거, 탐색을 해도 시간복잡도가 $O(logN)$이 보장되는 특징이 있기 때문이다.
이진 탐색 알고리즘 구현은 크게 두 가지 방법이 있다. 첫 번째는 재귀를 사용하지 않는 방식이고, 두 번째는 재귀를 사용하는 방식이다. 두 구현 방법 모두 공통적으로 세 종류의 변수들이 필요하다.
이 논문에서 문제점으로 삼고 있는 것은 dialouge management(이하 DM)을 scalable하고 robust하게 만드는 것이 어렵다는 것임. 그리고 이 논문의 저자가 말하고자 하는 것은 DM을 디자인 관점에서 연구자들에게 향후 연구 방향을 알려주고자 함.
1. Introduction
Conversational System은 크게 두 분류로 나뉨 1. task-oriented system 2. non-task-oriented system 여기서 non-task-oriented는 단순 대화 같이 별도 행위가 필요하지 않은 시스템이고 task-oriented는 예매와 같은 구체적인 태스크를 수행하는 시스템임. 이 논문에선 task-oriented 시스템을 다룸. DM에는 다양한 접근법이 있고, 각각 장단점이 있음.
2. Problem fundamentals and dimensions
A. Dialouge Management
위 그림은 DM의 전체적인 플로우임. DM은 크게 위 아키텍처를 벗어나지 않고 거의 정석으로 사용됨. NLU가 가장 처음으로 유저 발화 정보를 추출함. 크게 3가지로 Intent, entity, dialouge act를 가져옴. 즉 어떤 의도로 말했고, 어떤 것을 말했고, 어떤 행위를 요구하는지를 파악하기 위함임.
intent는 goal/task와 거의 동의어로 사용됨
entity는 slot과 동의어로 봐도 됨. 위 그림 1을 예로 들자면 departure_city나 destination_city가 entity가 됨.
dialouge act는 유저가 단순 서술인지, 질문인지, 요청인지 파악하기 위해 사용됨
그리고 이 모든 정보는 Dialouge State Tracking(이하 DST)에게 전달함. 그리고 DST는 NLU에서 받은 구조적 representation을 저장해둠. 어떻게 대답할지 결정하기 위해. 다른 말로 표현하면 Dialouge State(이하 DS) 유지를 위해 명시적이거나 암시적인 정보까지 전부 저장해둠
그리고 DS에 기반해서 다음 행동은 Dialogue Policy(이하 DP)가 결정함. DP는 일종의 함수로 봐도 됨. DS에 기반해서 행동(Dialouge Act)을 매핑시켜주기 때문에. (일종의 if else와 같이 룰 베이스 형식인듯. NLU에서 처리한 Dialouge Act를 DP에서 받아서 실행시켜주는 방식인듯). 예를 들면 flight-booking이라는 domain에선 action이 크게 4가지로 제한됨. Request, Confirm, Query, Execute. 만약 Request라면 출발 시간과 도착 시간을 물어봐야하고, Confirm이라면 도착 위치가 여기가 맞는지 물어봐야하고, Query라면 항공편 리스트를 가져와야하고, Execute라면 예약 신청해야 함. 이러한 DP 동작의 결과를 NLG가 적절한 응답으로 생성함.
DM 시스템은 이렇게 동작하지만 산학계에서 제안 된 다양한 아키텍처들이 있음. 제시한건 NLU, DST, DP, NLG지만 하나로 합쳐진 것도 있고 그럼.
B. Analysis Dimension
크게 4가지 차원에서 구체적으로 설명함
DS: 어떻게 DS가 representation되고, 어떤 정보가 포함되고, 수작업인지 데이터로 학습하는지 설명
DST: DS가 결정되는 과정을 설명
DP: 다음 action이 어떻게 결정되는지 설명
Context support: 유저 의도를 파악하고 적절한 답을 주기 위해, 크게 3가지를 활용함 Converstional history, User profile, External knowledge
3. DM 접근법
DM 방식에는 크게 3가지가 존재함 1. 수작업 2. data-driven 3. 혼합
3.1 Hand-crafted
Rule-based
Rule-based 방식은 가장 초기에 나온 방식으로 한 번에 NLU, DM, NLG 태스크를 수행하는 방식임. AIML(AI Markup Language)라는 개념이 있음. 이건 크게 두 개념으로 구성되는데 1. 카테고리 2. 주제로 구성됨. 명확히 이해는 안되지만 이 논문에선 챗봇으로 예를 들었는데 사용자가 Hi robot이라 입력해야 대화가 시작되고 Hi robot에 대한 답변이 이미 정해져 있어 Hi human이란 답을 하는 방식이라고 함. 아무튼 이 방식의 특징은 당연히 DST와 DP의 역할이 거의? 없다는 것. 바로 NLU 한 다음 NLG를 함. 결론적으로 수 많은 패턴이 있어야 하기 때문에 간단한 태스크 조차 쉽지 않고, 패턴간 중복이나 충돌이 발생해서 이걸 처리하는 비용이 들기 때문에 비효율적이다. (고비용 & 스케일업 어려움)
이런 비효율적인 Rule-based를 보완하기 위해서 DS와 DP가 필요했음. 왜냐면 rule-based는 보통 바로 이전 발화만 저장했는데, 정교하게 만들기 위해 이전 발화 모두를 저장해서 활용할 필요가 생겼고 또 사용자 맞춤을 위해 user-profile 정보가 필요했음. 이런 발화 정보와 유저 프로필과 같은 대화에 도움을 주는 것을 context support라 부름.
Finite State-based
Final State Method는 규칙 기반으로 동일함. 하지만 룰베이스에서 조금 더 확장된 것이라 볼 수 있음. 사용자가 원하는 행위가 충분히 polynomial한 질문 수와 절차로 해결하는 방식이기 때문임. 비행기 예약과 위 그림 3 시나리오로를 보자면 프로그래밍을 통해 시퀀셜하게 이미 정해진 절차가 있어서 반드시 이걸 따라야 함. “다음 주 월요일에 리옹에서 시드니로 가는 편도 항공편을 예약하고 싶다"고 말 못함 왜냐면 “출발지 → 목적지 → 날짜 → 편도/왕복”의 일련의 절차 대로 말해야 하기에.
Frame-based
domain ontology기반 방식임. 예를 들자면 음악 틀어달라는 태스크라면 사전정의된 frame은 domain으로 Music을 가질 것이고 intent는 Play music일 것임. 그리고 slot이 될 수 있는 장르와 뮤지션을 요구하거나 수집할 수 있음. frame-based는 사전 정의된 frame을 보고 어느 슬롯이 채워졌고 안채워졌는지 확인해서 DS를 파악할 수 있음. rule-based와 activity-based 기반과 비교해 다른 점은 조금 더 유연하단 것이 장점임.
앞서 기술했듯 어떤 slot이 채워졌는지 안채워졌는지 파악해서 추가 요구하기 때문임. 반면 단점으론 복잡한 DP 알고리즘이 필요하고, 모든 조건에서 추가적으로 정보를 요청하는지 안하는지 테스팅이 필요함. 그럼에도 불구하고 frame-based는 현재에도 사용되는 방식임. 애플 시리, 아마존 알렉사, 구글 어시스턴트가 여기에 해당함. 그래도 이런 어시스턴트 들에서 조금 더 추가되는 부분은 NLU에서 머신러닝 방식이 사용되고, 프레임외에 control model을 추가한다고 함. Control model이 정확히 무엇인지 모르겠지만 봇 개발자가 복잡한 DP 지정을 방지할 수 있다고 함.
3.2 Data-driven
Data-driven 방식은 위 Hand-craft 방식과 달리 DS와 DP를 학습해서 사용함. 이를 위해 Supervised Learning(이하 SL)과 Reinforce Learning(이하 RL)이 사용됨. SL로는 라벨 있는 데이터로 corpus를 학습하고, RL로는 tiral-and-error 과정을 학습함
1) Supervised approach
Data-driven 방식의 최초 접근은 SL로, CRF나 최대 엔트로피 모델을 사용했었음. 하지만 이는 대개 DS 정의를 위해 NLU의 출력에 의존하는 단점이 있었음. 하지만 DL이 사용되면서 DST에 대한 성능이 높아짐. 성능 증가의 배경에는 DS를 NLU에 종속시키는 것이 아니라 NLU와 DS를 단일 모델로 병합하는 연구가 대부분 이뤄지면서 가능했음. 이런 연구의 한 예시로 아래 그림과 같은 Neural Belief Trakcer (NBT)가 있음.
NBT 모델은 시스템 출력과 유저 발화와 slot-value pair를 입력으로 넣고 중간에 Context Modeling과 Semantic Decoding을 거쳐 최종적으로 이진 분류하고 최종적으로 slot-value에 들어갈 값을 결정하는 구조를 가짐.
더욱 최근 DL 모델은 GNN 모델과 attnetion 메커니즘을 사용하기도 함. 최근 DL 모델도 결국 두 가지로 나뉨. pre-defined ontology-based(사전 정의된 온톨로지 기반)과 open-vocabulary candidate generation(개방형 어휘 후보 생성)으로 나뉨. 전자의 경우 도메인과 그에 해당하는 슬롯과 값이 제공된다고 가정함. 하지만 알다시피 정의된 것은 정확도가 높지만 동적인 환경에서는 여전히 취약함. 동적인 환경 예시는 영화 이름이나 사람 이름, 날짜, 위치 등이 있음 반면 후자의 경우 미리 정의된 것 없이 대화 기록이나 NLU 출력 값에서 슬롯 후보를 추정하는 방식임. 새로운 의도나 슬롯, 도메인을 추가할 때 데이터 수집이나 재학습과 같은 비용이 발생하지 않도록 제로샷으로 DST를 일반화 시키는 것이 현재 가장 메인이 되는 연구임.
Dialouge Policy
DP에 지도학습을 적용시키는 두 가지 접근이 있음. 1. DP 모델을 파이프 라인 모델로 두어 DST와 NLU 모듈과 독립적으로 학습시키는 방법임. 이 방법은 DST의 DS로부터 input을 가져와서 넣거나 NLU 결과를 직접 넣어서 다음 action을 출력함. 그 과정은 아래 그림의 (a)와 같음
DP network안에는 Act와 Slot을 예측하는 두 개의 Softmax가 있음. Act는 request, offer, confirm, select, bye 중에 하나가 될 수 있고 Slot은 price-range, area 같은 것들이 될 수 있음. (b)의 모델은 3개의 메모리에 의존함 slot-value memory, external memory, control memory인데 read/write function과 augmented attention 메커니즘을 공유함.
두 번째 접근은 end-to-end 모델임. 이 방식은 user utterance를 읽어서 곧 바로 모델에 넣고 다음 system action을 생성하는 방식임. 구현을 위해선 seq2seq 계열 알고리즘이 사용됨. sqe2seq 알고리즘에 사용되는 encoder는 user utterance와 dialouge history이며 decoder는 API 호출, 데이터베이스 쿼리가 될 수 있음. 알다시피 RNN, LSTM 사용했지만 최근엔 어텐션 메커니즘 사용됨. end-to-end 방식의 괄목할만한 대표적인 DP 모델은 아래 논문에서 확인할 수 있다고 함.
" Z. Zhang, M. Huang, Z. Zhao, F. Ji, H. Chen, and X. Zhu, “Memory augmented dialogue management for task-oriented dialogue systems,” ACM Transactions on Information Systems (TOIS), 2019."
여하튼 end-to-end 방식은 앞전 pipelined policy과 달리 dialouge state를 추론할 수 있다는 것이 장점. 다만 데이터가 많은 데이터가 필요할 뿐. 참고로 pipelined policy 방법도 동일하게 지도학습함.
Context support
conversation history를 앞 전 하나만 사용하냐 모두 사용하냐도 나뉨. 크게 3가지 방법으로 conversation history 모델링이 이뤄짐. 첫 번째 방법은 모든 발화를 concatenation하는 것임. 근데 단점이 계산 복잡도가 증가하니까 두 번째 방법인 user/system dialouge act나 dialouge state의 특정한 feature들만 캡처하는 방식임. 세 번째 방식은 최근에 나온것으로 그래graph structrural information를 활용하는 거임. 이건 Spacy에 있는 dependency relation과 관련이 있다고 함.
2) Reinforcement learning
RL 접근은 DM을 최적화 문제로 봄. 유저의 경험과 시간이 지나면서 성능이 점진적으로 개선하는. 전형적으로 Markov Decision process가 사용됐었음. (RL 파트 생략)
결론부터 요약해두자면 이 논문에서 말하고자 하는 DM 접근법은 크게 3가지가 있고 장단점은 다음과 같다.
1. Handcrafted 방식은 구현 쉽다. 데이터 필요 없다. dialouge traceability 충족시킬 수 있다. 단점은 유지 비용 높고 스케일업과 모델의 robustness 측면에서 한계가 있다. 또 사용자 피드백 고려하지 않는다.
2. Data-driven 방식은 크게 지도학습 방식, 강화학습 방식으로 나뉨. (1) 지도학습 장점은 자연어의 variation을 다룰 수 있고 새로운 domain에 대한 적은 노력으로 적응 가능함. 반면 단점은 양질의 데이터 불충분과 DP에 적응하기 위한 유저 피드백 고려 못함. (2) 강화학습의 장점은 Robust하고 user utterance의 모호함을 다룰 수 있음. 단점은 작은 스케일의 대화 도메인에 한계가 있다..?, 양질의 데이터 필요하다.
3. Hybrid 방식은 위 둘을 섞은 것임. 장점은 학습 복잡도와 학습 데이터 줄어듦. 단점은 충분한 양질의 데이터와 개발 노력 필요
아래 표는 DM (Dialouge Manager)에 사용되는 3가지 피처임.
1. Conversation history 사용되고
2. User profile 사용되고
3. External knowledge 사용됨.
읽고 나서 궁금해진 것
- GNN (Graph Neural Network)
- Graph Attention Network
- Knowledge Graph
- End-to-end Dialouge Policy Modeling
- Reinforcement Learning
읽어 볼 논문
[1] Z. Zhang, M. Huang, Z. Zhao, F. Ji, H. Chen, and X. Zhu, “Memory augmented dialogue management for task-oriented dialogue systems,” ACM Transactions on Information Systems (TOIS), 2019.
[2] Y. Murase, Y. Koichiro, and S. Nakamura, “Associative knowledge feature vector inferred on external knowledge base for dialog state tracking,” Computer Speech & Language, vol. 54, pp. 1–16, 2019.
의도 분류는 Spoken Language Understanding(SLU)의 하위 태스크에 해당하며, 의도 분류는 SLU의 또 다른 서브 태스크인 Semantic Slot Filling 태스크로 곧 바로 연계되기 때문에 그 중요성을 가짐.
ML 기반으론 유저 발화 이해가 어렵다. 때문에 이 논문에선 DL 기반의 의도 분류 연구가 최근까지 어떻게 이뤄져왔는지 분석, 비교, 요약한하고, 나아가 다중 의도 분류 태스크가 어떻게 딥러닝에 적용되는지 기술함.
내가 추출한 키워드: intent detection, mulit-intent detection, spoken language understanding, semantic slot filling.
Introduction
Dialouge System은 크게 5개 파트로 나뉨: ASR, SLU, DM, DG, TTS.
유저가 발화 하면 ASR을 통해 유저의 발화를 생성하고 SLU 과정으로 넘어가 말하고자 하는 1. 주제 파악 2. 의도 파악 3. Semantic slot filling을 과정을 거침. 이후 Dialouge Management를 거치고 답변 생성 후 TTS로 유저에게 전달.
과거엔 SLU에서 Domain recognition이 없었다. 왜냐면 dialouge system이 specific domain에 국한됐기 때문임. 하지만 최근엔 넓은 범위의 domain을 다루고자 하는 필요성이 있기 때문에 추가 됨.
도메인 별, 의도 별 사전 정의된 카테고리를 이용해 유저 발화 분류함. 만약 사전 정의돼 있지 않다면 의도를 잘못 분류해서 잘못된 대답을 하게 됨.
의도 분류에서 어려운 것은 다중 Domain이 들어왔을 때 어떤 Domain에 속하는지 명확히 해야함. 그렇지 않으면 Domain보다 더 세분화되어 있는 Intent category으로 접근하기 어려움. 위의 예시로 들면 맥락상 기차 말고 비행기 탈꺼니까 기차 환불하고 가장 빠른 비행기 시간 확인해 달라는 것임. 근데 환불인지 시간 확인인지 Domain 수준에서 파악이 안되면 그 다음 단계인 Intent detection과 semantic slot filling을 못함.
2. Intent Detection의 어려움
2.1 데이터 부족
부족하다.
2.2 화자 표현 광범위, 모호함.
일반적으로 구어체 사용하고, 짧은 문장과 넓은 컨텐츠를 다루기 때문에 의도 파악이 어려움. 가령 예를 들어 “I want to look for a dinner place”라고 말하면 저녁 식사 장소 찾고 싶단건데 domain이 명확하지 않음. (사실 이 정도면 충분하다 생각하는데 불확실한가 봄)
다른 예시 들자면 Hanting이라는 호텔이 있지만 Hanting Hotel이라고 구체적으로 이야기하지 않으면 이해하기 어려움. 또는 티켓 예약 하고 싶다고만 말하면 비행기 티켓인지 기차 티켓인지 콘서트 티켓인지 알 수 없는 것처럼 화자의 표현이 광범위하거나 모호한 경우가 발생해서 machine이 적절한 답변을 주기 어려움.
2.3 암시적인 의도 분류
의도는 명시적인 것(Explicit)과 암시적인 것(Implicit)으로 나눌 수 있음. 유저가 암시적으로 말하면 진짜 유저 의도가 뭔지 추론할 필요가 생김. 예를 들어 요새 건강에 관심이 있다고 말하면 아 오래살고 싶구나 하고 이해할 수 있어야 하는데 그게 어려움. (내가 만든 예시)
2.4 multiple intents detection
multi-label classification과 비슷하지만 다름. 그 차이점은 multi-label classification은 긴 문장 multiple intnets detection은 짧은 문장을 다룸. 짧은 문장으로 다중 의도 분류 해야해서 어려움. 짧은 발화안에 다양한 의도 분류를 해야하고 그 의도 수를 결정해야 하는게 쉽지 않음.
3. Main methods of intent detection
3.1 전통적인 Intent detection 방법론
최근에는 intent detection을 Semantic Utterance Classification (SUC)로 여긴다.
1993년엔 rule-based가 제안된 적 있고, 2002-2014까진 통계적으로 피처를 뽑아서 분류했다. 가령 예를 들면 나이브 베이즈나 SVM이나, Adaboost, 로지스틱 회귀를 썼었다. 근데 룰베이스의 경우 정확도는 높지만 새로운 카테고리가 추가될 때마다 수정해야 하는 번거로움이 있고, 통계적인 방식은 피처의 정확도나 데이터 부족문제가 있다. 근데 지금도 화자의 real intent detection은 여전히 어려운 연구 주제다.
3.2 현재 주류 방법론
워드 임베딩, CNN, RNN, LSTM, GRU, Attention, Capsule Network 등이 있다. 전통적인 방법과 비교하면 성능이 크게 좋아졌다.
3.2.1 워드 임베딩 기반 의도 분류
3.2.2 CNN 기반 의도 분류
CNN 기반으로 해서 피처 엔지니어링 과정을 많이 줄이고 피처 표현력도 좋아졌다. 근데 여전히 CNN으론representation 한계 있다.
3.2.3 RNN 기반 의도 분류
CNN과 달리 워드 시퀀스를 표현할 수 있음. 2013년에 context 정보 이용해서 Intent detection의 error rate를 줄인 연구가 있음. RNN은 기울기 소실과 기울기 폭발 문제가 있고 이 때문에 long-term depdendence 문제를 초래함.
그래서 이 문제 해결하려고 LSTM이 나옴. LSTM가지고 ATIS 데이터셋 (Air Travel Information System)에서 RNN보다 에러율 1.48%을 줄임.
2018년엔 짧은 텍스트로 인해 발생하는 data sparse 문제를 해결하기 위해 Biterm Topic Model(BTM)과 Bidirectional Gated Recurrent Unit(BGRU) 기반 멀티턴 대화 의도 분류 모델이 제시됨.
위 두 모델을 합친 모델은 의료 의도 분류에서 좋은 성능을 냈음.
. . .
3.2.6 캡슐 네트워크 모델 기반 의도 분류
캡슐 개념은 CNN의 표현 한계 문제를 해결하기 위해 2011년에 힌튼에 의해 제시됐었음. 캡슐은 vector representation을 가짐. 이후 2017년에 CNN scalar output feature detector를 vector representation capsule로 대체하고 max pooling을 프로토콜 라우팅으로 대체하는 캡슐 네트워크가 제안됨. CNN과 비교하자면 캡슐 네트워크는 entity의 정확한 위치 정보를 유지함.
결론을 말하자면 capsule network는 텍스트 분류 태스크 잘 수행하고, multi-label 텍스트 분류에도 잘 동작함.
. . .
4. 의도 분류 평가 방법
현재 Intent Detection은 Semantic Discourse Classification 문제로 여겨짐. 결론은 F1-score 사용함.
5. 성능 비교
아래는 다른 연구 논문에서 가져온 성능 비교 결과임. 데이터셋은 SNIPS와 CVA(Commercial Voice Assistant)를 사용했음. 참고로 SNIPS는 영어 데이터셋이고 CVA는 중국어 데이터셋임.
Intent Capsnet이 가장 성능이 좋더라.
Conclusion
머신러닝 기반의 의도 분류 태스크는 깊이 이해 못한다. 그래서 딥러닝 기반 의도 분류 태스크가 성능이 좋다. capsule network model이 의도 분류 태스크에서 좋은 성능을 내고, multi-label classification도 잘한다. self-attention 모델은 의도 분류 과정에서 문장의 다양한 semantic feature들을 추출할 수 있다.
의도 분류는 e-commerce, travel consumption, medical treatment, chat에도 적용되고 있으며, 침입 탐지 시스템과 같은 네트워크 보안 분야에서도 적용된다.
전통적인 dialouge system은 주로 single intent detection만 가능하다. 하지만 다양한 의도는 셀 수 없이 많으므로 multi intent detection이 가능하도록 연구가 필요하다.
궁금해진 것
Semantic slot filling의 과정은 구체적으로 어떻게 이뤄지는가?
Dialouge Management란 무엇이고 어떻게 동작하는가?
Dialouge Generation 과정은 구체적으로 어떻게 이뤄지는가?
task-oriented vertical domain이 무엇인가? vertical이 있으면 horizontal domain도 있을 것인데 각각은 무엇인가?
알게 된 것
도중에 fine-grained라는 말이 나옴. 이건 잘게 쪼갠 것을 의미함. 반면 coarse-grained는 덩어리째를 의미함.
한 줄 평
큰 틀에서 연구가 어떻게 이뤄지는지 대략적으론 알 수 있어서 좋았지만 Dialougue System의 구체적으로 어떻게 이뤄지는지 나와있지 않고 데이터셋을 잘 정리해서 소개하지 않아서 아쉬움.
버블정렬은 서로 인접해 있는 요소 간의 대소 비교를 통해 정렬한다. 버블 정렬은 정렬 알고리즘 중 가장 단순한 알고리즘으로, 단순한 만큼 비효율적이다. 시간 복잡도가 최고, 평균, 최악 모두 $O(n^2)$이며 공간복잡도는 하나의 배열만 사용하므로 $O(n)$을 가진다. 동작 방식은 인접한 두 요소간의 대소 비교를 진행한다.
만약 배열에 n개의 요소가 있을 경우 1번째 원소 vs 2번째 원소를 비교하고 2번째 원소 vs 3번째 원소를 비교하고, ... n-1번째 원소 vs n번째 요소를 비교하면 1회전 비교가 끝난다. 1회전이 끝나면 가장 큰 원소는 맨 뒤에 위치하게 되므로 2회전 비교에서는 제외된다. 마찬가지로 두 번째로 큰 원소는 가장 큰 원소 앞에 위치하게 되므로 3회전 비교에서는 제외된다. 즉 버블 정렬을 1회 수행할 때 마다 정렬해야 할 원소가 하나씩 줄어든다. 이를 코드로 구현하면 아래와 같다.
def bubble_sort(array):
""" Best: O(n^2) Average: O(n^2) Worst: O(n^2) | O(n) """
for i in range(len(array)):
for j in range(len(array)-i-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
return array
2. 삽입 정렬 (Insert Sort)
삽입 정렬이란 정렬을 진행할 원소의 index보다 낮은 곳에 있는 원소들을 탐색하며 알맞은 위치에 삽입해주는 정렬 알고리즘이다. 동작 방식은 두 번째 index부터 시작한다. 그 이유는 첫 번째 index는 비교할 원소가 없기 때문이다. 알고리즘이 동작하는 동안 계속해서 정렬이 진행되므로 반드시 맨 왼쪽 index까지 탐색하지 않아도 된다는 장점이 있다. 모두 정렬되어 있는 Optimal한 경우 모든 원소가 한 번씩만 비교되므로 $O(n)$의 시간 복잡도를 가진다. 또한 공간복잡도는, 하나의 배열에서 정렬이 이루어지므로 $O(n)$이다.
삽입 정렬을 코드로 구현하면 아래와 같다. 첫 번째 for문은 정렬할 원소를 차례대로 선택하는 것이며, 두 번째 for문은 정렬할 원소보다 아래 인덱스에 있는 요소와 비교하기 위함이다.
def insert_sort(array):
""" Best: O(n) Average: O(n^2) Worst: O(n^2) | O(n) """
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
return array
삽입 정렬을 최적화할 경우 아래 코드와 같다.
def insert_sort(array):
for i in range(1, len(array)):
j = i
while j > 0 and array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]
j -= 1
return array
3. 선택 정렬 (Selection Sort)
선택 정렬이란 배열에서 최소값을 반복적으로 찾아 정렬하는 알고리즘이다.
시간복잡도 최선, 평균, 최악 모두 $O(n^2)$에 해당하는 비효율적인 알고리즘으로 정렬 여부와 상관없이 모든 경우의 수를 전부 확인한다. 동작방식 3단계로 구성된다. 첫 번째는 주어진 배열에서 최소값을 찾는다. 두 번째는 최소값을 맨 앞의 값과 바꾼다. 세 번째는 바꿔준 맨 앞 값을 제외한 나머지 원소를 동일한 방법으로 바꿔준다. 이를 알고리즘으로 나타내면 다음과 같다.
def selection_sort(array):
""" Best: O(n^2) Average: O(n^2) Worst: O(n^2) | O(N^2) """
for i in range(len(array)):
idx = i
for j in range(i+1, len(array)):
if array[idx] > array[j]:
idx = j
array[idx], array[i] = array[i], array[idx]
return array
덧붙여 선택 정렬은 크게 2가지로 최소 선택 정렬과, 최대 선택 정렬이 있다. 최소는 위와 같이 오름차순으로 정렬하는 것이고 최대는 위와 반대로 내림차순으로 정렬하는 것이다.
4. 퀵 정렬 (Quick Sort)
퀵 정렬은 분할정복법과 재귀를 사용해 정렬하는 알고리즘이다.
퀵 정렬에는 피봇(Pivot)이라는 개념이 사용된다. 피봇은 한 마디로 정렬 될 기준 원소를 뜻한다. 피봇 선택 방법에 따라 퀵 정렬의 성능이 달라질 수 있다. 최적의 피봇 선택이 어려우므로 임의 선택을 해야 한다. 보통 배열의 첫 번째 값이나 중앙 값을 선택한다. 퀵 정렬의 동작방식은 다음과 같다. 가령 예를 들어 배열 [5, 6, 1, 4, 2, 3, 7]이 있고, 피봇을 임의로 4를 선택했다 가정하자. 이후 4를 기준으로 작은 것은 왼쪽으로 큰 것은 오른쪽으로 보내 [1, 2, 3] < 4 < [5, 6, 7]를 생성한다. 다시 왼쪽에서부터 임의의 피봇 2를 설정하여 [1] < 2 < [3]을 생성하고 오른쪽에선 임의의 피봇 6를 설정하여 [5] < 6 < [7]로 나눈다. 만약 배열 길이가 1이 된다면 가장 정렬 완료된 것이므로 분할된 배열을 합쳐 줌으로써 정렬을 마친다. 이를 알고리즘으로 구현하면 다음 코드와 같다.
def quick_sort(array : list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(n^2) | O(nlogn) """
if len(array) <= 1:
return array
pivot = array[len(array) // 2]
small, equal, big = [], [], []
for num in array:
if num < pivot:
small.append(num)
elif num > pivot:
big.append(num)
else:
equal.append(num)
return quick_sort(small) + equal + quick_sort(big)
5. 병합 정렬 (Merge Sort)
병합 정렬은 분할정복과 재귀 알고리즘을 사용하는 정렬 알고리즘이다.
퀵 정렬과 함께 두 개의 알고리즘이 사용된다는 측면에서 공통점을 가진다. 하지만 차이점은 퀵 정렬이 피봇 선택 이후 피봇 기준으로 대소를 비교하는 반면, 병합 정렬은 배열을 원소가 하나만 남을 때 까지 계속 이분할 한 다음, 대소관계를 고려하여 다시 재배열 하며 원래 크기의 배열로 병합한다. 예를 들어 배열 [6, 5, 1, 4, 3, 2, 8, 7]이 있을 때, 첫 번째로 [6, 5, 1, 4]와 [3, 2, 8, 7]로 분리한다. 두 번째로 [6, 5], [1, 4], [3, 2], [8, 7]로 나눈다. 세 번째로 [6], [5], [1], [4], [3], [2], [8], [7]로 나눈다. 이렇게 모든 원소가 분리되면 대소 관계를 고려하여 병합 과정을 거친다. 첫 번째로 [5, 6], [1, 4], [2, 3], [7, 8]이 되며, 두 번째는 [1, 4, 5, 6], [2, 3, 7, 8]이 된다. 마지막으로 하나의 배열로 병합되면서 [1, 2, 3, 4, 5, 6, 7, 8]와 같이 정렬이 완료되면서 알고리즘이 종료된다. 이를 코드로 나타내면 아래 코드와 같다.
def merge_sort(array: list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(nlogn) | O(n) """
if len(array) < 2:
return array
mid = len(array)//2
low = merge_sort(array[:mid])
high = merge_sort(array[mid:])
merged_array = []
l, h = 0, 0
while l < len(low) and h < len(high):
if low[l] < high[h]:
merged_array.append(low[l])
l += 1
else:
merged_array.append(high[h])
h += 1
merged_array += low[l:]
merged_array += high[h:]
return merged_array
시간 복잡도의 경우 최선, 평균, 최악 모두 $O(nlogn)$이며 공간 복잡도의 경우 정렬된 원소를 담을 배열이 하나 필요로 하므로 $O(n)$.
6. 힙 정렬 (Heap Sort)
힙이란 트리 기반의 자료구조로서, 두 개의 노드를 가진 완전 이진 트리를 의미한다. 따라서 힙 정렬이란 완전 이진 트리를 기반으로 하는 정렬 알고리즘이다. 힙의 분류는 크게 최대 힙과 최소 힙 두 가지로 나뉜다. 최대 힙은 내림차순 정렬에 사용하며, 최소 힙은 오름차순 정렬에 사용한다.
최대힙의 경우 부모 노드가 항상 자식노드 보다 크다는 특징을 가진다. 반대로 최소힙의 경우 부모 노드가 항상 자식노드 보다 작다는 특징을 가진다. 이러한 힙에서 오해할 수 있는 특징은 힙은 정렬된 구조가 아니다. 부모 자식 간의 대소 관계만 나타내며 좌우 관계는 나타내지 않기 때문이다. 예를 들어 최소 힙에서 대부분 왼쪽 노드가 오른쪽 노드보다 작지만 4의 자식 노드인 7과 5는 왼쪽이 오른쪽보다 크다.
힙은 완전 이진 트리기 때문에 적절히 중간 레벨의 노드를 추출하면 중앙값에 가까운 값을 근사치로 빠르게 추출할 수 있다는 장점을 갖고 있다. 때문에 힙은 배열에 순서대로 표현하기 적합하다. 또한 균형을 유지하려는 특징 때문에 힙은 우선순위 큐, 다익스트라, 힙 정렬, 프림 알고리즘에 활용된다. 특히 힙 덕분에 다익스트라 알고리즘의 시간 복잡도는 $O(V^2)$에서 O(ElogV)로 줄어들 수 있었다.
힙 정렬 과정을 최대힙을 기준으로 우선 간략히 보자면 아래 GIF와 같다.
최대힙 정렬 동작 과정
최대 힙의 동작을 코드로 작성하면 아래와 같다.
def heap_sort(array : list) -> list:
""" Best: O(nlogn) Average: O(nlogn) Worst: O(nlogn) | O(nlogn) """
n = len(array)
for i in range(n//2-1, -1, -1):
heapify(array, i, n)
for i in range(n-1, 0, -1):
array[0], array[i] = array[i], array[0]
heapify(array, 0, i)
return array
def heapify(array : list, index : int, heap_size : int) -> None:
smallest = index
left = (2 * index) + 1
right = (2 * index) + 2
if left < heap_size and array[left] < array[smallest]:
smallest = left
if right < heap_size and array[right] < array[smallest]:
smallest = right
if smallest != index:
array[smallest], array[index] = array[index], array[smallest]
heapify(array, smallest, heap_size)
if __name__ == "__main__":
array = [1, 10, 5, 5, 2, 9, 8, 7, 6, 4, 0, 3, 2, 9]
print (heap_sort(array)) # [10, 9, 9, 8, 7, 6, 5, 5, 4, 3, 2, 2, 1, 0]
먼저 heapify 함수의 역할은 부모와 자식의 대소 관계를 확인해 자리를 바꿔주는 동작을 한다. 예를 들어 위 같이 최대힙을 구현할 때 부모 노드가 자식 노드보다 작다면 상호 간의 자리를 바꿔주는 것이다. left, right는 비교가 진행 될 노드의 인덱스를 의미한다. 초기 값은 루트 노드의 바로 아래 두 자식 노드이다. 첫 번째 조건문은 왼쪽 자식이 부모보다 작은지 확인한다. 두 번째 조건문은 오른쪽 자식이 부모보다작은지 확인한다. 세 번째 조건문은 초기 index와 동일하지 않다면 부모 자식간의 상호 위치를 변경한 뒤 재귀를 통해 반복한다.
7. 셸 정렬 (Shell Sort)
셸 정렬이란 삽입 정렬의 단점을 보완하고자 도입되었다. 삽입 정렬은 주어진 정렬 상태가 역순으로 배열되어 있을수록 비교횟수가 늘어나고, 최선의 경우 $O(N)$이지만 최악의 경우 $O(N^2)$으로 성능 차이가 크다. 셸 정렬은 이러한 시간복잡도를 평균적으로 $O(N^{1.25})$ 또는 $O(N^{1.5})$ 수준으로 낮추고자 도입된 알고리즘이다. 셸 정렬에 사용되는 핵심 개념은 interval (간격)이다. interval은 비교할 원소 간의 간격을 의미한다. 셸 정렬에서는 비교 횟수를 줄이기 위해 interval은 큰 값에서 낮은 값으로 낮춰간다. 동작 방식은 배열에서 interval 만큼 떨어진 원소들을 부분집합으로 구성한 뒤 삽입 정렬을 진행하는 방식으로 진행된다. 초기 interval 값은 len(array) // 2로 설정하며 계속 2로 나누어준다. 예를 들어 아래와 같이 배열 크기가 8이라면 초기 interval = 4가 되어 아래와 같이 비교가 진행 된다.
interval이 4인 경우 거리가 4만큼 떨어져 있는 원소끼리 부분집합을 이루어 비교대상이 된다. 위 그림에선 (35, 14), (33, 19), (42, 27), (10, 44)이 서로 비교 대상이 된다. 비교 진행한 뒤 interval을 2로 나누어주어 4에서 2가 된다. 이후 다시 interval만큼 떨어진 원소를 부분집합화하여 비교한다.
interval이 2인 경우 거리가 2만큼 떨어져 있는 원소끼리 부분집합을 이뤄 비교한다. (14, 27, 35, 42), (19, 10, 33, 34)가 부분집합이 되어 정렬이 진행된다. 이후 다시 interval을 2로 나눠주어 1이 되면 아래와 같이 삽입 정렬이 진행된다.
이를 코드로 구현하여 나타내면 다음과 같다. 주로 가독성을 위해 변수명을 interval을 h로 표현하기도 한다.
def shell_sort(array : list) -> list:
""" Best: O(n) Average: O(n^1.25,1.5) Worst: O(n^2) | O(n) """
n = len(array)
interval = n // 2
while interval > 0:
for i in range(interval, n):
j = i - interval
temp = array[i]
while j >= 0 and array[j] > temp:
array[j+interval] = array[j]
j -= interval
array[j+interval] = temp
interval //= 2
return array
8. 기수 정렬 (Radix Sort)
기수 정렬은 non-comparison 알고리즘으로 원소간의 대소 비교를 하지 않고 정렬하는 알고리즘이다. 대신 기수 정렬은 정렬하고자 하는 수의 낮은 자리 수를 차례대로 확인하여 정렬하는 방식이다. 정렬을 위해 총 10개의 queue를 사용한다.
첫 번째로, 1의 자리 수를 확인하여 각 원소의 1의 자리에 해당하는 queue에 쌓아준다. 이후 0~9의 queue를 순회하며 차례대로 가져온다. 두 번째로, 10의 자리 수를 확인하여 각 원소의 10의 자리에 해당하는 queue에 쌓아준다. 이후 0~9의 queue를 순회하며 차례대로 가져온다. 세 번째가 진행되기 위해서는 100의 자리수를 가진 값이 있어야 하며, n번째가 진행되기 위해서는 $10^{(n-1)}$의 자리수를 가진 수가 있어야 한다.
이를 코드로 구현하면 다음과 같다.
from collections import deque
def radix_sort(array : list) -> list:
""" Best: O(n) Average: O(n) Worst: O(n)"""
buckets = [deque() for _ in range(10)]
MAX = max(array)
queue = deque(array)
radix = 1
while MAX >= radix:
while queue:
num = queue.popleft()
buckets[(num // radix) % 10].append(num)
for bucket in buckets:
while bucket:
queue.append(bucket.popleft())
radix *= 10
return queue
자리수를 담을 bucket을 총 10개 생성해준다. 이후 가장 큰 자리 수 만큼 반복해야 하므로 max(array)를 통해 가져온다. 알고리즘은 크게 두 단계로 나눠서 보면 간단하다. 첫 번째는 queue에 있는 배열을 각 자리수에 해당하는 bucket에 담아주는 과정이다. 두 번째는 bucket에 담은 원소들을 다시 queue에 담아주는 과정이다. 다만 이 두 과정을 반복하되 배열 최대값이 가지는 최대 자리수까지는 비교해주어야 하므로 radix에 10을 곱해줘서 반복하며, 배열 최대값의 자리수보다 넘어가면 끝나는 것이다.
9. 카운팅 정렬 (Counting Sort)
카운팅 정렬(계수 정렬)은 non-comparison sort 알고리즘에 해당하는 알고리즘으로 comparison sort에 해당하는 버블, 선택, 힙, 병합, 퀵, 삽입이 기껏해야 평균적으로 $O(nlogn)$이나 $O(n^2)$의 시간복잡도를 갖기에 이를 $O(n)$ 수준으로 낮추고자 도입된 알고리즘이다. 카운팅 정렬의 동작은 이름 그대로 배열에 존재하는 원소 별 개수를 세어 정렬하는 방식으로 간단히 나타내보이자면 아래 GIF와 같다.
배열에 담긴 요소의 개수를 count라는 배열에 담아 넣은 뒤 차례대로 개수만큼 출력해준다. 우선, 결과적으로 코드를 구현해보자면 아래와 같이 간단한 코드로 나타낼 수 있으며 크게 5단계로 이뤄진다.
def counting_sort(array : list) -> list:
""" Best: O(n) Average: O(n+k) Worst: O(n+k) | O(n+k) """
count = [0] * (max(array) + 1) # 1. create a count array to check how many numbers each have.
for num in array: # 2. check how many numbers each have.
count[num] += 1
for i in range(1, len(count)): # 3. do cumulative sum
count[i] += count[i-1]
arr = [0] * len(array) # 4. create a new array to contain the numbers to be sorted.
for num in array: # 5. sort.
idx = count[num]
arr[idx-1] = num
count[num] -= 1
return arr
1. 배열에 있는 원소 개수를 담을 count 배열을 생성한다. 배열 크기는 원소 값 그대로를 인덱스로 사용하기 위해 max(array)+1로 해준다.
2. 배열에 있는 원소 개수를 count 해준다.
3. 누적합을 진행한다. 그 이유는 누적합을 진행하게 되면 앞 뒤 원소 간의 개수 차이가 곧 몇 칸을 차지할지 알 수 있기 때문이다. 이 부분이 제일 처음 잘 이해가 되지 않는 부분이었다. 예를 들어 설명하기 위해 임의의 배열 [2, 5, 3, 2, 1, 4, 4, 2]라는 배열이 있다 하자. 그러면 count 배열이 [0, 1, 3, 1, 2, 1]가 된다. 이후 count 배열에 누적합을 진행하면 [0, 1, 4, 5, 7, 8]이 된다. 이 누적합을 통해 아래와 같은 사실을 알 수 있다.
count[0] = 0: count 배열의 0번째 인덱스인 값 0은 (0-0)칸을 차지하고, 위치하게 되는 인덱스는 [0:0]이 된다. count[1] = 1: count 배열의 1번째 인덱스인 값 1은 (1-0)칸을 차지하고, 위치하게 되는 인덱스는 [0:1]이 된다. count[2] = 4: count 배열의 2번째 인덱스인 값 2는 (4-1)칸을 차지하고, 위치하게 되는 인덱스는 [1:4]가 된다. count[3] = 5: count 배열의 3번째 인덱스인 값 3은 (5-4)칸을 차지하고, 위치하게 되는 인덱스는 [4:5]가 된다. count[4] = 7: count 배열의 4번째 인덱스인 값 4는 (7-5)칸을 차지하고, 위치하게 되는 인덱스는 [5:7]이 된다. count[5] = 8: count 배열의 5번째 인덱스인 값 5는 (8-7)칸을 차지하고, 위치하게 되는 인덱스는 [7:8]이 된다.
즉, 누적합 해준 배열을 통해 원소 개수 만큼 도출된 인덱스에 넣어주면 자연스럽게 정렬 되는 것이다. 이러한 과정을 거치기 위해 다음 2단계를 더 진행 한다.
4. 정렬 된 원소를 담고자하는 새로운 배열을 생성해준다. 새 배열 크기는 원래 배열 크기와 동일하다.
5. 정렬하고자 하는 배열의 원소를 순회하며 count[원소]의 위치에서 누적합 되어 있는 값을 index로 지정해준다. 이후 새로 생성한 배열 result에 그 값을 넣어주고 누적합된 값을 -1을 해준다. 여기서 누적합 값에 -1을 해주는 것은 result의 index에 차례대로 같은 수를 담는 것이 아니라 역순으로 담아야 하기 때문이다. 역순으로 값을 담는 이유는 현재 알고리즘 구조상 역순으로 담아야 하기 때문이다. 이중 루프를 통해서 차례대로 값을 담을 수 있지만 코드 가독성과 동작 효율성을 고려하면 위와 같이 작성하는 것이 더 좋다.
마지막으로 시간복잡도는 $O(n+k)$가 된다. k가 상수이긴 하지만 생략되지 못하는 것은 그 만큼 영향을 미칠 수 있기 때문이다. 1~4번 과정 모두 $O(n)$에 해당한다. 하지만 5번에서 count 배열을 업데이트 하는 과정에서 원소 중 max 값인 k를 k만큼 반복하게 되므로 $O(n+k)$가 된다. 만약 정렬하고자 하는 배열의 max 값이 배열의 개수보다 작다면 $O(n)$이 된다. 하지만 배열의 개수보다 커지면 커질수록 배열 공간만 차지하고 값이 들어있지 않는 sprase한 배열이 될 수 있고, 무의미한 공간도 탐색해야 하므로 시간 복잡도가 높아질 수 있는 것이다.
10. Tim Sort
Tim Sort는 삽입정렬과 병합정렬이 결합된 정렬 알고리즘이다. Tim Peter라는 자에게 의해 고안된 알고리즘으로 파이썬 내장 정렬 알고리즘으로 채택되어 있다. Tim Sort는 왜 다른 알고리즘에 비해 상대적으로 느린 삽입정렬을 사용할까? 삽입정렬의 경우 앞서 기술한 바와 같이 평균과 최악의 경우 $O(n^2)$로 다른 알고리즘에 비해 시간복잡도가 높아 잘 사용되지 않는다. 하지만 이러한 단점에도 불구하고 삽입정렬에는 참조 지역성이라는 주요한 성질이 있다. 운영체제 시간에 배우거나 신입 개발자 인터뷰에 때때로 물어보는 내용이다.
CPU가 빠른 연산을 위해 사용하는 캐시 메모리에 데이터를 담을 때 적중률을 높이기 위해 사용하는 원리다. 쉽게 말해 최근 참조했던 메모리와 인접한 메모리를 참조할 확률이 높으니 이들을 캐시 메모리에 미리 담아두는 것이며, 삽입정렬은 인접한 메모리와 비교를 반복하기에 참조 지역성의 원리를 잘 만족하고 있다고 할 수 있다. 또 삽입정렬은 원소가 많아질수록 느려지는 단점이 있지만 정렬 수가 적당히 작은 수라면 퀵정렬보다 빨라지는 장점이 있다. Tim Sort는이러한 삽입정렬의 특성을 활용하여 전체 정렬 대상 원소들을 부분부분(divide)으로 작게 나눈 다음 삽입정렬을 수행하고 병합(conqure)을 수행하면 정렬이 조금 더 빠르지 않을까 하는 아이디어를 기반으로 만들어졌다. 이러한 Tim Sort는 실제로 시간복잡도를 최선의 경우 $O(n)$, 평균은 $O(n\log n)$, 최악의 경우 $O(n\log n)$를 갖는다.
Tim Sort에서는 이러한 삽입정렬을 그대로 사용하진 않고 속도를 개선한 이진삽입정렬을 사용한다. 이진삽입정렬을 사용하면 앞서 말한 참조 지역성이 떨어지게 되나 적당히 작은 수의 원소를 정렬한다면 참조 지역성이 크게 문제가 되지 않으면서 시간복잡도를 개선할 수 있게 된다.
RUN = 32
def insert_sort(array, left, right):
for i in range(left + 1, right + 1):
key = array[i]
j = i - 1
while j >= left and array[j] > key:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key
def merge(array, left, mid, right):
len1 = mid - left + 1,
len2 = right - mid
left_array, right_array = [], []
for i in range(0, len1):
left_array.append(array[left + i])
for i in range(0, len2):
right_array.append(array[mid + 1 + i])
i, j, k = 0, 0, left
while i < len1 and j < len2:
if left_array[i] <= right_array[j]:
array[k] = left_array[i]
i += 1
else:
array[k] = right_array[j]
j += 1
k += 1
while i < len1:
array[k] = left_array[i]
k += 1
i += 1
while j < len2:
array[k] = right_array[j]
k += 1
j += 1
def tim_sort(array):
""" Best: O(n) Average: O(nlogn) Worst: O(nlogn) | O(n) """
n = len(array)
for i in range(0, n, RUN):
insert_sort(array, i, min((i + RUN - 1), n - 1))
size = RUN
while size < n:
for left in range(0, n, size * 2):
mid = left + size - 1
right = min((left + size * 2 - 1), (n - 1))
merge(array, left, mid, right)
size = size * 2
return array
if __name__ == "__main__":
array = [5, 2, 8, 4, 1, 9, 6, 3, 7]
sorted_array = tim_sort(array)
print(sorted_array)
최근, 향후 창업을 준비하고자 몇몇 세미나를 듣고 있다. 이번이 세 번째다. 어제는 (2022.07.26(화) 16:00~18:00) 스타트업 해외진출 관련하여 마곡, 서울창업허브 (M+)에서"Awake, It's time to innovation Asia"라는 주제로 세미나를 들었다. 연사는 엑센트리벤처스의 윤우근 이사회 의장이다. 엑센트리는 런던베이스 엑셀러레이터로, 스타트업이 런던쪽에 랜딩할 수 있도록 자본 지원과 프로그램을 제공한다고 한다. 오늘 세미나의 핵심 내용은 간단했다. 스타트업의 해외 진출을 위해선 6~7가지로 요약할 수 있었다.
첫 번째로는 스타트업 의 핵심기술이 글로벌 IP(Intellectual Property)로 보호받고 있어야 하는 것이다. 그 이유는 대기업의 기술 탈취가 심하기 때문이라 한다. 법정 공방에서도 중소기업 vs 대기업 구도에서 중소기업의 패소율이 84%에 달하며 대기업은 0.2%이란 수치를 볼 수 있었다. 보통 선진국에서는 약자 보호 시스템이 마련되어 있지만 우리나라는 그렇지 않다는 것이다. 그렇기에 핵심 기술이 글로벌 IP로 보호받고 있어야 해외진출이 가능하다 말한다. 두 번째는 전 세계에 핵심 기술을 알릴 홍보맨이 반드시 필요하다는 것이다. 홍보맨은 CEO만큼 제품이나 서비스를 잘 알고 있는 사람이여야 하며, 투자유치를 위해 계속해서 IR도 함께 해야 한다고 한다. 쓰는 시점에서 헷갈리는 데, IR 은 대표의 역할인지 홍보맨의 역할인지 아니면 아무나 해도 상관 없는지 헷갈린다. IR에 대해 들으며 들었던 생각으론 가급적이면 외부 자본을 차입하지 않고 외부 자본에 독립적인 기업을 만들 수 있다면 가장 좋지 않을까 하는 생각이 들었다. 세 번째는 영어라고 말한다. 더 말하지 않아도 필요성을 절감한다. 창업 직전에는 어느 정도 네이티브와 비즈니스 영어를 문제 없이 구사하는 것을 목표로 하고 있다.
네 번째는 현지 모임에서 동양인, 한국인을 찾아 일원이 되어야 한다고 말한다. 런던 스타트업은 주로 60%~70%가 서양인이라 우리도 그렇듯 어느정도 차별이 있을 수 있기 때문이라 말한다. 다섯 번째는 정부지원 등 각종 프로그램을 타고 해외로 진출하는 것이 그나~마 성공 확률이 높다고 말한다. 여섯 번째는 현지 밴처캐피털이나 CEO와 밋업을 하는 것이라 말하고, 일곱 번째는 잠재적 고객과의 만남이라고 한다. 또 중요한 것은 Global standard 수립이라는 것이다. 삼성과 SK케미칼과 같이 1,2차 벤더사가 되기 위해서는 회계나 법률적인 부분을 6개월간 수정을 거쳐 일종의 표준화를 시키는 과정이 있다는 것이다. 여기까지가 들었던 핵심 내용이다.
이외의 내용으론 몇몇이 있었는데 그 중 첫 번째는 유니콘 기업 관련 산업이었다. 전세계 유니콘 기업이 약 1,170(?)개가 있고 미국 629개, 중국 173개, 인도 68개, 영국 44, 독일 29, 프랑스 24, 이스라엘 22 등등이 있다고 한다. 이러한 유니콘 기업은 대부분 헬스케어, 전기차, 빅데이터, 바이오이지만 한국에는 이러한 기업이 없고, 따라서 기회가 있다고 한다. 두 번째는 창업은 돌파구라고 말하며 창업 은 돈이 아니라 소명의식이 필요하다 말한다. 절감한다. 소명의식의 예로는 사회공헌이나 고용창출이 있다고 말했다. 고용창출은 생각해본 적 없었지만 유니콘 기업 하나가 많은 고용창출을 하여 사회에 도움이 된다고 한다.
세 번째는 지금은 산업간의 경계가 모호한 빅테크의 시대라고 말한다. 단계를 밟아가면 느릴 수 있다고 말한다. 뛰어넘어야 관심받고 투자 받는다고 한다. 중국이 현금 사용하다가 곧 바로 QR로 넘어간 것을 예를 들어 줬다. 네 번째부턴 맥락이 잘 기억이 나질 않는데 초기엔 VC 심사역을 만나는 것은 도움이 되지 않는다는 것이다. 엔젤이나 LLC(?)를 만나야 한다고 한다. 또 한국 법인과 해외 법인을 함께 만들라 한다. 해외법인만 설립하면 지원받기 힘들다는 이야길 하셨다.
이후 로 생각나는 대로 적자면 정부에선 예산 사용에 관심 있지 스타트업이 잘 되는 것 관심이 없다.
현지서 피봇 기다려주는 엑셀러레이터 별로 없다. 하지만 최근 피봇까지 도와주는 몇몇이 생겨났다. 찾아서 그 프로그램 타고 글로벌 진출해라.
한 나라에 특화된 산업 거의 없다. 장벽 거의 허물었다.
희석된 지분에 대해 VC가 바라보는 관점은 Co-founder에게 많으면 +고 단순 엔지니어에게 많으면 -다. 한 질문자가 표면적으로라도 지분 조정을 해야할까요 하는 질문으로 미루어 서류상으로 무언가가 되나보다. 연사께서 CEO가 67.4%를 가져야 한다고 말한다. 어떤 배경에서 이런 수치가 나온 것인지 검색해보니 주총에서 보통 결의사항과 특별 결의사항이 있는데 이 중 특별 결의사항을 통과시키기 위해 2/3의 지분이 있어야 한다는 것이다. 결론적으론 안정적인 경영을 위한 것이다.
홍보 담당자는 스타트업 초기에 채용은 부담스러울 수 있기에 스케일 업이 필요 할 때 채용하는 것이 적합하다.
국내 글로벌 진출 프로그램관련해서 무역협회~, 중소기업~ 두 가지 추천해주셨는데 잘 듣지 못했다.
엑센트리 벤처스에서 하는 것은 기업 특징에 따라 다르지만, 크게 두 가지로 첫 번째론 잠재 고객이 누굴까 깊이 고민해서 BM을 재구성해주는 것과 두 번째는 해외 투자자의 관점으로 어떤 것을 수정하면 조금이라도 더 투자를 받을 수 있을지를 도와준다고 한다
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
dp = [[0] * (N+1)]
for _ in range(N):
nums = [0] + list(map(int, input().split()))
dp.append(nums)
for i in range(1, N+1):
for j in range(1, N):
dp[i][j+1] += dp[i][j]
for j in range(1, N+1):
for i in range (1, N):
dp[i+1][j] += dp[i][j]
for _ in range(M):
x1, y1, x2, y2 = map(int, input().split())
result = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]
print (result)
이 문제를 관통하는 핵심아이디어는 아래와 같이, 입력 받은 표의 수를 행축으로 합을 구해준 다음 열 축으로 합을 구해주는 것이다.
행 슬라이딩 합 이후 열 슬라이딩 합까지 해준 테이블을 우리는 DP 테이블이라 하자. 이후 구간합을 구하기 위한 예시로 (1, 1)과 (4, 4)를 입력 받았다면 구간합은 입력 받은 표의 빨간 영역의 합이 될 것이다. (45 = 3+4+5+4+5+6+5+6+7)
빨간 영역의 합을 구하기 위해선 전체 입력 받은 표에서 파란 부분을 각각 빼주고 초록 부분이 두 번 차감되었으니 한 번 더해주는 것이다.
전체 입력 받은 표를 대표하는 값은 (1, 1) ~ (4, 4)의 합이 모두 저장된 DP[$x_2$][$y_2$]에 있다. 또한
첫 번째 파란색 영역을 대표하는 값은 DP[$x_1-1$][$y_2$]에 저장돼 있으며
두 번째 파란색 영역을 대표하는 값은 DP[$x_2$][$y_1-1$]에 저장돼 있으며
세 번째인 초록 영역을 대표하는 값은 DP[$x_1-1$][$y_1-1$]에 저장돼 있다.
따라서 최종 점화식은 dp[$x2$][$y2$] $-$ dp[$x_1-1$][$y_2$] $-$ dp[$x_2$][$y_1-1$] $+$ dp[$x_1-1$][$y_1-1$]이 된다.
import sys
input = sys.stdin.readline
def dfs(K: int) -> None:
tree[K] = -2
for i in range(N):
if K == tree[i]:
dfs(i)
if __name__ == "__main__":
# input
N = int(input())
tree = list(map(int, input().split()))
K = int(input())
# main algorithm
dfs(K)
# output
count = 0
for i in range(len(tree)):
if tree[i] != -2 and i not in tree: # 제거 표시인 -2도 아니고, 자신을 부모 노드로 갖는 노드도 존재하지 않을 경우
count +=1
print(count)
풀이 과정
핵심 아이디어는 DFS 알고리즘을 통해 부모 노드를 제거 한 뒤, 부모 노드에 종속된 자식 노드를 탐색하며 제거해주는 것이다.
가령 예제 입력 4번으로 예시를 들면 다음과 같다.
[-1, 0, 0, 2, 2, 4, 4, 6, 6]은 0~8까지의 노드 번호 위치에 부모 노드를 나타낸 것이다. 이 중 4번 노드를 없애고자 한다면 5번째 인덱스 값인 2를 제거해주어야 한다. 하지만 실제로 리스트에서 제거할 경우 인덱스의 변화가 생겨 일관된 알고리즘 적용에 번거로워지므로 제거했단 표기로 대신한다. -1은 루트 노드로 사용되니 -2란 값이 적당할 것이고 이를 적용하면 다음과 같아진다. [-1, 0, 0, 2, -2, 4, 4, 6, 6]
위 그림에서 노드 4를 -2로 제거 표기 해준 것이다. 이후 4에 종속된 5, 6 그리고 6에 또 종속된 7, 8을 DFS 알고리즘으로 반복 탐색하며 -2로 변경한다면 4에 종속되지 않았던 노드들만 남아 있게 될 것이다.
문제에서 요구하는 핵심은 어떤 한 마을에 우체국이 세워진다 가정할 때, 다른 마을 사람들이 우체국이 세워진 마을에 가기 위해 필요한 거리의 합이 최소가 되는 마을 번호를 찾는 것이다. 크게 두 가지 아이디어가 있다. 첫 번째는 단순하게 모든 마을 사람의 총합을 구하고 [(마을 번호, 사람 수), (마을 번호, 사람 수), ...]의 리스트를 순회할 때 절반이 넘어가는 그 마을 번호를 찾는 것이다. 이 접근이 정답의 핵심 아이디어다. 처음에 이 방법이 희번뜩하며 떠올랐지만 단순하단 이유로 올바른 접근이 아닐 것이란 생각을 하고 다른 방법을 찾게 됐다.
[정답 코드]
import sys
input = sys.stdin.readline
villiage = []
all_people = 0
N = int(input())
for i in range(N):
n_viliage, people = map(int, input().split())
villiage.append([n_viliage, people])
all_people += people
villiage.sort(key= lambda x: x[0])
count = 0
for i in range(N):
count += villiage[i] [1]
if count >= all_people/2:
print (villiage[i][0])
break
두 번째 아이디어는, 반복문을 통해 [(마을 번호, 사람 수), (마을 번호, 사람 수), ...]을 차례대로 돌면서 최소 값을 구하는 것이다. 구체적으로 첫 번째 마을에 우체국이 세워졌다 가정하면 두 번째 세 번째 마을에서 사람들이 오기 위해 얼마나 비용이 드는지를 구하는 것이다. 예제 입력을 예시로 삼는다면
첫 번째 루프 즉, 첫 번째 마을에 우체국이 세워진다면 아래와 같이 총 11의 비용이 든다.
(1번째 마을 - 1) * 3 = (1-1) * 3 = 0
(2번째 마을 - 1) * 5 = (2-1) * 5 = 5
(3번째 마을 - 1) * 3 = (3-1) * 3 = 6
두 번째 루프 즉, 두 번째 마을에 우체국이 세워진다면 아래와 같이 총 6의 비용이 든다.
(1번째 마을 - 2) * 3 = (1-2) * 3 = 3
(2번째 마을 - 2) * 5 = (2-2) * 5 = 0
(3번째 마을 - 2) * 3 = (3-2) * 3 = 3
세 번째 루프 즉, 세 번째 마을에 우체국이 세워진다면 아래와 같이 총 11의 비용이 든다.
(1번째 마을 - 3) * 3 = (1-3) * 3 = 6
(2번째 마을 - 3) * 5 = (2-3) * 5 = 5
(3번째 마을 - 3) * 3 = (3-3) * 3 = 0
* 음수가 되는 부분은 절대값을 취해줘야 함
따라서 총 6의 비용이 드는 두 번째 마을이 가장 우체국을 세우기 적합한 것이다. 이를 구현한 코드는 아래와 같으며, O(N^2)의 시간 복잡도로 인해 시간 초과가 발생한다.
[초기 시도한 코드]
import sys
input = sys.stdin.readline
N = int(input())
village = [0] * (N + 1)
people = [0] * (N + 1)
min_values = [0] * (N +1)
for i in range(1, N+1):
x, a = map(int, input().split())
village[i] = x
people[i] = a
for i in range(1, N+1):
value = 0
for j in range(1, N+1):
value += abs(village[j] - i) * people[j]
min_values[i] = value
del min_values[0]
index = min_values.index(min(min_values))
print (village[index+1])
def recursion(start):
if M == len(picked):
print (*picked)
return
for i in range(start, len(numbers)):
picked.append(numbers[i])
recursion(i)
picked.pop()
if __name__ == '__main__':
N, M = list(map(int, input().split()))
numbers = list(map(int, input().split()))
numbers.sort()
picked = []
recursion(0)
def recursion():
if M == len(picked):
print (*picked)
return
for i in range(len(numbers)):
picked.append(numbers[i])
recursion()
picked.pop()
if __name__ == "__main__":
N, M = list(map(int, input().split()))
numbers = list(map(int, input().split()))
numbers.sort()
picked = []
recursion()
from itertools import combinations
def library():
numbers.sort()
result = list(combinations(numbers, M))
for i in result:
print (*i)
def recursion(start):
if M == len(picked):
print (*picked)
return
for i in range(start, len(numbers)):
if numbers[i] not in picked:
picked.append(numbers[i])
recursion(i+1)
picked.pop()
if __name__ == "__main__":
N, M = list(map(int, input().split()))
numbers = list(map(int, input().split()))
numbers.sort()
picked = []
recursion(0)
#library()
def recursion():
if M == len(picked):
print (*picked)
return
for i in inputValue:
if i not in picked:
picked.append(i)
recursion()
picked.pop()
if __name__ == "__main__":
N, M = list(map(int, input().split()))
numbers = list(map(int, input().split()))
picked = []
inputValue = [i for i in numbers]
inputValue.sort()
recursion()
def recursion(start):
if M == len(picked):
print (*picked)
return
for i in range(start, N):
picked.append(i+1)
recursion(start)
picked.pop()
start += 1
if __name__ == "__main__":
N, M = list(map(int, input().split()))
picked = []
recursion(0)
def recursion():
if M == len(picked):
print (*picked)
return
for i in range(N):
picked.append(i+1)
recursion()
picked.pop()
if __name__ == "__main__":
N, M = list(map(int, input().split()))
picked = []
recursion()
from itertools import combinations
def dfs(start):
if M == len(picked):
print (*picked)
return
for i in range(start, N+1):
if i not in picked:
picked.append(i)
dfs(i+1)
picked.pop()
if __name__ == "__main__":
N, M = list(map(int, input().split()))
# method 1. using combinations in litertools library
# array = [i+1 for i in range(N)]
# result = list(combinations(array, M))
# for i in result:
# print (*i)
# method 2. using maual recursion
picked = []
dfs(start=1)
N, M = list(map(int, input().split()))
picked = []
array = [i for i in range(N)]
n = len(array)
def permutation():
if len(picked) == M:
print (' '.join(str(i) for i in picked))
return
else:
for i in range(1, n+1):
if i not in picked:
picked.append(i)
permutation()
picked.pop()
permutation()
#include <iostream>
using namespace std;
int main(void)
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int T = 0;
int A = 0;
int B = 0;
cin >> T;
if (T<=1000000)
{
for (int i=0; i<T; i++)
{
cin >> A >> B;
if ((A>=1 and A<=1000) and (B>=1) and (B<=1000))
{
cout << A+B << '\n';
}
}
}
return 0;
}
import sys
def dfs(idx, count):
global result
if count == N // 2:
start, link = 0, 0
for i in range(N):
for j in range(N):
if selected[i] and selected[j]:
start += score[i][j]
elif not selected[i] and not selected[j]:
link += score[i][j]
result = min(result, abs(start - link))
for i in range(idx, N):
if selected[i]:
continue
selected[i] = 1
dfs(i+1, count+1)
selected[i] = 0
if __name__ == "__main__":
sys.setrecursionlimit(100000)
input = sys.stdin.readline
N = int(input())
score = [list(map(int, input().split())) for _ in range(N)]
selected = [0 for _ in range(N)]
result = sys.maxsize
dfs(0, 0)
print (result)
import sys
from itertools import permutations
def get_operations(in_operation: list) -> list:
basic_operation = ['+', '-', '*', '/']
operations : list = []
for i in range(len(in_operation)): # [2, 1, 1, 1]
for j in range(in_operation[i]):
operations.append(basic_operation[i])
return operations
def get_min_max_value(operations: list) -> None:
global minimum, maximum
for case in permutations(operations, N-1):
total = numbers[0]
for i in range(1, N):
if case[i-1] == "+":
total += numbers[i]
elif case[i-1] == "-":
total -= numbers[i]
elif case[i-1] == "*":
total *= numbers[i]
elif case[i-1] == "/":
total = int(total / numbers[i])
if total > maximum:
maximum = total
if total < minimum:
minimum = total
if __name__ == "__main__":
input = sys.stdin.readline
N = int(input())
numbers = list(map(int, input().split()))
in_operation = list(map(int, input().split()))
maximum = -1e9
minimum = 1e9
operations = get_operations(in_operation)
get_min_max_value(operations)
print (maximum)
print (minimum)
#include <iostream>
using namespace std;
int main(void)
{
int X = 0;
int Y = 0;
cin >> X >> Y;
if ((X>=-1000 and X<=1000) and (X!=0) and (Y>=-1000 and Y<=1000) and (Y!=0))
{
if (X>0 and Y>0)
cout << "1" << endl;
if (X<0 and Y>0)
cout << "2" << endl;
if (X<0 and Y<0)
cout << "3" << endl;
if (X>0 and Y<0)
cout << "4" << endl;
}
return 0;
}
