Reference no: EM133305627 , Length: word count:2400

Database Systems

Objective: Identify an English phrase on Bigram Language Model by Perplexity

You can call functions and facilities on the preprocessing procedure. You are not allowed to call functions for obtaining bigram, corpus cross entropy, and perplexity, and the test accuracy.

Given corpora D, where D = < x[i], y[i] > |i = 1...n, s.t. each of x =< verb, noun, prep, prepobj >=< x1, x2, x3, x4 > with a class label y V, N = y1, y2 . The corpora D is divided into two sets which are Dtrain and Dtest, specified by Dtrain.csv and Dtest.csv files.

Training procedures.

Compute bigram probability for jth attribute of ith feature under a class label y for all i, j and y in Dtrain by MLE algorithm (and a smoothing technique), where C is a counting function.

p(x_i,j|x_i-1,j,Y) = p(xi-1,j, xi,j, y)/p(xi-i,j,Y) = C(xi-1,j, Cxi,j , y)/C(Xi-1, Y)

Testing procedures.

Compute the corpus cross entropy for each of the data instances in Dtest. A data instance of size m is associating with a probability distribution p with m probabilities.

               m
H(p|y) = - ∑pi,ylog2pi,y
              i=1
• Compute the perplexity of the probability distribution of p.

PP(p|y) = 2^H(p|y)

• Assign a class label for a data instance in Dtest.

y ← argmin_yk {PP(p|y = yk)}

• Evaluate your system by the following accuracy measurement.

ACCD_test = 1/|D_test|∑^T_i=1L(yˆⁱ, yⁱ)

where yˆi is the assigned class label by the classifier and yi is the true class label of a data instance x[i] in Dtest and T is the number of data instances in D_test.

L(yˆ , yi) = { 1  if yˆ_i  y_i

                { 0  if yˆ_i ≠ y_i

Report on your design.

Write a 10 page report. The first page should list the names of group members as well the associated tasks.

Introduction
Describing your algorithms.
∗ Preprocessing procedures
∗ The algorithm(s) of obtaining bigrams
∗ The algorithm(s) of obtaining corpus cross entropy and perplexity
∗ The running time complexity of an algorithm (optional)
∗ The missing data handling
∗ Testing metrics Experiments
∗ Experiments and results discussions.
• Experiment settings.
• The results discussions and comparisons.
• Pros and cons of the design. Further improvements.

Presentation.
• 13 minutes of oral presentation.
• 2 minutes of question-answering.
Presentation Date
- Nov. 21, 3 -4 groups
- Nov. 23 (reading day), 3 -4 groups
- Nov. 28, 3 -4 groups
- Nov. 30, 3 -4 groups