Matching Items (4)
Filtering by

Clear all filters

150190-Thumbnail Image.png
Description
Sparse learning is a technique in machine learning for feature selection and dimensionality reduction, to find a sparse set of the most relevant features. In any machine learning problem, there is a considerable amount of irrelevant information, and separating relevant information from the irrelevant information has been a topic of

Sparse learning is a technique in machine learning for feature selection and dimensionality reduction, to find a sparse set of the most relevant features. In any machine learning problem, there is a considerable amount of irrelevant information, and separating relevant information from the irrelevant information has been a topic of focus. In supervised learning like regression, the data consists of many features and only a subset of the features may be responsible for the result. Also, the features might require special structural requirements, which introduces additional complexity for feature selection. The sparse learning package, provides a set of algorithms for learning a sparse set of the most relevant features for both regression and classification problems. Structural dependencies among features which introduce additional requirements are also provided as part of the package. The features may be grouped together, and there may exist hierarchies and over- lapping groups among these, and there may be requirements for selecting the most relevant groups among them. In spite of getting sparse solutions, the solutions are not guaranteed to be robust. For the selection to be robust, there are certain techniques which provide theoretical justification of why certain features are selected. The stability selection, is a method for feature selection which allows the use of existing sparse learning methods to select the stable set of features for a given training sample. This is done by assigning probabilities for the features: by sub-sampling the training data and using a specific sparse learning technique to learn the relevant features, and repeating this a large number of times, and counting the probability as the number of times a feature is selected. Cross-validation which is used to determine the best parameter value over a range of values, further allows to select the best parameter value. This is done by selecting the parameter value which gives the maximum accuracy score. With such a combination of algorithms, with good convergence guarantees, stable feature selection properties and the inclusion of various structural dependencies among features, the sparse learning package will be a powerful tool for machine learning research. Modular structure, C implementation, ATLAS integration for fast linear algebraic subroutines, make it one of the best tool for a large sparse setting. The varied collection of algorithms, support for group sparsity, batch algorithms, are a few of the notable functionality of the SLEP package, and these features can be used in a variety of fields to infer relevant elements. The Alzheimer Disease(AD) is a neurodegenerative disease, which gradually leads to dementia. The SLEP package is used for feature selection for getting the most relevant biomarkers from the available AD dataset, and the results show that, indeed, only a subset of the features are required to gain valuable insights.
ContributorsThulasiram, Ramesh (Author) / Ye, Jieping (Thesis advisor) / Xue, Guoliang (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2011
151231-Thumbnail Image.png
Description
Gray codes are perhaps the best known structures for listing sequences of combinatorial objects, such as binary strings. Simply defined as a minimal change listing, Gray codes vary greatly both in structure and in the types of objects that they list. More specific types of Gray codes are universal cycles

Gray codes are perhaps the best known structures for listing sequences of combinatorial objects, such as binary strings. Simply defined as a minimal change listing, Gray codes vary greatly both in structure and in the types of objects that they list. More specific types of Gray codes are universal cycles and overlap sequences. Universal cycles are Gray codes on a set of strings of length n in which the first n-1 letters of one object are the same as the last n-1 letters of its predecessor in the listing. Overlap sequences allow this overlap to vary between 1 and n-1. Some of our main contributions to the areas of Gray codes and universal cycles include a new Gray code algorithm for fixed weight m-ary words, and results on the existence of universal cycles for weak orders on [n]. Overlap cycles are a relatively new structure with very few published results. We prove the existence of s-overlap cycles for k-permutations of [n], which has been an open research problem for several years, as well as constructing 1- overlap cycles for Steiner triple and quadruple systems of every order. Also included are various other results of a similar nature covering other structures such as binary strings, m-ary strings, subsets, permutations, weak orders, partitions, and designs. These listing structures lend themselves readily to some classes of combinatorial objects, such as binary n-tuples and m-ary n-tuples. Others require more work to find an appropriate structure, such as k-subsets of an n-set, weak orders, and designs. Still more require a modification in the representation of the objects to fit these structures, such as partitions. Determining when and how we can fit these sets of objects into our three listing structures is the focus of this dissertation.
ContributorsHoran, Victoria E (Author) / Hurlbert, Glenn H. (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Colbourn, Charles (Committee member) / Sen, Arunabha (Committee member) / Arizona State University (Publisher)
Created2012
158314-Thumbnail Image.png
Description
The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum

number of colors needed to color $V(G)$ such that no adjacent vertices

receive the same color. The coloring number $\col(G)$ of a graph

$G$ is the minimum number $k$ such that there exists a linear ordering

of $V(G)$ for which each vertex has

The chromatic number $\chi(G)$ of a graph $G=(V,E)$ is the minimum

number of colors needed to color $V(G)$ such that no adjacent vertices

receive the same color. The coloring number $\col(G)$ of a graph

$G$ is the minimum number $k$ such that there exists a linear ordering

of $V(G)$ for which each vertex has at most $k-1$ backward neighbors.

It is well known that the coloring number is an upper bound for the

chromatic number. The weak $r$-coloring number $\wcol_{r}(G)$ is

a generalization of the coloring number, and it was first introduced

by Kierstead and Yang \cite{77}. The weak $r$-coloring number $\wcol_{r}(G)$

is the minimum integer $k$ such that for some linear ordering $L$

of $V(G)$ each vertex $v$ can reach at most $k-1$ other smaller

vertices $u$ (with respect to $L$) with a path of length at most

$r$ and $u$ is the smallest vertex in the path. This dissertation proves that $\wcol_{2}(G)\le23$ for every planar graph $G$.

The exact distance-$3$ graph $G^{[\natural3]}$ of a graph $G=(V,E)$

is a graph with $V$ as its set of vertices, and $xy\in E(G^{[\natural3]})$

if and only if the distance between $x$ and $y$ in $G$ is $3$.

This dissertation improves the best known upper bound of the

chromatic number of the exact distance-$3$ graphs $G^{[\natural3]}$

of planar graphs $G$, which is $105$, to $95$. It also improves

the best known lower bound, which is $7$, to $9$.

A class of graphs is nowhere dense if for every $r\ge 1$ there exists $t\ge 1$ such that no graph in the class contains a topological minor of the complete graph $K_t$ where every edge is subdivided at most $r$ times. This dissertation gives a new characterization of nowhere dense classes using generalized notions of the domination number.
ContributorsAlmulhim, Ahlam (Author) / Kierstead, Henry (Thesis advisor) / Sen, Arunabha (Committee member) / Richa, Andrea (Committee member) / Czygrinow, Andrzej (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2020
161893-Thumbnail Image.png
Description
A $k$-list assignment for a graph $G=(V, E)$ is a function $L$ that assigns a $k$-set $L(v)$ of "available colors" to each vertex $v \in V$. A $d$-defective, $m$-fold, $L$-coloring is a function $\phi$ that assigns an $m$-subset $\phi(v) \subseteq L(v)$ to each vertex $v$ so that each color class

A $k$-list assignment for a graph $G=(V, E)$ is a function $L$ that assigns a $k$-set $L(v)$ of "available colors" to each vertex $v \in V$. A $d$-defective, $m$-fold, $L$-coloring is a function $\phi$ that assigns an $m$-subset $\phi(v) \subseteq L(v)$ to each vertex $v$ so that each color class $V_{i}=\{v \in V:$ $i \in \phi(v)\}$ induces a subgraph of $G$ with maximum degree at most $d$. An edge $xy$ is an $i$-flaw of $\phi$ if $i\in \phi(x) \cap \phi(y)$. An online list-coloring algorithm $\mathcal{A}$ works on a known graph $G$ and an unknown $k$-list assignment $L$ to produce a coloring $\phi$ as follows. At step $r$ the set of vertices $v$ with $r \in L(v)$ is revealed to $\mathcal{A}$. For each vertex $v$, $\mathcal{A}$ must decide irrevocably whether to add $r$ to $\phi(v)$. The online choice number $\pt_{m}^{d}(G)$ of $G$ is the least $k$ for which some such algorithm produces a $d$-defective, $m$-fold, $L$-coloring $\phi$ of $G$ for all $k$-list assignments $L$. Online list coloring was introduced independently by Uwe Schauz and Xuding Zhu. It was known that if $G$ is planar then $\pt_{1}^{0}(G) \leq 5$ and $\pt_{1}^{1}(G) \leq 4$ are sharp bounds; here it is proved that $\pt_{1}^{3}(G) \leq 3$ is sharp, but there is a planar graph $H$ with $\pt_{1}^{2}(H)\ge 4$. Zhu conjectured that for some integer $m$, every planar graph $G$ satisfies $\pt_{m}^{0}(G) \leq 5 m-1$, and even that this is true for $m=2$. This dissertation proves that $\pt_{2}^{1}(G) \leq 9$, so the conjecture is "nearly" true, and the proof extends to $\pt_{m}^{1}(G) \leq\left\lceil\frac{9}{2} m\right\rceil$. Using Alon's Combinatorial Nullstellensatz, this is strengthened by showing that $G$ contains a linear forest $(V, F)$ such that there is an online algorithm that witnesses $\mathrm{pt}_{2}^{1}(G) \leq 9$ while producing a coloring whose flaws are in $F$, and such that no edge is an $i$-flaw and a $j$-flaw for distinct colors $i$ and $j$.
Contributorshan, ming (Author) / Kierstead, Henry A. (Thesis advisor) / Czygrinow, Andrzej (Committee member) / Sen, Arunabha (Committee member) / Spielberg, John (Committee member) / Fishel, Susanna (Committee member) / Arizona State University (Publisher)
Created2021