Archive for Course

Turing’s formula

Turing’s formulaというのは、unigramというモデルを推定するため、Good-Turingという手法の元の理論です。

これはどんなことかというと、例えば、ある学習データの中で、出現した単語は何回で出現する可能性があります。それに従って、r回出現した単語の種類は、Nrと表します。だから、P(Wr)=r*Nr/Nsとなると、P(Wr)というのは、r回出現した単語の出現確率、或いは相対頻度と呼ばれます。ここで、Nsというのは、学習データの全体の単語のtoken数と表します。

それぞれによって、出現した単語の確率はもちろん求められますが、学習データのサイズの制限があるので、一回でも出現してない単語の確率はどう計算すれば良いか、これは難しい問題になります。こういった問題に向けるため、幾つかの提案手法がありますけれども、Good-Turingという手法は一つとなります。

これはどのような手法かというと、学習データでr+1回出現した単語の確率は、真のデータでr回出現する単語の確率を代わりにするという手法です。

この手法を検証するため、NLP授業の最後のレポートが出されました。この件について、ほかの方のやり方により、30分かかったことがあるようですので、俺はそれぞれのやり方を止めて、MySQLを利用し、SQLを用いて、left join・selectなどのコマンドを使うと、今回の検証結果がすぐ出てきました。すごく速くなりましたよ! :-) 一分でもかかってなかったのです。

どんな結果とどのような比較的な図が出てきたかというと、下記のようなfigureとなります。

画像をダウンロードするには、ここを右クリックします。プライバシー保護を促進するため、この画像はインターネットから自動的にダウンロードされません。 相対頻度の合計の比較

Comments

NLPに関する感想

NLPとはなんですけれども、Natural Language Processingという意味です。今学期の1つの科目として、今週まで円満に終了します。

こんな感想があるかというと、実践的で面白かったかなと思ってます。何故かというと、この授業内、ngramモデルの推定手法が幾つかマスターされたからです。また、先生の教え方も面白くて分かりやすかったのです。

特に、この科目の最終評価手法については、最終の課題の出てきた結果により、A・B・C・Dとなることです。とっても公正だと思ってましたけれども、もちろん皆もAの成績を取りたいはずです。ただし、最終の課題に関しては、あまり易しくなかったのですよ。

俺は、幾つかの推定方法を使ったことがありまして、最後に、Interplated-Modified-Kneser-Neyという推定手法に決定してしまいました。Aとなれる評価結果がちょうとう出てきましたので、良かったのですね。

おそらく、これからの検索に関する研究でもNLPの計算手法を利用できるところもあるかもしれないですので、今回のNLP科目は良い勉強になったかなと思うんです。

以上、といった感想なんです。

Comments

Presume bigram model

かきのようにbigramの推定するプログラムとなりますが、Kneser-Ney手法を使って、ソースコードの交流をしたいと思いますので、ここにしか公開されません。もし、転載したければ、僕の承認を取らなければなりません。よろしくお願いいたします。

/*
 * Function: Presume bigram according to training data
 * Author  : Jianquan LIU, 200720946
 * Date    : Mon. 11/5/2007
 * Language: C++
 * Compile : g++ -o kneser-ney kneser-ney.cpp
 */

#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <vector>
#include <string>
using namespace std;

// definitions
#define STRLEN      (256)    //length of string
#define MAX_WORD    (12822)  //maximum number of words
#define FIX_WORD    (1285)   //fixed value of word "で"

// type definitions
typedef unsigned int UINT;   //unsigned int is often used
typedef vector<UINT> WORDS;  //vector to storage words
typedef double       PROBS[MAX_WORD];  //list to storage probabilitis
typedef unsigned int COUNT[MAX_WORD];  //list to storage counts

/*
 * Input training data from data file
 * @Parameter:
 *   data,  a vector to storage words in data file.
 *   sFile, a string of data file's path.
 * @Return:
 *   0, success; -1, fail.
 */
int input_train_data(WORDS &data, const string sFile)
{
    if (freopen(sFile.c_str(), "r", stdin) == NULL) return -1;

    UINT word;
    data.clear();
    while (scanf("%d", &word) != EOF) data.push_back(word);

    fclose(stdin);

    return 0;
}

........
........
........

//usage of this program
void usage(const char *argv)
{
    printf("%s input_data_file output_modeln", argv);
    printf("Example:n");
    printf("  %s neko.num bigram.modeln", argv);
    return ;
}

//main program
int main(int argc, char **argv)
{
    if (argc != 3)
    {
        usage(argv[0]);
        return -1;
    }

    WORDS data;
    PROBS dPWiWa;
    char inFile[STRLEN]={0}, outFile[STRLEN]={0};

    strncpy(inFile, argv[1], STRLEN-1);
    strncpy(outFile,argv[2], STRLEN-1);

    if (input_train_data(data, string(inFile)) < 0)
    {
        fprintf(stderr, "Error: fail to read training data!n");
        return -1;
    }

    bigram_model(data, dPWiWa);

    if (output_model_result(dPWiWa, string(outFile)) < 0)
    {
        fprintf(stderr, "Error: fail to write model result data!n");
        return -1;
    }

    return 0;
}

細かいソースコードはここになります。

Comments (1)

単語長さの分布

これは最初のレポートとなりました。日本語の単語と英語の単語の長さの分布を調べるため、

まず、分布を求めるプログラムをPerlで書きました。下記のようなソースコードとなります。

#!/usr/bin/perl -w

# Function: Statistic distribution of word's length in text file
# Author  : Jianquan LIU, DSE Lab., University of Tsukuba, Japan
# Email   : ljq (AT) dblab.is.tsukuba.ac.jp
# Date    : Sun Sep 16 18:22:54 JST 2007

use strict;

binmode(STDIN, ":encoding(ja_JP.euc)");
binmode(STDOUT, ":encoding(ja_JP.euc)");

# usage $prog_name
my $prog_name = "./length_frequency.pl";
sub usage
{
    my($name) = @_;

    printf("Usage: %s <token | type> <input> <distr>n", $name);
    printf("      token | type, treat word as token or type.n");
    printf("      input,        text file containing many words.n");
    printf("      distr,        file to save distribution result.n");

    exit -1;
}

.........
.........
.........

# check parameters
my $numargs = @ARGV;
if ($numargs != 3)
{
    &usage($prog_name);
}
my $type  = $ARGV[0];
my $input = $ARGV[1];
my $distr = $ARGV[2];

if ($type eq "token")
{
    &stat_token($input, $distr);
    exit 0;
}
if ($type eq "type" )
{
    &stat_type($input, $distr);
    exit 0;
}

&usage($prog_name);

詳細なソースコードはここにあります。

次に、プログラムによって、分布データを図で可視化します。次の図となります。
画像をダウンロードするには、ここを右クリックします。プライバシー保護を促進するため、この画像はインターネットから自動的にダウンロードされません。 English words’ distribution 画像をダウンロードするには、ここを右クリックします。プライバシー保護を促進するため、この画像はインターネットから自動的にダウンロードされません。 Japanese words’ distribution

Comments (3)