pei’s blog

情報科学を学ぶ大学4年生。主にプログラミング(機械学習寄り)の話題を書いていきます。

SQLのWHERE句の書き方による実行速度の違い

今回はSQLの書き方によって実行速度がどのくらい変わるのか簡単な実験をします。
最近バイトでSQLを書いている時、よく「WHERE句の記述の順序を変えたらどのくらいパフォーマンスが変わるのだろう?」と思っていたのでやってみました。


目次

  1. 準備
  2. 実験内容
  3. 結果・考察


準備

CREATE TABLE (id integer primary key autoincrement, name text, grade integer);

文字列型のname、数値型のgradeを持つ構造のテーブルを用意して、1,000,000件データを入れておきます。 nameは1つのアルファベット30文字を繋げた文字列を25種類(a〜y)生成します。gradeは0〜24までの数字を入れます。


実験内容

以下の2つのSQL文を比較します。

  1. SELECT * FROM SAMPLE_TABLE1 WHERE name = 'aaa...' AND grade = 1;
  2. SELECT * FROM SAMPLE_TABLE1 WHERE grade = 1 AND name = 'aaa...';

1.のSQL文は、最初にnameで文字列比較をして40,000件に絞り、その後にgradeで数値比較して1,600件に絞ります。すなわち、文字列比較回数は1,000,000回、数値比較回数は40,000回になります。

2.のSQL文は、最初にgradeで数値比較して40,000件に絞り、その後にnameで文字列比較して1,600件に絞ります。すなわち、文字列比較回数は40,000回、数値比較回数は1,000,000回になります。

数値より文字列の比較の方が処理時間は長くなるため、2つめの処理の方が速くなると予想されます。


結果・考察

結果は以下の通りです。100回試行した平均の数値です。

実行時間
SQL1 0.0776s
SQL2 0.0667s

2. の方が0.01速いことがわかり、やはりWHERE句の順序により実行速度が変わることが確認できました。どのくらい速くなるかはデータ構造次第ですが、文字数が増えれば比較処理時間が増えるのでより差が開くと考えられます。


参考書レビュー 詳解ディープラーニング

今回は詳解ディープラーニングのレビューについて書きます。※私個人の感想です。


ざっくり言うとどんな本?

ニューラルネットワークの道具としての使い方がわかり、なおかつ仕組みについても詳しくわかる本です。

目次

  • 前提知識
  • 内容
  • 特徴
  • 他の参考書との違い
  • 終わりに

  • 前提知識

    が必要だと思います。これらは一応ニューラルネットワークの内容の前に説明があります。ただ、微分偏微分は全くわからない人がこの本の説明のみで理解するのは厳しいと思います。


    内容

    Pythonの基本的な文法、微分線形代数の基礎から始まり、Numpy, Tensorflow, kerasなどライブラリについて、単純・多層パーセプトロンからLSTM, GRUを含む再帰ニューラルネットワークまで載っています。その他勾配消失、オーバーフィッティング問題など仕組み以外の周辺知識についても書かれています。


    特徴

    Early Stoppingや勾配消失問題の説明など周辺知識も多数載っています。また、実装の設計や学習の可視化などの記述もあり実用的な内容だと思います。また、畳み込みニューラルネットワーク(CNN)については載っていません。


    他の参考書との違い

    他に有名なニューラルネットワークの参考書はゼロから作るDeep Learningがあります。こちらは仕組みに特化しており実際にニューラルネットワークのライブラリ自体を手を動かして作るような内容です。一方、詳解ディープラーニングは仕組みも詳しく載ってますが、ライブラリを使った実装が書かれていてより実用的な内容だと思います。


    おわりに

    Tensorflow, kerasなどライブラリの使い方、再帰ニューラルネットワークについても載っており、私が知りたかったことが全部書いてあった本でした。個人的にはゼロから作るDeep Learningで仕組みを理解して、この本で周辺技術やライブラリを使った実装の仕方を学ぶと良いと思います。





    Python pickle化できないときの解決策(dill)

        今回はPythonのオブジェクトをシリアライズするライブラリのdillについて書きます。


        pythonシリアライズはpickleを使っている人が多いと思いますが、pickleだと特定の条件での関数オブジェクトをシリアライズできないなどの制約があります。

    こんなコード書くな!って思うかもしれませんが、たとえばこんなコードはpickle化できません。関数オブジェクトに他の箇所で定義されたオブジェクトが使われている場合はpickle化できないみたいです。

    import pickle
    
    
    def build_func(text):
        def a():
            return text
        return a
    
    with open('./a.pkl', 'wb') as file:
        func_obj = build_func("aaa")
        pickle.dump(func_obj, file)
    
    with open('./a.pkl', 'rb') as file:
        func_obj = pickle.load(file)
    

    このようなエラーが起きます

    AttributeError: Can't pickle local object 'build_func.<locals>.a'



    dillならそのようなオブジェクトもシリアライズできます!
    dillはpipで簡単にインストールできます。

    pip install dill
    

    dillは基本pickleと同じように扱えるため、先ほどのコードはこのようになります。これでシリアライズが可能になります。

    import dill
    
    
    def build_func(text):
        def a():
            return text
        return a
    
    with open('./a.dill', 'wb') as file:
        func_obj = build_func("aaa")
        dill.dump(func_obj, file)
    
    with open('./a.dill', 'rb') as file:
        func_obj = dill.load(file)
    






    Pythonでドキュメントの重み付け(Okapi BM25)

    今回はOkapi BM25での文書の重み付けを実装します。

    目次



    Okapi BM25とは

     TF-IDFに似た文書の重み付けの方法です。wikipedia(英語)
        以下の式で表されます。

     score(D, Q) = \sum_{q_i\in Q}^i IDF(q_i) \left( \frac{TF(q_i, D) \cdot (k_1 + 1)}{TF(q_i, D)+k_q \cdot (1 - b + b \cdot \frac{|D|}{avgdl})} + \delta \right)

        Dはドキュメント、Qは検索したい単語の集合、 q_iはQ中の単語、|D|はドキュメント長、avgdlは全ドキュメントの平均単語数です。

        TFはD中の q_iの出現数、IDFはInverse Document Frequencyの略で、多くのドキュメントに出現している単語は値が小さくなるような関数です。IDF( q_i) は \log{\frac{D}{d_w}}で表されます。ここでのDはドキュメントの総数、 d_wはwがいくつのドキュメントに出現したかを表します。

        また、b, k1,  \deltaは定数で、b=0.75, k1=1.2〜2.0,  \delta=1.0が最良みたいです。 \deltaがあるものはBM25+で、ないものはBM25と呼ぶようです。+のほうは改良版だそうです。ちなみに私が試した中で最良の結果だったのはb=0.75, k1=1.6,  \delta=1.0でした。

        TF-IDFと違うところはD/avgdlの箇所から分かるように、ドキュメントが短い時は重みが大きくなり、長ければちいさくなるということです。つまり、長いドキュメントに出現する単語より、短いドキュメントに出現する単語を重要視する感じです。







    実装

    計算の流れはこんな感じです。カッコ内は実際にその処理をするメソッド名です。
    1. IDFの計算(fit)
    2. TFの計算(transform)
    3. 重み付け(transform)
     文書をベクトル化したものは大抵疎なベクトルなので、値のあるインデックスと値のみを保管しないとパフォーマンスが非常に悪くなります。最後にscipy.sparse.lil_matrixで疎行列に変換します。 fitやtransformなどsklearnのVectorizerライクな関数名にしました。fitでベクトル化するオブジェクトのセットアップ、つまりIDFの計算、transformで実際に変換します。実際はクラスを実装したのですが、長くなるので一部だけ載せてます。全てのコードはこちら

    import numpy as np
    from scipy import sparse as sp
    import math
    
    def fit(self, documents, extract_words_func):
      """IDFの設定
      documentsはドキュメントのリスト、 
      extract_words_funcはドキュメントを単語リスト分割する関数"""
      self.average_words_len = 0  # 1つのドキュメントの平均の単語数を記録
      for document in documents:
        searched_dict = {}
        word_ls = extract_words_func(document)  # ドキュメントを単語リストに分割
        self.average_words_len += len(word_ls)
        for word in word_ls:
          # このドキュメント内で始めて出た単語
          if not searched_dict.get(word):
            searched_dict[word] = True
            # 他のドキュメントですでに出た単語
            if self.word_index_dict.get(word):
              self.idf[self.word_index_dict[word]] += 1.0
            # 初めて出現する単語
            else:
              self.feature_names.append(word)
              self.word_index_dict[word] = self.counter
              self.counter += 1  # 単語数を記録
              self.idf = np.append(self.idf, [1.0])
    
      documents_len = len(documents)
      self.idf = np.log2(documents_len / self.idf)
      self.average_words_len = self.average_words_len / documents_len
    
    
    def transform(self, documents, extract_words_func, K1, B, delta):
      """ドキュメントをConvine Weigthで重み付け
      documentsはドキュメントのリスト
      extract_words_funcはドキュメントを単語リスト分割する関数
      K1, B, deltaは定数
      返すのはscipy.sparse.lil_matrixオブジェクト
      """
      len_ls = []  # 1つのドキュメントに出現した単語数
      word_index_ls, word_weight_ls = [], []  # 単語のインデックス, 単語の出現数
      for doc in documents:
        word_weight_dict = {}  # 値のあるインデックス: 値
        word_ls = extract_words_func(doc)
        # Term Frequency
        for word in word_ls:
          if self.word_index_dict.get(word):
            if word_weight_dict.get(self.word_index_dict[word]):
              word_weight_dict[self.word_index_dict[word]] += 1.0
            else:
              word_weight_dict[self.word_index_dict[word]] = 1.0
    
        # 重み付け
        dist, word_len = 0, len(word_ls)
        for ind in word_weight_dict.keys():
          word_weight_dict[ind] = self.idf[ind] * \
            (delta + (word_weight_dict[ind] * (K1+1.0)) /\
            (word_weight_dict[ind] + K1 * (1.0 - B + B*(word_len / self.average_words_len))))
          dist += word_weight_dict[ind] ** 2
        # 正規化
        dist = math.sqrt(dist)
        for ind in word_weight_dict.keys():
          word_weight_dict[ind] /= dist
    
        len_ls.append(len(word_weight_dict))
        word_index_ls.extend(word_weight_dict.keys())
        word_weight_ls.extend(word_weight_dict.values())
    
      # sp.lil_matrixで疎行列オブジェクト生成
      it = 0
      result = sp.lil_matrix((len(documents), self.counter))
      for i in range(len(len_ls)):
        for _ in range(len_ls[i]):
          result[i, word_index_ls[it]] = word_weight_ls[it]
          it += 1
      return result
    



    導入してみた

        重み付けをOkapi BM25+にして全結合ニューラルネットワークを学習させて2値分類器を作成したところ、TFIDFより性能がよかったです(98%->98.5%くらいに向上)。やはり文書の長さによって単語の重要度は変化するようです。

    pythonで機械学習(kerasのOneHotレイヤーの作り方)

    今回はkerasで学習時にOneHotベクトル化するレイヤーの作り方を書きます。

    テキスト分類などでは、学習の前に特徴ベクトル化するとメモリを大量に消費してしまい、PCのスペックが高くないとメモリ不足で動かなくなることがあります。それなら学習前はOneHotベクトルのフラグの立つインデックスのみを保持し、学習時にOneHotベクトル化をしたほうがメモリ効率は断然いいです。


    実装方法

     Lambdaレイヤは引数に関数オブジェクトを渡し、Layerオブジェクトのような振る舞いをさせるレイヤです。
     Lambdaレイヤにkerasのbackedのone_hot関数を渡すことでデータをOneHot化するレイヤを追加できます。
     Lambdaの引数のarguments['numclasses']は1つのOneHotベクトルの次元数で、input_shapeは1つのデータにOneHotベクトルをいくつ保持するかを表します。そのため、output_shapeは(data_length, vec_size)とします。
     1つの入力データは長さがdata_lengthで、フラグの立つインデックスを保持した配列になります。

      from keras.models import Sequential
      from keras.layers.recurrent import LSTM
      from keras import backend as K
      from keras.layers.core import Lambda, Dense, Activation
      def init_model(self, vec_size, data_length, output_num):
        self.model = Sequential()
        # OneHot化するレイヤー
        self.model.add(Lambda(K.one_hot, dtype='int32', arguments={'num_classes': vec_size},
                                        input_shape=(data_length, ), output_shape=(data_length, vec_size))
    
        self.model.add(LSTM(output_num, activation='relu', dropout=0.5))
        self.add(Dense(output_num))
        self.model.add(Activation('softmax'))
    

    注意点

     kerasでネットワークモデルを保存するとき、model.saveをすると、紹介したOnehotレイヤは外部の関数(keras.backend.one_hot)を利用しているため、そのような関数はないというエラーがロード時に起こります。
     そのため、モデルを保存したいときはmodel.save_weightでパラメータのみを保存してください。





    IT系就活についての話

    私と友達の話や経験を元にIT系(主に独立系SIer、Web企業)の就活に向けてやっておくといいことをまとめてみました。

    目次

    この記事の対象とする人
    軽く自己紹介
    なにをしておくといい?
    まとめ


    この記事の対象とする人

     この記事は
    • 独立系SIer、もしくはweb企業を目指す人
    • プログラミングをこれから勉強したい、もしくはプログラミングや情報技術について少しは勉強してきたが、すごい知識や実績、成果物とかがあるわけではない
     という人を対象にしてます。また、Web系企業は多くは受けていないので偏った情報かもしれません

    軽く自己紹介

     情報科学専攻の大学4年生です。内定先は超大手Web企業(一度も使ったこと無い人は多分いないようなサービスを運営するとこ)と大手独立系SIerです。就活は3年の10月から少しずつはじめて4年の4月で終了しました。


    なにをしておくといい?

    やっておくといいことは
    • チームでの開発経験
    • IPAの資格
    • 集大成となるような成果物を作る
    です。

     チームでの開発経験はハッカソンプログラマーのアルバイト、インターンや友達とアプリ作るなどです。どの企業でも大抵チームでの開発経験の有無を聞かれました。作ったプログラムの内容、自分の担当した役割、具体的になにをしたかをまとめておきましょう。

     IPAの資格は基本情報、応用情報技術者などのことです。基本情報はあって当然、応用情報はしっかり勉強してきているという反応がありました。知識をどれくらい持っているかは面接などを通して全て伝えるのは難しいので、一定の知識量はあるという証明になる資格は持っていると良いです。Web系企業ではあまり重視されませんでした。

     集大成となるような成果物は、参考書のサンプルを変えただけのようなものではなく、利用する側を考慮したものを作るといいです。企業によっては成果物を提出させ選考対象にしたり、プレゼンさせることもあります。これは特にWeb企業に多かったです。そうでなくてもどういうものを開発してきたかということは技術者面接では大抵聞かれるため、話のネタになります。

    まとめ

     IT系の就活ではプログラミング未経験の文系なども受けてくるため、これらの経験は大きなアドバンテージになります。それらの経験をうまく伝える力も大事です。

        また、これらを活かすためにも自己分析やSPI対策も怠らないようにしましょう。個人的には、今までしてきたことや準備が非常に大事で、就活は選考が始まる前に勝負がついていると感じました。先々後悔しないために選考が始まる前に意味のある経験を積み、準備をしっかりしましょう!





    Pythonでテキストの機械学習(相互情報量を使った特徴ベクトル選定)

    今回は、ドキュメント群から生成したベクトルから、機械学習で重要な特徴ベクトルを抽出する内容です。テキストをベクトル化したものは何万次元にもなりますが、中には10000個あるドキュメントの中で1回しか出てこない単語など学習に必要のないデータが大量にあります。また、次元数が多いと学習時間が長くなり、メモリの消費量も増えます。
     そのため、今回は相互情報量に基づいて、学習に本当に必要な特徴ベクトルの抽出の仕方を考えます。

    目次


    相互情報量とは


     相互情報量とは、ざっくりいうと2つの事象(の集合)がどれだけ互いに関連性があるかを表す数値です。定義は以下のとおりです。
    こちらにより詳しいことが載ってます。相互情報量とは

    \displaystyle
I(X;Y) = \sum_{y\in{Y}}\sum_{x\in{X}}p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)}


    実装するアルゴリズム

     ドキュメントから生成した単語の頻度を表すベクトルとラベルにおいての相互情報量は以下のようになります。Classesはドキュメントに紐付いたラベルの集合で、Wordsはベクトル化されている単語の出現頻度を表す集合です。

    \displaystyle
I(Words;Classes) = \sum_{word\in{Words}}\sum_{class\in{Classes}}p(word, class)\log_2\frac{p(word,class)}{p(word)p(class)}



     今回は単語ごとのすべてのラベルの相互情報量の中で最大の数値を比較して、機械学習に使うデータを選択します。
       相互情報量を用いた以下の式を単語ごとの関連度の指標として、すべての単語でこの数値を計算します。相互情報量の特性上、値が大きいとラベルと単語の出現頻度の関連性が高いことがわかるため、値が大きければ大きいほど学習に重要な単語であると判断できます。


    \displaystyle
Output(word) = MAX\Bigl(p(word, Classes)\log_2\frac{p(word,Classes)}{p(word)p(Classes)}\Bigl)










    実装

     先ほど説明したアルゴリズムを実装していきます。式を展開してまとめると以下のようになります。c(〜)は該当する事象の出現数を意味します。
     単純に値を比較するだけのため、単語の出現頻度、ラベルの数に依存しない数値は定数とみなして省略してあります。

    \displaystyle
Output(word) = MAX\Bigl(c(word, Classes)\log_2\frac{c(doc)c(word,Classes)}{c(word)c(Classes)}\Bigl)

    必要なパラメータは以下のとおりです。

    c(word, class) ラベルがclassの全ドキュメント中のwordの出現数
    c(class) ラベルがclassのドキュメントの数
    c(word) 全ドキュメント上のwordの出現数
    c(doc) ドキュメントの総数


     以下が単語ごとの相互情報量を保管したリストを返す関数です。extract_wordsメソッドは前回の記事に乗っています。
       vectorsはドキュメントをベクトル化したもののリスト、doc_listはドキュメントのリスト、label_listはドキュメントに対応するラベルのリスト、label_numはラベルの種類の数です。

    def get_mi_list(vectors, doc_list, label_list, label_num):
        mi = []  # 単語ごとの相互情報量を保管するリスト
        word_sum = np.sum(vectors, axis=0)  # 全ドキュメント上の単語の出現数
    
        # すべてのドキュメントを単語リストに変換してラベルごとに保存
        labels_doc_words = [[] for i in range(label_num)]
        for doc_index in range(len(doc_ls)):
            labels_doc_words[labels[doc_index]].extend(extract_words(doc_ls[doc_index]))  # ドキュメントを単語のリストに変換
        # 各ラベルに属するデータ数を保管
        label_count = []
        for label in range(label_num):
            label_count.append(labels.count(label))
    
        # 全ワードの相互情報量を計算
        for word_index in range(len(words)):
            max_num = -100.0
            # 全ラベルの相互情報量の最大値をリストに追加
            for label in range(label_num):
                counter = labels_doc_words[label].count(words[word_index])  # ラベルがlabelの全文章中で出現するwordの数
                mi_num = counter * \
                             (np.log2(len(label_list) * counter / (label_count[label] * word_sum[word_index])))
                if not math.isnan(mi_num):
                    max_num = max(mi_num, max_num)
                mi.append(max_num)
    
        return np.array(mi)
    

     実装は難しいことは無いですが、注意点はlogの中身が0以下だとNaNが返るため if not math.isnan(~)をする必要があるという点です。
     返ってきた相互情報量のリストに基づいて学習対象のデータを選定することで学習に重要な特徴ベクトルを抽出できます。