FM?

  • Factorization Machines (FM)은 feature engineering 하는데 사용되는 generic approach
  • large domain에서의 categorical variables 사이에 interaction을 estimating하는데 사용된다.
  • libFM stochastic gradient descent (SGD), alternating least squares (ALS) optimization:

설치

  • latest release를 다운로드 받자
    • $ wget http://www.libfm.org/libfm-1.42.src.tar.gz
  • $ tar xvf libfm-1.42.src.tar.gz

메뉴얼

  • http://www.libfm.org/libfm-1.42.manual.pdf
  • 데이터 포맷은 어떻게 맞추는지, estimate은 어떻게 하는지에 대해서 자세하게 설명이 되어 있음.

categorical 데이터를 FM의 Data Format으로 변경

  • $ ./tripleformatto_libfm.pl -in /home/lee/workspace/ -target 2 -separator "\t"

참고

  • http://www.libfm.org/
  1. ymk 2019.01.29 18:27

    논문 잘읽었습니다!! 저도 feature engineering에 관심이 생겨서 공부중인데
    다음과 같은 논문들이나 자료들은 어디서 볼 수 있나요? nips같은데 뒤적뒤적해보는데 잘 모르겠네요 ㅠㅠ

    • 2019.01.29 18:37

      비밀댓글입니다

FM?

  • Factorization Machines (FM)은 feature engineering 하는데 사용되는 generic approach
  • large domain에서의 categorical variables 사이에 interaction을 estimating하는데 사용된다.
  • libFM stochastic gradient descent (SGD), alternating least squares (ALS) optimization:

설치

  • latest release를 다운로드 받자
    • $ wget http://www.libfm.org/libfm-1.42.src.tar.gz
  • $ tar xvf libfm-1.42.src.tar.gz

메뉴얼

  • http://www.libfm.org/libfm-1.42.manual.pdf
  • 데이터 포맷은 어떻게 맞추는지, estimate은 어떻게 하는지에 대해서 자세하게 설명이 되어 있음.

categorical 데이터를 FM의 Data Format으로 변경

  • $ ./tripleformatto_libfm.pl -in /home/lee/workspace/ -target 2 -separator "\t"

참고

  • http://www.libfm.org/

Neural Factorization Machines for Sparse Predictive Analytics

Abstract

  • web applications의 predictive tasks는 categorical variables을 modeling하는게 필요하다.
  • categorical data
    • user IDs
    • demographics
    • genders
    • occupations
  • standard machine learning에서는 binary features의 set으로 변환을 했다 (one-hot encoding). 결과적으로 feature vector는 highly sparse한 결과물이 생긴다. 이러한 sparse data를 효과적으로 학습하기 위해서는 features 사이에 interactions를 설명하는게 중요하다.

  • Factorization Machines(FMs)는 second-order feature interations을 효율적으로 사용하는 유명한 솔루션이다. 그러나 FM은 feature interactions을 linear way로만 학습을 할 수 있고, real-world data의 non-linear와 complex inherent structure를 capturing하기 충분하지 못하다.

  • deep neural networks는 최근 non-linear feature interactions를 학습하는데 적합하다.
    • Wide & Deep (google)
    • DeepCross (Microsoft)
  • deep structure는 그동안 train하는게 어렵다.

  • Neural Factorization Machine (NFM)을 제안 sparse settings에서.

  • NFM은 seamlessly combine
    • linearity of FM in modeling second-order feature ineteractions
    • non-linearity of neural network in modeling higher-order feature interactions
  • 기존 알고리즘과 비교했을때 shallower structure, better performance, much easier to train and tune in practice

Introduction

  • Predictive analytis는 most important techniques information retrieval(IR), data mining(DM), ranking from recommendation systems, targeted advertising to search ranking, visual anlaysis, and event detection
  • predictive는 estimating a function으로서 formulated하는 task를 말한다. 예를 들면 real value는 regression, classification은 categorical target. continuous predictor variables는 images, audio
  • web applications에서는 대부분 discrete and categorical 데이터

    • online advertising
    • predict how likely (target) a user (first predictor variable) of a particular occupation (second predictor variable) will click on an ad (third predictor variable)
    • predictive models을 build 하기 위해서는 공통적으로 categorical variable을 a set of binary features으로 변경을 해야 한다.(a.k.a feature vector) - one hot encoding

    • 그 이후에 standard machine learning에 적용을 한다.

  • possible value of categorical predictor variables에 따라 generated feature vector는 sparse하지만, 매우 높은 dimension을 가질 수 있다.
  • sparse data로 효율적으로 ML models을 build 하기 위해서는 features 사이의 interactions을 설명하는게 가장 중요하다.
  • crafting combinatorical features
    • cross features: constructing new features by combining multiple predictor variables
    • occupation = {banker, docker}, gender = {M, F} ---> occupationgender = {bankerM, bankerF, dockerM, docker_F}
  • crafting combinatorical features는 high cost로 heavy engineering efforts, useful domain knowledge to design effective features가 요구 된다. 이 말은 즉 solutions은 새로운 문제 또는 도메인에서 generalize하는게 어렵다

  • argumenting(늘리다) feature vectors 대신에 다른 솔루션으로 ML model을 디자인 하기 위한것으로 raw데이터 에서 feature interfactions을 자동으로 배운다. factorization machines (FMs)는 embededs features를 latent space와 embedding vectors의 inner product를 통해서 features 사이의 interactions을 모델링 한다.

  • FM의 성능은 linearity에서 한계가 있다. (modeling of pairwise feature interactions only)
  • real-world data는 complex, non-linear underlying structure를 갖고 있다. 결과적으로 FM은 충분히 real-word의 데이터를 표현하기에는 부족함이 있을 것이다. higher-order FMs가 제안되긴 했지만, 그것은 여전히 linear models에 속할 것이고, estimate하는데 어려움이 있을 것이다. higher-order FMs은 FM보다 더 좋은 성능을 보여주고 있다고 주장을 하지만, linear way의 higher-order interactions을 lineary way로 modeling했기 때문이라고 주장하고 있다.

  • sparse data prediction인 Neural Factorization Machiens (NFMs)을 제안한다.

    • modeling higher-order and non-linear feature ineteractions
  • Bilinear Interaction (Bi-Interaction) pooling 의 새로운 operation을 devising했다.
  • FM을 neural network framework에서 첫번째로 위치 시켰다.
  • Bi-Interaction layer위에 non-linear lyaers를 stacking을 shallow linear FM을 deepen 할 수 있었다.
  • higher-order and non-linear feature interactions은 FM의 표현을 증가시킬 수 있었다.
  • traditional deep learning methods 방식인 low level에서 concatenate, average embedding vectors와 반대로 이 논문에서는 Bi-Interaction pooling informative feature interactions을 encodes 했다. Bi-Interaction은 따라오는 deep layers에서 meaningful information을 배우기 수월하게 해준다.

  • Contributions

    • Bi-Interaction pooling operation
    • FM아래 neural network framework를 deep하게 해서 higher-order, non-linear interactions을 학습시킨것
    • extensive experiments

Modeling Feature Interactions

  • large space of combinatorical features의 이유로 feature enginerring을 하거나, feature selection techniques(boosted decision tree to select imprortant feature interactions)을 사용했다.
    • 위 솔루션은 tarining data에서 갖고 있지 않은 combinatorical features을 generalize 할 수 없다.
    • 데이터가 많으면 문제 해결이 아닌가?
  • 최근 embedding-based methods가 popular한데, raw data로 부터 feature interactions을 학습한다.
  • high-dimensional sparse features를 low-demensional latent space로 embedding을 하면 model은 unseen feature combinations을 generalize를 할 수 있다.
  • domain과 상관없이 factorization machine-based linear models, neural network based non-linear models에 적용이 가능하다.

Factorization Machines

  • factorization machines은 collaborative recommendation을 위해서 제안된 방법
  • FM은 모든 feature의 interactions에 대해서 학습을 한다.
  • matrix factorization (MF)와 반대로 FM은 오직 두개의 entities의 관계를 모델링
  • FM은 linear/logistic regression (LR)과 함께 second-order factorized interactions between features.
  • FM은 sparse data prediction을 위한 effective embedding methods

Expressiveness Limitation of FM

  • FM의 성능은 좋지만, FM은 linear models이다. 다른말로 target은 linear 모델로 설명이 가능하다.
  • FM을 pre-training해서 사용하면 성능이 더 좋음

Deep Neural Networks

  • speech recognition, computer vision, natural language processing에 deep learning이 사용이 되고 있는데, IR과 DM에서는 많이 사용을 안하고 있는데, 그 이유는 대부분의 데이터가 sparse하기 때문이다.
  • DNNs이 dense data로 부터 patterns을 학습하는데 강력한 능력을 갖고 있지만, sparse data에서는 less scrutiny(정밀한 조사)이고, sparse settings에서 feature interactions을 효율적으로 learning하기 위해 어떻게 employ해야하는지 모른다.
  • 최근들어서 DNNs을 sparse predictive analytics에서 사용하기 시작했다.
    • neural collaborative filtering framework는 users와 items의 관계를 interactions을 학습한다. 이후에 model attribute interactions을 위해서 CF가 등장. 그러나 이 방법들은 두개의 entities의 관계만을 학습하고, general settings of supervised learnings을 직접적으로 지원하지 않는다.
    • FM-supported Neural Network(FNN), FM으로 feature embeddings을 사용해서 DNNs을 초기화
    • Wide & Deep, Multi-layer perceptron, concatentation of feature embeddings vectors to learn feature interactions
    • DeepCross
    • Wide & Deep 과 유사하고, MLP를 residual network로 변경

Optimization Difficulties of DNN

  • neural network-based approaches의 공통된 structure
    • stacking multiple layers above the concatenation of embedding vectors to learn feature interactions
  • implicit way의 combinatorical features of arbitary orders 을 배울수 있는 multiple layers
  • 단순하게 concatenating feature embedding vectors는 too little information about feature ineteractions in the low level
    • item, user를 단순하게 concatenating을 하면 embedding vectors는 collaboriative filtering에서 very poor results를 가져다 준다.
  • 위 문제를 해결하기 위해서, deep layers을 사용해 meaningful interaction function을 학습하는 방법이 있다. multiple non-linear layers는 feature inteactions을 잘 학습할 수 있다.
  • deep architecture는 vanishing/exploding gradients, overfitting, degradation, among otehrs의 notorious(유명한) problems으로 optimize하는게 어렵다.

  • DNNs의 optimzation의 어려움을 설명하기 위해서, training, test error를 each epoch에 plot을 했다.

  • 실제 실험에 사용한 parameters와 architectures를 사용했다.
    • Wide&Deep 3 layers, DeepCross 10-layer residual network
  • Wide&Deep에서 training error는 상대적으로 높았다. 이 문제를 degradation problem 때문
    • pre-training 해서 degradation problem을 해결
  • DeepCross에서는 낮은 training error를 보여주었지만, high test error를 보여줬다. overfitting
    • pre-training을 해도, overfitting 을 해결할 수 없었음
  • FNN으로 pre-train을 하고, DNNs을 initialize했다. (11%의 성능향상)
  • concatenating feature embedding vectors, Bi-Interaction operation을 적용
    • informative representation이 더 높음
    • higher-order interactions을 학습하기 위해 subsequent non-linear layers를 도와준다.

Neural Factoriaztion Machines

  • NFM은 sparse data modeling을 하기 위해서 FMs와 neural networks를 합쳤다
  • 거기에 플러스로 dropout, batch normalization을 사용

The NFM Model

  • factorization machines과 유사하게 NFM은 general machine learner
  • sparse Vector가 input으로 들어올때, xi=0은 i-th feature의 값은 존재하지 않는다를 의미
  • f(x)는 NFM의 core component로서 feature interactions을 modlieng하기 위한 것. (multi-layered feed forward neural network)

  • Embedding Layer

    • 임베딩 레이어. 임베디드 레이어는 각 기능을 밀집된 벡터 표현으로 투사하는 완전히 연결된 레이어입니다. 공식적으로, vi ∈ Rk를 i 번째 피쳐에 대한 임베딩 벡터 라하자. 우리는 임베딩 벡터 Vx = {x1v1, ..., xnvn}의 집합을 얻어서 입력 특징 벡터 x를 표현한다. x의 드문 드문 한 표현 때문에 비 - 제로 피처, 즉 Vx = {xi vi}에 대해 임베딩 벡터를 포함하기 만하면됩니다. 여기서 xi는 0입니다. 단순히 입력 특성 값으로 매립 벡터를 재조정했습니다 실제 가치있는 기능을 설명하기 위해 임베딩 테이블 조회
    • embedding layer는 fully connected layer로 각 feature를 dense vector representation으로 project
    • vi는 i-th feature에 embedding vector
    • embedding 이후에 input feature vector x를 나타내기 위해 embedding vectors의 set을 얻게 된다. Vx = {x1v1, ... ,xnvn}
    • x의 sparse representation 때문에, non-zero features를 위한 embedding vectors를 포함해야 한다.
  • Bi-Interaction Layer
    • embedding set Vx를 Bi-Interaction layer에 feed
    • pooling operation (set of embedding vectors을 one vector로 converts)
    • embedding space에서 features사이에 second-order interactions를 encodes -> k-dimension vector로 Bi-interaction pooling
    • Bi-Interaction pooling은 extra model parameter가 필요하지 않고, linear time에 효율적으로 계산이 가능하다.
    • 이 property는 average/max pooling, concatenation과 같다.
    • pairwise feature interactions modeling을 하는데 추가적인 코스트가 필요 없다.
  • Hidden Layers
    • 위에서 Bi-Interaction pooling layer는 stack of fully connected layer로, features 사이에 higher order interactions을 학습할 수 있다.
  • Prediction Layer

    • last hidden layer Zl은 final prediction score로 변환되는 ouput vector
  • NFM Generalize FM

    • FM은 shallow, linear model, hidden layer가 없는 NFM의 special case에서 볼 수 있다.
    • L에 zero를 세팅하고 Bi-Interaction pooling to prediction score (L은 hidden layer의 개수)
    • neural network framework의 아래에서 FM의 표현력을 확인할 수 있다.
    • FM에서 learning, generalization ability를 향상시키기 위해서 다양한 neural network techniques를 사용했다.
    • dropout을 써서 overfitting을 prevent
    • Bi-Interaction layer는 regularize FM을 하기 위한 방법으로 사용, conventional L2 regularization보다 더 효과적인 것을 찾아 냈음.
  • Relation to Wide&Deep and DeepCross

    • NFM은 여러 유사한 deep learning 솔루션과 유사하게 multi-layered neural architecture를 갖고 있다.
    • key difference는 Bi-Interaction pooling component는 NFM에서 만 사용하고 있다.
    • Bi-Interaction pooling을 concatenation과 변경하고 MLP(residual units)에 적용하면 Wide&Deep (DeepCross)
    • concatentation operation의 분명한 한계는 features 사이의 어떤 interactions은 해결을 할 수 없다. 그 처럼 이 deep learning approaches는 deep layers에서 meaningful feature ineteractions을 배워야 하는데, 실제 train하는게 매우 어렵다.
    • low level에서 Bi-Interaction pooling captures second-order feature ineteractions은 concatenation operation보다 더 informative하다.
    • NFM의 subsequent hidden-layers가 수월하게 useful higher-order feature ineteractions을 더 쉽게 가능
  • Time Complexity Analysis

    • Bi-interaction pooling은 O(kNx)time에 효율적으로 계산이 가능하다. (=FM)
    • hidden layers에서 추가적인 비용이 발생한다.
    • hidden layer l은 O(dl-1 dl) > 다 필요없고 그냥 좋다. Wide&Deep, DeepCross와 같다.

Learning

  • NFM은 다양한 prediction tasks에 적용이 가능하다. (regression, classification, ranking)
    • regression - squared loss object function을 사용
    • classification - hinge loss, logloss를 사용
    • ranking task - pairwise personalized ranking loss, contrastive max-margin loss
  • 본 논문에서는 regression에 초점을 맞췄지만, ranking/classifiation도 같은 방법으로 진행하면 된다.
  • Stochastic gradient descent (SGD)은 neural network models을 최적화 하기 위한 universal solver

  • Dropout

    • dropout는 estimating할때 사용하는 전체 네트워크에서는 disable 되어야만 한다.
  • Batch Normalization
    • multilayered neural network의 어려움중 하나는 fact of covariance shift의 원인
    • 각 layers의 inputs의 distribution이 training하는 중에 이전 layers의 변화의 파라미터로서 변화된다.
    • 그 결과 later layer은 이 변화(noisy)들에 대해서 자신들의 parameters의 업데이트할때 adapt할 필요가 필요하다.
    • 반대로 training 이 slow down
    • 위 문제를 해결하가기 위해 batch normalization (BN)이 등장!,
    • layer inputs을 normalizae한다 zero-mean unit-variance Gaussian distribution 각 mini-batch training에서
    • faster covergence, better performance의 결과를 준다.

Experiments

  • Bi-Interaction pooling이 효율적으로 second order feature ineteractions을 찾을 수 있는지?
  • 어떻게 dropout과 batchnormalization으로 Bi-Interaction pooling에 적용하는지
  • FM보다 features사이에 higher order interactions을 찾을 수 있는지?
  • Wide&Deep, DeepCross와 비교했을때 더 좋은지?

Experimental Settings

datasets

  • frappe
  • movielens
  • Dataset, Instance #, Feature #, User #, Item #
  • 70% training, 20% validation, 10% testA

Evaluation Protocols

  • RMSE를 evaluate performance하는데 사용하고, explicit ratings와 함께 recommendations, click-through rate prediction 과같은 regression task에서 많이 사용된다.

Baseline

  • sparse data prediction에 design된 embedding-based models과 비교
  • LibFM
  • HOFM
  • Wide&Deep
  • DeepCross

Parameter Settings

  • learning rate 모든 method에 대해서 [0.005, 0.01, 0.02, 0.05]
  • regularization (prevent overfitting)
    • LibFM, HOFM에는 overfitting을 피하기 위해서 regularization
    • Wide&Deep, DeepCross, NFM에서는 drop out [0, 0.1, 0.2, ... ,0.9]
    • DeepCross에서는 regluarize가 잘 되지 않았음 (residual units)
  • batch size
    • batch size가 클수록 training time이 줄어들고 convergence rate가 줄어든다.
  • embedding size는 64로

Study of Bi-Interaction Pooling (RQ1)

  • Bi-Interaction pooling operation의 성능을 비교하기 위해서 hidden layer가 없이 prediction socre를 계산! (NFM-0)
  • NFM-0은 다른 모델의 expressiveness에 영향을 받지 않아 FM과 동일하다고 생각하면 된다.
  • drop out을 L2 regularization, batch normalization impact를 비교!

Dropout Improves Generalization

  • LR, reg, drouput을 각각 비교했을때, dropout을 한 결과가 더 좋았음.
  • L2 reg보다 dropout의 generalization이 좋은 이유
    • L2 regularization은 values of parameters를 only suppresses 하기 때문에, 반면 dropout은 ensembling multiple sub-models

RNN Recursive Neural Networks

RNN 구조

  • 자연어처리 분야에서 각광받고 있는 모델, 음석 문자 등 순차적 데이터 처리에 강점

Recurrent VS Convolutional VS Recursive

  • Recurrent Neural Networks
    • 입력값을 순서대로 받아 하나씩 순차적으로 처리하는 네트워크.
  • CNN
    • 입력값을 생략없이 모두 반영한다는 점에서는 Recurrent Neural Networks와는 차이가 없다.
    • filter(2)를 이용해 2개의 단어씩 한번에 분석하고 있는 것을 알 수 있다
    • filter의 크기로 한칸씩 슬라이딩하면서 문장을 단어 두개씩 읽어들여 분석하는 구조
    • 문장의 지역적인 정보를 반영한다는 점
  • Recursive Neural Networks
    • 입력값으로 주어지는 몇 개 단어를 묶어서 분석한다는 점에 있어서 CNN과 유사
    • CNN은 모든 지역정보를 생략없이 반영하는 데 비해 RNN은 일부 정보는 스킵
    • CNN과 달리 트리 구조의 입력값을 반드시 필요
    • RNN은 여러 단어의 결합으로 이루어진 표현을 벡터 공간에 임베딩해 파싱, 감성분석
    • RNN은 부모노드를 만들 때마다 점수도 함께 생성
    • 파싱을 위한 RNN이라면 이 스코어는 합쳐진 단어들이 얼마나 말이 되는지를 나타내는 점수
    • 감성분석을 위한 RNN이라면 해당 점수는 긍/부정 극성을 나타내는 지표

Simple RNN 구조

  • 간단한 RNN구조는 트리형태로 표현이 가능하다.
  • i번째 부모노드인 p(i)의 값은 아래처럼 정의된다.
    • p(left), p(right)의 결합 * W + b
  • 학습 과정에서 트리 탐색은 greedy 방식, Beam Search 알고리즘은 BFS기법을 기본으로 하되 기억해야하는 노드 수를 제한해 효율성 높인 방식

참고

  • https://ratsgo.github.io/deep%20learning/2017/04/03/recursive/

RNN

RNN은 Recurrent Neural Networks와 더불어 자연어처리 분야에서 각광받고 있는 모델.
Recursive, Recurrent Neural Neworks

두 모델은 음성, 문자 등 순차적 데이터 처리에 강점을 지니고 있음
이름이 유사하지만, 조금은 차이가 있다.

Recurrent Nueral Networks

RNN의 기본 구조

  • RNN은 히든 노드가 방향을 가진 엣지로 연결돼 순환구조를 이루는(directed cycle) 인공신경망의 한 종류
  • 시퀀스 길이에 관계없이 인풋과 아웃풋을 받아들일 수 있는 네트워크 구조 > 다양하고 유연하게 구조를 만들 수 있다는 점 RNN 큰 특징
  • ht는 직전 시점의 히든 state h(t-1)를 받아 갱신
  • hidden state의 activation function은 tanh

RNN의 기본 동작

  • 글자가 주어졌을때 바로 다음 글자를 예측하는 Chracater-level-model을 만든다고 칠때
    • h0는 random하게 주어지고, hidden layer를 fowrard propagation을 하면서 모두 갱신
    • 정답셋을 바탕으로 backpropagation을 수행해 parameters의 값들을 갱신
  • RNN이 학습하는 parameter는 무엇일까?
    • Wxh, Whh, W_hy의 parameters
    • x > hidden, hidden > hidden, hidden > y

LSTM

  • RNN은 관련 정보와 그 정보를 사용하는 지점 사이거리가 멀 경우 vanishing gradient problem이 발생
    • vanishing gradient problem: backpropagation시 gradient가 점차 줄어들어 학습 능력 저하
  • 위 문제를 극복하기 위해서 바로 LSTM을 사용 (https://ratsgo.github.io/natural%20language%20processing/2017/03/09/rnnlstm/)
    • LSTM은 RNN의 hidden state에 cell_state를 추가
    • cell state는 일종의 컨베이어 벨트 역할
      • state가 꽤 오래 경과하더라도 gradient가 비교적 전파가 잘 된다.
    • forget gate
      • '과거 정보 잊기'
      • sigmoid를 하기 때문에 0이라면 이전 상태의 정보를 잊고, 1이라면 이전 상태의 정보를 온전히 기억
    • input gate
      • '현재 정보를 기억하기 위한'
      • i(t)의 범위는 0~1, g(t)의 범위는 -1~1, 각각 강도와 방향을 나타낸다.
    • H(t)에서 행을 기준으로 4등분해, i,f,o,g 각각에 해당하는 activation 함수를 적용

Python 코드

참고

  • https://ratsgo.github.io/natural%20language%20processing/2017/03/09/rnnlstm/
  • https://ratsgo.github.io/deep%20learning/2017/04/03/recursive/

Complte Guide to Parameter Tuning in XGBoost (with codes in Python)

Introduction

XGBoost는 highly sophisticated algorithm. irregularities of data를 처리하는데 강력한 알고리즘이다.

XGBooster model을 building 하는 과정은 쉽다. 하지만 성능을 향상시키는건 쉽지 않다. 이 알고리즘은 multiple paramters를 사용해서 model을 향상시킨다. 그렇기 때문에 paramter tuning은 필수 작업이다. 그렇다면 어떻게 파라미터를 tuning해야 할까? 파라미터중에서 어떤 파라미터가 optimal ouput일까?

아래 내용은 parameter tuning하는 방법에 대해서 설명한다.

What should you know?

XGBoost(eXtreme Gradient Boosting)은 gradient boosting algorithm의 advanced implementation이다. GBM파라미터 튜닝에 대한 글은 아래 참고

https://www.analyticsvidhya.com/blog/2016/02/complete-guide-parameter-tuning-gradient-boosting-gbm-python/

Table Of Contents

  • The XGBoost Advantage
  • Understanding XGBoost Parameters
  • Truning Parameters (with Example)

The XGBoost Advantage

  • Regularization
    • Standard GBM implementation은 regulariztion을 가지고 있지 않음. 그러므로 overfitting을 줄이는데 도움을 준다고?
    • XGBoost는 ‘regularized boosting’ technique으로도 알려져 있음
  • Parallel Processing:
    • XGBoost는 parallel processing이기 때문에 GBM과 비교했을때, 놀랄만큼 빠른 속도를 가지고 있음
    • boosting은 seuqeuntial process 근데 어떻게 parallelize를 하느냐? 이전에 트리가 있어야 다음 트리를 생성하는데, 그럼 모든 트리가 모든 코어를 사용해서 만들어질때까지 동작을 멈추냐? 그 자세한 내용을 알고 싶으면 아래 링크
    • http://zhanpengfang.github.io/418home.html
    • XGBoost는 또한 Hadoop에서 구현이 가능하다.
  • High Flexibility
    • XGBoost는 custom optimization objectives와 evaluation criteria를 사용자가 직접 정의가 가능하다.
    • 그렇기 때문에 결과적으로 제약이 없지
  • Handling Missing Values
    • Xgboost는 missing values를 처리할 수 있는 in-build routine을 가지고 있다.
    • 사용자는 다른 관측치와 다른 값을 제공해야하며, 이를 paramters로 전달해야 한다. XGBoost는 각 노드에서 누락된 값을 만나고, 미래에 누락 된 값을 위해 어떤 경로를 취해야 하는지 알기 때문에 다른 것들을 시도합니다.

7 Techniques to Handle Imbalanced Data

  • intrusion detection
  • real-time bidding

Introduction

  • fraud detection in banking
  • real-time bidding in marekting
  • intrusion detection in networks

    위 분야에서는 1%보다 낮게 interesting의 events가 포함되어 있다. (예를 들면 fraudsters using credit cards, clicking advertisement, corrupted server scanning its network)
    그러나 머신러닝 알고리즘에서는 imbalanced datasets에 대해서 처리를 잘 하지 못한다. 아래 7개의 techniques은 abnormal class를 detect하기 위한 classifier를 학습하는데 도움을 줄것이다.

1.Use the right evaluation metrics

imbalanced data를 사용해서 model을 생성하게 되면 evaluation metrics를 부적절하게 해석을 할 수 있기 때문에 매우 위험하다. 0이 데이터의 99%를 차지한다면, 모델의 정확도는 99%를 보여줄것이다. 하지만 이 정확도는 가치있는 정확도가 아니다.

이러한 경우에는, 다른 대체 가능한 evaluation metrics를 사용하는게 좋다.

  • Precision/Specificity: how many selected instances are relevant
  • Recall/Sensitivity: how many relevant instances are seleted.
  • F1 score: harmonic mean of precision and recall
  • MCC: correlation coeeficient between the observed and predicted binary classifiations
  • AUC: relation between true-positive rate and false positive rate

2.Resample the training set

undersampling과 over-sampling을 통해서 balanced dataset으로 resampling을 하는 방법이 있다.

2.1. Under-sampling

abundant class의 사이즈를 줄여서 balanced dataset으로 만드는것을 말한다. 이 방법은 데이터의 양이 충분할때 사용할 수 있는 방법이다. rare class의 모든 샘플을 keeping하고, abudant class의 샘플들의 숫자를 랜덤으로 선택해서 숫자를 같게 만드는 방법이다.

2.2. Over-sampling

데이터의 양이 충분하지 않을때 사용하는 방법으로, rare sample의 사이즈를 증가시켜 balanced dataset으로 만드는 것이다. 새로운 rare samples을 생성하기 위해서는 repetition, bootstrapping, SMOTE(Synthetic Minority Over-Sampling Technique)를 사용하면 된다.

하나의 리샘플링 방법이 다른 리샘플링 방법보다 절대적인 이점은 없다. 이 두 가지 방법의 적용은 적용되는 사용 사례와 데이터 세트 자체에 따라 다르다. Over-, under-sampling을 조합하면 종종 좋은 결과를 보여준다.

3.Use K-fold Cross-VAlidation in the right way

over-sampling을 사용할때 적절한 방법이다. over-sampling은 rare samples의 distribution function을 기반으로 새로운 random data를 생성하기 위해서 bootstrapping을 적용하게 된다. 만약 cross-validation이 over-sampling이후에 적용이 되면, 기본적으로 우리가하고 것은 우리의 모델을 특정 artificial bootstrapping 결과에 맞추는 것이다. cross-validation은 over-sampling을 하기 전에 항상 완료가 되어야 한다.

4.Ensemble different resampled datasets

더 많은 데이터를 사용해서 model을 성공적으로 generalize하기 위한 가장 쉬운 방법이다. 이 문제는 out-of-the-box classifier같은 logistic regression, random forest와 같이 rare class를 버리기 위해 generalize를 하는 경향이 있다. rare class의 모든 샘플들과, abundant class의 n-differing samples을 사용해서 n 개의 models을 building을 해보자. 10개의 ensemble models이 만들어 질것이다. (1000개의 rare class, 10,000개의 abundant class) 10,000개를 10개의 chunks로 split을 해서 10개의 다른 모델을 train한다.

이 방법은 심플하고 데이터가 많아도 완벽하게 horizontally scalable다. 또한 다른 클러스터의 노드들에서 각각의 모델을 학습할 수 있다는게 장점이다. ensemble models은 또한 generalize better, approach도 쉽다.

5.Resample with different ratios

이전의 approach는 rare와 abundant class사이에 fine-tune이 가능하다. best ratio는 data에 의존적이고 그 모델은 사용이 된다. 그러나 ensemble에서 같은 ratio를 사용한 모든 모델을 train을 하는 대신에, different ratios를 ensemble하는게 더 좋다. 10개의 모델을 train을 했다면, 하나는 1:1, 나머지는 1:3, 2:1로. 사용 된 모델에 따라 하나의 클래스가 얻는 가중치에 영향을 줄 수 있습니다.

6.Cluster the abundant class

tranining samples의 variety를 커버하기 위해서 random samples을 사용하는 대신에, clustering을 통해 abundant class를 r groups으로 clustering을 하는 것을 제안했다. r에 있는 classes의 개수를 r로. 각 그룹에 대해서, medoid(centre of cluster)에 유지 된다. 그 모델은 rare class와 medoids로 부터 trained 된다.

7.Design your own models

cost function을 design해라!

만약 모델이 imbalanced data에 적절하다면, resample은 필요가 없다. 유명한 XGBoost는 내부적으로 imbalanced가 되지 않도록 trains을 하기 때문에 이미 class가 너무 많이 skewed가 되지 않았다면 좋은 결과를 준다. 그러나 그 다음 다시 data가 resampled되면 안좋다는거야 뭐야…

abundant class의 잘못된 classification보다 rare class의 잘못된 classification이 더 penalizing하다. cost function을 설계함으로써, rare class의 favour(편애)에서 naturally generalize를 할 수 있다. 예를 들어서 SVM을 tweaking(조정)을 한다. penalize하기 위해서 rare class의 잘못된 분류를. 같은 ratio

Final Remarks

위의 방법들은 starting points로 시작하면 된다.

Class imbalance problem

imbalance problem

Class Imbalance Problem이 무엇인가

데이터에서 각 클래스의 개수가 현저하게 차이가 나는 문제를 말한다. 이 문제는 실제로 여러 학문에서 나타나는데 그 중에는 fraud detection, anomaly detection, medical diagnosis, oil spillage detection, facial recognition 등에서 나타난다.

무엇인 문제인가

머신 러닝 알고리즘은 각 클래스들의 개수가 거의 비슷한 경우에 가장 좋은 결과를 보여준다. 하나의 클래스의 개수가 다른 클래스보다 많게 되면 아래와 같은 문제가 발생한다.

transaction data의 데이터셋이 주어졌을때, fraudulent(사기를 치는)과 genuine(진짜의)것을 찾아야 한다. 지금 e-commerce company에서는fraudulent transaction인지 아닌지를 구별하는게 매우 중요하다. 가능하다면 많은 fraudulent transactions을 발견하는 것을 원한다.

만약 데이터 셋이 10000개의 genuineㅇ과 10개의 fraudulent transactions으로 이루어져 있다면, classifier는 fraudulent transactions을 genuine transactions으로 분류를 하는 경향이 나타날 것이다. 이 이유는 쉽게 설명이 가능하다. 머신러닝 알고리즘은 두개의 가능한 outputs을 가지고 있다고 생각한다.

  • Model 1은 10개 중 7개의 fraudulent transactdions을 genuine transactions으로, 100000개 중 10개의 genuine transactions을 fraudulent transactions으로 분류
  • Model 2는 10개 중 2개의 fraudulent transactions을 genuine transactions으로, 100000개 중에 100개의 genuine transactions을 fraudulent transactions으로 분류

만약 mistakes의 개수로 classifier의 성능을 평가한다면, Model1은 17개의 mistakes를 했고, 반면 Model2는 102개의 mistakes를 했다. 결론적으로 Model1의 성능이 더 좋다고 할 수 있다. 하지만 우리가 풀고자 하는 문제는 fraudulent transactions의 개수를 minimize를 원하기 때문에, 우리는 Model2가 fraudulent transactions을 분류하는데 있어서, 2개의 mistakes를 했기 때문에 Model1보다 좋다고 할 수 있다. 물론 genuine transactions을 fraudulent transactions으로 분류한 비용은 생기게 된다. 그러나 이 비용은 사실 그렇게 큰 비용이 아니다. 일반적인 머신러닝 알고리즘은 Model1을 Model2보다 선택을 하게 될것이다. 이게 바로 문제이다. 실제로 Model2를 사용하여 많은 fraudulent transactions을 처리를 할 수 있었을 텐데, 할 수 없었다. 라는 것을 의미하고, 해석하면 회사 입장에서는 금전적 손실과 customers를 unhappy하게 만드는 것이다.

How to tell machine learning algorithm which is the better solution

Model2가 Model1보다 더 좋다고 말하기 위해서는 단순히 mistakes의 개수를 카운팅하는 방법보다는 더 좋은 metric이 필요하다.

  • TP: positive -> postivie
  • TN: negative -> negative
  • FP: negative -> postivie
  • FN: positive -> negative

위를 기본으로 True Positive Rate, True Negative Rate, False Positive Rate, False Negative Rate:

name formula explanation
TP rate TP / (TP + FP) The closer to 1, the better
TN rate TN / (TN + FN) The closer to 1, the better
FP rate FP / (FP + TN) The closer to 0, the better
FN rate FN / (FN + TP) The closer to 0, the better

새로운 metrics와, 단순히 mistake의 개수를 측정하는 conventional metrics와의 비교를 해보면

Error(Model 1)
= (FP + FN) / total dataset size
= (7 + 10) / 10010
= 0.0017 = (0.1% error)

Error(Model 2)
= (FN + FP) / total dataset size
= (2 + 100) / 10010
= 0.01 (= 1% error)

단순히 mistakes의 개수로 에를 측정하면 Model 1의 에러 0.1%이 Model 2의 에러 1%보다 더 작기 때문에 Model 2보다 Model 1이 더 좋다라고 마할 수 있다. 하지만 우리는 Model 2가 더 좋은 것을 이미 알고 있으니…

새로운 metrics을 계산을 해보면

Model 1

  • TP_rate(M1) = 3 / (3 + 7) = 0.3
  • TN_rate(M1) = 9990 / (10 + 9990) = 0.999
  • FP_rate(M1) = 10 / (10 + 9990) = 0.001
  • FN_rate(M1) = 7 / (7 + 3) = 0.7

Model2

  • TP_rate(M2) = 8 / (8 + 2) = 0.8
  • TN_rate(M2) = 9900 / (100 + 9900) = 0.990
  • FP_rate(M2) = 100 / (100 + 9900) = 0.01
  • FN_rate(M2) = 2 / (2 + 8) = 0.2

Model1의 false negative rate는 70%, Model2는 20%, 즉 Model2의 성능이 더 좋음

How to mitigate this problem

지금까지 class imbalance problem이 무엇인지 알아보았다. 이제 어떻게 imbalance dataset의 문제를 다루는지에 대해서 설명한다.

우리는 대략적으로 두개의 카테고리 형태로 접근이 가능하다: sampling based approaches, cost function based approaches

Cost function based approaches

Sampling based approaches

  • oversampling: minority class를 추가
  • undersampling: majority class를 제거
  • hybrid (mix of oversampling and undersampling)

sampling based approaches응 확실하게 drawbacks이 있음

undersampling

더 많이 나타나는 majority class instances를 제거하는 방법으로, useful information이 버려지게 된다.

초록색 선은 ideal decision boundary이다. 파란선은 actual result이다.
왼쪽은 general한 machine learning algorithm에 undersampling없이 적용한 것이고, 오른쪽은 ngative class를 undersampled하고, 그러나 negative class의 정보가 제거되었다. 그리고 파란색 decision boundary는 경사가 때문에, 어떤 negative class는 positive class로 잘못 classified될 수 있다.

oeversampling

minority classess를 duplicating하게 되면 classifier가 overfitting될 수 있다.

왼쪽 그림은 oversampling하기 전의 그림이고, 반면 오른쪽은 oversampling을 적용했을때의 모양이다. thick positive signs은 positive instances를 여러번 duplicate한 것을 나타낸다.

hybrid approach

undersampling, oversampling을 합쳐놓은 접근 방법이지만, 이 방법 또한 drawbacks이 있음 여전히 trade-off가 존재.

more recent approaches to the problem

2002년에는 class imbalanced problem을 해결하기 위해 SMOTE( Synthetic Minority Over-Sampling Technique)라는 샘플링 기반 알고리즘이 도입되었다. simplicity, effectiveness으로 인해 채택된 접근 방법이다. SMOTE는 oversampling과 undersampling의 조합이지만, oversampling은 소수 클래스를 복제하는 것이 아니라, 알고리즘을 통해 새로운 minority class의 데이터를 구성하는 것이다.

일반적으로 oversampling에서는 minority class를 replicated하는데, SMOTE에서는 새로운 minority instances를 아래와 같은 방법으로 생성한다.

Add new minority class instances by

minority class instances별로

  • neighbours = get KNN(5)
  • n = random pick one from neighbours
  • create a new minority class r instance using c’s feature vector, and the feature vector’s difference of n and c multiplied by a random number
    • i.e. r.feats = c.feats + (c.feats - n.feats) * rand(0, 1)

기존 overfitting과는 다르게 “similar” examples을 대신 사용해 새로운 instances를 생성하였다. 그러므로 기존에 boundary가 soften하게 생기게 된다. 결과적으로 classifier는 더 general하고 overfit이 되지 않음.

Even more recent approaches

RUSBoost, SMOTEBagging, 그리고 Underbagging에 관한 literature가 최근에 볼 수가 있는데, 이 모든게 SMOTE로 부터 시작된 approaches이다.
하지만 여전히 SMOTE는 단순하기 때문에 매우 사용이 많이 되고 있음.

Summary

Clas Imbalance Problem은 실제로 class의 instances의 개수의 불균형의 원인으로 머신러닝에 영향을 주는 문제중 하나이다. 솔루션들을 비교하기 위해, alternative metrics를 mistakes의 개수를 카운팅하는 general accuracy와 비교를 하였다.

샘플링하는 방법은 크게 sampling based, cost function based가 있고, sampling based는 oversampling, undersampling, hybrid가 있다.

[참고]
http://www.chioka.in/class-imbalance-problem/

Machine Learning?

  머신러닝에 대한 정의는 두가지가 있는데, 오래전에 Arthur Samuel의 정의는 'the field of study that gives computers the ability to learn without being explicitly prgrammed'. 하지만 현재는 Tom Mitchell의 정의를 따르고 있습니다. "A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.". 풀어 말하면 하나의 사건에서 나오는 여러 경험들을 토대로 컴퓨터에게 학습을 시키고, 사건의 성능이 개선되도록 하는 알고리즘을 구현하는 것을 말합니다.

체스를 예로 들면

  • E는 많은 체스 게임들의 경험 (어떻게 수를 두는지에 대한)
  • T는 체스를 플레이하는 사건
  • P는 다음 경기에서 프로그램이 이길 확률

E를 통해서 T의 P가 개선되도록 하는 알고리즘은 두가지로 분류가 됩니다. 

  • supervised learning
  • unsupervised learning

Supervised Learning

  Supervised Learning은 데이터 셋과 그에 대한 정답을 알고 있는 상태에 적용이 가능한 학습 방법을 말합니다. 즉, 입력값과 출력값의 관계가 있는 것을 말합니다. 예를 들면 사진이 주어지고, 이 사진이 고양이다. 라는 정답을 아는 상태에서 고양이 사진을 주면 이 사진은 고양이라고 대답해주는 문제를 말합니다.

  supervised learning은 regrssion과 classification 문제로 나눌 수 있습니다. regrssion문제는 continuous output의 결과를 예측하는 문제입니다. 이 말은 continuous function에 input 값을 넣고 결과를 continuous output으로 받는다고 생각 할 수 있습니다. classification문제는 descrete output의 결과를 예측하는데 사용합니다. 

  두 문제의 예를 들면 regression은 단순하게 아파트의 가격은 아파트의 사이즈로 예측이 가능하다 라는 가정을 갖고 생각하면, 아파트의 사이즈는 continuous한 데이터이고, 결과적으로 continous한 결과인 가격을 예측을 합니다. classification은 학교, 나이, 수입, 성별 등의 features를 통해 이 사람이 은행에서 대출을 받을 것인가 아닌가를 예측할때, output을 yes 또는 no로 즉, descrete output의 결과를 예측합니다.

Unsupervised Learning

  supervised learning과 다르게 unsupervised learning은 정답을 모르고 예측을 하는 방법입니다. 결과적으로 입력된 데이터의 값들 사이의 관계를 기반으로 데이터에서 clustering(군집화) 구조를 얻을 수 있습니다. unsupervised learning은 예측 결과를 기반으로 feedback을 주지 않습니다. 즉, 이게 정답인지 아닌지를 알 수가 없고, 내가 눈으로 확인을 할 수 밖에 없습니다.

  clustering의 예를 들면, 1000개의 글이 있을때, 글을 자동적으로 그룹핑을 하고 싶습니다. 이때 글의 단어의 빈번도, 문장의 길이, 페이지의 개수 등을 통해서 각 글의 관계를 기반으로 clustering을 할 수 있습니다. 추후에 글이 들어오면 단어의 빈번도, 문장의 길이, 페이지 개수 등을 통해서 비슷한 성격의 문서와 함께 그룹핑이 될 것입니다.



+ Recent posts