• '다음 볼 영상'(youtube) 추천을 위한 large scale multi objective ranking system 제안함
• multi task learning 방식을 제안했는데, ctr 뿐 아닌, 좋아요, 공유 등 multiple competing ranking objectives 가 동시에 존재하는 현실의 상황을 해결하기 위한 것임.
• 방식
  • Multi-gate Mixture-of-Experts 방식을 Wide & deep model 에 적용하고 selection bias 완화를 위한 shallow tower를 제시함.
  • soft-parameter sharing techniques(such as Multi-gate Mixture-of-Experts) 을 통해서 여러 objective를 고려한 ranking을 하는 방법을 제시함.

Introduction

• 시장에서 자주 문제시 되는 '상충 되는 목표에 대한 최적화'를 달성하기 위해 multi task learning 을 이용함.
  • 상충되는 목표 최적화가 필요한 경우의 예 : 영상 재생율 뿐 아니라, 사용자들이 높게 평가하고 친구들과 공유하는 동영상을 추천하고 시청하기를 원하는 경우.
• 시스템에 종종 존재하는 내재적인 편향을 "shallow tower" 라는 방식으로 제거하고자 함.
  • 내재적 편향의 예시 : 사용자가 비디오를 클릭하고 시청한 이유가 단순히 높은 순위에 있었기 때문이며, 사용자가 가장 좋아하는 것이 아니었을 수 있음.
• 평가 방식
  • 1. multitask learning 자체에 대한 평가
  • 2. position bias가 제거 되었는지 평가

Model architecture

Ranking objectives

• 유저의 행동을 아래의 두 가지 기준으로 나눠서 objective 로 설정함.
• 1. Engagement objectives
  • e.g. 클릭, 시청
  • binary classification task(click) 나 regression task(시청 시간)으로 설정
• 2. Satisfaction objectives
  • e.g. 좋아요 클릭, 별점
  • 동일하게 objective 성격에 따라 binary classification task(좋아요 클릭) 나 regression task(별점 수)으로 설정

Modeling Task Relations and Conficts with Multi-gate Mixture-of-Experts

• 과거의 deep learning 을 이용한 multi task learning task 는 좌측과 같은 구조를 이용한다. 그런데 이때 자주 발견됐던 단점이, 두 objective 중 적어도 하나는 single task 로 학습시켰을 때보다 결과가 좋지 않았다. 아마도 서로 다른 objective 에만 기여할 feature 들이 간섭을 하게 되면서 오히려 성능이 떨어진 걸로 보인다.
• 최근 연구에서 이런 단점을 해결해 줄 방안으로 MMoE(Multi-gate Mixture of Experts) architecture 가 제시되었다. 이는 우측의 그림에서처럼 shared bottom layer 위에 expert layer 를 위치시키고, 이 expert layer 의 out connection 을 바로 task layer 로 연결시키지 않고, softmax gate 를 통해서 연결시킨다. 이를 통해 shared bottom을 이용할때 처럼 쓸데없는 정보가 서로 다른 objective에 관여하여 성능이 저하되는 현상을 막을 수 있게 한 것이다.

Modeling and Removing Position and Selection Biases

• Implicit feedback(e.g. click)은 랭킹 모델을 학습하는 데 널리 사용되지만(사용자 로그에서 추출된 대규모의 click feedback을 사용하여 모델을 학습), 이런 피드백들은 기존의 랭킹 시스템에서 생성되었기때문에 편향되어있을 수 밖에 없다.
  • 사용자가 실제 사용자 효용과 사용자 선호도와 관계없이 목록 상단에 표시된 비디오를 클릭하고 시청하는 경향이 있다는게 이런 position bias의 예시라고 볼 수 있고, 이로 인한 문제점들은 다수의 연구에서 이미 확인된 바 있다.
• 이걸 해결하기 위해 shallow tower 를 사용하게 된다. 모델 예측을 두 부분을 figure1의 그림에서처럼 main tower 와 shallow tower로 나누고, main tower에서의 사용자 feature 로 학습하되, shallow tower 에서는 bias에 대한 요소를 학습하게 한다.
• 즉, shallow tower에서는 position bias 학습을 위한 position feature등의 같은 selection bias에 기여하는 피쳐로 shallow tower 를 학습시키고, 이를 main tower의 최종 logit에 추가하는 식으로 학습하게 된다.
• 학습 시에는 모든 위치를 사용하며, position feature에 과도하게 의존하지 않도록 10%의 피쳐 드롭아웃 비율을 적용한다.
• 단 serving 할때에는 position feature를 제거한다.

Experiment

Multitask ranking with MMoE

• live experiment
  • baseline model 로는 shared bottom 형태로 만들고, 단 이때에 공평한 설계를 위해서 model architecture 내의 multiplication 수를 동일하게 한다.
  • MMoE를 썼을때에 모든 메트릭의 지표가 상승함
• Gating Network Distribution
  • 일부 expert들의 결과물이 다른 작업들에서 잘 공유되고 있단걸 볼 수 있음.
• Gating Network Stability.
  • 여러 개의 machine을 사용하여 모델을 학습시킬 때, distributed training strategy는 모델 발산을 자주 야기시키곤 한다.(e.g. Relu death)
  • MMoE에서는 softmax gating network가 불균형한 expert distiribution 문제를 가질 수 있다고 보고되었다. (즉, 대부분의 전문가에 대한 제로 활용으로 수렴되는 것)
  • distribution training을 통해 이 모델에서는 gate network 극성 문제가 발생할 가능성이 20%라는 것을 관찰했다.
  • 이 문제를 해결하기 위해 gating network에 drop out을 적용했고, 10%의 확률로 expert의 활용도를 0으로 설정하고 softmax 출력을 다시 regularization해서 모든 gate network의 극성을 제거한다.

첫번째 섹션에서는 open ai 의 약력부터, gpt에 대한 간단한 개요, 트랜스포머에 대한 소개, 계정 생성하는 부분까지로 이어지는데, 여기까지 본 강의 내용을 요약해보았다.

Open ai 약력

2015년 연구만을 위한 비영리단체로, 일론머스크를 포함하여 아주 유명한, 몇몇 개인의 투자로 설립되었다. 처음 설립된 이래로 내 주변 사람들 모두 저 저 회사가 얼마나 오래 비영리 단체로 유지될 수 있을지 의심하고 있었는데, 일론머스크 이탈, 산하에 영리단체 신설, 2020년 gpt3 api 를 유료 형태로 open 등의 결국은 어느정도 수익화하는 모습이었고, 그 이후로 DALL-E(generate image from text), Codex(generate code based on language input), chat GPT 를 잇달아 공개했다. 일부 영리 프로젝트가 있기는 하지만, 여전히 open ai 자체는 비영리 단체로 유지되고 있다. 그러나 2021과 2023년에는 마이크로소프트에서 추가 투자를 받으면서 GPT-4 지적재산권 라이센스와 기타 제품 상용화 독점계약을 얻어서, GPT4까지는 마이크로 소프트 소유라고 생각해도 되지 않나 싶다.

GPT와 prompt

• Generative Pre-Trained Transformer
• 생성형 language model 이라 initial text 를 주면 그 다음에 이어질 text들을 생성해내는 방식으로 사용할 수 있으며, 이때의 initial text를 prompt라고 부르고, 이 prompt를 잘 생성해내는 과정을 prompt engineering 이라고 한다.
• 
• gpt 와 상호작용하는 방법은 크게 아래의 두 가지라고 볼 수 있다.
  • completion : 하나의 text prompt를 주는 방식(Expects a single text prompt)
    • (gpt4는 미지원)
  • chat : chat based format 으로 message 의 list를 주는 방식(Expects a list of messages in a chat-based format)

Transformer 란

• Neural network 를 구분하는 방법이 여러가지가 있을텐데, 여기서는 CNN, RNN, Transformer 로 구분짓고, 있다.
• Natural language 에 대한 연구가 처음 시작될때에는 RNN을 기반으로 했었는데, 여기엔 여러 단점이 있었는데,
  • token을 하나씩 순차적으로 인식하다보니, 분량이 긴 텍스트는 분석이 어렵다는 점이 있었고,(gradient banishing)
  • 속도가 느려서 많은 데이터를 학습시키기가 어렵고,
  • 순차적으로 처리되다보니, 병렬화가 불가능했다.
• 이런 단점을 극복하고자 transformer가 등장했는데, 이 경우
  • 전체 input을 순차 처리 하지 않다보니, (텍스트를 순차적으로 인식하는 대신 positional encoding을 이용한다) gradient banishing 문제가 사라졌고,
  • 병렬화 또한 가능해졌다

positional encoding

• 순차 처리할 필요가 없어지고(위치를 encoding 해서 이미 알고있기때문에!)
• 어순의 중요도를 파악하는 역할을 해줄 수 있다.

attention

• 입력 데이터의 특정 부분에만 선택적으로 주의를 기울이는 방식으로, 입력 데이터 각 부분에 어텐션 점수를 매겨서 요소들의 가중치나 평균값을 구하게 된다.
• 이렇게 어디에 집중해야할지를 모델에 배우는게 가능지면서, 데이터가 충분하면 문법, 어순, 시제 동사 등의 언어 작동원리를 알아서 파악하는게 가능해졌다!
• attention 자체는 이미 sequence to sequence model 에서 등장했던 바가 있고 (이건 large language model 이 나오기 이전의 일이다... ㅎㅎ 옛날 같지만 별로 안됐다ㅠ), 인코더가 해당 단어를 vector 화 한 결과는 디코더가 그 단어를 예측할때에 쓰는 vector 와 같을거라는 가정에서, 각 출력에 대응되는 입력상태를 더 많이 참조하도록 가중치를 주자는 컨셉에서 등장했다. (이전에 til 하면서 정리를 했었...)
• 2018 년 cmu의 nlp 강의를 들으면서 요약했던 자료도 있는데,,, 이것도 꼭 다시 정리를 해놔야겠다... ㅎㅎ 과거의 업보가 많다...

open ai 계정

• chat gpt 를 써봤어서, 이미 계정은 있었다.
• platform.openai.com의 document 페이지에서 쓸 수 있는 api 들은 다 하나씩 찾아볼 수 있고
• api key 페이지에서 secret key 를 생성해야한다. 여기서의 key를 복사해서 보관하고 있어야 계속 쓸 수 있다.
• api document 에서 pricing도 확인할 수 있는데, 무료인 api는 하나도 없다... 카드 등록해두고, 한달에 쓰는 돈의 limit 을 꼭 걸어놔야 한없이 빠져나가지 않는다 ㅎㅎㅎ

create text project

• pip install openai 로 필요한 모듈을 설치할 수 있는데, 강의가 만들어진 이후에 업데이트가 꽤 많았던 건지,,, 강의에 나온 create text project예제로 나온 코드를 그냥 실행시키면 실행이 안된다. (pip 할때에 version을 1.0 이하로 지정해두거나, 아니면 새 버전 방식으로 콜해야한다)

이 논문에서는 Bandit 알고리즘을 multi objective 문제 해결에 사용할 수 있는 방법을 제시하고 있다. 언제부터인가 추천 시스템에서 bandit을 활용한 논문들이 싹 사라져버렸다. ㅠ 그럼에도 bandit은 streaming 에 쉽게 활용할 수 있고, cold start 문제에 적용하기도 비교적 쉽기에, 이 연구를 발견했을때에 매우 반가웠다. :)

Abstract

온라인 추천시스템의 경우 multi-stakeholder 의 objective 를 만족시켜야 하는경우가 종종 있다. 예를들어 아래와 같은 경우를 들 수 있다. - 구매자와 판매자를 모두 만족시켜야하는 amazon - guest 와 host 를 모두 만족시켜야하는 airbnb - rider 와 driver를 모두 만족시켜야하는 uber - listener와 artist를 모두 만족시켜야하는 spotify

이 논문에서는 contextual bandit 을 multi objective setting 으로 확장시켜서 multi-stakeholder를 만족시키는 추천 시스템을 만드는걸 목표로 한다. 기본적으로는 contextual bandit 세팅하에서 여러개의 objective 를 동시에 공정한 방식으로 학습하는데, 알고리즘 진행은 아래의 두 과정으로 요약할 수 있다.

1. GGI(Generalized Gini Index) 라는 aggregation function이용해서, 여러개의 objective 를 결합함과 동시에 밸런싱한다.
2. online gradient ascent learning algorithm 사용해서, GGI 로 scalarise된 objective들에 대한 reward vector를 최대화 시킨다

Introduction

Background and Related work

Multi objective Optimization

• 전통적인 MOO(Multi objective optimization) 방식은 Pareto front 를 바로 찾아내는걸 목표로 한다.(Pareto front line 을 그어서, 여러 objective 모두에서 손해를 보지는 않는 포인트를 찾아내는 방식)
• 이 외에는 aggregation function 등을 활용해서 vector 형태의 objective(여러 objective)를 scala 화 해서 최적화 시키는 방식 등이 있다. (aggregation function 에는 weighted sum 이나 regularized maximin fairness policy 등이 있을 수 있음)
• 이 논문에서는 위에서의 두 번째 방식인 aggregation function을 이용하는 방식을 취하는데, 이때에 generalised Gini function을 이용하고, 이 방식은 total ordering과 선형적 우선순위 모두에 대해서 일반화를 잘 시킨다고한다.
• MOO 를 supervised learning 방식으로 해결했던 과거 접근법과 달리 이 논문의 방식에선 더 interactive하고, user feedback 을 기반으로 adaptive 한 learning이 가능한 방식에 초점을 맞췄다.

MOO in Search & Recommender system

• recommendation에서의 MOO를 시도했던 예시로 collaborative filtering의 확장 또한 포함될 수 있을 것이다.
• 기존 방식과 이 논문에서 소개한 접근 방식의 주요 차이점은 밴딧기반 세팅에 초점을 맞췄다는 점인데, 그런만큼 item 간의 유사성 정보가 불확실 하거나, 새로운 item 이 들어왔을때에 더 큰 힘을 발휘한다.

Bandits & Multi-objective Bandit

• Multi objective multi-armed bandit, multi-objective variants of contextual bandit들에 대한 연구는 최근 주목을 덜 받고 있는 편이다.
• 요즘 주목받는 연구들은 그 대신 item 간의 유사성 정보(item similarity)가 이미 있다거나, objective 가 여러개더라도 dominant 한 하나가 있는 상황을 가정한 경우가 많은데, 실제 비지니스 현장에서는 이런 상황들은 많지 않다.(특히 사용자 행동 데이터를 기반으로 reward를 도출해야하는 상황에서는 더 그렇다..)

Objectives & stakeholders

Objective Definitions

• 이 논문은 spotify에서 작성된 만큼, 유저의 음악 스트리밍 상황을 가정한다. 두 가지 objective를 목표로 둔다.

1. user centric objectives
   • stream : 유저의 음악 스트리밍 시간
   • clicks : 플레이 리스트 클릭 수
   • songs played : 재생한 음악 수
2. two artist and platform centric objectives
   • Diversity : 추천된 set 에서의 gender 다양성
   • promotion : platform 에서 promotion 하고자 하는 아티스트의 음악의 수

• 위 objective 들을 보면 일부를 최적화 하는게, 다른 objective 에 좋지 않은 영향을 줄 수 있도록 설계되었음을 알수 있다.
• 이런 서로 상충되는 objective 들 간의 미묘한 밸런스를 맞추는 것에 이 알고리즘도 주안점을 둔다.

Contextual Bandit based Recommendation

• 다른 여타 Contextual Bandit algorithm 처럼 이 알고리즘에서도

  1. context feature 들을 관찰하고
  2. 이 feature 들이 의해서 k개의 가능성들 중 a라는 action을 선택할 수 있게 되는데
  3. 주어진 context와 action에 대한 reward가 분포로서 주어지게 될 것이고, 이에 따라 action을 결정할 수 있게 될 것이다.

• 위의 과정에서 이 논문에서는 아래의 feature 들을 활용했다.

• Context feature:

  • (i) user: 나이, 성별, 사는 지역, 장르 선호도
  • (ii) playlist: 아티스트, micro or macro 장르, diversity, 인기도 등
  • (iii) affinity between the user and the playlist: user와 playlist 사이의 과거 interaction 들(streams, skips, likes, saves)
  • (iv) 그 외... (the day of the week and the time of day)

• Actions: selecting a set to recommend to the user.

  • 사용자에게 playlist(a collection of tracks)를 제공하는 세트 기반 추천
  • 각 트랙은 특정 아티스트로 구성

• Rewards:

  • 전통적인 user-centric system 이라면 user들이 얼마나 이 추천을 좋아했는지를 확인할테지만,
  • 이 논문에선 multi- stakeholder recommender system을 지향하기에, reward function에서도 vectorial rewards에 대해서 최적화시킨 arm 이 선택되는 방식을 취한다.

Multi-objective Contextual Bandit

arm selection strategy

• 다른 bandit 알고리즘이 그렇듯, 아래처럼 arm selection 함수를 정의할 수 있다.

  • alpha : arm 선택여부 / 뮤 : k번째 arm 선택시의 reward
  • G : scalarisation function (여기서는 GGI 쓴 것이고, 이에 대한 설명은 아래에 있다!)

• GGI (Generalised Gini Index)

  • (본인은 이 함수를 처음 봤는데, 대충 1981년에 쓰여진 논문에 등장하고 있는걸로 확인했고, 그 특성에 대해서만 아래처럼 알고 있으면 될듯하다...)
  • 
  • 𝜎 permutes the elements of 𝒙 such that (𝒙𝜎 )𝑖 ≤ (𝒙𝜎 )𝑖+1
  • GGI 자체는 좀 생소하지만, 아래와 같은 속성을 갖는 인덱스이기때문에 여기서 활용이 가능하단걸 알 수 있다.
    • GGF는 strictly monotonic하기때문에, 이 함수를 maximize시킨 지점이 pareto front(여러 objective 에 대한 최적의 해 중 하나에 해당하게 됨) 에 존재하되, weight 에 따라서 다른 지점의 점을 선택하게 된다.
      • GGF exhibits afairness property under the Pigou-Daltontransfer: if 𝒙𝑖 <𝒙𝑗, then 𝐺𝒘(𝒙′)>𝐺𝒘(𝒙) for 𝒙𝑖′=𝒙𝑖+𝜖 and𝒙′𝑗 =𝒙𝑗−𝜖 where 𝜖<𝒙𝑗−𝒙𝑖 and 𝒙𝑘′ =𝒙𝑘 for𝑘≠𝑖,𝑗.In other words, an equitable transfer of an arbitrarily small amount from a larger component to a smaller component is always preferable.
    • -> 이 말에 대해서 완벽히 해석하긴 좀 어려워서 일단 본문을 가져왔다... 그치만 대충만이라도 요약을 하자면 이 함수는 Loss 가 높은 objective에 더 weight를 많이 주어서 더 많이 고려하여 업데이트 하면서도, 전체 objective 들에 대해서 공평하게 aggregate 를 해준다는 의미 인것으로, 여러 objective를 공평하게 스칼라화할때에 이 function을 쓰는게 유효하다는걸 강조하는 내용인걸 알 수 있다 ㅎㅎ

• Regret 을 정의하는 과정

  • (arm selection strategy에서) 시점 t에 얻을 평균 reward
  • T시점에서의 regret은 아래처럼 정의 가능함

• regression으로 풀수도 있겠으나, matrix 가 커지면 쉽지 않을 것

  • First estimate parameter 𝜗∗ via 𝑙2-regularised least-squares regression with regularisation parameter 𝜆 > 0 at each round 𝑡 ,:

• Online gradient ascent

  • 아래를 최대화시킬 alpha를 찾는 방식으로 문제 해결
  • GGF의 concave 성질에 따라서 아래처럼 풀 수 있고,
  • 이걸 optimize시켜도 되지만,
  • 근데 위의 것을 linear programing으로 풀면 계산량이 많아서 아래처럼 gradient ascent로 풀 수 있음.

Experimental evaluation

(이 논문에서 실험 분석할때에 그래프 형태가 아주 신박하다. 실무에서 활용해볼 기회가 있길!)

Reward base evaluation

• 이 실험에서는 다양한 bandit 알고리즘에 GGF 로 정의한 reward를 넣었을때에 어떤 알고리즘이 reward를 가장 잘 최적화 시키는지를 확인한다. 위의 그래프에서는 아래의 세가지를 확인할 수 있다.
  1. MO-OGDE(Non contextual bandit)와 random strategy 간 비교를 했을때엔 둘의 결과가 다르지 않았다는 걸로 봐서, context 가 중요한 역할을 한다는 걸 알 수 있다.
  2. mixed strategy(아마도 thompson sampling 등 sampling 기반 선택을 하는 알고리즘?) 가 pure strategy(아마도 항상 max 값을 고르는 greedy 한 알고리즘?) 보다 항상 결과가 좋았던걸로 보아서, greedy 한 선택보다는 probability distribution을 바탕으로 선택하는게 더 좋다는 걸 알 수 있다.
  3. 여러 알고리즘 중 MO-LinCB에서 GGF가 가장 잘 최적화 된다.

Optimizing for multiple user metric

• 유저 메트릭(clicks, stream, songs played)관점에서 봤을때에 각 알고리즘을 비교해보면 세가지를 알 수 있다.
  1. 위 그래프에서 e-g(c), e-g(l), e-g(s)는 각각 click, length of stream, songs played의 한가지 메트릭만 최적화 시킨 single objective algorithm인데, 이 들 셋 중에서 비교를 해보면 click에 대해서 최적화시킨 알고리즘(e-g(c))이 세가지의 모든 메트릭에 대해서 다른 알고리즘에 비해 우위를 보인다는걸 알 수 있다. 이로써 click 이 feature 로서 강력하며, 다른 objective 들과의 상관성 또한 크게 있음을 알 수 있다.
  2. 모든 메트릭에서 single objective algorithm(e-g(c), e-g(l), e-g(s)) 보다 objective algorithm(e-g(MO), MO-LinCB)의 성능이 항상 더 좋았다.
     • 하나의 정보에만 집중해서 학습시키는 것 보다 여러가지의 정보를 혼합해서 좋았을때에 더 효과가 있음을 알 수 있었다!
  3. MO-LinCB 알고리즘의 성능이 가장 좋았다.

Impact of Promotional Objective

• promotional objective 는 다른 object 들과의 상관관계가 없음을 위의 히트맵으로 확인할 수 있었는데, 이건 objective 들간 competing이 생길 수 있다는 것을 의미하기도 한다.
• 그러나 promotional objective(여기서는 gender diversity) 를 포함시켰을때에, 다른 수치들이 떨어지지 않는다는게 보여서, 상반된 objective 간의 zerosum 게임이 아니라는 것을 확인할 수 있었다.

Comparing Multi-optimization Methods

• 아무 알고리즘에서나 MO 가 통하지 않음을 확인함
• e-greedy 는 MO해도 성능이 나아지지 않음

Time series anomaly?

• 집단의 공통적인 trend, seasonality, cycle 형태를 따르지 않는 데이터
• 다른 데이터들과 ‘상당한 수준으로’ 다른 데이터
• 위의 다섯개의 점이 전형적인 anomaly

왜 이게 중요한가?

• anomaly 의 발생은 “new normal”에 대한 새로운 정의, regroup, restructure business strategy, decision making process 가 필요한 시점임을 보여줄 수 있음
• anomaly 를 항상 트래킹하고, 상세 특징에 대해서 연구해두는게 필요함.

어떻게 알아내지?

• 주로 아래 세가지 방법으로 알아낼 수 있음
  1. Predictive Confidence Level Approach
  2. Statistical Profiling Approach
  3. Clustering Based Unsupervised Approach

1. Predictive Confidence Level Approach

   • 과거 데이터로부터 전체적인 트렌드, seasonality, cycle pattern 을 읽어와서 predictive model 을 만들어내는 것 부터 시작
   • 이 predictive model 로부터 MAPE(Mean Absolute Percentage Error)를 찾아내는 것
   • 신뢰 구간을 찾아내거나 predictive model 로부터의 신뢰 가능한 band 를 찾아내고, 이 band 밖으로 떨어지는 data point 들을 anomaly로 간주하는 것
   • Predictive model 만들어내는 유명한 방법들
     • ARIMA, SARIMA, GARCH, VAR
     • 이 외의 Regression, LSTM 등의 방법론 들
   • 장점
     • local outlier 를 찾아내기 편하다
   • 단점
     • predictive model 의 효과성에 지나치게 의존하는 경향이 생길 수 있음
       • predictive model 의 어떤 loop hole 이 있어도, 잘못된 결과(false positive, false negative)를 낼 수 있음

2. Statistical Profiling Approach

   • 통계학자나 수학자가 가장 좋아하는 방법
   • 경제학, 금융 섹터에서 효과가 좋다고 알려짐
   • 통계적 모델이나 profile을 만들ㅇ어 내는게 가장 빠르고 효율적인 방법 → 이방법을 쓰면 통제되고, 설명 가능한 결과를 만들어낼 수 있다.
   • 과거 데이터의 mean, median moving average 와 standard deviation을 이용해서 upper bound, 혹은 lower bound 를 만들어 주는 방식(즉, 통계적 값에 band 를 생성), 이 band 밖을 벗어나는 data point 를 anomaly 로 상정
   • 장점
     • 편해서 복잡한 방법론 적용해보기 전에, baseline approach로 유용함
     • 변덕이 심한 데이터에 효과적임(predictive model 알고리즘은, 이런 데이터에서는 실패하는 경향이 크다)
   • 단점
     • local outlier 를 잘 못잡아낸다.(위의 그림상에 못잡아낸 세개의 포인트들)

3. Clustering Based Unsupervised Approach

   • labeled data 가 필요하지 않아서 유용하다.
   • 근데 위험성 혹은 bottleneck으로는 clustering 알고리즘을 적용할때에 몇개의 cluster를 만들어낼지를 직접 손으로 넣어야한다는 단점
     • cluster 수를 추정하는 여러 테크닉들이 있지만, time series data 에서는 dynamic 하게 적용하기가 어렵다!
   • → DBSCAN
     • cluster 수를 안넣어줘도 된다는 점에서 자주 쓰이는 알고리즘
     • (cluster 당 최소 data 수, cluster 간 distance만 넣어주면 됨)
   • local anomaly 잡아내려면 rolling window based DBSCAN을 적용해줘야할 것.

Spark executor 에서 메모리가 부족할 경우 yarn 은 자동적으로 이 잡을 죽여버린다. 이때에 worker 의 log 를 보면 "Container killed on request. Exit code is 137" 이라는 메시지가 남게 되고, executor 의 stdout까지 잘 살펴보면 "java.lang.OutOfMemoryError: Java heap space" 이런 메시지가 있단걸 확인할 수 있다.

해결방법

1. driver 나 executor 의 메모리를 늘린다.

   • 어떤 container 가 이 에러를 발생시켰는지를 확인해서 spark.executor.memory 혹은 spark.driver.memory의 parameter 값을 튜닝한다.
   • emr 이라면 master node 에 접속해서, /etc/spark/conf/spark-defaults.conf 에서 해당 값들을 수정한다.
   • 하나의 잡에 대해서만 늘리고 싶다면, 해당 잡을 spark submit 할때에 spark.executor.memory 혹은 spark.driver.memory의 값들을 수정한다.
   • 근데 만약 node 에서 이미 maximizeResourceAllocation 등의 옵션을 쓰고 있다면 이런 조치를 취할 수 없다.

2. Spark partition 을 늘린다.

   • partition 의 수를 늘리면 하나의 spark task 에서 처리하는 데이터의 양이 줄어들게 되므로, 하나의 executor 가 소모하는 메모리의 양이 줄어들게 된다.
   • partition 의 수를 늘리고 그 수에 의해 repartition 하게 하면 된다.

     val numPartitions= 500
     val newDF=df.repartition(numPartitions)

   • 만약 이 에러가 join, groupby 등의 wide transformation 과정에서 발생하는 것 이라면 shuffle partition 의 수를 늘린다. (default 값은 200이다)
     • emr 이라면 master node 에 접속해서, /etc/spark/conf/spark-defaults.conf 에서 spark.sql.shuffle.partitions의 값을 200이상으로 바꿔주거나
     • spark submit 할때에 해당 parameter 를 바꿔주면 된다.

3. executor 의 core 수를 줄인다.

   • executor 의 core 수를 줄이면 하나의 executor 에서 동시에 돌아가는 task 의 수가 줄어들기때문에 사용되는 메모리가 줄어들게 된다.
     • emr 이라면 master node 에 접속해서, /etc/spark/conf/spark-defaults.conf 에서 spark.executor.cores의 값을 줄여주거나,
     • spark submit 할때에 해당 parameter 를 바꿔주면 된다.

• time dependent 한 feature 라면 -> 지금까지 user 가 click 을 몇번 했는가 등 -> training time 동안 계산해서 넣는건 쉽지 않다(그 이전까지만의 값으로 잘 넣아야한다.)

• 데이터 수집 자체에 문제가 있을 수 있음 -> 이들에 있어서 큰 변화가 없는지 모니터링하는 시스템이 있어야한다.

[offline evaluation]

• baseline model(simplest possible model) - 과의 비교 필요

  데이터의 분리

• gold standard 는 데이터를 세개로 나누는 것
  • training, evaluation, test
• 교과서에서는 세개로 random하게 나눈 후 k-fold cross validation 하라고 나옴.
• 현실에서는 progressive evaluation을 많이 사용한다
  • older data로 학습, newer data로 evauation, test

Evaluation

뭘 위해 모델을 만드느냐에 따라서 evaluation 방법이 달라져야한다.

• first clicker를 위한 모델이라면
  • training할때에 first clicker가 아닌사람들을 다 빼버리는거는 데이터 손실이 클 것
  • (small amount of specific data) vs (lots of non-specific data)

  • 이럴때는 실험을 통해 결정하자 e.g. training 에서는 다 쓰고, validation, test 할때에 first clicker에 대한 정보만 쓰기 와 training 부터 first clicker만 쓴 것을 비교해서 효과가 나은걸 쓴다!

• 만약 evaluation 결과가 통계적으로 유의하지 않다면 데이터의 양을 늘려야할텐데, 이때에 recent data를 쓰는건 여전해야함을 잊지 말것(online 에서도 유효하게 만들어야함)

calibration

• calibration
  • (sum of predictions/sum of labels)의 값이 training 결과, validation 결과, test 결과에서 계속 유지되는지 확인해야한다.
  • 더 정확하게는 데이터를 특정 기준으로 나눈 후에도 계속 유지되는지까지 꼼꼼하게 확인하는게 좋다
• evaluation 자체를 (first clicker로 나눴던 것 처럼) 작은 그룹들로 나눠보는게 의미가 있을 수 있다! -> 어디서 성과가 나오는지를 알아볼 수 있게될 것

[feature]

• output 에 대한 정보를 갖고있어서는 안된다 -> feedback loop 에 빠질 수 있음(model 에 의해 영향받는 feature 가 될 수 있는 것), 다른 feature 들의 정확한 영향력을 계산할 수 없음
• outlier 나 dramatic change 가 있는지에 대한 monitoring 이 있어야함
• training때에 feature 마는 코드와 online testing 할때에 feature 마는 코드는 동일해야한다.
• feature 의 semantic 은 어떻게 해도 변하지 않음.(ranking team 이 front team과 함께 일하는 그림이 좋은 그림)
• 뭔가 semantic 을 변화시키고 싶다면, 기존 feature 를 삭제하지 말고, 변화시킨 후 대신 적용해보고, 성능이 기존보다 좋을때 그때 deprecate한다.

feature leakage

training time 에는 사용한 feature 를 prediction time 에 사용할 수 없는 경우.

• prediction 할 당시에 모를만한 데이터는 제거한다
• data cross validation을 할 것
• leaky 하다고 여겨지는 변수가 있다면 빼고 다시 돌려봐라
• near-perfect model accuracy 는 경고신호
• 과하게 feature importance가 높은 feature 가 있는지 확인하라

feature coverage

• 특정 feature 가 corruption, noise가 있을 수 있을 것
• 이때 해당 feature 의 믿을 만한 정도를 feature coverage라고 함.
• e.g. birth day 같은 feature 들

[model]

linear model 에 대한 고려

• linear 하지 않은 상황들이 막 생길 수 있지만 특정 조건을 미리 줘서 각 조건에 대한 linear model 들을 따로 만들수도 있다.
• density feature 들을 decision tree로 만들고 나서 이걸 linear model 의 feature로 만들수도 있다.
• object detection deep learning model 을 만든다음 마지막 layer 를 more specialized 된 형태로 만들수도 있음

  bias variance model

  • calibration 이 잘 된 것 같아도 데이터를 쪼개가면서 보다보면 특정 그룹에서는 calibration 이 잘 안맞게 마련. 여기서 뭐가 잘못됐는지를 확인해봐야한다.

[Experiment]

1. Minimize the time to first online experiment

• negative feedback 을 잘 예측하는 모델을 만들었어도 전체의 sentiment 가 어떻게 변했는지는 여기서 확인해야함

2. Isolate engineering bugs from ml performance issues

• 코드를 바꿔서 생긴문제인가, 모델을 바꿔서 생긴 문제인가를 고려해봐야함.
• identity transform 으로 비교해봐야한다.

3. test model in the presence of real world(feedback loops)

• 어제는 이걸로 서빙하고, 오늘은 이걸로 서빙해서 발생하는 문제라면 backtest 를 해본다 (old test model 99%, new candidate 1%로 테스트(front test) 했다면 갈아치운 후에는 1% old model, 99% new model 로 테스트(back test)해볼것)

4. Tips

• be able to triangulate the cause of any changes
  • 한번에 하나만 테스트해서 뭐때문인지를 분명히 알 수 있게 해야한다.
• measure the right thing
  • metric 이 제대로 작동하는지 확인해보자 (값에 무조건 1을 더했을때에 어떻게 변하는지 확인해보는 등)
• have a backup plan
• calibrate
  • average prediction 가 average response rate와 일치하는지 확인할 것
  • sanity checking performance
  • miscalibration means
    • training time : hasn't learned properly
    • testing time : doesn't generalize well
    • online testing time: online/offline gap

중복금지 (DRY, OAOO)

• Do not Repeat Yourself, Once only once
• 코드에 있는 지식은 단 한번, 단 한곳에 정의되어야한다.
• 그렇지 않을경우
  • 오류 발생이 쉬워진다 (여러 반복중에 하나라도 빠트리면 버그발생)
  • 비용이 비싸다 (변경에 더 많은 시간이 쓰이게 될 것)
  • 신뢰성이 떨어진다 (여러 코드를 변경해야하는 경우 사람이 모든 인스턴스의 위치를 기억해야하게 됨)

    과잉 엔지니어링 금지 (YAGNI: You ain’t gonna need it)

• 유지보수가 가능한 소프트웨어를 만드는 것은 미래의 요구사항을 예측하는 것이 아니다
• 오직 현재의 요구사항을 잘 해결하기 위한 소프트웨어를 작성하고 가능한 나중에 수정하기 쉽도록 작성하는 것이다.

KIS(keep it simple)

• 디자인이 단순할수록 유지 관리가 쉽다.

  EAFP(Easier to ask forgiveness than permession) vs LBYL(Look before you leap)

• 실제로 동작하지 않을때 대응한다 vs 도약하기 전에 무엇을 사용하려고 하는지 확인한다.
• 파이썬은 EAFP 방식으로 만들어졌고, 그렇게 사용할 것을 권한다

  #이것보단
  if os.path.exists(filename):
  with open(filename) as f:
    ...

  #이렇게 쓸 것.
  try:
  with open(filename) as f:
    ...
  except FileNotFoundError as e:
  logger.error(e)

계약에 의한 디자인

• 관계자가 기대하는 바를 암묵적으로 코드에 삽입하는 대신 양측이 동의하는 계약을 먼저 한 다음 계약을 어겼을 경우는 명시적으로 왜 계속할 수 없는지 예외를 발생시키라는 것.
• 계약 작성이 필요하고 단위테스트 추가해야할 수도 있으나 품질은 장기적으로 보장된다.

방어적 프로그래밍

• 에러핸들링
  • 값대체
  • 예외처리
    • 함수에 예외가 많을수록 호출자가 호출하는 함수에 대해 더 많은 것을 알아야만한다(호출할때마다 발생가능한 부작용을 염두에 두고 문맥을 유지해야하기 때문)
    • 처리할 예외가 많다는건 응집력이 약하고 너무 많은 책임을 가지고 있다는 의미인 것. → 함수를 분리한다 (event connection 맺는 일과 send를 하면서 event parameter value 를 확인하는 함수)
    • The zen of python
      • 예외는 조용히 처리되어선 안된다, 보다 구체적 예외를 사용해야한다.

관심사의 분리

• 책임이 다르면 컴포넌트, 계층 또는 모듈로 분리되어야한다.
• 파급효과를 최소화하여 유지보수성을 향상시키기 위한 것.
  • 파급효과 : 어느 지점에서의 변화가 전체로 전파되는 것.
• 나머지 부분에 대한 영향성을 최소화하면서 코드를 수정하거나 리팩토링 하고싶다면 적절한 캡슐화가 필요하다
• 응집성과 결합성
  • 응집성 : 객체가 작고 잘 정의된 목적을 가져야하며 가능하면 작아야한다.
  • 결합성 : 두 개 이상의 객체가 어떻게 의존하는지를 나타냄. (객체 또는 메서드의 두 부분이 서로 너무 의존적이라면 바람직하지 않다)
    • 너무 의존적일경우의 부작용
      • 낮은 재사용성 : 만약 어떤 함수가 특정 객체에 지나치게 의존하는 경우 또는 너무 많은 파라미터를 가진 경우 이 함수는 해당 객체에 결합되게 된다. 즉 다른 상황에서는 이 함수를 사용하기가 매우 어렵다.
      • 파급효과 : 너무 가깝게 붙어 있게 되면 두 부분 중 하나를 변경하면 다른 부분에도 영향을 미친다.
      • 낮은 수준의 추상화 : 두 함수가 너무 가깝게 관련되어 있으면 서로 다른 추상화 레벨에서 문제를 해결하기 어렵기때문에 관심사가 분리되어있다고 보기 어렵다.

• MATOMO를 이용하여 Java script tracker 방식으로 로그를 수집하면 아래와 같은 경우에 대해서 로그 수집이 불가능해진다.
  • JavaScript를 disable 해둔 사용자 로그
  • 내가 제어하지 않는 웹사이트에서 페이지가 조회된 경우(타사 마켓 플레이스 등)
  • 뉴스레터 이메일에 대한 접근 로그

이런 때에는 matomo image beacon 방식으로 방문자를 추적할 수 있다.

image beacon 방식의 한계

• 단, 이방식을 활용하게 되면 java script를 사용하지 않으며 자사 쿠키를 생성할 수 가 없게 되어서, 방문자 로그 생성이 어려워질 수 있다.
• 아래와 같은 것들에 대해 tracking이 불가능해진다.

  • Referrers, including Search Engine Keyword, Referrer Website URL and Social network URL
  • Screen resolutions
  • Browser plugins
  • Page titles
  • Time in local user’s timezone
  • The image tracker code also does not create first party tracking cookies which results in some information being lost.
  • Files that were clicked and downloaded (Download)
  • Links to an outside domain that were clicked (Outlink)
  • Pages generation time (the time it takes for webpages to be generated by the webserver and then downloaded by the user)

• 그래도 아래와 같은 것들은 잘 트래킹 된다.

  • User IP address
  • Date and time of the request
  • URL of the page being viewed (Page URL)
  • Location of the user: country, region, city, approximate latitude and longitude (Geolocation)
  • Main Language of the browser being used (Accept-Language header)
  • Browser, operating system, device used (desktop, tablet, mobile, tv, cars, console, etc.), brand and model

참조

1. https://matomo.org/faq/how-to/faq_176/
2. https://matomo.org/faq/general/when-tracking-visitors-using-an-image-beacon-instead-of-the-javascript-tracker-what-are-the-differences/

• 오픈 소스 웹 분석 플랫폼(유료 cloud버전도 있기는 함)
• 웹 사이트를 방문하는 모든 사용자의 행위를 평가 및 분석 (로그 데이터를 저장하고, 이에대한 보고서 제공)
• 즉 원하는 웹사이트에 matomo tracker script를 심어놓으면 그와 관련된 분석데이터(클릭 로그, 유저 행동데이터) 등에 대한 데이터를 수집, 저장하고, 이에 대한 보고서 또한 제공해준다.

  Visitant - 웹 사이트 방문자 수, 페이지 뷰, 방문기간 등의 정보 기록 및 분석 Behavior - 웹 사이트 방문자의 행위 기록 및 분석 Acquisition - 웹 사이트 유입 경로 기록 및 분석

• Apache 웹 서버에서 구동되며 2018년 6월 기준 약 1,455,000개 이상의 Web Site에서 사용되고 있음

MATOMO 작동 원리

• website page에 javascript tracker를 포함시켜서 배포한다.
• tracker 는 tracker가 포함돼있는 페이지에서 데이터를 모아다가 http 추적 api를 호출해서 matomo에 보낸다.
• 데이터 archiving task가 돌아가고, preprocessing이 on the flow 로 혹은 cron task로 실행된다.

plug in architecture

• matomo codebase
  • Matomo core - extention point통해서 application base제공
  • Plugins - extention point를 사용자 행동이나 content를 application에 더하는데 사용
    • 두 가지 종류의 plugin 존재
      • 기본형 플러그인 : matomo 기본기능 (배포판에 있는 기능들
      • 선택형 플러그인 : 사다 쓰는 것...(plugins 폴더에 복사해서 쓰거나, https://plugins.matomo.org/이런데서 받을 수 있음)

Interface

user interface

• 진입점은 index.php 이 파일이 모든걸 initialize 하고, FrontController class를 호출한다.
• matomo의 user interface는 html, javascript로 돼있음
• 몇몇 파트는 php controller에 의해 돌아가는 html document지만, 몇몇 파트는 anguler js로 짜여짐(vue js로 바꾸는 중)

  controller

• front controller 는 들어오는 http request를 url parameter를 바탕으로 plugin controller로 rounting 한다.
• 
• 만약 위와같은 http request 가 오면 front controller는 CoreHome plugin의 action index를 호출한다. plugins/CoreHome/Controller.php의 index() method 가 호출됨
• plugin controller는 http response에 보내질 string(보통은 html content)를 return 한다.

Widgets and reports

• request에 해당되는 controller action이 없으면, matomo는 매칭되는 widget 이나 report가 있는지 본다.
• 만약 있다면 widget이나 대체 report의 render method를 호출한다.(CoreHome.renderWidget, CoreHome.renderReportWidget)

Http Reporting API

• reporting 역할하는 api
• report 를 xml이나 json형식으로 serving 하는 역할(sites, user, goals,.. 같은 다양한 entity에 대한 정보를 제공함
• 
• 이런게 오면 plugin 이름은 api, action name 은 주어지지 않았으니 index로 돌아가게 될 것.
  • Piwik\Plugin\APi\Controller class 가 호출되고, target api 에게 전달 할 것
  • 즉, 여기서는 Piwik\Plugin\SEO\API::getRank()가 호출될 것.
  • api 는 token_auth url parameter를 통해서 인증될거고, force_api_session=1 parameter가 존재하지 않는 한 session 이 load 되지는 않을 것.

HTTP Tracking API

• JavaScript tracker가 Matomo(이전 Piwik)에 저장할 분석 데이터를 제출하게 해줌
• Matomo's web application 이나 HTTP reporting API 는 달리, entry point가 matomo.php파일이다.(오래된 버전은 piwik.php)
• tracking 되는 동안 모든 플러그인들이 load되지는 않고, 필요한것들만 loading된채로 진행된다.(속도 이슈)
• tracking된 데이터들은 log_* table에 저장된다. 모든 raw데이터를 저장하고나서, 나중에 report archive로 집계되는 형식이다.(log_visit도 tracking 요청중에 업데이트 된다.)

데이터 모델, 처리, 저장

log - raw data

• HTTP tracking API(Piwik\Tracker component)는 log data(raw data)를 수신함
• 로그 데이터는 PHP에서 Piwik\Tracker\Visit객체로 표시되며 아래 테이블에 저장된다.

  • log_visit : 방문당 하나씩 찍힘(재방문자)
  • log_action : 웹사이트에서 가능한 모든 유형의 action당 찍힘(예: 고유한 URL, 페이지 제목, 다운로드 URL 등).
  • log_link_visit_action : 방문자의 하나의 액션당 하나씩 찍힘(페이지 보기, …)
  • log_conversion : 방문 중에 발생한 전환당 찍힘(목표와 일치하는 액션)
  • log_conversion_item : 전자상거래 전환당 찍힘

• 자세한 matomo schema 는 https://developer.matomo.org/guides/database-schema#log-data-persistence 여기서 확인 가능함

Archiving process

• log table 은 말 그대로 log table이기때문에 raw한 상태라 report를 위해서는 별도의 aggregation이 필요하다.
• Aggregation process는 날것의 log data를 읽어서 archived data(report 가능한 상태)로 바꿔준다.
• 이 과정은 특정한 날에 report를 위해서 돌아가게 된다(리포트 직전에만 돌아가는 배치잡형태)
  • 기간을 너무 길게 설정하면 돌아갈때 시간이 너무 오래걸려서 모든 기간에 대해서 지원하지는 않음(unique visit, unique user등 몇가지 항목에 대해서만 제공)
  • e.g. 아래 쿼리 같은게 돌아가는 것

    select count(*) as nb_visits from log_visit where idsite = 1 and visit_last_action_time >= '2021-08-04 00:00:00' and visit_last_action_time < '2021-08-05 00:00:00'

  • e.g. 아래같은 테이블이 생길 것

    archive_numeric_2021_10: 2021년 10월 측정항목 archive_blob_2021_10: 2021년 10월 보고서 archive_numeric_2021_11: 2021년 11월 측정항목 archive_blob_2021_11: 2021년 11월 보고서

Auto archiving VS. browser archiving

• 기본적으로 Matomo는 브라우저 또는 API를 통해 요청될 때마다 이러한 보고서를 "요청 시" 생성한다.(browser archiving)
• 이렇게 요청시마다 하는건, Matomo의 속도를 늦출 수 있으므로 cron을 통해 백그라운드에서 주기적으로 이러한 보고서를 생성하도록 구성할 수 있다.(auto archiving)
  • archiving process참고 : https://developer.matomo.org/guides/archiving
  • archiving behavior 참고 : https://developer.matomo.org/guides/archiving-behavior-specification

From Archive data to reports

• 위와같이 테이블 형태로 데이터가 저장되고 나면, plugin 에서 정의된 api 클래스에 의해 제공된다. api 는 metric 혹은 record에 access하고 이걸 표시 가능한 report로 변환한다.
• report 작성 방법: https://developer.matomo.org/guides/reports

• imbalanced되어있으면서도, ranking이 중요한 데이터에 대해서(e.g. click이 잘 일어나지 않지만, ctr의 순위를 잘 결정하는것이 중요한 데이터에 대해서) 평가 지표를 찾는다.
• accuracy, f1score, ROC AUC, PR AUC 등의 여러 지표를 탐구함.
• 결론
  • 일반적으로 imbalanced data 는 f1-score, pr auc 등의 지표를 쓰는게 좋다고 하지만, 지속적 모니터링을 위해서는 기준점이 명확한 것이 좋다는 점이 있었음(아래 상세 기술) 이런 이유로 이 지표들보다는 데이터의 balance를 맞춰준 후, roc auc 를 적용하는게 더 옳다고 판단함.
• pr auc vs roc auc
  • pr auc
    • imbalanced data 에서 성능평가를 할때에 유용함
    • recall 의 어느 시점에 precision 이 빠르게 떨어지기 시작하는지를 파악해서 threshold 지정
    • 단, 데이터에 따라서 기준 score 가 변화함(random 분류의 경우 기댓값은 positive:negative=1:k 일때 1/(1+k)가 됨)
  • roc auc
    • imbalanced data 에 취약함
    • 기준 score 변화가 전혀 없음(random 분류의 경우 데이터에 상관없이 score 값은 0.5)

Evaluation metric recap

1. Accuracy

• imbalanced 된 상태에서는 절대 써선 안된다

• 대부분을 majority class로 분류해버리는 경우 accuracy 가 높게 측정될 수 있음

• beta >1 이면 커질수록 optimal threshold는 점점 낮아진다.

• class 단위로 구분돼있을때 사용할 수 있는 지표라서, softlabel로 존재하는 경우 threshold 를 정하기 위해 위에서와 같은 차트를 그려볼 수도 있다.

• 언제 사용?

  • balanced 돼 있을때
  • non-technical stakeholder 에게 설명할때
  • 모든 class 가 중요할때

2. F1 score

• precision, recall 을 조화평균한 것

• recall 이 더 중요할 수록 beta 값을 올려야

• 0<beta<1이면 precision 을 더 중시하는 것 → threshold 가 높을수록 f-beta score 도 올라감

• beta >1 이면 커질수록 optimal threshold는 점점 낮아진다.

• class 단위로 구분돼있을때 사용할 수 있는 지표라서, softlabel로 존재하는 경우 threshold 를 정하기 위해 위에서와 같은 차트를 그려볼 수도 있다.

• 언제쓰나

  • positive class 에 대해서 더 신경쓸때 많이 씀
  • easily explained to business stakeholders

3. ROC AUC

• (Receiver Operating Characteristics)
• True positive rate(x축) 와 false positive rate(y축) 사이의 tradeoff 를 visualize 함
• ranking 에 대해 focus
  • prediction 과 target 의 rank 사이의 상관관계와 동치 → 해당 모델의 ranking prediction 이 얼마나 좋은지를 측정
  • 임의로 고른 positive instance 가 임의로 고른 negative instance 보다 score 가 낮은지를 확인
• 기준값이 명확
  • 랜덤상황을 가정하면 그 socre 값이 positive negative 와 상관없이 정확히 0.5가 된다.
  • 0.5 : 랜덤 (전체집합에서 positive negative 와 상관없이)
  • 0.7~ : 괜찮은 모델이라 판단 가능
• 언제쓰나?
  • 정확한 확률값에 대한 것 보다 ranking 에 대한 prediction 을 할때에 사용해야함
  • 데이터가 심하게 imbalanced 되어있으면 사용해선 안된다.
    • true negative 가 많아서 false positive rate 가 내려갈 수도 있기 때문
  • positive negative 둘 다에 대해서 동일하게 중요하게 생각할때 사용
    • 만약 true negative 만큼 true positive 가 중요하면 roc auc 를 쓰는게 말이 된다.

4. PR AUC(=Average Precision)

• precision 과 recall 을 한방에 그리는 것
  • recall 의 변화에 따른 precision 들을 다 모아서 평균을 낸다.
• y 축 값이 높을수록 좋은 모델인 것
• recall 의 어느 시점에서 precision 이 빠르게 떨어지기 시작하는지를 파악해서 threshold 를 정해야함
• recall 에 따른 평균이기때문에 랜덤하게 pick 했을때의 기댓값은 0.5가 아니고 초기 p:n=1:k 라고 할 때 1/(1+k) 가 됨. → threshold 이동하면서 그린 그림에서는 true label 안에서 p 와 n의 비율이 계속해서 변하기때문에 random 과의 관계를 표현할 수 있다면 괜찮지만, 그렇지 않다면 값 자체를 신뢰하기는 어려워질 수 있음
• 언제쓰나
  • 설득용
  • business 에 맞는 threshold 찾고자 할때
  • 데이터가 매우 imbalanced 되어있을 때
  • positive class가 negative class 에 비해서 더 중요할 때
    • pr auc 는 주로 positive class 에 주목하게 되므로, frequent negative class 에 대해서는 무시하게 되는 경향이 크다.(https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4349800/)

5. others

• micro macro
  • micro : 평균을 계산할때 각 클래스의 샘플 수를 고려해서 평균을 취함(이전에 내가 balancing 을 한 것과 동일한 듯)
    • 클래스 불균형 등에 민감하게 반응 가능
  • macro : 각 클래스의 샘플 수에 상관 없이 평균 취함
    • 모델의 전반적인 성능에 대해 평가 가능

Evaluation metrics comparison

ROC AUC vs PR AUC

• roc auc 는 true positive rate(tp/(tp+fn)), false positive rate(1-tn/(fp+tn)를 보는 반면, pr auc 는 positive predictive value(tp/(tp+fp)), true positive rate(tp/(tp+fn))를 보게 됨
• positive class 가 더 중요하다면 이것에 대해 더 민감한 pr auc 가 더 나음(tn 을 전혀 보지 않음, positive 에 더 민감함)
  • e.g.) fraud detection 등에서처럼 데이터가 imbalanced 되어있고, positive 가 더 중요한 경우
• 예시
  • 총 데이터: 1,000,000개, Positive 데이터: 100개
  • Model 1: 100개를 P로 predict했는데, 90개가 맞음. -> TP = 90, TN = 999890, FP = 10, FN = 10.
  • Model 2: 2000개를 P로 predict했는데, 90개가 맞음. -> TP = 90, TN = 997990, FP = 1910, FN = 10.
  • Model 1이 더 뛰어난 model임을 알 수 있다. 하지만 ROC curve의 TPR, FPR은 이에 대한 차등을 두지 않는다.
    • ROC curve
      • Model 1: 0.9 TPR, 0.00001 FPR
        • TPR = TP/(TP + FN) = 90/(90 + 10) = 0.9
        • FPR = FP/(FP + TN) = 10/(10 + 999890) = 0.00001
      • Model 2: 0.9 TPR, 0.00191 FPR (difference of 0.0019)
        • TPR = TP/(TP + FN) = 90/(90 + 10) = 0.9
        • FPR = FP/(FP + TN) = 1910/(1910 + 997990) = 0.00191
      • 이때 랜덤일 경우 roc auc 값은 0.5 (데이터 분포에 상관없이 항상 일정함)
    • PR curve
      • Model 1: 0.9 precision, 0.9 recall
        • Precision = TP/(TP + FP) = 90/(90 + 10) = 0.9
        • Recall = TP/(TP + FN) = 90/(90 + 10) = 0.9
      • Model 2: 0.045 precision (difference of 0.855), 0.9 recall
        • Precision = TP/(TP + FP) = 90/(90 + 1910) = 0.045
        • Recall = TP/(TP + FN) = 90/(90 + 10) = 0.9
      • 랜덤일 경우 PR auc 값은 (100/1000000)*0.5
• 위의 두 지표를 비교해봤을때 PR curve의 경우, 랜덤일경우에 대한 기준이 정해져있지 않기때문에(데이터 분포에 따라서 변하기때문에) 데이터 분포에 대한 파악없이, 숫자만으로 어떤 insight를 얻는 것이 쉽지 않다.
• 즉, 주기적으로 매일매일 성능을 확인해야하는 경우에는 pr auc 로는 daily의 추세등을 한눈에 파악하기 어려워서 적절하지 않은 것으로 보인다.

1장. 불확실성은 어떻게 무기가 되는가

• 세계는 복잡하고 빠르게 변화하며 그 안에 존재하는 문제들 또한 복잡하고 빠르게 변화한다. (기후변화에 대응할 수 있도록 경제체제를 변경하는 방법, 가난한 나라를 부유하게 만드는 방법, 투자은행들이 또다시 금융 시스템을 붕괴시키지 못하도록 제어하는 방법 등)

• 이런 문제들을 전문가들을 통해 해결할 수 있을까? → 없다!

  • 리더의 역량
    • 모든 대통령은 정치를 바꾸겠다는 공약을 내건 다음 당선이 되지만, 현실이 피부에 와닿기 시작하면서 지지율이 급락한다.
    • → 리더를 계속 잘못 뽑아서가 아니다. 단지 현대 사회에서 리더십이 달성할 수 있는 업적의 범위를 과대평가하기 때문이다.
  • 전문가의 판단에 의문을 제기했던 경제학자(테틀록)
    • 계량화가 가능한 구체적 예측을 요구하고 실현되는지 지켜보는 형태로 실험
    • 현실화 된 전망은 거의 없었음
    • 학부생들로 이뤄진 대조군보다 살짝 나았지만 객관적으로 월등하지 못했음
    • 전문성과 적중률이 비례하지도 않음
    • 세부 영역에서의 깊은 전문성이 있어도 예측이 더 나아지지 못했음(러시아에 관한 예측을 캐나다 전문가가 더 잘맞춘다던가...)
  • 초우량 기업
    • 1912년 세계적으로 가장 규모가 컸던 기업들의 운명을 추적
      • 100대 기업 중 10개가 10년 안에 망했고 83년동안 절반이 없어짐
    • 1400년대 활판 인쇄술 발명
      • 최초의 활판 인쇄술 - 구텐베르크 성서 인쇄 직후 완전히 파산
      • 이후 12개 회사 설립됐지만 그 중 9개가 3년안에 팧산
    • 자동차 산업 초창기
      • 미국에 2천개 회사가 있었으나 1%가 살아남음
    • 닷컴 버블
    • 해마다 미국 기업의 10%가 사라짐
    • 왜 그렇게 많은 기업이 파산 했느냐고 묻는 것은 왜 그렇게 소수의 선수만이 올림픽 금메달을 따느냐고 묻는 것과 같다. 시장경제체제는 각 부문마다 오직 소수의 승자만을 허용한다.
    • 컴퓨터 산업
      • 팔로알토 연구소 - 최초의 개인용 컴퓨터 Alto 개발 / 그러나 이분야 강자가 되지는 못함
      • → zx 스펙트럼, bbc마이크로, msx표준 등 Alto계승자 등장 했으나 다 망함
      • → 현대 pc의 직접적 조상은 IBM이 개발
      • → 근데 os 주도권을 micro soft에 뺏김
      • →(글이 쓰여질 당시에는) ms가 검색 주도권을 google 에 뺏기면서 인터넷 시장에서의 주도권 뺏겼고, 조만간 software 분야의 지배적 입지를 잃어버릴지도 모름.
      • 이 시장의 변화무쌍한 내일을 예상할 수 있는 사람은 아무도 없다!
        • 현대 사회는 너무 복잡하며 빠르게 변화하기때문에, 리더의 힘, 전문가의 힘, 초우량 기업의 힘을 가졌다고해서 살아남지는 못한다.

• 성공적인 아이디어가 뜨고 그보다 덜 성공적인 아이디어가 소멸하는 가운데 시장은 더듬더듬 성공을 향해 나아간다. 우리는 이 프로세스의 생존자들을 바라볼 때 단순히 성공만을 보아서는 안된다. 그 이면에 끝까지 살아남지 못한 회사와 아이디어들, 즉 길고 뒤얽힌 실패의 역사를 함께 보아야 하는것이다.

"진화"

• 생태학에서의 진화
  • '적자생존' 상대적으로 부적합한 개체의 도태에 의해 주도되는 프로세스
  • 이미 갖고 있는 것들의 몇 가지 이형을 시도해본 다음 실패작을 솎아내고 성공작을 모방하는 과정을 되풀이하는 단순한 프로세스로부터 믿기 힘든 복잡성이 등장한다. 변이와 선택을 계속적으로 반복하는 것
  • 단, 이 프로세스가 "맹목적"으로 일어남(계획성 없이 랜덤성에 의해서 변이가 발생(돌연변이))
• 시장 경제
  • 동일하게 변이와 선택이 작용한다.
  • 생태학에서의 변이와의 차이점 - "계획성"에 의한 변이
  • 과학자와 기술자, 대기업의 꼼꼼한 중간 관리자, 대담한 창업자들이 새로운 아이디어를 내놓으면(계획)
  • 좋은 아이디어는 그 아이디어를 가진 기업의 성장, 직원들의 창업, 경쟁사들의 모방을 통해 널리 확산된다.
  • 나쁜 아이디어는 시장에서 오래 살아남지 못하기 때문에 자연도태된다.

우리는 생각보다 맹목적이다.

• 화석 분석 데이터(생물 진화 과정)와 기업 소멸 데이터를 비교
• 기업의 실제 생사 패턴은 계획이 허용된 모델과 완전히 상이한 반면, 계획이 허용되지 않은 모델과 묘하게 닮아있었다.
  • 만약 기업이 정말 성공적으로 계획을 세울 수 있다면, 기업의 소멸 특징은 생물의 멸종 특징과 완전히 다른 모습일 텐데, 실제로는 양쪽의 특징들이 매우 흡사했다.
  • 추상적인 수학적 모델을 바탕으로 성급한 결론을 내려서는 안되지만 오머로드의 발견은 현대 경제에서 효과적인 계획이 보기 드물다는 사실을 강하게 함축한다.
  • 기업의 의사 결정이 성공적이지 않은 경우가 많으므로, 기업들은 끊임없이 나쁜 아이디어들을 도태시키고 그보다 나은 아이디어를 탐색해야한다.
• 우리는 생각보다 맹목적이다. 복잡하고 변화무쌍한 세계에서 시행착오 과정은 필수적이다. 의식적으로 그걸 이용하든 그저 나오는 결과에 몸을 맡기든 이 점은 사실이다.

변이와 선택을 허용하지 않으면 적응은 불가능해진다.

• 소비에트 연방의 실패 원인
  • 인상적인 초반 성과
    • 1950년대에는 많은 서구 전문가가 공산주의는 자본주의보다(반민주적이고 잔인하기는 하지만)효과적인 경제 운영방식이라고까지 결론을 내릴 정도였다.
    • 비록 한때였지만 소비에트 경제가 얼마나 성공적이었는지를 쉽게 잊어버리곤 하며, 계획경제의 붕괴 원인이 수익 동기라는 중요한 원동력과 민간 창업자들의 창의성 부족에 있다고 생각한다. → 말이 안 되는 소리다
      • 소비에트연방에도 팔친스키를 비롯해서 창의력 넘치는 사람들은 많았다. 그들이 단지 국유기업에서 활동했다는 이유만으로 창의성을 잃었을 리는 없다.
      • 소비에트연방의 동기부여 기법이 부족했던 것도 아니다. 사실 소비에트는 긍정적인 보상에서부터 끔찍할 정도로 부정적인 보상까지 역사상 어느 문명 못지않게 다양하고 폭넓은 보상 방식을 갖추고 적극적으로 활용했다.
  • 소비에트의 실패 원인 -> 병리적 실험 불능성
    • 진화 프로세스의 구성요소는 반복적인 변이와 선택. 소비에트는 이에 실패한 것. 어떤 문제에 대해서도 실질적인 다양한 접근법들을 용납하지 못했고, 무엇이 효과가 있고 없는지 판단하기 어려워했다. 소비에트 경제가 발달할수록 입안자들이 참고할 만한 기준점이 줄어들었다. 시스템 전체가 적응하지 못했다.
  • 팔친스키
    • 공학자 - 탄광 상황 평가 보고서 작성(탄광 위험도 개선, 근무환경 개선 등 주장) / 무모한 토목공사를 자주 비판
    • 팔친스키 3대원칙(현실의 문제점들이 생각보다 복잡하다는 사실을 알고 있었다.)
      1. 새로운 아이디어를 찾고 새로운 것을 시도해볼 것 (변이)
      2. 새로운 걸 시도할 때는 실패하더라도 살아남을 수 있는 규모로 시도할 것 (생존가능성의 중요성 - 6장)
      3. 피드백을 구하면서 실수로부터 교훈을 얻을 것 (선택)
    • 처형됨: 치명적인 기술적 문제의 발생 가능성을 지적하고 대안을 제시하는 사람은 누구든 '파괴자'로 고발되었다.
  • 소비에트 체제의 경제적 결함 - 변이와 선택을 허용하지 않음으로써 적응을 불가능하게 한다
  • 중앙 계획 당국은 눈앞에 지도나 통계표를 펼쳐놓고 스스로 전지전능하다는 착각 속에서 무엇을 지을지 결정했다. 그런 탁상공론식 계획에서 현장의 복잡성이 고려되지 않는 것은 당연했고 허용되는 변이의 수도 턱없이 적었다.
  • 어느 실험이 성공했고 어느 실험이 실패했는지를 결정하려면 피드백이 무엇보다 필수적이다. 그러나 소비에트 연방에서 피드백은 무자비하게 억제되었다.

변이가 어려운 이유

• 변이가 어려운 이유는 조직이 갖는 두 가지 자연스러운 성향때문
  1. 과장성 - 정치가와 기업가는 국가 전체의 의료 시스템 개혁이라든지, 대규모의 기업 합병 같은 덩치 큰 프로젝트를 좋아한다.
     1. 그래야만 이목을 끌 수 있고 자신들이 열심히 일하는 사람으로 비쳐지기 떄문이다.
     2. 그러나 그런 과시성 프로젝트들은 오류가 많고 적응의 여지가 거의 남아있지 않다는 점에서 팔친스키의 첫번째 원칙에 위배된다.
  2. 일관성 없이 장소마다 바뀌는 기준을 사람들이 달가워하지 않기 때문이다.
     • 코카콜라식 문제
       • 어떤 환경에나 동일한 기준을 적용해도 되는 단순한 문제를 뜻함
       • 코카콜라는 세계 어디를 가든 모든 사람이 좋아한다. 생산량에 대해서는 높은 기준을 적용해도 괜찮은 것
       • 병원, 학교 운영은 완전히 다른 사안
     • 보통의 사람들은 모든 것이 하나하나 동일하게 높은 품질을 실현해야 한다고 생각한다. 일종의 전국민적인 집착증. 우리는 모든 공공서비스가 코카콜라처럼 똑같이 우수하기를 원한다. 그러나 그건 불가능하다.
     • '변이와 선택'에서 변이를 진지하게 받아들인다면 한결같이 높은 기준은 불가능할 뿐 아니라 바람직하지도 않다.
     • 문제가 해결되지 않거나 지속적으로 변할 때 거기 접근하는 최상의 방법은 다양한 접근법으로 실험을 해보는 것이다. 아무도 색다른 것을 시도해보지 않는다면 우리는 새롭고 더 나은 방법들을 찾아내는 데 애를 먹을 것이다. 그러나 변이를 수용하려면 이 새로운 접근법 중 일부는 별로 효과적이지 않을 거라는 사실도 받아들여야만 한다.

전통적 조직의 한계

• 대부분의 리더가 정말 듣고 싶어하는 정직한 피드백의 양에는 한계가 있다.
  • 그리고 우리는 이 사실을 알고 있기 때문에 힘 있는 사람에게 보고할 때마다 의견을 듣기 좋게 꾸민다. 계층 구조가 깊은 조직에서는 그런 프로세스가 여러 차례 반복되면서 진실이 두꺼운 사탕발림 안에 완전히 감추어지게 된다. 야심이 큰 사람일수록 '예스맨'이 될 가능성이 높다는 증거가 있다. 예스맨들에게 보상이 따르는 경우가 많음을 감안하면 충분히 그럴 만하다.
• 리더와 관리자가 진심으로 원한다고 해도 솔직한 피드백을 받지 못하는 경우도 있다.
  • 계획의 각 단계마다 하급 관리자나 말단 공무원들은 어떤 자원이 필요하고, 그 자원을 어떻게 쓰는 것이 좋을지 제안을 덧붙여 상사에게 보고해야 한다. 그 과정에서 그들은 성공에 대한 욕심으로 과도한 약속을 한다든지, 과제의 실현 불가능성을 강조한다든지, 성공에 필요한 자원을 부풀려 말하는 등 그럴싸한 거짓말을 하기로 마음먹을 수 있다. 관료주의적 위계 내에서는 아무것도 덧바르지 않은 진실을 곧이곧대로 말하는 것은 최상의 전략이 아닐지도 모른다. 누군가가 진실을 말하더라도 팔친스키같이 정직한 의견과 예산 인상을 노린 냉소적인 항변을 어떻게 구분할 수 있겠는가.
• 전통적인 조직은 시행착오라는 탈 중심적 프로세스를 활용할 준비가 전혀 되어있지 않다.
  • 그런 조직에는 이미 해결된 정적 문제들이 제격이다. 마찬가지로 업무에서도 일반화된 전문성이 현장 지식보다 훨씬 더 중요하게 취급된다. 그러나 급변하는 세계에서 '코카콜라식 문제'들은 갈수록 보기 힘들어지고 있다.
  • 많은 기업들이 탈집중화를 시도하면서 관리자들에게서 권한을 빼앗는 이유도 여기에 있다.
• 올바른 조직 설계보다 더 근본적인 문제 -> 실수를 인정하고 거기 적응하는 데 어려움을 느끼는 것은 조직만이 아니다. 개인도 대부분 똑같은 문제에 시달린다.
  • 시행착오를 수용한다는 건 오류를 용납하는 것이다. 또한 불운 때문이든 잘못된 판단 때문이든 어떤 결정이 효과가 없을 때 상황에 침착하게 대처하는 것이다. 하지만 인간의 뇌는 이런 일을 수월하게 해내지 못한다.

왜 우리는 실수를 인정하지 않는가

• 포커에서 급작스러운 감정 상승에 극도로 취약해지는 순간 -> 불운이나 나쁜 전략때문에 큰 돈을 잃고 난 직후
  • 그 손실은 선수를 'on tilt'상태로 만들어서 이미 잃은 돈을 아직도 자신의 돈이라고 착각하고 그걸 다시 따오기 위해 더욱 공격적인 베팅을 하게 한다. 뇌는 돈이 사라졌다는 사실을 받아들이지 않는다. 손실을 인정하고 전략을 재정비하는 것이 올바른 수수이겠지만 그러기는 너무 고통스럽다. 대신 선수는 무의식중에 그 상황을 일시적이라고 여기고 이를 바로잡기 위해 무리한 베팅을 하게 된다. 그를 파국으로 몰고 가는 것은 애초의 손실이 아니라 그런 손실이 일어난 사실을 거부하기 위해 그가 두는 무리수다.
• "손실과 화해하지 않는 사람은 다른 때 같았으면 용납하지 않았을 도박을 받아들일 가능성이 높다."
• 실수 또는 손실에 직면했을 때 올바른 대응법은 이를 인정하고 방향을 바꾸는 것이다. 그러나 우리의 본능적인 반응은 일단 부정이다. "실수에서 교훈을 얻으라"는 지혜로운 조언을 받아들이기 힘겨운 이유가 바로 여기에 있다.

새로운 도전의 레시피

• 이 책에서 우리는 성공적인 적응의 레시피를 배우게 될 것
  1. 새로운 것들을 시도해보되 그중 일부는 실패하리라는 사실을 예상하라
  2. 생존 가능한 범위 내에서 실패하라. 실패는 보편적인 일이다.
  3. 일단 실패했을 때 그 사실을 인정하라
• 사실 여기엔 만만찮은 장애물이 존재함
  • 새로운 아이디어를 내놓기 위해서는 주변 사람들과 보조를 맞추려는 성향을 극복하고 기득권층의 반대를 무릅써야한다.
  • 생존 가능한 범위 내에서 실패한다는 것은 때로 한걸음 한걸음씩 착실하게 진행하라는 의미지만 항상 그런 것만은 아니다. 많은 혁신은 모험적인 도약으로부터 나타나며 그런 도약에서 살아남는 것은 쉬운 일이 아니다. 금융 시스템의 붕괴에서 살아남기도 쉽지 않다.
  • 그리고 묘하게도 실패와 성공의 구분이야말로 가장 어려운 일일 수 있다.
    • 오만한 리더는 구분 자체를 무시할 수도 있고, 자기 부정으로 그 구분이 애매해질 수도 있으며 세상의 복잡성 떄문에 가장 객관적인 판단력을 가진 사람조차 그걸 구분하기가 어려운 경우도 있다.

2장. 탄력성 : 가족 같은 조직은 왜 무너지는가

조직도의 함정

• 리더의 훌륭한 결정에 대한 환상
• 어떤 리더도 매번 올바른 의사결정을 내릴 수가 없다는 데 문제가 있다.
• 최고의 리더가 실수를 하더라도 훌륭한 조직은 이를 바로잡을 방법을 마련해둔다.
• 이상화된 계층(완벽한 조직도)가 정확한 결정을 이행하는 데 매력적인 수단이 되는 몇 가지 이유가 있다. 정제된 정보로 '큰 그림'을 도출해낼 수 있고 팀 전체가 한 방향으로 힘을 모으며 명확한 책임 소재 덕분에 정보가 명령 체계 위아래로 순조롭게 흐르기 때문이다.
• 그러나 조직의 과제가 실수로부터 교훈을 얻는 것이라고 한다면 이런 자산들 하나하나가 오히려 장애요소가 될 수 있다. 큰 그림은 자기 망상적인 선전선동 포스터가 되고 단합된 팀은 집단사고로 후퇴하며 명령 체계는 마치 휴지통처럼 정보를 정체시켜서 피드백이 최상단까지 도달하는 것을 철저히 방해한다. 이보다 훨씬 체계가 없고 무질서하며 제멋대로인 것처럼 보이는 조직이 현실적으로는 더 효과적이다.

완벽한 조직의 실패

• 이라크전
  • 이라크전의 역사를 되짚어보면, 그 침공 자체가 오판이었다는 결론을 피할 수 없음. 그럼에도 전쟁이 여러 해 동안 위태하게 계속 수행됨 -> 그런 낭패가 그렇게 오랫동안 지속된 이유는 무엇인가
  • 피드백 기회의 무시
    • 1. 에릭 신세키 장군 - 럼스펠드가 할당해놓은 규모의 두세배의 병력이 필요함을 권고했으나 럼스펠드에게 즉석 일축됨 - 훗날 그 정확성이 입증됨.
    2. 애비제이드(이라크에서 서열 2위 현장 사령관/서아시아 문제에서의 권위자) - 이라크인들은 민족적, 종교적 분열이 깊기때문에 협조를 얻기 위해 책임 있는 모습을 보여야한다는 피드백 - 일축됨 (유사한 전략을 사용한 몇개의 부대만 성공적으로 작전을 수행할 수 있었음)
  • '벌레의 시각'(눈앞에 문제를 직접 직면하고, 돌아갈 길을 스스로 찾아야 하는 입장에서의 시각. 즉, 실무자의 시각)을 무시하고, 본인이 전능하다고 믿는 리더들에 의해서 올바르지 못한 전략을 반복하게 됨.
  • 전쟁에서 전략의 오류는 드문일이 아니나(이라크에 간 것이 잘못이 아니라) '적응의 실패' 그보다 더 나쁜 '적응의 거부'가 더 큰 문제였다.
• 베트남전(가족같은 팀)
  • 대통령, 국방장관, 합참본부 장군들의 실패에 격분해 "직무유기"라는 제목을 붙임
    • 이상적인 위계가 어떻게 역효과를 가져올 수 있는지를 명확하게 보여준다.
    • 이상화된 의사결정 위계의 세가지 요소
      1. 활용 가능한 모든 정보의 정밀 분석을 통한 '큰 그림' 도출
      2. 한 방향으로 힘을 모으는 단합된 팀
      3. 엄격한 명령 체계
  • 이라크전에서와 마찬가지로, 올바른 말을 하는 지휘관들은 경질되고, 사탕발림에 가까운 정보들만 위로 흘러감. 큰그림은 완벽히 틀렸고, 적절하지 않은 전략(위에서 내려온 큰그림)을 반복한 결과 실패만을 거듭할수밖에 없었음.
• 중앙에서 요약하고 분석해낸 '큰 그림'은 결과적으로 중요성이 떨어지는 정보
• 충성도 높고 단합된 팀은 대안적인 관점을 허용하지 않는다.
• 엄격한 명령 체계는 조직의 아래 단계에서부터 나쁜 소식을 차단해 상위 조직(대통령 등)으로의 전달을 방해한다.
• '벌레의 시각'(눈앞에 문제를 직접 직면하고, 돌아갈 길을 스스로 찾아야 하는 입장에서의 시각. 즉, 실무자의 시각)을 무시하고, 본인이 전능하다고 믿는 리더들에 의해서 올바르지 못한 전략을 반복하게 됨.
• 전쟁에서 전략의 오류는 드문일이 아니나(이라크에 간 것이 잘못이 아니라) '적응의 실패' 그보다 더 나쁜 '적응의 거부'가 더 큰 문제였다.
• 결국 위 전쟁들이 끝나긴 했는데, 위 전쟁들로 부터 미국을 구한건 몇몇 하급 장교들이 징계를 무릅쓰고 상부의 지시를 따르지 않았기 때문이었다. (본인이 파악한 전략대로 행동한 이들과(트랩대위, H.R 맥마스터 연대장 등)과, 이들의 성공을 모방했던 다른 하급 장교들 덕분이었음)
  • 그렇다면 새로운 전략을 펼친 사람들이 리더였으면 상황이 달랐을까? → 그렇지 않다
    • 현장에서 기존 전략의 실패를 직접 경험했기때문에 새로운 전략을 시도해볼 수 있었고, 그 새로운 전략들 중 몇몇개가 성공적이었을 뿐인 것.

바람직한 지휘체계의 조건

• 실수로부터 교훈을 얻는 비결은 공식적인 지휘 체계를 맹목적으로 고수하는 것이 아니라 필요한 경우 그걸 뒤집는 것이고, 만장일치를 추구하는 것이 아니라 반대 의견을 경청하는것이며
• 무엇보다도 상의하달식의 전략에 의존하는 것이 아니라 하급 장교들이 서로서로 교훈을 얻고 빠르게 변하는 현지 상황에 즉각적으로 대응하면서 적응해나갈 것을 믿고 탈집중화하는 것이다.
  • 목표를 세우는 것은 고위장교들이지만 융통성 있게 현지 정보에 적응하며 그 목표를 어떻게 달성할지를 결정하는 것은 하급장교들이다. 임무형 지휘 체계하에서 공중 지원병과 포병을 배치하는 것은 회전의자에 앉아 단추만 누르는 3성 장군이 아니라 현지 상황을 실제로 이해하고 올바른 결정을 내릴 것으로 믿을 수 있는 대위나 소장이다.
• 그러나 단일 조직에게 가능한 혹은 전쟁터에서 바람직한 실험(다윈의 용어로 표현하면 변이)에는 한계가 있다.
• 때로는 조직이(아무리 유연성을 발휘해도) 감당할 수 있는 수준을 넘어서는 수많은 실험과 변이가 요구되는 경우도 있다. 그런 경우에는 새로운 아이디어의 촉진을 위해 훨씬 급진적인 접근법이 요구된다.

3장. 변이: 해결책은 생각지 못한 곳에서 온다

• 변이하는 방법 → 새로운 시도에서 예상치못한 행운이 온다
• 우리는 미래의 보상을 바라고 지금 돈을 투자하면서 투자 대비 수익을 생각한다.
• 그러나 새로운 아이디어와 신기술을 투자 대비 수익의 관점으로 생각하는 것은 바람직하지 못하다. 대부분의 신기술은 완벽한 실패로 끝나며, 독창적인 아이디어가 효과적일 때는 그 보상이 너무 엄청나서 합리적인 측정이 불가능하다.

혁신의 특성

• 아주 드물지만 보상이 한 번 돌아오면 대박이 난다는 점에서 이런 프로젝트는 복권 당첨에 비유할 수 있음. 복권은 제로섬 게임이지만, 연구개발 성과는 모든 사람을 이롭게 하므로 복권보다 더 이로움. 복권과 달리 대담한 혁신 프로젝트는 보상금이 알려져 있지 않고 성공 확률도 고정되어있지 않음. 골칫거리인 모험이기도 함 어마어마한 보상이 따르기 때문에 피할 수는 없다. 좌절감을 주기도 하고, 예측이 불가능하다. 아무런 보상이 돌아오지 않는 경우도 많다. 외면할 수도 없고, 그렇다고 효과적으로 관리하기도 어렵다. → 행운의 검은백조
  • ↔ 검은백조(black swan)이론 - 전혀 예상치 못한 사건이 일어나는 현상
  • 세계 2차대전 중 스핏파이어(전투기) - 정상적인 위탁 절차를 우회해서 "가장 흥미로운 실험작"을 주문 → 궤도 수정이 가능한 초고속 전투기가 되어 영국을 승리로 이끌었다.
• 혁신의 고립성
  • 그 잠재성이 발현되기 전까지 일종의 고립 과정을 필요로 한다.
  • 새로운 아이디어가 기존의 통념에 흡수되거나 압도되지 않고 성숙 발전할 수 있도록 숨 쉴 공간을 줘야 함.
  • (여러 아이디어가 병렬적으로 발전하도록 허용해야한다는 개념)
• 비싸고 느려진 혁신
  • 세상이 점점 정교화되고 복잡해지면서 '지식의 부담'이 발생하고 있음을 이해해야한다.
  • 특허 인용된 팀들의 규모는 꾸준히 커지고 있고, 발명가들이 처음 특허를 내는 연령도 꾸준히 상승하고 있다.
  • 기숙사 혁신(차고 또는 기숙사에서 게임 또는 소프트웨어를 개발해 내던 혁신)은 점점 적어지고,
  • 아이폰과 안드로이드 앱의 확산은 혁신이 느려지고 어려워졌으며 값비싸졌다는 불편한 진실
  • → 대부분의 분야에서 이전 세대가 걸었던 기대에 훨씬 못미치는 성과를 올리고 있음

혁신 장려의 방법

• 특허의 문제점
  • 신기술의 장려 방법으로 흔히 특허를 생각하지만 특허는 그리 효과적이지 못함
  1. HIV 백신, 청정에너지 개발등을 장려하기엔 특허는 힘이 없음 - 최초 개발 이후 산업 경쟁력을 갖출 무렵이면 이미 특허 기간은 만료 되었을 것.
  2. 정부가 특허권을 포기 하라거나 가격을 삭감하라고 압력을 넣는 일이 왕왕 일어나고 있음
• 방법 1: 조건없는 후원
  • 당연히 될 것으로 예상 되는 연구보다, 언뜻 불가능하고 매우 도전적으로 보이는 연구들이 더욱 큰 성과를 가져온다 (행운의 블랙스완)
  • 하워드 휴스 의학 연구소 - 상세 연구계획 없이 대략적 아이디어 스케치와 지원자의 최근 연구결과 사례만 보고 채택 (별다른 단서 조항 x) → 꼼꼼한 서류 검토를 통한 투자를 한 미국 국립보건원보다 더 좋은 연구성과(노벨상, 논문 제출 수, 특허 수 등)
• 새로운 기술을 장려하는 데 필수적인 두 가지 핵심 원칙
  1. 무엇이 효과적일지 서로 상충되는 관점을 내재한듯 보이더라도 대부분이 실패할 것을 염두에 두고 가급적 많은 실험을 시도해야한다.
  2. 실패의 가능성이 보이더라도 성공에 대한 엄청난 보상을 생각해서 장기적인 안목을 지닌 실험을 장려해야한다.
• 방법 2: 포상제도
  • 넷플릭스 상 - 기존 추천엔진 개선 프로젝트
    • 1년 안에 추천오류 8% 낮아짐.
  • 포상제도가 멋진 이유는 성공하기 전까지 비용이 한푼도 들지 않음
    1. 실패가 용납될 뿐 아니라 가장 대담하고 위험성 높은 아이디어가 성공할 수 있는 완전히 개방적인 경쟁의 장
    2. 문제가 해결된 경우에만 거액의 비용이 지출됨

4장 선택: 가난한 사람들을 위한 임상실험

• 이전까지 변이의 중요성을 강조했다면 이번엔 선택의 중요성 → 어떻게 선택할 것인가
• 벌레의 시각
  • "사물을 가까운 거리에서 보아야 날카롭게 볼 수 있다" "도중에 어떤 장애물을 발견하면 벌레처럼 그 주위를 돌아갈 것이고, 그런 방법으로 분명 목적을 이루고 뭔가 성취할 수 있을 것"
  • 겸손하게 장애물에 적응하면서 성공에 이르는 길이 명확히 보일 때까지 경로를 바꾸어나가는 방법
  • 동시에 그 장애물을 가까운 거리에서 날카롭게 보는 방법이기도 함
• e.g. 플레이 펌프
• 신 컴플렉스를 버리고 무작위 실험(대조실험)을 거듭하라
  • 더 좋은 전략을 이미 알고있다고 생각하여, 대조군에 불이익을 주고 있다는 착각을 하게 되는 경우가 있음.
  • 그러나 이는 신 컴플렉스에 갇힌 것. 본인이 다 알고있다는 확신을 버리고 명확한 실험 후 선택하는 과정이 필요하다.
• 피드백 루프를 개선하라
  • 어떤 아이디어가 효과있는지 알더라도 그 아이디어를 더욱 폭넓게 적용할 수 있는지 검증이 필요하기 때문
  • e.g. 플레이 펌프
• 빅 푸시가 필요할 수도 있다.
  • 빅푸시 : 정부나 기부자들이 끼어들어 진보를 주도하는 것
    • 우편제도, 금융 시스템, 인터넷 인프라를 동시다발적으로 개혁하는 등
  • 빅푸시는 필요한가?
    • 항상 효과적이지는 않지만 효과적인 경우가 있더라.
• 도시 실험 프로젝트
  • 독립적인 도시국가(헌장도시)들이 생존, 번영할 수 있음을 확인한 바 있음
    • 싱가폴, 홍콩,
    • 선전(중국) - 중국의 첫 '특별경제구역'으로 지정된 이후 홍콩에 견줄만한 라이벌 도시로 성장
• 헌장도시의 성공
  • 성공비결 1. 헌장도시는 바람직한 규모로 적응의 여지를 제공한다.
    • 변화를 가져올 수 있을 만큼 크면서도, 수십 혹은 수백가지의 실험이 공존할 수 있을 정도로 작다.
    • 빅푸시는 실패하기 일쑤고 작은 발걸음으로는 효과가 미흡한 개발분야의 딜레마를 해결해줄 대안이 된다.
  • 성공비결2. 변이만 아니라 선택이 가능하다.
    • 정부가 도시를 만들어 놓고, 국민들 중 새로운 규칙에 따라 생활하고 싶어하는 사람들이 있는지 지켜보는 것.
    • 도시의 규칙, 기관, 물리적인 인프라가 시민들에게 훌륭하 삶의 질, 범죄의 공포로부터의 자유로움 훌륭한 소득 창출의 기회를 제공해주도록 설계될 수 있다면 그런 도시에는 잘 살고 싶은 사람들이 모여들 것이다.

• pinterest 에서 19년에 kdd에 냈던 논문.
• https://dl.acm.org/doi/10.1145/3292500.3330671

Abstract

• bert 등의 pretrained model 은 산업환경에 맞지 않다며, 새로운 방법의 multitask text embedding solution을 제안함.
• word level semantic vectors 생성함. 이때 randomly sampled background 에 비해 positive engagement pair 에 더 큰 similarity 를 주도록 강제해서 학습하는 방식

Introduction

• pin, user text - pin's title, description, board name, url을 데이터로 이용
• 원하는 result - text embedding하고 word level embedding vector 를 average 해서 pin, user, search query 를 하나의 space 에 놓는 것
  • → 다른 type 의 object 들에 대한 retrieval, classification 등을 nearest neighbor search 의 통합된 방법으로 해결
• pretrained word embedding(bert 등)에 대한 저자의 부정적 의견
  • 연구에서의 요구사항과 산업에서의 요구사항은 다르다는 견해
  • key design philosophy
    1. storage cost
       • embedding 의 갯수는 multiple versions of embedding 과 cosine similarity 같은 realtime cost를 증가시킴
       • → storage 를 아끼기 위한 all in one solution 를 원함
    2. memory cost
       • top 10 language 에 대한 fasttext(character 기반모델) 모델의 경우 50기가
       • → 메모리에 올리기 좋은 크기의 word 기반 모델
    3. supervised information
       • guide model learning 이 더 효율적임
    4. throughput and latency
       • latency critical realtime computation
• 위와 같은 needs로 in-house text embedding system이 필요하다고 생각함
• repin, click engagement 를 positive training data 로 활용 (supervised learning)

Related work

1. text embedding in nlp
   • sota 에서는 sequential text 를 이용한 모델이 대부분임
   • But, internal data distribution 이 public corpus 와 매우 다름
     • pinterest 의 데이터는 long sentence 보다는 concrete annotation term
   • But, objective function 이 매우 다름
     • cbow, skip gram 등은 co-occurance 를 기반으로 학습하게 됨
     • facebook 의 starspace 등을 참고해서 supervised embedding training type 을 사용하고자 함
2. multitask learning
   • 결과 모델은 세가지 태스크에 적합해야하므로, multitask learning 을 진행할 예정
   • classification 에는 흔한 task 이지만, word embedding 에서는 흔치 않음
3. transfer learning
   • off-the-shelf text features independent on specific task - 이걸 top 에 올리고 downstream task 를 진행하는 transfer learning 과 연관이 있다고 볼 수 있음
   • e.g. elmo, gpt, bert...
   • 그러나 pinterest 에 적합하지 않음
     1. 종종 not sequential 함
     2. inference efficiency 가 매우 중요함
   • retrieval 이 중요 task 이기 때문에 bert의 next sentence prediction task 에는 적합하지 않음
   • 태생적으로 retrieval task 를 handling 하는 starspace 를 참고할 예정

System design

• 세개의 모듈로 구성 : offline model training, index building, online serving
• offline training
  • kafka로 user engagement data 수집
  • training data 구성
• index building
  • kubernetes cluster (embedding vector를 distributed way 로 만든다)
  • user, pin, query entity 의 candidate embedding 에 lsh 적용(pre-compute token), 여기에 inverted index 적용
  • embedding vector 와 knn 결과를 caching
• online serving
  • embedding vector lsh token 사용해서 retreival 등에 사용

Multitask text embedding

• task definition

  • q, p
  • positive pair - repin, long click
  • q 에 해당하는 task
    • home feed 에서 user
    • search 에서의 search query
    • related pin 에서의 subject pin
  • p - a set of words {w } where each word wi appears in the union of pin’s text metadata:
    • title, description, boardname, url
  • u - a set of words {w } where each word wi appears in the union of user’s interests

• Multitask formulation

  • 
    • L : hinge loss
    • S : cosine similarity
    • → positive entity 의 similarity 가 random 에 비해 크게 학습되도록 함
    • details
      1. importance of each task - 따로 주지 않음 (objective function 이 natural engaged traffic 을 반영하게 하고자 함)
         2. tradeoff btw coverage and precision - positive pair 에 대해서 강한 filter를 주면 precision 은 늘어나지만, coverage 가 좁아짐
         • 처음엔 약한 filter로 낮은 precision 으로 학습을 시켜보고, 점차 filter 강화
         • coverage가 높은 모델의 결과로 다음 모델학습에서 initialization embedding dictionary로 사용함.

• 이상치 데이터는 거리상으로 멀리 떨어져있을 것이라는 가정
• 이때엔 거리만으로 이상치 여부를 판단하고, normal class에 대해서 어떠한 사전분포도 가정하지 않는다.

k-nearest neighbor

• parzen window density estimation 에서 p(x)=k/(N*V) (k=영역에 존재하는 데이터의 수 , N=객체의 수, V=영역 R의 volumn) 에서 V를 고정시킨게 parzen window density estimation 이라면 k-nearest neighbor는 k를 고정시킨 것 (k를 커버하는 V를 추정하는 것)
• k번째까지의 거리를 어떻게 측정할 것인가에 따라서 변종들이 있음
  • max distance, average(개별적 거리를 먼저 계산 후 average), 평균까지의 거리(무게중심하나 놓고, 무게중심까지의 거리를 측정)
  • 아래 그림에서처럼 측정 방법에 따라서 이상치 스코어가 달라진다.

knn 기반 anonaly detection 에서의 반례

• knn 기반의 기법들이 찾아내지 못하는 반례들이 존재한다.
• 위 그림에서처럼 B에서의 세모는 polygon 내부에 있기때문에, 다른 어떤 점들 보다도 이상치 스코어가 더 낮아야한다. 또한 A, B에서 동그라미는 polygon 바깥에 있으므로 더 높은 이상치 스코어를 나타내야한다.

• 그런데 그렇지 않음!

반례 보완

• A hybrid novelty score and its use in keystroke dynamics-based user authentication (PilsungKang, SungzoonCho, 2009)
• 보정 하는 factor 만듦
• 현재 알아보고자 하는 객체가 이웃들로 만들어지는 convex 안에 위치하는지 확인하는 것
• 객체(x)와 이웃(z(x))가 있을때, 이웃들을 x와 가장 유사하게 변형시키는 w를 찾아낸다.
• polygon 밖에 있다면(convex hull distance가 0이 아니라면) 분모가 커지면서 average distance 에 대한 penelty 부분이 증폭되게 된다. 위의 그림상에서 보자면 원이 세모보다 더 큰 이상치 스코어를 갖게 되었다. 제안하는 score 를 이용했을때에(f) 밀도가 낮은 영역에 구멍이 뚫리는 현상도 사라지고, 밀도가 높은 영역 중간영역 또한 잘 구분해 내는걸 알 수 있었다.

총 21개의 데이터에 대해서 14개 알고리즘을 30회 반복 실험을 했을때(21*14*30)에 더 좋은 결과를 보여주었다.

Clustering-based approach

• DBSCAN 같은 알고리즘은 군집에 속하지 않은 객체들은 전부 이상치로 취급한다
• 이 외에 일반적인 clustering algorithm을 이용해서도 이상치 판단이 가능함.
• 가장 가까운 군집과의 거리가 멀 경우 이상치로 판단하는 것이 그 방법이다.
• k means clustering을 진행한 후, 이상치를 판단하는데, 그 판단에는 아래의 두 방식이 존재한다.

1. absolute distance to the nearest centroid
   • 가장 가까운 centroid 까지의 거리를 구한다
2. relative distance to the neariest centeroid
   • 군집의 지름을 계산해서, 군집 지름대비 얼마나 더 멀리떨어져있는지로 계산

• kmeans based anomaly score 를 sklearn 에서 제공하고 있는데 그걸 이용하면 아래와 같이 나타난다.

• 뉴스 기사의 multi lingual bert emb 를 차원 축소시키는데에 auto encoder를 이용하게 될 예정.
• model 의 학습에 쓰이는 feature를 정기적으로 재학습 시키고 update하는 과정을 꼭 해야만 할지 알아보기 위해 실험을 진행한다.
• 5월에 학습시킨 오토인코더를 6월부터 11월 데이터에 적용해보고, 성능 저하가 발견되는지(loss 값이 크게 증가하는지)확인한다.
• 시간이 지나도 loss 값은 크게 증가하지 않는 모습을 보인다.
• 즉, 5월 데이터로 학습한 오토인코더를 11월에 사용해도 성능은 뒤떨어지지 않음을 알 수 있다.

실험 목표

• 뉴스 기사 multi lingual bert embedding vector의 차원 축소시키는데에 auto encoder를 이용하게 될 예정.
• model 의 학습에 쓰이는 feature를 정기적으로 재학습 시키고 update하기 위해서는 준비해야할 부분이 너무 많다.
• 이 번거로운 준비를 해보기 전에, auto encoder의 성능 열화를 정량적으로 확인하고, 차원 축소 모델의 정기적 업데이트가 불가피한 일인지를 확인한다.

실험 방법

• 5월 데이터로 오토인코더를 학습시킨다.
• 학습시킨 오토인코더로 6,7,8,9,10,11월의 데이터를 encoding 후 decoding 했을때에 loss 가 얼마나 증가하는지를 확인하여, 오토인코더가 시간이 지남에 따라 그 성능이 얼마나 나빠질 수 있을지 확인한다.
• (차원 축소된 item vector를 이용한 ctr 실험으로 성능열화실험을 진행하려 했으나, 서로 다른 데이터에 대해서 ctr 예측 결과의 정확한 정도를 나누는 것이 합리적이지 않다고 여겨졌다. 또한 그럼에도 실험을 해보았을때에 데이터가 매우 튀어 비교가 불가능한 상태였다.)

auto encoder 학습

• 4단 stacked auto encoder 활용 (768 → 64 → 32 → 16 →5)
• 뉴스기사 제목과 내용의 270만개의 multi lang bert 결과로 학습 (2021-05-01 ~ 2021-05-05)

Loss 확인 대상 데이터

• 6,7,8,9,10,11월의 1일부터 15일까지의 뉴스기사 중 unique 한 25000개를 random 하게 추출한다.
• 위의 데이터를 AE 를 통과시킨 후의 loss 값이 얼마나 늘어나는지를 확인한다.

실험 결과

• 시간이 지나도 loss 값은 크게 증가하지 않는 모습을 보인다.
• 즉, 5월 데이터로 학습한 오토인코더를 11월에 사용해도 성능은 뒤떨어지지 않음을 알 수 있다.

• model 의 feature 로 뉴스기사 제목과 내용의 embedding 을 사용하고 있다. 이때 768차원의 bert embedding 결과물을 축소할 방법으로 auto encoder, pca 둘 중 어떤 방법이 적절할지를 실험을 통해 비교한다.
• 각 방법으로 차원축소한 item embedding 결과로 ad ctr 예측실험을 했을때에 auto encoder 로 차원축소한 경우 예측 성능이 더 뛰어났다.
• 즉, item 의 multi lingual bert emb 의 차원 축소 방법으로 auto encoder 를 이용하는 것이 더 적절함을 알 수 있다.

실험 목표

• model 의 feature 로 뉴스기사 제목과 내용의 embedding 을 사용하고 있다. 이때 768차원의 bert embedding 결과물을 축소할 방법으로 auto encoder, pca 둘 중 어떤 방법이 적절할지를 실험을 통해 비교한다.

실험 방법

• 뉴스기사 의 multi lingual bert vector 의 차원을 pca 로 축소시켰을때와 auto encoder로 축소시켰을 때의 값을 feature 로 사용하여 각각의 feature 로 뉴스기사에 달린 광고의 ctr 예측을 lgbm으로 학습하여, 예측 성능을 비교한다.
• 즉, pca로 압축한 뉴스기사 feature 로 광고 ctr을 예측하는 lgbm model 을 만들고, auto encoder로 압축한 feature 로 ad ctr을 예측하는 lgbm model 을 만들고, 이 각각의 예측 성능을 비교한다.
  • lgbm을 사용하는 이유?
    • 현재 서빙중인 모델인 deepfm 을 사용할 수 도 있지만, 이를 학습시키기 위해서는 더 많은 feature 와 더 많은 데이터가 필요하다. 적은 데이터로 빠르게 실험하기 위해서는 더 작고 간단한 lgbm model을 쓰는게 낫다고 판단했다.
  • ctr 예측 실험을 구성한 이유
    • 이전 실험에서 뉴스기사의 제목과 내용 정보가 광고 ctr에 영향을 미친다는것을 이미 확인했기때문에, 이 feature 를 차원 축소시킨 feature 로 광고 ctr 예측을 더 잘하는 쪽이 더 좋은 차원 축소 기법이라 생각했기 때문.

각 차원 축소 모델의 학습

• auto encoder
  • layer 구성
    • 4개 encoder layer 활용 (768 → 64 → 32 → 16 → 5)
    • 선행실험에서 좀 더 효율적인 방식이라 확인했던 bottle neck layer 주변에 layer 를 더 쌓는 방식으로 구성
  • 학습 데이터
    • 100만개 뉴스기사 의 제목과 내용의 multi lang bert emb 결과 활용 ('2021-10-29'~'2021-10-31')
• pca
  • spark ml의 pca 활용
  • 학습 데이터는 autoencoder와 동일

ctr 예측을 위한 lgbm 모델의 학습

• 데이터
  • 2021-10-31부터 2021-11-04까지의 뉴스기사 중 2021-10-31부터 2021-11-15일간 view 수가 2000회 이상인 item 14016개와 동일기간에서 이 뉴스기사의 광고 ctr 데이터를 학습
    • view 2000회 이상이라는 조건을 준 이유는 이런 조건이 없다면 대부분의 뉴스기사의 광고 ctr이 0인 경우가 지나치게 많다. (읽히지 조차 않은 뉴스기사들을 제거하기 위한 룰)
    • 10% 는 testing, 나머지 90%는 training 에 활용
• 비교대상
  • 뉴스기사의 제목과 내용을 multi lingual bert로 vector화 한 후 이를 pca 로 5차원으로 압축시킨 feature 를 활용하여 lgbm을 학습
  • 뉴스기사의 제목과 내용을 multi lingual bert로 vector화 한 후 이를 auto encoder 로 5차원으로 압축시킨 feature 를 활용하여 lgbm을 학습
  • 위의 두 학습 모델의 예측 성능을 비교

실험 결과 확인

Histogram

• 실제 ctr 값의 분포와, 모델이 예측한 ctr 값의 분포를 비교한다
  • (모델이 중앙값만 예측값으로 반환해서 mse 만 낮추고 있을 수도 있기 때문)
• 아래의 히스토그램을 비교해봤을때 문제가 있어 보이는 모델(유사한 값만 계속 예측한다거나, label data 의 분포를 크게 벗어나거나)은 보이지 않는다
• x 축 : ctr, y 축 : 빈도

Roc auc score 확인

• 각 모델에서의 구분력을 알아보기 위해 classification에서의 평가기준인 roc auc score 를 적용
• 기준 ctr(regression 결과에서 classification 결과로 해석을 위해 true, false 를 가를 기준 ctr 을 둔다)을 변경하면서, 이때의 roc auc score 계산하여 그래프로 그린다.
• 아래 그래프를 확인해봤을때에 거의 모든 기준 ctr 상에서 차원 축소 방법으로 auto encoder 를 사용했을때에 ad ctr예측에서 더 높은 성능을 보이는 것을 확인할 수 있다.
• x 축 : 기준 ctr, y축 : roc auc score

• Multi-lingual bert 의 차원을 축소시킬 방법으로 auto encoder 를 사용할 수 있을지(loss 값이 줄어드는 등 학습이 잘 진행되는지), 적절한 layer 갯수와, layer dimension은 무엇일지 확인한다.
• 실험결과, auto encoder 로 dimension reduction을 하는 것이 유효함을 알 수 있고(loss 값이 줄어드는 등 학습이 잘 진행됨을 알 수 있었음), layer 는 4단, 이때 dense layer 의 dimension 구성은 input layer 부터 bottle neck까지 균일하게 줄일 때보다, bottle neck 과 유사한 dimension의 layer 이 더 많을때에 더 높은 성능을 보임을 알 수 있었다.
  • 실험결과, 적절한 데이터의 양을 100만 row, epoch 10회 이하라고 가정한다면 layer 4단까지가 적절한 것으로 보인다.
  • encoder 의 layer dimension을 input layer 부터 bottle neck까지 균일하게 줄일 때보다, bottle neck 과 유사한 dimension의 layer 를 더 많이 쌓을때에 loss 값이 더 낮음을 확인할 수 있다.

실험 목표

• Multi-lingual bert 의 차원을 축소시킬 알고리즘으로 auto encoder 를 사용할 수 있을지(loss 값이 줄어드는 등 학습이 잘 진행되는지), 적절한 layer 갯수와, layer dimension은 무엇일지 확인한다.

Auto encoder 란?

• input vector 를 encoder layer 를 거쳐서 bottle neck layer 의 dimension 만큼 줄였다가, 다시 decoder layer 를 통해 output 을 input 의 크기만큼 확장한다.
• output 을 input 과 최대한 가까운 값을 낼 수 있도록 학습하는 과정을 통해서, encoder layer 를 활용한 차원 축소와 decoder layer 를 통한 데이터 복원을 가능하게 한다.
• 우리는 이 중 encoder를 사용하여, bert 의 차원 축소에 활용할 수 있을지 그 가능성을 보고자 한다.

실험 방법

• input 과 auto encoder 를 통과한(차원을 축소 한 후 다시 복원한) 결과의 차이를 mse loss 로 계산한다.
• auto encoder 의 encoder layer 수와 layer내부의 차원을 바꿔가면서 loss 값을 비교하여 더 적절한 Layer 구성을 알아낸다.
• 단, 이때 decoder 성능에 의한 loss 값 차이를 막기 위해 decoder부분의 layer 는 1단으로 모든 실험에서 동일하게 유지한다. (우리의 목표는 차원축소를 잘 하는 것 이므로)
• activation function과 optimizer, learning rate 는 실험 대상이 되는 autoencoder 중 가장 작은 것에 일단 최적화 시킨 후 나머지 모델에도 동일하게 적용하여 학습한다.

데이터

• 크롤링한 뉴스기사 제목, 내용 데이터(약 100만건) 활용하여 autoencoder 학습 (2021-10-29 01시 ~ 2021-10-31 04시)
• 100만 개 데이터에서 10%를 test, 90%를 train 에 활용하여 loss 값을 비교한다.

실험 결과

encoder layer 갯수에 따른 test set loss값 비교

input 에서 bottle neck 까지 layer 크기를 균일하게 감소시키기

• epoch 을 10회까지 증가시키면 2단, 3단까지 쌓은 layer 에서는 오히려 epoch 5회일때보다 loss 값이 증가한다.
• epoch 상관없이 layer 갯수당 최소 loss 값 : 3단 > 2단 > 5단 > 4단
• encoder 에 layer 를 추가하면 capacity 는 커지는 반면 tuning 이 필요한 parameter 는 증가한다. 2단에서 3단으로 갈 때, 4단에서 5단으로 갈 때에는 이런 이유로 오히려 loss 값이 증가하는것으로 볼 수 있다. (epoch 을 이 이상으로 증가시킨다면 5단에서 더 성능이 좋을지도)
• epoch 을 증가시킬수록, 데이터를 증가시킬수록, 더 많은 layer 를 쌓았을때에 좋은 성능을 보여줄수도 있지만, 그 만큼 학습에 들어가는 비용이 커진다.
• 적절한 데이터의 양을 100만 row, epoch수를 10회 이하라고 가정한다면 layer 4단까지가 적절할 것이라 생각된다.

4단 auto encoder에서 layer 구성에 따른 loss 값 비교

• 이전 실험을 진행하면서, layer 쌓는 방식을 다양하게 시도해봤는데, bottle neck layer 주변에 layer 를 더 많이 쌓았을 경우에 loss 값이 더 많이 감소하는 것 같은 모습이 관찰됐다. 이와 같은 관찰에 대해 정량적으로 확인하기 위해 실험을 진행했다.
• 위의 그림과 같이 layer 의 dimension을 bottle neck 까지 균일하게 감소시켰을때와, bottle neck 부분에 더 많이 쌓았을 때 각각에 대해 학습시키고 loss 값을 비교했다
• 위의 표를 보면 bottle neck 주변으로 layer 를 모았을때에 loss 값이 점점 더 낮아지고 있음을 확인할 수 있다.

• TFX 가 뭐고, 어떤 구성요소, 라이브러리를 포함하는지 확인한다. 또한 우리 시스템에 적용이 가능한 부분이 있는지 확인한다.
• 특히 TFX라이브러리 중 TFT(TensorFlow Transform)부분만 독립형 라이브러리로 사용해본 바 있는데, 아래 네개 구성요소에 대해서 활용해도 좋을 것 같다는 생각이 든다.
  • StatisticsGen : 인풋데이터의 통계를 계산 → 지금은 feature null ratio 계산하는 부분 다른 잡으로 두고 있는데 이걸 대체 시켜도 될 듯
  • ExampleValidator : 인풋 데이터에서 이상치 및 누락된 값 찾기 → 지금은 없음
  • Tuner : 모델 hyperparameter 조정 → 지금은 hyper parameter tuning 전혀 안하고 있는데 이거 정기적으로 하도록 수정이 가능하다
  • Evaluator : 학습 결과를 분석(auc등 도출)해서 이전 모델과 비교하여 현재 모델이 프로덕션에 푸시할 수 있을 정도로 '좋은' 상태인지 확인 → 지금은 검증 없이 그냥 올리고, 문제 있을 경우에만 확인해서 후 조치.

무엇?

• Google 에서 제공하는 MLOps 플랫폼 자체

  • 

• TensorFlow를 기반 머신러닝 시스템을 정의, 시작, 모니터링하는 데 공통으로 필요한 구성요소, 라이브러리들을 통합적으로 제공한다

• 데이터 입력(csv, tfrecord 등등의 형태, 선행 플랫폼은 gcp) → kubeflow, airflow, beam 등으로 orchestrating → TFT(TensorFlow Transform)으로 feature화 및 전처리 → Tensorflow 로 학습해서 모델 내보내기(Pusher) → Tensorflow serving 으로 서빙 → TFDV(TensorFlow DataValidation)등으로 모니터링

제공

구체적으로는 아래 세가지를 제공한다고 함

1. ml pipeline과 build 를 위한 toolkit
2. 표준 구성 요소
3. TFX 라이브러리

1. ml pipeline과 build 를 위한 toolkit

• tfx pipeline 쓰면 airflow, apach beam, kubeflow 등에서 ml 워크플로우 조정 가능
• ml 의 주기적 학습과 데이터 적재를 위해서 에어플로우, 쿠베 플로우 등을 사용할 수 있을텐데, 이걸 tfx pipeline에 통합해서 사용이 가능한 듯

2. 표준 구성 요소

• 파이프라인의 일부 혹은 모델 학습 스크립트에 일부로 사용될 수 있는 표준 구성요소의 집합

• 즉, ml pipeline을 구현하는 일련의 구성요소 자체들(모델링, 학습, 추론 제공 및 배포 관리가 포함됨)

• 여러가지가 있지만 이것들중 일부는 kubernetes에서만 지원한다거나 tfx 전체를 써야만 이용 가능하다거나 한 게 있어서 주의해야한다.

• ExampleGen : 입력 데이터 세트를 수집하고 선택적으로 분할하는 파이프라인의 초기 입력 구성요소 (즉, 데이터 입력 부분)

  • 입력: CSV, TFRecord , Avro, Parquet 및 BigQuery와 같은 외부 데이터 소스의 데이터 / 출력: 페이로드 형식에 따라 tf.Example 레코드, tf.SequenceExample 레코드 또는 proto 형식
  • 빅쿼리 쓰고 있다면 쿼리기반으로 바로 연결할 수도 있음 (이게 빅쿼리만 되는게 너무 아쉬움 ㅠ 회사에서 주로 아테나 쓰는데 이게 가능한거면 앞에 있는 데이터 밸런스 맞추는 전처리 spark 코드 다 드러낼 수 있을 것 ㅠ)
  • 빅쿼리 안쓰고 있으면 파일을 읽어와서 쓰면 됨(https://www.tensorflow.org/tfx/guide/examplegen#%ED%8C%8C%EC%9D%BC_%EA%B8%B0%EB%B0%98_examplegen)
  • 이 다음으로 statistics gen, schema gen, example validator, transform, trainer, tuner, evaluator 를 쭉 쓸 수 있음

• StatisticsGen : 데이터 세트의 통계를 계산

  • 입력: ExampleGen 파이프라인 구성 요소로 만들어진 데이터세트 / 출력: 데이터세트 통계

• SchemaGen : 통계를 검사하고 데이터 스키마를 생성

  • examplegen 이랑 statistics gen 의 결과 받아서 스키마 생성한다.
  • (회사에서는 tfx 안쓰고 transform 만 썼는데, 그러다보니 여기서 생성해주는 schema 없어서 이런 경우에는 schema 정의를 수동으로 해주면 된다)

• ExampleValidator : 데이터 세트에서 이상치 및 누락된 값을 찾는다.

  • 여기서 TFDV(TensorFlow Data Validation) 라이브러리 이용하는 것(https://www.tensorflow.org/tfx/guide/tfdv)
  • 스키마가 잘못들어온건 없는지, 학습 데이터가 imbalanced 돼있는지는 않은지를 체크해준다.

• Transform : feature 추출

  • 입력: ExampleGen 구성 요소의 tf.Examples 및 SchemaGen 구성 요소의 데이터 스키마 / 출력: SavedModel을 Trainer 구성 요소로
  • 들어온 데이터를 feature 화 하는것까지 담당하는걸 목표로 하는 듯
  • 근데 사실 해주는게 embedding, scaling 등 같은 기본적인것들밖에 없고 이 안에 또다른 모델을 삽입하거나 하는게 없어서, 거기까지 기대하기는 쉽지 않음
  • 이부분은 TFT(TensorFlow Transform) 라이브러리 쓰는건데, 이거는 TFX 전체를 쓰지 않더라도 따올 수 있는 부분이라 현재 우리 모델에서도 이용하고 있음
  • 이게 있으면 scaling 등의 전처리를 모델 그래프에 포함시킬 수 있게 돼서 데이터 관리가 매우 쉬워짐
    • 이걸 안쓴다면 학습 데이터 앞에, 그리고 inference 하기 직전에 각각 따로 전처리 과정을 적용하게 된다. 즉 전처리 코드를 python구현, typescript 구현 두가지가 각각 존재하게 되어 그 관리가 매우 어려워짐.

• Tuner : 모델 hyperparameter 조정

  • 올해(2021년) 9월까지만해도 이 내용 없었던 것 같은데 새로 생겼나보다!
  • 모델 재학습할때마다 계속 조정하게 할 수도 있고, 이전에 조정했던 내용을 갖고 오게 할 수도 있다고 한다
  • 지금은 keras 모델만 가능하다.
  • 업무에 새로 적용하는거 생각해보자!

• Evaluator : 학습 결과를 분석(auc등 도출)해서 이전 모델과 비교하여 현재 모델이내보낼 모델을 검증하여 프로덕션에 푸시할 수 있을 정도로 '좋은' 상태인지 확인

  • 검증이 활성화되면 Evaluator는 새 모델을 기준선(예: 현재 제공 중인 모델)과 비교하여 기준선에 비해 "충분히 좋은지" 확인. 이를 위해, 평가 데이터세트에서 두 모델을 모두 평가하고 메트릭(예: AUC, 손실)의 성능을 계산. 새 모델의 메트릭이 기준선 모델과 관련하여 개발자가 지정한 기준을 충족하면(예: AUC가 더 낮지 않음) 모델이 "탄생"(양호로 표시됨)하여 Pusher에 모델을 프로덕션 환경으로 푸시해도 괜찮음을 나타낸다.
  • TMA(TensorFlow Model Analysis) 라이브러리 이용하는 부분
  • 이것도 독립형 라이브러리로 사용이 가능하다(tfx사용 안해도 쓸 수 있다.)
  • 지원되는 모델 유형(tf2 keras 등)이 몇가지로 정해져있어서 주의해야한다

• InfraValidator: 모델이 인프라에서 실제로 제공 가능한지 확인, 잘못된 모델이 푸시되지 않도록 한다.

  • 앞에서의 Evaluator 가 모델의 성능을 보장한다면, InfraValidator는 모델이 기계적으로 정상인지 확인하고 잘못된 모델이 배포되는 것을 방지한다.

• Pusher: 인프라에 모델 배포

  • 위의 evaluator 랑 infra validator에서 검증이 만족되면, tensorflow serving 등에 배포한다.

3. TFX 라이브러리

• 아래의 라이브러리들은 tfx구성을 다 쓰지 않더라도 독립형 라이브러리로 제공한다.

• TensorFlow Data Validation(TFDV): 머신러닝 데이터를 분석하고 검증하기 위한 라이브러리. 확장성이 뛰어나고 TensorFlow 및 TFX와 원활하게 연동되도록 설계됐다.

  • 학습 및 테스트 데이터에 관한 요약 통계의 확장 가능한 계산
  • 데이터 분포 및 통계를 위한 뷰어와의 통합 및 데이터세트 쌍(패싯)의 패싯 구조 비교
  • 필수 값, 범위 및 어휘와 같은 데이터에 관한 기대치를 설명하는 자동화된 데이터 스키마 생성
  • 스키마를 검사하는 데 도움이 되는 스키마 뷰어
  • 누락된 특성, 범위를 벗어난 값 또는 잘못된 특성 유형 등과 같은 이상치를 식별하기 위한 이상 감지
  • 이상치가 있는 특성을 확인하고 문제를 수정하기 위해 자세히 알아볼 수 있는 이상치 뷰어

• TensorFlow Transform(TFT): TensorFlow를 사용하여 데이터를 전처리하기 위한 라이브러리.

  • 평균 및 표준 편차로 입력 값을 정규화
  • 모든 입력 값에 걸쳐 어휘를 생성하여 문자열을 정수로 변환
  • 관찰된 데이터 분포를 기반으로 부동 소수점 수를 버킷에 할당하여 부동 소수점 수를 정수로 변환

• TensorFlow: TFX를 통한 모델 학습에 사용됩니다. 학습 데이터 및 모델링 코드를 수집하며 SavedModel 결과를 생성. 또한 입력 데이터 사전 처리를 위해 TensorFlow Transform에서 생성한 특성 추출 파이프라인을 통합한다.

• TensorFlow Model Analysis(TFMA): 모델을 평가하기 위한 라이브러리. TensorFlow와 함께 사용되어 EvalSavedModel을 생성하며, EvalSavedModel은 분석의 기초가 됩니다. TFMA를 통해 사용자는 트레이너에 정의된 것과 동일한 측정항목을 사용하여 분산된 방식으로 대량의 데이터에서 모델을 평가한다. 이러한 측정항목은 다양한 데이터 슬라이스에 걸쳐 계산되어 Jupyter 메모장에서 시각화될 수 있다.

• TensorFlow Metadata(TFMD): TensorFlow를 사용하여 머신러닝 모델을 학습시킬 때 유용한 메타데이터의 표준 표현을 제공. 메타데이터는 입력 데이터 분석 중에 수동으로 또는 자동으로 생성될 수 있으며, 데이터 유효성 검사, 탐색 분석 및 변환에 사용된다. 메타데이터 직렬화 형식에는 아래 두가지가 포함된다.

  • 테이블 형식 데이터를 설명하는 스키마(예: tf.Examples)
  • 이러한 데이터 세트에 걸친 요약 통계 컬렉션

• ML Metadata(MLMD): ML 개발자 및 데이터 과학자 워크플로와 관련된 메타데이터를 기록하고 검색하기 위한 라이브러리. 대체로 메타데이터는 위에서 말한 TFMD 표현을 사용한다.. MLMD는 SQL-Lite, MySQL 및 기타 유사한 데이터 저장소를 사용하여 지속성을 관리한다.

  • validator 결과를 여기다가 쭉 저장해놨다가 나중에 검색해서 쓰는 용도
  • 이것도 쓰면 좋을텐데, 시간이 될지 모르겠다.

• "새로운 블록과 비트코인이 블록 체인 네트워크 상에 추가되는 과정"
• 채굴자
  • 블록 생성 위해서 어려운 수학문제를 푸는데 필요한(해시값을 찾아내기 위한) 네트워크에 컴퓨팅 파워 제공(PoW:Proof of Work)하고 보상(bitcoin 등)을 제공받는다. 이때 블록 생성 권한을 얻기 위해 각 노드들은 문제를 푸는데 있어서 속도 경쟁을 해야한다.
  • 채굴자는 네트워크상에서 발생하는 새로운 거래들을 승인(검증)한 후, 전 세계의 노드들이 가진 장부에 해당 거래들을 기록한다.
  • 새 블록에는 지난 블록 이후에 발생한 거래들이 포함되며, 블록의 일부가 되어 블록체인에 추가된 거래는 승인되었다고 간주된다.
• 채굴 보상
  1. 새 블록으로부터 새로운 코인을 생성, 채굴자가 이를 소유할 수 있게 된다.
  2. 해당 블록 내에 들어있는 거래들에 대한 수수료를 받는다.

새 블록을 수신했다는 것이 다른 채굴 노드들에게 주는 의미

• 채굴자는 새 블록을 생성하기 위해서 다른 채굴 노드들과 경쟁을 하게 되는데, 채굴 도중에 새로운 블록이 전파된다면, 노드 사이의 경쟁이 실질적으로 종료되었다고 볼 수 있다.
• 즉, 새로운 블록을 수신한다는 것은, 해당 경쟁에서 다른 누군가가 이미 승리하고 본인이 패배했다는걸 뜻한다.
• 또한 이 경쟁의 종료는 다음 블록을 위한 새로운 경쟁이 시작됐음을 뜻한다.

채굴노드

• 비트코인 네트워크상에는 여러 종류의 노드들이 존재하는데, 이 중 몇몇 노드는 채굴자(miner)라고 부르는 특수 노드들이다.
• 채굴 노드는, 즉 마이너는 비트코인 상에 있는 미승인 거래를 전송받아서 다른 노드들에게 전파하며, 또한 미승인 거래들을 새로운 블록에 추가하는 역할(채굴)을 한다.

마이닝 풀

• 비트코인 개발 초기에는 개인들이 자신의 pc를 이용해 채굴에 참여했지만, 시간이 지날수록 경쟁하는 노드들이 많아지고, 채굴 난이도가 높아져서, 채굴이 어려워졌다. 채굴자들은 혼자 채굴하기보다는, 여러 사람들 개개인의 컴퓨팅 파워를 모아 함께 채굴하여 채굴 확률을 높이기 시작했는데, 이게 'mining pool'이다.
• 혼자 마이닝을 한다고 했을 때 보상을 모두 독차지하는 반면 채굴 확률이 매우 떨어진다. 그러나 마이닝 풀에 참여하여 함께 채굴하면 수익을 셰어해야하지만, 채굴 확률이 높아지므로 적은 금액이라도 꾸준히 수익을 얻을 수 있다.
• 현재 다양한 마이닝 풀이 존재하며, 각 마이닝 풀마다 보상금을 분배하는 다양한 방식이 존재하는데, 대부분의 경우 마이너가 PoW (Proof of Work) 방식을 통하여 풀에 얼마나 기여했는지에 따라 지분의 크기가 결정된다.
• 마이닝 풀을 이용한 채굴 과정
  • 마이닝 풀별로 보상금을 분배하는 기준이 다르기 때문에 자신의 컴퓨터 사양 등을 고려하여, 자신에게 유리한 풀을 선택해야 이익을 극대화한다. 참여하고 싶은 풀을 찾았다면 해당 풀의 웹사이트에 계정을 만들고 채굴을 시작할 수 있다.

마이닝 전체적 과정

• 위 그림에서 노드들은 비트코인 네트워크에서 모두 full node이고, 특히 노란색은 miner라고 가정해보자

  트랜젝션 수신

  1. 몇몇 노드(full node 일수도 wallet 과 같은 light node일수도)들이 거래를 생성하면, 해당 노드는 자신과 연결된 peer node 들에게 생성한 transaction 을 broadcasting 한다.
  2. miner 가 이 전파된 transaction 을 받으면, 이 transaction 이 유효한지 검증한다.
• (트랜잭션의 syntax와 structure가 올바른지, input으로 사용된 UTXO가 mempool이나 블록체인 안에 이미 포함된 것인지 등을 검사)
  3. 유효한 transaction 으로 판단되면 transaction 을 memory pool(=transaction pool)에 추가하고, 자신과 연결된 peer node들에게 전파시킨다. 3-1. 유효하지 않다면 이 트랜젝션 버린다.

마이닝

• 마이너들은 쉬지않고 마이닝을 한다. 마이닝 도중에도 transaction 을 수신, transaction 을 검증, memory pool 에 채우기를 반복한다.
  • 마이너가 마이닝을 중단했다는 것은 알맞은 nonce 값을 찾았거나 다른 마이너가 생성한 새로운 블록을 수신했다는 것을 의미한다.

1. nonce 값을 찾은 경우
   • 새로운 블록을 만든 후, 브로드캐스팅을 하며, 바로 그 블록의 블록헤더 해시를 PreviousBlockHash 에 넣고, 새로운 블록 바디를 구성하여 마이닝을 다시 시작합니다.
2. 다른 마이너가 생성한 블록을 받았을 경우(경쟁에서 진 것)
   • 그 블록의 유효성을 검증하고, 유효하다면, 수신한 블록의 블록헤더 해시를 PreviousBlockHash에 넣고, 새로운 블록 바디를 구성하여 마이닝을 다시 시작한다.

새로운 블록 바디 만드는 과정

• 1. 마이너에게 보내는 코인베이스(블록체인 생성한 자에게 코인을 주는 거래) 트랜잭션을 추가한 후, memory pool에 있는 트랜잭션 중 우선순위가 높은 트랜잭션을 우선적으로 블록 바디에 추가(마이너 자신의 memory pool에 있는 트랜잭션 중에서 새로 생성된 블록에 포함될 트랜잭션들을 제거)
• 2. 이 블록 바디에 있는 트랜잭션들을 이용해서 머클루트를 계산하고, 이것을 블록헤더의 머클루트값으로 사용한다.
• 3. 1,2의 과정으로 후보블록 구성을 완료하고 나면 마이닝 과정을 시작한다.
• 4. 마이닝
  • 위에서 구성한 블록 헤더 전체와 nonce 값을 포함한 값의 hash 값이 bitcoin network 상의 difficult target 값과 비교해서 이 값보다 작거나 같아야 블록 체인 네트워크에 포함시킬 수 있다.
  • nonce 값은 후보 블록에서 유일하게 변경되는 값이기때문에, 이 값을 0부터 시작해서 1씩 증가시켜보면서 전체의 해시값이 적절한지를 비교하게되는데, 이 과정을 마이닝이라고 부르게 된다.
  • nonce 값을 증가시켜 가며 해시값을 계산하는 것을 반복하는 과정은 많은 컴퓨팅 파워를 필요로 하게 되는데, 이렇게 자신의 컴퓨팅 파워를 소모하는 작업을 증명하는 것이 mining의 핵심인 PoW이다.
• 5. 알맞은 nonce 값을 찾고 나면 성공한 블록을 주변 peer 노드들에게 전파한다.
• 6. 새로 생성된 블록을 전달받은 노드들은 블록의 유효성을 검증하고, 블록 유효성 검사를 제대로 통과하면, 각 노드는 자신이 보유하고 있는 local blockchain에 해당 블록을 연결한다.

여러 마이너가 동시에 블록을 생성한 경우

• 위의 블록 바디를 만드는 과정은 하나의 마이너만 하는게 아니기 때문에, 여러 마이너가 동시에 블록을 생성한 경우가 발생할 수 있다. 이때 p2p 네트워크에서 지연 등의 이유로 각 노드는 다른 local blockchain을 보유하게 된다.
• 위의 그림에서 3번 노드는 2번 마이너로부터 생성된 블록을 더 빨리 전달받아서 자신의 local blockchain에 연결했고, 그 이후 5번 마이너로부터 생성된 블록을 전달받아서 이를 고아 블록으로 처리한다.(상황 종료)
• 우선 두 마이너가 동시에 블록 생성에 성공했을 때, 블록의 전파지연으로 블록의 분기(fork)가 발생할 수도 있다. 위의 그림에서처럼 블록체인이 분기된 경우 비트코인에서는 가장 긴 체인을 메인체인으로 정하게 된다. 그림에서는 블록이 하나 더 연결되어 있는 검은색 선의 체인이 메인 체인이 될 것이다.
• 그러면 어떻게 해서 검은색 선의 체인에 블록이 하나 더 연결된 것일까?
  • 왼쪽 그림을 보면 3개의 node가 하늘색 블록을 연결했고, 2개의 node가 파란색 블록을 연결했다.
  • 이 비트코인 네트워크는 축소된 것이라 마이너가 둘밖에 없지만, 사실은 수많은 마이너 들이 비트코인 네트워크에 분포되어 있다. 이런 상황이라면, 상대적으로 해시 파워가 큰 마이너들이 previous 블록으로 연결한 하늘색 블록 뒤에 새로운 블록을 연결할 것이다. 즉, 결국 하나의 메인체인으로 수렴하게 될 것이다.

Reference

• kmooc 블록체인 이론 및 응용 강의 : http://www.kmooc.kr

• 비트코인의 분산화된 합의는 네트워크상의 노드들 사이에서 독립적으로 일어나는 아래의 프로세스에 따라 이루어진다.
  1. 모든 full node 가 각 거래에 대해 독립적으로 검증
  2. 작업 증명(PoW) 알고리즘을 이용하여, 마이너들은 검증된 거래들을 새로운 블록에 추가한다.
  3. 모든 노드들이 새 블록을 검증한 후 블록체인에 연결한다.
  4. 모든 노드가 작업증명을 통해 연결한 체인들 중 가장 긴 체인을 선택한다.
• 위 네 과정을 자세히 보고, 이 과정들이 어떻게 서로 상호작용하는지 확인하자

1. 각 거래의 검증

• 자세한 검증 과정은 (https://en.bitcoin.it/wiki/Protocol_rules)여기에서 확인할 수 있다. 아래는 이중 몇가지를 가져온 내용이다.
  • 1. 트랜잭션의 구문과 데이터 구조가 정확한지 확인
  • 2. 코인 베이스 거래는 전송할 수 없음. 새로운 블록이 생성될 때 보상으로 제공되는 코인 베이스의 경우, 일반적인 거래처럼 다른 노드에게 전송할 수 없다.
  • 3. 각각의 입력값에 대해, 참조 출력값이 풀 내의 어떠한 거래 내부에 이미 존재한다면 해당 거래는 거부되어야 한다.
  • 4. 짝을 이루는 거래가 풀에 존재하지 않는 경우 고아 거래 풀에 추가된다.
  • 5. 각각의 입력값에 대해 참조 출력값은 존재해야 하며, 해당 UTXO가 이미 소비된 상태가 아니어야 한다.
  • 6. 입력값 금액이 출력값 총액보다 작은 경우 해당 거래를 거절해야 한다. 입력값이 출력값보다 작을 수 없다.
  • 7. 새로운 블록에 포함되기에 거래 수수료가 너무 작은 경우, 해당 거래를 거절할 수 있다.

2. 블록에 추가

• 비트코인 네트워크에 있는 노드들은 peer 로부터 전달받아, 스스로 검증한 transaction 들을 Memory pool(=transaction pool)에 추가한다. 각 transaction 들은 블록에 포함되기 전까지 Memory pool에서 대기하게 된다.
• 간단히 예시로 transaction 이 block 에 추가되는 과정을 보자.
• 위와 같은 block 과 memory pool 이 있을때에 앨리스라는 사람이 비트코인을 이용해 커피 한 잔을 사려고 한다고 가정해보자.
• 앨리스가 커피를 구매할 때쯤, 비트코인 네트워크상에 277314번까지의 블록이 생성되어 있는 상태이다. 이때, 채굴 노드는 다른 노드들처럼 앨리스의 커피 구매라는 transaction을 수집하고 검증하며, 다른 노드들에게 전파하려 할 것이다.
• 노드가 채굴하는 동안 비트코인 네트워크를 통해 277315번째 블록을 전달받을 수 있는데, 이렇게 새로운 블록이 도착했다는 것은 277315번 블록에 대한 경쟁이 끝나고, 다음 번 블록, 277316번 블록을 생성하기 위한 경쟁이 시작된다는 것을 의미한다. 이전 10분 동안 노드는 277315번 블록을 위한 문제를 푸는 동시에, 다음 번 블록에 대비하여 거래들을 수집하고 있었을 것이다.
• 메모리 풀에는 이렇게 수집된 수백 개의 거래가 있다고 가정해보자. 277315번 블록이 도착해서 검증되자마자, 노드는 메모리 풀 내에 있는 거래들 중 277315번 블록에 포함된 거래들을 모두 삭제한다. 이후 남아있는 거래들은 모두 미승인 상태이며, 새로운 블록에 기록되기 위해 대기 중이다.
• 이 미승인 거래들을 기록 하기 위해, 노드는 즉시 비어 있는 블록을 새로 만들며, 이 블록이 277316번째 블록이 될 수 있는 후보가 된다. 이 블록은 아직 증명되지 않아, 유효한 블록이 아니기 때문에 후보 블록이라고 칭하며, 뒤에 설명할 작업증명(PoW) 알고리즘에 대한 솔루션을 찾은 경우에만 유효화된다.
• 따라서 앨리스가 커피를 구입한 것에 대한 거래가 포함된 후보 블록이, 채굴 노드에 의해 채굴되면 비로소 277316번째 블록에 앨리스의 거래가 추가된다.

PoW

• 새로운 블록을 블록체인에 추가하기 위해서는 블록 헤더의 해시를 계산해야 한다. 이 블록 해시값이 블록 내에서 설정한 숫자, 즉 난이도보다 작다면 문제의 해답을 찾은 것이다.
• 해시값은 원본 데이터에 따라 결과값이 달라지게 되는데, 블록 헤더의 필드들 중 nonce를 제외한 나머지 필드는 그 값이 고정되어 있다. 따라서 PoW 알고리즘에서는, 특정 범위에 포함되는 출력값을 얻기 위해, 적절한 nonce 값을 찾는 것이 목표다. 즉, nonce 값은 이 nonce 값을 입력값 중 하나로 취하여 계산되는 블록 해시값이 _특정 숫자_보다 작아지게 하는 값을 말한다.
• 해시 함수의 특성에 따라 역방향 계산이 어렵기 때문에 특정 결과에 도달할 때까지 nonce 값을 무작위로 바꿔가며 값을 찾아야 한다.
• 이러한 연산은 어렵고 복잡한 연산은 아니지만, 특정 nonce 값을 찾기 위해 기하학적인 횟수의 연산을 실행해야 한다.

Difficulty bit (난이도 bit)

• 위에서 블록 해시값이 특정 숫자보다 작아지게 하는 값을 찾는 과정이 nonce 값을 찾는 마이닝 과정이라고 했는데, 이 특정 숫자는 어떻게 정해지는지 알아보자
• 이 특정 숫자는 난이도 값이라고 불리는데, 블록 헤더 내의 ‘난이도 비트’ 정보에 따라 결정된다.
• 해당 필드는 얼마나 많은 리딩 비트가 0이어야 하는지 나타내는 단위로, 목표값의 0의 개수가 많을수록 난이도가 더 어려워진다. 리딩 0의 숫자를 1비트씩 증가시킬 때마다, 가능한 검색 공간의 크기가 절반으로 줄어들기 때문이다. 이는, 한정된 범위를 만족하는 특정 값을 도출해내는 것이 더 어려워짐을 의미한다.
• 0의 개수가 많아질수록 허용 가능한 범위가 더 작아진다. 따라서 1비트씩 난이도가 상승할 때마다, 솔루션을 찾는 데 걸리는 시간이 기하급수적으로 증가한다.

Difficulty bit 의 조절

• 위에서 말한 난이도는 어떻게, 누가 조정하게 되는지 알아보자.
• 비트코인 네트워크상에서 블록은 10분에 하나씩 블록이 생성되는것을 목표로 하며, 이 생성 주기를 바탕으로 통화 발행 빈도와 거래 정상 속도가 결정된다. 블록의 생성 시간을 10분으로 유지하기 위해서, 채굴의 난이도는 컴퓨터 능력의 증가 속도와 채굴에 참여하는 컴퓨터의 수에 따라 조정하게 된다.
• 난이도 재설정은 풀 노드 전부에서 독립적으로 실행한다.
• 2,016 개의 블록이 네트워크상에 추가될 때마다 노드들은 난이도 목표값을 재설정한다. 난이도 재설정 동작은 다음과 같은 방정식으로 요약할 수 있다.
• 2,016개의 블록이 생성되는데 소요되는 시간이, 평균 시간인 20,160분보다 오래 걸린다면, 채굴 난이도를 낮추고, 적게 걸린다면 채굴 난이도룰 높이는데, 이 난이도 조정에 따라 블록이 생성되는 주기를 10분으로 유지한다. 이 난이도는 노드 별로 다른 값을 가지는 것이 아니라, 블록체인 전체에 걸쳐 일률적으로 적용되는 수치이다.

후보 블록은 어떤 transaction들로 채워지는가

• 블록 내부의 첫 50KB는 우선순위가 높은 거래들에게 할당되고, 블록의 최대 크기 이내의 나머지 공간들은 최고 수수료를 가진 거래부터 우선적으로 선택되게 된다.
• 우선순위
  • Transaction 의 우선순위는 소비될 UTXO의 나이를 근거로 정해진다.
  • UTXO의 나이는 블록체인에 기록된 이후 지난 시간과 같다. 해당 UTXO가 블록체인상에 얼마나 깊이 파묻혀 있는지를 나타낸다. 나이가 많고 큰 입력값을 가진 UTXO가 나이가 어리고 작은 입력값을 가진 UTXO에 비해 높은 우선순위를 가진다.
  • 트랜잭션의 우선순위는 입력값의 가치와 나이의 총합을 거래의 크기로 나누어 계산한다.
  • 위에서 언급했듯 블록 내부의 첫 50KB는 우선순위가 높은 거래들에게 할당되어 있기때문에, 수수료 없이도 처리될 수 있다. 그러나 자신이 생성한 거래가 블록에 빨리 포함되길 원하는 경우, 수수료를 높임으로써 시간을 줄일 수도 있다.(나이가 많지 않아도 블록에 포함될 기회를 얻을 수 있기 때문)

블록 생성 보상

• 블록 생성에 대한 보상은 (코인베이스) + (블록에 적힌 transaction 들의 거래수수료)이다.
• 코인베이스
  • 이전 글에서, 채굴에 대한 댓가로 비트코인과 거래수수료를 얻을 수 있다고 했었는데, 이때의 블록 생성으로 얻는 코인 보상을 코인베이스(블록을 생성하면서 새롭게 생성된 코인을 의미)라고 부른다.
  • 블록에 첫 번째로 추가되는 거래는 특수 형태의 거래로, 생성 거래(transaction) 혹은 코인베이스 거래 라고 부른다.
  • 코인 베이스 보상금은 네트워크의 반감 횟수에 따라 결정된다. 최초의 비트코인 코인베이스는 50비트코인이었다. 210,000개의 블록마다 반감기가 한 번 발생하기 때문에, 현재 블록의 높이를 반감기 간격으로 나눔으로써 반감 횟수를 결정할 수 있다. 반감 횟수만큼 보상금이 절반씩 감소한다.
• 거래 수수료
  • 거래 수수료의 총액은 거래의 입출력 값을 각각 더한 후, 두 값을 빼서 계산할 수 있다.

3. 블록의 유효성 검증

• 아래 항목들을 충족하지 못할 경우 해당 블록들은 유효성 검증을 통과하지 못한다.
  • 해당 블록의 데이터 구조는 문법적으로 유효해야 한다.
  • PoW의 원리에 따라, 블록 헤더의 해시값은 사전에 정의된 목표 난이도보다 작아야 한다.
  • 해당 블록의 타임 스탬프는 향후 2시간 이내여야 한다.
  • 해당 블록의 크기가 허용 가능한 한도 내에 있어야 한다.
  • 마지막으로, 블록 내에 포함되는 제일 첫 거래는 코인베이스 생성거래여야 한다.

4. 가장 긴 체인의 선택

• 비트코인 합의 메커니즘의 마지막 단계는 블록을 체인 안에 모아 가장 많은 작업 증명을 보유하고 있는 체인을 선택하는 것이다.
• 노드가 새로운 블록을 검증하고 나면, 해당 블록을 기존의 체인에 연결함으로써 체인을 연장하려고 한다. 블록체인에는 메인 블록체인에서 나와 브랜치를 형성하는 2차 체인이 존재한다. 누적 난이도가 가장 큰 값을 가진 블록들로 구성된 체인이면 어떠한 것이라도 메인 체인이 될 수 있다. 대부분의 경우, 가장 많은 블록으로 연결된 체인이 메인 체인이 된다.
• 블록체인 네트워크상에서 동시에 둘 이상의 새로운 블록이 생성되면, 블록체인의 분기(fork)가 발생하게 된다.
• 이 그림과 같이, 네트워크상에 2개의 블록이 동시에 생성되었다고 가정해보자. 네트워크상에 같은 높이로 존재하는 두 블록을 각각 초록색과 주황색으로 표시했다. 이 블록들은 가까운 이웃 노드들에게 전파된다.
• 이 상태에서, 한 노드의 마이닝에 의해 초록색 블록을 부모 블록으로 가지는 새로운 검정색 블록이 생성되었다고 해보자.
• 이 검정색 블록이 네트워크상에서 전파되어 나가다가, 주황색 노드가 체인에 연결된 노드를 만나게 될 것이다.
• 주황색 블록이 체인에 연결되어 있는 노드들의 경우, 새롭게 전달받은 검은색 블록의 부모 블록인 초록 블록이 존재하지 않기때문에, 이러한 경우 블록체인의 분기가 발생한다.
• 주황색 블록을 연결하고 있던 노드의 경우는 그림과 같이 분기된 체인을 형성하게 된다. 이때 주황색 체인이 2차 체인으로 변경되고, 더 긴 길이를 가지는 녹색-검은색 블록을 메인체인으로 연결하게 된다.
• 2차 체인으로 분류된 주황색 블록은 녹색-검정 블록이 메인체인으로 연결됨에 따라 고아 블록이 된다.

고아블록(orphan block)

• 유효한 블록이긴 하지만, 부모 블록이 현 체인에서 발견되지 않는 블록을 고아 블록이라고 한다. 기록은 있으나 메인체인에서 유지되지 않기 때문에 아무런 의미를 지닐 수 없는 블록이다.
• 분기된 두 체인에서 동시에 블록이 생성되어 연결되는 경우가 있을 수 있다. 이 경우, 두 체인은 체인을 더 길게 연결하려는 경쟁을 하게 되는데, 이 경쟁에서 승리해 더 긴 체인을 유지하는 체인이 메인체인이 된다.
• 그렇다면, 주황색 블록(고아블록)에 포함된 거래들은 어떻게 되는 것일까?
  • 생성된 거래들은 네트워크 전체로 전파되기 때문에, 주황색 블록에 포함된 거래들은 이미 녹색 또는 검은색 블록에 포함되었거나 추후에 포함될 것이다.
  • 거래 자체가 유효하기만 한다면, 시간이 걸릴 뿐 반드시 블록에 포함되게 된다.

컨퍼메이션(confirmation)

• 컨퍼메이션은 특정 트랜잭션이 블록에 포함된 이후 몇 개의 블록이 뒤에 더 추가되었는지를 알려주는 지표이다. 컨퍼메이션이 충분히 크다는 것은, 이 트랜잭션은 충분히 오랫동안 변동 없이 블록에 보관되어왔기 때문에, 취소될 가능성이 적다라는 것을 의미한다.
• 1 컨퍼메이션은 해당 거래가 블록에 포함되어 블록체인에 연결되었음을 나타낸다. 체인이 분기된 경우, 분기된 체인 중 하나의 체인이 확실히 메인 체인으로 선택되기까지의 기준을 6 컨퍼메이션으로 정하고 있다. 두 체인이 경쟁하게 된다 하더라도 새로운 블록이 6개가 추가로 생기기 전에 경쟁이 끝나게 됩니다.
• 따라서, 자신이 생성한 거래가 포함된 블록이 체인에 연결된 이후 6 컨퍼메이션을 가진다면, 해당 블록이 추후에 버려질 가능성이 없다는 것을 의미한다.

Reference

• kmooc 블록체인 이론 및 응용 강의 : http://www.kmooc.kr

1. explainer 의 선택

• 해당 레포는 아래 링크에서의 여러 explainable model 논문의 구현체를 통합하여 제공하고 있다.
  • https://github.com/slundberg/shap#methods-unified-by-shap
  • 이 각 방법들은 explainer 라는 이름으로 제공되고 있으며, TreeExplainer, GradientExplainer, DeepExplainer 등의 9개의 explainer 가 있다.
• 이 9개의 explainer 들 중 deep learning model 에 활용할 수 있는 건, DeepExplainer 와 GradientExplainer, 이렇게 딱 두 가지이다.
• 이중 GradientExplainer 는 tensorflow, keras, pytorch의 세 모델 코드에 적용이 가능한 한편, DeepExplainer 는 tensorflow, keras 에만 적용이 가능하니 주의하자.

2. embedding layer 의 존재에 따른 explainer 선택

• (이걸 꽤 나중에야 깨달아서 많이 화가났었다...)
• gradient explainer 의 경우 multi input 을 받으면서도, embedding layer 를 포함한 경우 사용할 수 없다!
• issue에 보면 이것과 관련해서 말이 많은데, 명확히 된다 안된다 말이 나오는 경우 없이, 성토의 자리가 되고 있어서(혹은 이거말고 다른 explainer 를 썼더니 되는것같더라) 이걸 확신하고 다른 길로 트는데에 나도 오래걸렸다.
• 2021년 9월 29일까지는 분명히 안된다...
• issue 에는 embedding layer 의 element 각각을 평균 내서라도 어떤 값을 떨어트려주면 안되냐는 식의 요청 혹은 질문들인데, 아직까지 반영이 안되고 있다.

3. input 형태

• 다른 explainer 는 잘 모르겠지만 deep explainer 와 gradient explainer 의 경우 input layer 가 하나만 존재하는 경우를 기본 상황으로 보고 있는지, api document 에는 이에 관해서만 설명되어있다.(https://shap-lrjball.readthedocs.io/en/latest/generated/shap.DeepExplainer.html#shap.DeepExplainer)
• 그러나 여러 input layer 를 병렬적으로 두고, 합쳐서 사용하는 것이 이보다 더 일반적인 사용이기때문에, 이 표기만 보면 문제가 생길 수 있다.
• api document 에서는 input 으로 np array 와 dataframe 만을 받는다고 나와있지만, multiple input layer 를 사용할 경우 경우 각 feature 들을 np.array 로 하는 list 형태로 넣어줘야한다...

4. input 의 순서

• 위에서와 같이, 여러 feature 들을 list 로 받다보니, feature 입력 순서가 중요해진다.(input layer 이름과 매핑하는 등의 과정이 전혀 없다.)
• 이때 tensorflow 와 keras의 경우, model.summary()에서 표시되는 feature 의 순서로 하면 된다.

5. tf2 지원X

• deep explainer 의 경우, tf2 지원이 되지 않는다.(gradient explainer는 된다!)
• 사실 5번의 이유를 먼저 깨닫고, 2번의 이유를 나중에 깨달았기때문에, 본인은 gradient explainer 를 쉽게 포기하지 못하여 길게 삽질을 했었다...
• 아래의 글을 잔뜩 참조하고 나서야 tf2지원이 안되는것을 깨달았다.
  • https://github.com/slundberg/shap/issues/1079
  • https://github.com/slundberg/shap/issues/1406
  • https://stackoverflow.com/questions/64226155/lookuperror-gradient-registry-has-no-entry-for-shap-tensorliststack-using-de
  • https://github.com/slundberg/shap/issues/1551
• 위에 글에서와 같이 eager execution 을 끄고 진행하면 잘 동작한다.
• 그러나 이때에는 tf2에서처럼 tfrecord 에서 parsing 한 tensor 자체를 input으로 바로 넣어줄 수는 없게 돼서, 3번의 그림에서와 같은 괴상한 형태로 input을 만들게 된다 ;ㅁ;

마무리 하며...

• 내가 사용한 https://github.com/slundberg/shap의 레포는 받는 관심에 비해서, as가 활발하지는 않은 안타까운 레포인 것 같다.
• 글을 쓰고 있는 현재(2021년 12월 20일)star 수가 14k 인 것에 반해, issue 1.2k개가 open 된 상태로 방치되어있다...
• 쓸 수는 있는 상태지만, 그 편의성이 다소 안타까울 따름이다...