Back to search

Cornell University

Sub-Linear Algorithms For Non-Homogeneous Large Alphabet Source Classification

Abstract

dc:description.abstract

Suppose we have several unknown distributions the same discrete countable sample space, namely, {1, 2, 3, 4, ..., n}. and given sequences of samples generated i.i.d from one of the distributions, where the sequence length is smaller than n, known as the sparse sample case. One interesting fundamental question we want to ask is to figure out which distribution the sequence is generated from. Can be viewed as a supervised classification problem using generic model in machine learning. In this thesis, we formulate the problem in an asymptotic way and study the existing algorithms on homogeneous classification problem and closeness testing problem, and extend it to a classification algorithm, mixed 2 distance classifier, using O(n 3 ). Details and theorems of performance guarantees on some specific class of i.i.d distributions is proved in Chapter2. In following chapters we give the performance tables and figures when implementing this idea on synthetic data and real text datasets and outperforms in some of them.

Degree

thesis:*
Name thesis:degree_name
M.S., Electrical Engineering
Level thesis:degree_level
Master of Science
Discipline thesis:degree_discipline
Electrical Engineering
Grantor
Cornell University
Year dc:date.issued
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Xu, Yang
Chair dc:contributor.chair
  • Wagner,Aaron B.
Committee member dc:contributor.committeemember
  • Doerschuk,Peter

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
9333230

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Xu, Yang. Sub-Linear Algorithms For Non-Homogeneous Large Alphabet Source Classification. Master of Science thesis, Cornell University, 2015. https://hdl.handle.net/1813/41179