Feature engineering and classifier ensembling for KDD CUP 2010


Team Leader

Hsiang-Fu Yu
National Taiwan University
Taiwan

Team Members

Chih-Jen Lin
National Taiwan University

Hsuan-Tien Lin
National Taiwan University

Shou-De Lin
National Taiwan University

Yin-Hsuan Wei
National Taiwan University

Jui-Yu Weng
National Taiwan University

Chun-Fu Chang
National Taiwan University

En-Syu Yan
National Taiwan University

Todd McKenzie
National Taiwan University

Jing-Kai Lou
National Taiwan University

Hsun-Ping Hsieh
National Taiwan University

Jung-Wei Chou
National Taiwan University

Chia-Hua Ho
National Taiwan University

Po-Han Chung
National Taiwan University

Hung-Yi Lo
National Taiwan University

Che-Wei Chang
National Taiwan University

Tsung-Ting Kuo
National Taiwan University

Yi-Chen Lo
National Taiwan University

Chieh Po
National Taiwan University

Chien-Yuan Wang
National Taiwan University

Po Tzu Chang
National Taiwan University

Yu-Shi Lin
National Taiwan University

Yi-Hung Huang
National Taiwan University

Chen-Wei Hung
National Taiwan University

Yu-Xun Ruan
National Taiwan University

Overview

Supplementary online material

Provide a URL to a web page, technical memorandum, or a paper.

Background*

Provide a general summary with relevant background information: Where does the method come from? Is it novel? Name the prior art.

At National Taiwan University, we design a course targeting at KDD CUP 2010. 19 students and one non-registered RA were split to seven groups. Six groups expand features by various binarization and discretization techniques. The resulting sparse feature sets are trained by logistic regression (using LIBLINEAR). One group condenses features so that the number is less than 20. Then random forest is applied (using Weka). Initial development was conducted on an internal split of training data for training and validation. We identify some useful feature combination. For the final submission, each group submits a few results and TAs ensemble them by linear regression.

Method

Summarize the algorithms you used in a way that those skilled in the art should understand what to do. Profile of your methods as follows:

Data exploration and understanding

Did you use data exploration techniques to

  • [checked]  Identify selection biases
  • [checked]  Identify temporal effects (e.g. students getting better over time)
  • [checked]  Understand the variables
  • [checked]  Explore the usefulness of the KC models
  • [checked]  Understand the relationships between the different KC types

Please describe your data understanding efforts, and interesting observations:

No response.

Preprocessing

Feature generation

  • [checked]  Features designed to capture the step type (e.g. enter given, or ... )
  • [checked]  Features based on the textual step name
  • [checked]  Features designed to capture the KC type
  • [checked]  Features based on the textual KC name
  • [checked]  Features derived from opportunity counts
  • [checked]  Features derived from the problem name
  • [checked]  Features based on student ID
  • [checked]  Other features

Details on feature generation:

Features derived from the step name Features based on unit ID Features based on section ID

Feature selection

  • [not checked]  Feature ranking with correlation or other criterion (specify below)
  • [not checked]  Filter method (other than feature ranking)
  • [checked]  Wrapper with forward or backward selection (nested subset method)
  • [not checked]  Wrapper with intensive search (subsets not nested)
  • [not checked]  Embedded method
  • [not checked]  Other method not listed above (specify below)

Details on feature selection:

No response.

Did you attempt to identify latent factors?

  • [checked]  Cluster students
  • [checked]  Cluster knowledge components
  • [checked]  Cluster steps
  • [checked]  Latent feature discovery was performed jointly with learning

Details on latent factor discovery (techniques used, useful student/step features, how were the factors used, etc.):

No response.

Other preprocessing

  • [checked]  Filling missing values (for KC)
  • [not checked]  Principal component analysis

More details on preprocessing:

No response.

Classification

Base classifier

  • [checked]  Decision tree, stub, or Random Forest
  • [checked]  Linear classifier (Fisher's discriminant, SVM, linear regression)
  • [not checked]  Non-linear kernel method (SVM, kernel ridge regression, kernel logistic regression)
  • [not checked]  Naïve
  • [not checked]  Bayesian Network (other than Naïve Bayes)
  • [not checked]  Neural Network
  • [not checked]  Bayesian Neural Network
  • [not checked]  Nearest neighbors
  • [not checked]  Latent variable models (e.g. matrix factorization)
  • [not checked]  Neighborhood/correlation based collaborative filtering
  • [not checked]  Bayesian Knowledge Tracing
  • [not checked]  Additive Factor Model
  • [not checked]  Item Response Theory
  • [not checked]  Other classifier not listed above (specify below)

Loss Function

  • [not checked]  Hinge loss (like in SVM)
  • [not checked]  Square loss (like in ridge regression)
  • [checked]  Logistic loss or cross-entropy (like in logistic regression)
  • [not checked]  Exponential loss (like in boosting)
  • [not checked]  None
  • [not checked]  Don't know
  • [not checked]  Other loss (specify below)

Regularizer

  • [checked]  One-norm (sum of weight magnitudes, like in Lasso)
  • [checked]  Two-norm (||w||^2, like in ridge regression and regular SVM)
  • [not checked]  Structured regularizer (like in group lasso)
  • [not checked]  None
  • [not checked]  Don't know
  • [not checked]  Other (specify below)

Ensemble Method

  • [checked]  Boosting
  • [checked]  Bagging (check this if you use Random Forest)
  • [checked]  Other ensemble method
  • [not checked]  None

Were you able to use information present only in the training set?

  • [checked]  Corrects, incorrects, hints
  • [not checked]  Step start/end times

Did you use post-training calibration to obtain accurate probabilities?

  • [selected]  Yes
  • [not selected]  No

Did you make use of the development data sets for training?

  • [not selected]  Yes
  • [selected]  No

Details on classification:

No response.

Model selection/hyperparameter selection

  • [checked]  We used the online feedback of the leaderboard.
  • [checked]  K-fold or leave-one-out cross-validation (using training data)
  • [not checked]  Virtual leave-one-out (closed for estimations of LOO with a single classifier training)
  • [checked]  Out-of-bag estimation (for bagging methods)
  • [not checked]  Bootstrap estimation (other than out-of-bag)
  • [not checked]  Other cross-validation method
  • [not checked]  Bayesian model selection
  • [not checked]  Penalty-based method (non-Bayesian)
  • [not checked]  Bi-level optimization
  • [not checked]  Other method not listed above (specify below)

Details on model selection:

No response.

Results

Final Team Submission

Scores shown in the table below are Cup scores, not leaderboard scores. The difference between the two is described on the Evaluation page.

A reader should also know from reading the fact sheet what the strength of the method is.

Please comment about the following:

Quantitative advantages (e.g., compact feature subset, simplicity, computational advantages).

- Sparse feature set - Fast linear classifier

Qualitative advantages (e.g. compute posterior probabilities, theoretically motivated, has some elements of novelty).

- Effective ensemble of classifiers - Posterior probabilities from logistic regression models

Other methods. List other methods you tried.

No response.

How helpful did you find the included KC models?

  • [selected]  Crucial in getting good predictions
  • [not selected]  Somewhat helpful in getting good predictions
  • [not selected]  Neutral
  • [not selected]  Not particularly helpful
  • [not selected]  Irrelevant

If you learned latent factors, how helpful were they?

  • [not selected]  Crucial in getting good predictions
  • [selected]  Somewhat helpful in getting good predictions
  • [not selected]  Neutral
  • [not selected]  Not particularly helpful
  • [not selected]  Irrelevant

Details on the relevance of the KC models and latent factors:

No response.

Software Implementation

Availability

  • [not checked]  Proprietary in-house software
  • [not checked]  Commercially available in-house software
  • [checked]  Freeware or shareware in-house software
  • [checked]  Off-the-shelf third party commercial software
  • [checked]  Off-the-shelf third party freeware or shareware

Language

  • [checked]  C/C++
  • [checked]  Java
  • [checked]  Matlab
  • [checked]  Python/NumPy/SciPy
  • [not checked]  Other (specify below)

Details on software implementation:

We use two packages to conduct classification - LIBLINEAR http://www.csie.ntu.edu.tw/~cjlin/liblinear/ - Weka http://www.cs.waikato.ac.nz/ml/weka We use linear regression for ensembling classifiers.

Hardware implementation

Platform

  • [not checked]  Windows
  • [checked]  Linux or other Unix
  • [checked]  Mac OS
  • [not checked]  Other (specify below)

Memory

  • [not selected]  <= 2 GB
  • [not selected]  <= 8 GB
  • [not selected]  >= 8 GB
  • [selected]  >= 32 GB

Parallelism

  • [checked]  Multi-processor machine
  • [checked]  Run in parallel different algorithms on different machines
  • [not checked]  Other (specify below)

Details on hardware implementation. Specify whether you provide a self contained-application or libraries.

No response.

Code URL

Provide a URL for the code (if available):

No response.

Competition Setup

From a performance point of view, the training set was

  • [selected]  Too big (could have achieved the same performance with significantly less data)
  • [not selected]  Too small (more data would have led to better performance)

From a computational point of view, the training set was

  • [not selected]  Too big (imposed serious computational challenges, limited the types of methods that can be applied)
  • [selected]  Adequate (the computational load was easy to handle)

Was the time constraint imposed by the challenge a difficulty or did you feel enough time to understand the data, prepare it, and train models?

  • [not selected]  Not enough time
  • [selected]  Enough time
  • [not selected]  It was enough time to do something decent, but there was a lot left to explore. With more time performance could have been significantly improved.

How likely are you to keep working on this problem?

  • [not selected]  It is my main research area.
  • [selected]  It was a very interesting problem. I'll keep working on it.
  • [not selected]  This data is a good fit for the data mining methods I am using/developing. I will use it in the future for empirical evaluation.
  • [not selected]  Maybe I'll try some ideas , but it is not high priority.
  • [not selected]  Not likely to keep working on it.

Comments on the problem (What aspects of the problem you found most interesting? Did it inspire you to develop new techniques?)

No response.

References

List references below.

No response.