ばびぞうブログ

統計モデリング・機械学習・Python・R・Django・PostgreSQLに関してはなにもわかりません

AtCoder Beginner Contest 169　B-Multiplicationの振り返り

競技プログラミング

愚直に実装した場合に起きる問題

　・Python：オーバーフローは起こらないが、計算量O(N^2)でTLEになってしまう。

　・C++：計算量は大丈夫だが、オーバーフローにより誤った計算結果になる。

＊オーバーフロー（桁あふれ）とは？？
 数値型の変数について、己が持てる最大値を超えること。
これが起きるとぐちゃぐちゃな数字が変数に入ってしまうため、正しい数値が得られなくなる。
（例）A1～A3に10^9が入っている場合、A1×A2の段階では10^18でlong long型にギリギリ間に合う。しかし、A3がここに掛け算されるとオーバーフローし想定外の数値が入る。この後に10^18との間で大小比較を行っても、正しい結果が得られない。

　【オーバーフローへの対処法】

①Pythonなどオーバーフローの心配がない言語で書く
②int 128型に変換する

 

正解のために求められる能力

　・Pythonの場合：　TLEへの対処力（正しい順序で判断処理を行い計算量を減らす）

　・C++の場合：　オーバーフローへの対処力 or 正しい順序で判断処理を行う力

入力値に０が含まれる場合に、正しい処理方法を実装できるかが勝利を分けた模様（なみだ）

 

解答例１（この順番で行うのが重要！）

①入力全読み込み　→　②Aに0が含まれるか判断　→　③順番に掛け算を行い、積が10^18を超えるか判断

・②がなかったら・・・「Aに0を含んでいるケースで、誤った出力結果をしてしまう」

（例）A1とA2に10^18、A3に0が入っていた場合を考えてみる！このとき、A1×A2×A3は0になるはず。
しかし③のみで判断していると、A1×A2の段階で10^18を超えたことにより-1を出力してしまう結果に。

解答例２（よりスマートに見える）：

①入力全読み込み　→　②Aを小さい順に並び替え　→　③順番に掛け算を行い、積が10^18を超えるか判断

 

まとめ　

・今回のPythonでTLEが発生した理由は、普通に掛け算していくと計算結果は最大10^50000まで取りうるため計算量がO(N^2)になるから。


・そこで計算量を減らすための工夫が必要になるが、以下の２通りが多くみられる。


【方法１】
①入力値のいずれかに０があるかを判断し、あれば０を出力してプログラムを終了
②順番に掛け算し、10^18を超えているかを逐次判断。超えたら-1出力しプログラム終了

 

【方法２】
①入力値を小さい順にソートする
②順番に掛け算し、10^18を超えているかを逐次判断。超えたら-1出力しプログラム終了

 

・入力値のいずれかに０を含む場合は、他の入力値がどんなに大きかったとしても計算結果は０になることを想像できたかがカギでした。むずかしかった泣いちゃうほぼ泣いた

負の二項分布（Negative Binomial Distribution）

統計学

設定

赤玉と白玉の２種類が入っている袋があり、袋の中には赤玉θ個と白玉n-θ個の合計n個の玉が入っている。

かき混ぜて、中を見ず１個取り出す。

もし、赤玉が出たら、d個の赤玉を袋に加えて袋に戻す。

もし、白玉が出たら、d個の白玉を袋に加えて袋に戻す。

（その選択が次の選択に正の影響を与える感じ。成功は成功を呼ぶてきな。）

この操作をN回繰り返す。

負の二項分布（Negative Binomial Distribution）

M、Kを次のように定める。

M = N \times \displaystyle \frac{θ}{n}　 （N回中、赤玉が出る平均回数）

K = \displaystyle \frac{θ}{d}

N回中、r回赤玉が出る確率をP_{r}とすると、

P_{r} = \displaystyle \frac{(1 + \displaystyle \frac{M}{K}) ^ {-K} \times \Gamma(K + r)}{\Gamma(r + 1) \times \Gamma(K)} \times (\displaystyle \frac{M}{M + K})^{r}

で表される分布を負の二項分布というらしい。

導出

また後ほど

実問題への適用

消費者全体の購買行動で負の二項分布を適用する。

また後ほど

思ったこと

TeXで数式書くのが面倒。

 

 

LightGBMでよくやるやつ

機械学習

パラメータチューニング（optuna）、CV

scikit-learn インターフェースを使わずLightGBM

import numpy as np
import pandas as pd
from sklearn import metrics
from sklearn.model_selection import train_test_split, StratifiedKFold
import optuna
import lightgbm as lgb

def get_evaluate(y_test, predict):

    fpr, tpr, thr_arr = metrics.roc_curve(y_test, predict)

    auc = metrics.auc(fpr, tpr)
    precision = metrics.precision_score(y_test, predict)
    recall = metrics.recall_score(y_test, predict)      

    return auc, precision, recall_score

def objective(trial):

    train_x, test_x, train_y, test_y = train_test_split(X_train, y_train, test_size=0.25, 
                                                        shuffle=True, stratify=y_train)
    dtrain = lgb.Dataset(train_x, label=train_y)

    param = {
        'objective': 'binary',
        'metric': 'auc',
        'verbosity': -1,
        'boosting_type': trial.suggest_categorical('boosting', ['gbdt', 'dart', 'goss']),
        'num_leaves': trial.suggest_int('num_leaves', 10, 1000),
        'learning_rate': trial.suggest_loguniform('learning_rate', 1e-8, 1.0)
    }

    if param['boosting_type'] == 'dart':
        param['drop_rate'] = trial.suggest_loguniform('drop_rate', 1e-8, 1.0)
        param['skip_drop'] = trial.suggest_loguniform('skip_drop', 1e-8, 1.0)
    if param['boosting_type'] == 'goss':
        param['top_rate'] = trial.suggest_uniform('top_rate', 0.0, 1.0)
        param['other_rate'] = trial.suggest_uniform('other_rate', 0.0, 1.0 - param['top_rate'])

    gbm = lgb.train(param, dtrain)
    preds = gbm.predict(test_x)
    pred_labels = np.rint(preds)
    
    fpr, tpr, thr_arr = metrics.roc_curve(test_y, pred_labels)
    accuracy = metrics.auc(fpr, tpr)

    return accuracy

k = 5
skf = StratifiedKFold(n_splits=k, shuffle=True, random_state=0)

lgbm_params = {'objective': 'binary'}

auc_list = []
precision_list = []
recall_list = []

for train_index, test_index in skf.split(X, y):

    X_train = X.iloc[train_index]
    y_train = y.iloc[train_index]
    X_test = X.iloc[test_index]
    y_test = y.iloc[test_index]

    study = optuna.create_study(direction='maximize')
    study.optimize(objective, n_trials=100)

    print('Number of finished trials: {}'.format(len(study.trials)))

    print('Best trial:')
    trial = study.best_trial

    print('  Value: {}'.format(trial.value))

    print('  Params: ')
    for key, value in trial.params.items():
        print('    {}: {}'.format(key, value))    

    # optunaでサーチしたパラメータ
    trial.params['objective'] = 'binary'
    lgbm_params = trial.params

    # ここではvalidをモデル評価、evalをフォールドアウト検証に使う・・・分割の大きさはデータセットと相談する
    X_eval, X_valid, y_eval, y_valid = train_test_split(X_test, y_test, random_state=90, 
                                                        shuffle=True, stratify=y_test, test_size=0.3)

    # データセットを生成する
    lgb_train = lgb.Dataset(X_train, y_train)

    # モデル評価用
    lgb_valid = lgb.Dataset(X_valid, y_valid, reference=lgb_train)

    model = lgb.train(lgbm_params, 
                      lgb_train,
                      valid_sets=lgb_valid,
                      num_boost_round=100000,
                      early_stopping_rounds=10)

    predict = model.predict(X_test, num_iteration=model.best_iteration)

    auc, precision, recall = get_evaluate(y_test, predict)

    print('AUC:{}, precision:{}, recall:{}'.format(auc, precision, recall))

    auc_list.append(auc)
    precision_list.append(precision)
    recall_list.append(recall)

# kfoldの平均値を取得
print('Kfold平均 AUC:{}, precision:{}, recall:{}'.format(np.mean(auc_list), 
                                                         np.mean(precision_list), 
                                                         np.mean(recall_list)))

scikit-learn インターフェースでのLightGBM

また今度