Search results

Title: Referential grounding towards mediating shared perceptual basis in situated dialogue
Creator: Liu, Changsong, Ph. D.
Date: 2015
Collection: Electronic Theses & Dissertations
Description: In situated dialogue, although an artificial agent (e.g., robot) and its human partner are co-present in a shared environment, they have significantly mismatched perceptual capabilities (e.g., recognizing objects in the surroundings). When a shared perceptual basis is missing, it becomes difficult for the agent to identify referents in the physical world that are referred to by the human (i.e., a problem of referential grounding). The work presented in this dissertation focuses on...
Show moreIn situated dialogue, although an artificial agent (e.g., robot) and its human partner are co-present in a shared environment, they have significantly mismatched perceptual capabilities (e.g., recognizing objects in the surroundings). When a shared perceptual basis is missing, it becomes difficult for the agent to identify referents in the physical world that are referred to by the human (i.e., a problem of referential grounding). The work presented in this dissertation focuses on computational approaches to enable robust and adaptive referential grounding in situated settings.First, graph-based representations are employed to capture a human speaker's linguistic discourse and an agent's visual perception. Referential grounding is then formulated as a graph-matching problem, and a state-space search algorithm is applied to ground linguistic references onto perceived objects. Furthermore, hypergraph representations are used to account for group-based descriptions, and one prevalent pattern of collaborative communication observed from a human-human dialogue dataset is incorporated into the search algorithm. This graph-matching based approach thus provides a principled way to model and utilize spatial relations, group-based descriptions, and collaborative referring discourse in situated dialogue. Evaluation results demonstrate that, when the agent's visual perception is unreliable due to computer vision errors, the graph-based approach significantly improves referential grounding accuracy over a baseline which only relies on object-properties.Second, an optimization based approach is proposed to mediate the perceptual differences between an agent and a human. Through online interaction with the human, the agent can learn a set of weights which indicate how reliably/unreliably each dimension (object type, object color, etc.) of its perception of the environment maps to the human’s linguistic descriptors. Then the agent can adapt to the situation by applying the learned weights to the grounding process and/or adjusting its word grounding models accordingly. Empirical evaluation shows this weight-learning approach can successfully adjust the weights to reflect the agent’s perceptual insufficiencies. The learned weights, together with updated word grounding models, can lead to a significant improvement for referential grounding in subsequent dialogues.Third, a probabilistic labeling algorithm is introduced to handle uncertainties from visual perception and language processing, and to potentially support generation of collaborative responses in the future. The probabilistic labeling algorithm is formulated under the Bayesian reasoning framework. It provides a unified probabilistic scheme to integrate different types of evidence from the collaborative referring discourse, and to generate ranked multiple grounding hypotheses for follow-up processes. Evaluated on the same dataset, probabilistic labeling significantly outperforms state-space search in both accuracy and efficiency.All these approaches contribute to the ultimate goal of building collaborative dialogue agents for situated interaction, so that the next generation of intelligent machines/devices can better serve human users in daily work and life.
Show less

Title: Computational identification and analysis of non-coding RNAs in large-scale biological data
Creator: Lei, Jikai
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Non-protein-coding RNAs (ncRNAs) are RNA molecules that function directly at the level of RNA without translating into protein. They play important biological functions in all three domains of life, i.e. Eukarya, Bacteria and Archaea. To understand the working mechanisms and the functions of ncRNAs in various species, a fundamental step is to identify both known and novel ncRNAs from large-scale biological data.Large-scale genomic data includes both genomic sequence data and NGS sequencing...
Show moreNon-protein-coding RNAs (ncRNAs) are RNA molecules that function directly at the level of RNA without translating into protein. They play important biological functions in all three domains of life, i.e. Eukarya, Bacteria and Archaea. To understand the working mechanisms and the functions of ncRNAs in various species, a fundamental step is to identify both known and novel ncRNAs from large-scale biological data.Large-scale genomic data includes both genomic sequence data and NGS sequencing data. Both types of genomic data provide great opportunity for identifying ncRNAs. For genomic sequence data, a lot of ncRNA identification tools that use comparative sequence analysis have been developed. These methods work well for ncRNAs that have strong sequence similarity. However, they are not well-suited for detecting ncRNAs that are remotely homologous. Next generation sequencing (NGS), while it opens a new horizon for annotating and understanding known and novel ncRNAs, also introduces many challenges. First, existing genomic sequence searching tools can not be readily applied to NGS data because NGS technology produces short, fragmentary reads. Second, most NGS data sets are large-scale. Existing algorithms are infeasible on NGS data because of high resource requirements. Third, metagenomic sequencing, which utilizes NGS technology to sequence uncultured, complex microbial communities directly from their natural inhabitants, further aggravates the difficulties. Thus, massive amount of genomic sequence data and NGS data calls for efficient algorithms and tools for ncRNA annotation.In this dissertation, I present three computational methods and tools to efficiently identify ncRNAs from large-scale biological data. Chain-RNA is a tool that combines both sequence similarity and structure similarity to locate cross-species conserved RNA elements with low sequence similarity in genomic sequence data. It can achieve significantly higher sensitivity in identifying remotely conserved ncRNA elements than sequence based methods such as BLAST, and is much faster than existing structural alignment tools. miR-PREFeR (miRNA PREdiction From small RNA-Seq data) utilizes expression patterns of miRNA and follows the criteria for plant microRNA annotation to accurately predict plant miRNAs from one or more small RNA-Seq data samples. It is sensitive, accurate, fast and has low-memory footprint. metaCRISPR focuses on identifying Clustered Regularly Interspaced Short Palindromic Repeats (CRISPRs) from large-scale metagenomic sequencing data. It uses a kmer hash table to efficiently detect reads that belong to CRISPRs from the raw metagonmic data set. Overlap graph based clustering is then conducted on the reduced data set to separate different CRSIPRs. A set of graph based algorithms are used to assemble and recover CRISPRs from the clusters.
Show less

Title: Contributions to Machine Learning in Biomedical Informatics
Creator: Baytas, Inci Meliha
Date: 2019
Collection: Electronic Theses & Dissertations
Description: With innovations in digital data acquisition devices and increased memory capacity, virtuallyall commercial and scientific domains have been witnessing an exponential growth in the amountof data they can collect. For instance, healthcare is experiencing a tremendous growth in digitalpatient information due to the high adaptation rate of electronic health record systems in hospitals.The abundance of data offers many opportunities to develop robust and versatile systems, as longas the...
Show moreWith innovations in digital data acquisition devices and increased memory capacity, virtuallyall commercial and scientific domains have been witnessing an exponential growth in the amountof data they can collect. For instance, healthcare is experiencing a tremendous growth in digitalpatient information due to the high adaptation rate of electronic health record systems in hospitals.The abundance of data offers many opportunities to develop robust and versatile systems, as longas the underlying salient information in data can be captured. On the other hand, today’s data,often named big data, is challenging to analyze due to its large scale and high complexity. For thisreason, efficient data-driven techniques are necessary to extract and utilize the valuable informationin the data. The field of machine learning essentially develops such techniques to learn effectivemodels directly from the data. Machine learning models have been successfully employed to solvecomplicated real world problems. However, the big data concept has numerous properties that poseadditional challenges in algorithm development. Namely, high dimensionality, class membershipimbalance, non-linearity, distributed data, heterogeneity, and temporal nature are some of the bigdata characteristics that machine learning must address.Biomedical informatics is an interdisciplinary domain where machine learning techniques areused to analyze electronic health records (EHRs). EHR comprises digital patient data with variousmodalities and depicts an instance of big data. For this reason, analysis of digital patient data isquite challenging although it provides a rich source for clinical research. While the scale of EHRdata used in clinical research might not be huge compared to the other domains, such as socialmedia, it is still not feasible for physicians to analyze and interpret longitudinal and heterogeneousdata of thousands of patients. Therefore, computational approaches and graphical tools toassist physicians in summarizing the underlying clinical patterns of the EHRs are necessary. Thefield of biomedical informatics employs machine learning and data mining approaches to provide the essential computational techniques to analyze and interpret complex healthcare data to assistphysicians in patient diagnosis and treatment.In this thesis, we propose and develop machine learning algorithms, motivated by prevalentbiomedical informatics tasks, to analyze the EHRs. Specifically, we make the following contributions:(i) A convex sparse principal component analysis approach along with variance reducedstochastic proximal gradient descent is proposed for the patient phenotyping task, which is definedas finding clinical representations for patient groups sharing the same set of diseases. (ii)An asynchronous distributed multi-task learning method is introduced to learn predictive modelsfor distributed EHRs. (iii) A modified long-short term memory (LSTM) architecture is designedfor the patient subtyping task, where the goal is to cluster patients based on similar progressionpathways. The proposed LSTM architecture, T-LSTM, performs a subspace decomposition on thecell memory such that the short term effect in the previous memory is discounted based on thelength of the time gap. (iv) An alternative approach to T-LSTM model is proposed with a decoupledmemory to capture the short and long term changes. The proposed model, decoupled memorygated recurrent network (DM-GRN), is designed to learn two types of memories focusing on differentcomponents of the time series data. In this study, in addition to the healthcare applications,behavior of the proposed model is investigated for traffic speed prediction problem to illustrate itsgeneralization ability. In summary, the aforementioned machine learning approaches have beendeveloped to address complex characteristics of electronic health records in routine biomedical informaticstasks such as computational patient phenotyping and patient subtyping. Proposed modelsare also applicable to different domains with similar data characteristics as EHRs.
Show less

Title: Novel computational approaches to investigate microbial diversity
Creator: Zhang, Qingpeng
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Species diversity is an important measurement of ecological communities.Scientists believe that there is a strong relationship between speciesdiversity and ecosystem processes. However efforts to investigate microbialdiversity using whole genome shotgun reads data are still scarce. With novel applications of data structuresand the development of novel algorithms, firstly we developed an efficient k-mer countingapproach and approaches to enable scalable streaming analysis of large and error...
Show moreSpecies diversity is an important measurement of ecological communities.Scientists believe that there is a strong relationship between speciesdiversity and ecosystem processes. However efforts to investigate microbialdiversity using whole genome shotgun reads data are still scarce. With novel applications of data structuresand the development of novel algorithms, firstly we developed an efficient k-mer countingapproach and approaches to enable scalable streaming analysis of large and error-prone short-read shotgun data sets. Then based on these efforts, we developed a statistical framework allowing for scalable diversity analysis of large,complex metagenomes without the need for assembly or reference sequences. Thismethod is evaluated on multiple large metagenomes from differentenvironments, such as seawater, human microbiome, soil. Given the velocity ingrowth of sequencing data, this method is promising for analyzing highlydiverse samples with relatively low computational requirements. Further, as themethod does not depend on reference genomes, it also provides opportunities totackle the large amounts of unknowns we find in metagenomicdatasets.
Show less

Title: A framework for verification of transaction level models in systemc
Creator: Hajisheykhi, Reza
Date: 2016
Collection: Electronic Theses & Dissertations
Description: Due to their increasing complexity, today's SoC (System on Chip) systems are subject to a variety of faults (e.g., single-event upset, component crash, etc.), thereby their verification a highly important task of such systems. However, verification is a complex task in part due to the large scale of integration of SoC systems and different levels of abstraction provided by modern system design languages such as SystemC.To facilitate the verification of SoC systems, this dissertation proposes...
Show moreDue to their increasing complexity, today's SoC (System on Chip) systems are subject to a variety of faults (e.g., single-event upset, component crash, etc.), thereby their verification a highly important task of such systems. However, verification is a complex task in part due to the large scale of integration of SoC systems and different levels of abstraction provided by modern system design languages such as SystemC.To facilitate the verification of SoC systems, this dissertation proposes an approach for verifying inter-component communication protocols in SystemC Transaction Level Modeling (TLM) programs. SystemC is a widely accepted language and an IEEE standard. It includes a C++ library of abstractions and a run-time kernel that simulates the specified system, thereby enabling the early development of embedded software for the system that is being designed. To enable and facilitate the communication of different components in SystemC, the Open SystemC Initiative (OSCI) has proposed an interoperability layer (on top of SystemC) that enables transaction-based interactions between the components of a system, called Transaction Level Modeling (TLM).In order to verify SystemC TLM programs, we propose a method that includes five main steps, namely defining formal semantics, model extraction, fault modeling, model slicing, and model checking. In order to extract a formal model from the given SystemC TLM program, first we need to specify the requirements of developing a formal semantics that can capture the SystemC TLM programs while still benefiting from automation techniques for verification and/or synthesis. Based on this intuition, we utilize two model extraction approaches that consider the architecture of the given program too.In the first approach, we propose a set of transformation rules that helps us to extract a Promela model from the SystemC TLM program. In the second approach, we discuss how to extract a timed automata model from the given program.When we have the formal model, we model and inject several types of faults into the formal models extracted from the SystemC TLM programs. For injecting faults, we have developed a tool, called UFIT, that takes a formal model and a desirable fault type, and injects the faults into the model accordingly.The models extracted from the SystemC TLM program are usually very complex. Additionally, when we inject faults into these models they become even more complex. Hence, we utilize a model slicing technique to slice the models in the presence or absence of faults. We have developed a tool, called USlicer that takes a formal model along with a set of properties that needs to be verified, and generate a sliced model based on the given properties. The results show that verification time and the memory usage of the sliced version of the model is significantly smaller than that of the original model. Subsequently, in some cases where the verification of the original formal models is not even possible, using our model slicing technique makes the verification possible in a reasonable time and space.We demonstrate the proposed approach using several SystemC transaction level case studies. In each case study, we explain each step of our approach in detail and discuss the results and improvements in each of them.
Show less

Title: Exploiting smoothness in statistical learning, sequential prediction, and stochastic optimization
Creator: Mahdavi, Mehrdad
Date: 2014
Collection: Electronic Theses & Dissertations
Description: In the last several years, the intimate connection between convex optimization and learning problems, in both statistical and sequential frameworks, has shifted the focus of algorithmic machine learning to examine this interplay. In particular, on one hand, this intertwinement brings forward new challenges in reassessment of the performance of learning algorithms including generalization and regret bounds under the assumptions imposed by convexity such as analytical properties of loss...
Show moreIn the last several years, the intimate connection between convex optimization and learning problems, in both statistical and sequential frameworks, has shifted the focus of algorithmic machine learning to examine this interplay. In particular, on one hand, this intertwinement brings forward new challenges in reassessment of the performance of learning algorithms including generalization and regret bounds under the assumptions imposed by convexity such as analytical properties of loss functions (e.g., Lipschitzness, strong convexity, and smoothness). On the other hand, emergence of datasets of an unprecedented size, demands the development of novel and more efficient optimization algorithms to tackle large-scale learning problems. The overarching goal of this thesis is to reassess the smoothness of loss functions in statistical learning, sequential prediction/online learning, and stochastic optimization and explicate its consequences. In particular we examine how leveraging smoothness of loss function could be beneficial or detrimental in these settings in terms of sample complexity, statistical consistency, regret analysis, and convergence rate. In the statistical learning framework, we investigate the sample complexity of learning problems when the loss function is smooth and strongly convex and the learner is provided with the target risk as a prior knowledge. We establish that under these assumptions, by exploiting the smoothness of loss function, we are able to improve the sample complexity of learning exponentially. Furthermore, the proof of our results is constructive and is rooted in a properly designed stochastic optimization algorithm which could be of significant practical importance. We also investigate the smoothness from the viewpoint of statistical consistency and show that in sharp contrast to optimization and generalization where the smoothness is favorable because of its computational and theoretical virtues, the smoothness of surrogate loss function might deteriorate the binary excess risk. Motivated by this negative result, we provide a unified analysis of three types of errors including optimization error, generalization bound, and the error in translating convex excess risk into a binary excess risk, and underline the conditions that smoothness might be preferred.We then turn to elaborate the importance of smoothness in sequential prediction/online learning. We introduce a new measure to assess the performance of online learning algorithms which is referred to as gradual variation. The gradual variation is measured by the sum of the distances between every two consecutive loss functions and is more suitable for gradually evolving environments such as stock prediction. Under smoothness assumption, we devise novel algorithms for online convex optimization with regret bounded by gradual variation. The proposed algorithms can take advantage of benign sequences and at the same time protect against the adversarial sequences of loss functions. Finally, we investigate how to exploit the smoothness of loss function in convex optimization. Unlike the optimization methods based on full gradients, the smoothness assumption was not exploited by most of the existing stochastic optimization methods. We propose a novel optimization paradigm that is referred to as mixed optimization which interpolates between stochastic and full gradient methods and is able to exploit the smoothness of loss functions to obtain faster convergence rates in stochastic optimization, and condition number independent accesses of full gradients in deterministic optimization. The key underlying insight of mixed optimization is to utilize infrequent full gradients of the objective function to progressively reduce the variance of the stochastic gradients. These results show an intricate interplay between stochastic and deterministic convex optimization to take advantages of their individual merits. We also propose efficient projection-free optimization algorithms to tackle the computational challenge arising from the projection steps which are required at each iteration of most existing gradient based optimization methods to ensure the feasibility of intermediate solutions. In stochastic optimization setting, by introducing and leveraging smoothness, we develop novel methods which only require one projection at the final iteration. In online learning setting, we consider online convex optimization with soft constraints where the constraints are allowed to be satisfied on long term. We show that by compromising on the learner's regret, one can devise efficient online learning algorithms with sub-linear bound on both the regret and the violation of the constraints
Show less

Title: Making heads and tails of Molgula : next generation sequencing analysis of closely related tailed and tail-less ascidian species
Creator: Lowe, Elijah Kariem
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Tunicates are invertebrate chordates and are the sister group to the vertebrates. Although tunicates share little morphological resemblance to vertebrates in their adult stage, they do share several features in their larval stage: a hollow dorsal neural tube, gill slits, and a post-anal tail, containing a notochord--a group of cells organized in a rod shaped structure - the key features that classify the phyla. Within the tunicates, several ascidians have undergone tail-loss, and many of them...
Show moreTunicates are invertebrate chordates and are the sister group to the vertebrates. Although tunicates share little morphological resemblance to vertebrates in their adult stage, they do share several features in their larval stage: a hollow dorsal neural tube, gill slits, and a post-anal tail, containing a notochord--a group of cells organized in a rod shaped structure - the key features that classify the phyla. Within the tunicates, several ascidians have undergone tail-loss, and many of them are Molgulidae. Hybrids have been produced through the cross fertilization of two Molgula species (Molgula occulta and Molgula oculata), and no other solitary Molgula species have been known to hybridize. Here we have sequenced the transcriptomes of several developmental stages of both M. occulta and M. oculata-- two closely related, free-spawning ascidian species, and their hybrid, in order to study the mechanisms behind tail lost in M. occulta. We were first presented with the problem of identifying the best pipeline for the de novo assembly of our transcriptomes. Here we determined that processing reads through digital normalization, a redundancy reduction step, had less of an effect on assemblies than the assembler used. We then sequenced and assembled the genomes of M. occulta, M. oculata and a more distant species, M. occidentalis. This allowed us to characterize the genomes, discovering that the species are more divergent then they appear phenotypically, and also building better gene models. Through differential expression analysis we determined that M. oculata and the hybrid appear to have overlapping transcripts that are up-regulated during the formation of the ascidian tail, and that the genes are primarily overexpressed by the tailed species and hybrid in relation to the tail-less species.
Show less

Title: Structure and evolutionary dynamics in fitness landscapes
Creator: Pakanati, Anuraag R.
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Evolution can be conceptualized as an optimization algorithm that allows populations to search through genotypes for those that produce high fitness solutions. This search process is commonly depicted as exploring a “fitness landscape”, which combines similarity relationships among genotypes with the concept of a genotype-fitness map. As populations adapt to their fitness landscape, they accumulate information about the fitness landscape in which they live. A greater understanding of...
Show moreEvolution can be conceptualized as an optimization algorithm that allows populations to search through genotypes for those that produce high fitness solutions. This search process is commonly depicted as exploring a “fitness landscape”, which combines similarity relationships among genotypes with the concept of a genotype-fitness map. As populations adapt to their fitness landscape, they accumulate information about the fitness landscape in which they live. A greater understanding of evolution on fitness landscapes will help elucidate fundamental evolutionary processes. I examine methods of estimating information acquisition in evolving populations and find that these techniques have largely ignored the effects of common descent. Since information is estimated by measuring conserved genomic regions across a population, common descent can create a severe bias by increasing similarities among unselected regions. I introduce a correction method to compensate for the effects of common descent on genomic information and empirically demonstrate its efficacy.Next, I explore three instantiations of NK, Avida, and RNA fitness landscapes to better understand structural properties such as the distribution of peaks and the size of basins of attraction. I find that the fitness of peaks is correlated with the fitness of peaks within their neighborhood, and that the size of peaks' basins of attraction tends to be proportional to the heights of the peaks. Finally, I visualize local dynamics and perform a detailed comparison between the space of what evolutionary trajectories are technically possible from a single starting point and the results of actual evolving populations.
Show less

Title: ON DESIGN AND IMPLEMENTATION OF FAST & SECURE NETWORK PROTOCOLS FOR DATACENTERS
Creator: Munir, Ali
Date: 2019
Collection: Electronic Theses & Dissertations
Description: My PhD work focuses on improving the performance and security of networked systems. For network performance, my research focuses on scheduling and transport in datacenter networks. For network security, my research focuses on multipath TCP security.To improve the performance of datacenter transport, I proposed PASE, a near-optimal and deployment friendly transport protocol. To this end, I first identified the underlying strategies used by existing datacenter transports. Next, I showed that...
Show moreMy PhD work focuses on improving the performance and security of networked systems. For network performance, my research focuses on scheduling and transport in datacenter networks. For network security, my research focuses on multipath TCP security.To improve the performance of datacenter transport, I proposed PASE, a near-optimal and deployment friendly transport protocol. To this end, I first identified the underlying strategies used by existing datacenter transports. Next, I showed that these strategies are complimentary to each other, rather than substitutes, as they have different strengths and can address each other’s limitations. Unfortunately, prior datacenter transports use only one of these strategies and as a result they either achieve near-optimal performance or deployment friendliness but not both. Based on this insight, I designed a datacenter transport protocol called PASE, which carefully synthesizes these strategies by assigning different transport responsibility to each strategy. To further improve the performance of datacenter transport in multi-tenant networks, I proposed Stacked Congestion Control (SCC), to achieve performance isolation and objective scheduling simultaneously. SCC is a distributed host-based bandwidth allocation framework, where an underlay congestion control layer handles contention among tenants, and a private congestion control layer for each tenant optimizes its performance objective. To my best knowledge, no prior work supported performance isolation and objective scheduling simultaneously. To improve task scheduling performance in datacenters, I proposed NEAT, a task scheduling framework that leverages information from the underlying network scheduler to make task placement decisions. Existing datacenter schedulers optimize either the placement of tasks or the scheduling of network flows. Inconsistent assumptions of the two schedulers can compromise the overall application performance. The core of NEAT is a task completion time predictor that estimates the completion time of a task under given network condition and a given network scheduling policy. Next, a distributed task placement framework leverages the predicted task completion times to make task placement decisions and minimize the average completion time of active tasks.To improve multipath TCP (MPTCP) security, I reported vulnerabilities in MPTCP that arise because of cross-path interactions between MPTCP subflows. MPTCP allows two endpoints to simultaneously use multiple paths between them. An attacker eavesdropping one MPTCP subflow can infer throughput of other subflows and also can inject forged MPTCP packets to change priorities of any MPTCP subflow. Attacker can exploit these vulnerabilities to launch the connection hijack attack on the paths he has no access to, or to divert traffic from one path to other paths. My proposed vulnerabilities fixes, changes to MPTCP specification, provide the guarantees that MPTCP is at least as secure as TCP and the original MPTCP. And has been adopted by IETF.
Show less

Title: Face search and clustering at scale
Creator: Otto, Charles
Date: 2016
Collection: Electronic Theses & Dissertations
Description: There has been a great deal of progress on the problem of unconstrained face recognition in recent years, particularly with the emergence of deep learning methods for generating face representations. Developing robust face representations is not only of great practical interest for classic biometric problems like face verification, but also for emerging large scale face search problems. In both social media, and law-enforcement applications, an extremely large volume of face data is becoming...
Show moreThere has been a great deal of progress on the problem of unconstrained face recognition in recent years, particularly with the emergence of deep learning methods for generating face representations. Developing robust face representations is not only of great practical interest for classic biometric problems like face verification, but also for emerging large scale face search problems. In both social media, and law-enforcement applications, an extremely large volume of face data is becoming commonplace. One emerging problem related to this high volume of data is to devise methods to search for persons of interest among the billions of shared photos on these websites. Another challenge is to group or cluster large collections of unlabeled face images by identity, for example as a prelude to manual examination of a collection of images in law-enforcement applications.Regarding the face search problem, we propose a face search system which combines a fast search procedure, coupled with a state-of-the-art commercial off the shelf (COTS) matcher, in a cascaded framework. Given a probe face, we first filter the large gallery of photos to find the top-k most similar faces using features learned by a convolutional neural network. The k retrieved candidates are re-ranked by combining similarities based on deep features and those output by the COTS matcher. We evaluate the proposed face search system on a gallery containing 80 million web-downloaded face images. Experimental results demonstrate that while the deep features perform worse than the COTS matcher on a mugshot dataset (93.7% vs. 98.6% TAR@FAR of 0.01%), fusing the deep features with the COTS matcher improves the overall performance (99.5% TAR@FAR of 0.01%). This shows that the learned deep features provide complementary information over representations used in state-of-the-art face matchers. On the unconstrained face image benchmarks, the performance of the learned deep features is competitive with reported accuracies. LFW database: 98.20% accuracy under the standard protocol and 88.03% TAR@FAR of 0.1% under the BLUFR protocol; IJB-A benchmark: 51.0% TAR@FAR of 0.1% (verification), rank 1 retrieval of 82.2% (closed-set search), 61.5% FNIR@FPIR of 1% (open-set search). The proposed face search system offers an excellent trade-off between accuracy and scalability on galleries with millions of images. Additionally, in a face search experiment involving photos of the Tsarnaev brothers, convicted of the Boston Marathon bombing, the proposed cascade face search system could find the younger brother's (Dzhokhar Tsarnaev) photo at rank 1 in 1 second on a 5M gallery and at rank 8 in 7 seconds on an 80M gallery, using a Intel Xeon processor clocked at 3.1 GHz.In terms of clustering, in social media, law enforcement, and other applications the number of unlabeled faces can be of the order of hundreds of million, while the number of identities (clusters) can range from a few thousand to millions. To address the challenges of run-time complexity and cluster quality, we present an approximate Rank-Order clustering algorithm that performs better than popular clustering algorithms (k-Means and Spectral). Our experiments include clustering up to 123 million face images into over 10 million clusters. Clustering results are analyzed in terms of external (known face labels) and internal (unknown face labels) cluster quality measures, and run-time. Our clustering algorithm achieves an F-measure of 0.87 on the LFW benchmark (13K faces of 5,749 individuals), which drops to 0.27 on the largest dataset considered (13K faces in LFW + 123M distractor images). Additionally, we show that frames in the YouTube benchmark can be clustered with an F-measure of 0.71. An internal per-cluster quality measure is developed to rank individual clusters for manual exploration of high quality clusters that are compact and isolated.Finally, we further develop our face representation, leveraging more advanced network architectures, and an order of magnitude more training data--attaining a verification rate of 92.22% at 0.1% FAR on the BLUFR verification protocol, using a single model.
Show less

Title: Fingerprint recognition : contributions to latent matching and 3D fingerprint target generation
Creator: Arora, Sunpreet Singh
Date: 2016
Collection: Electronic Theses & Dissertations
Description: Automatic fingerprint capture and comparison methods have led to the ubiquitous use of fingerprint-based person recognition in applications ranging from law enforcement and border control to national identification and smartphone unlock. However, despite tremendous advancements in the state-of-the-art, improvements are still needed in case of some challenging applications, e.g, to recognize poor quality and distorted fingerprints acquired from non-cooperative users, improve fingerprint reader...
Show moreAutomatic fingerprint capture and comparison methods have led to the ubiquitous use of fingerprint-based person recognition in applications ranging from law enforcement and border control to national identification and smartphone unlock. However, despite tremendous advancements in the state-of-the-art, improvements are still needed in case of some challenging applications, e.g, to recognize poor quality and distorted fingerprints acquired from non-cooperative users, improve fingerprint reader fidelity, and determine anti-spoofing capability of different fingerprint readers. In this thesis, we address two such impending challenges: (i) comparison of latent prints found at crime scenes to large collections of reference prints (rolled tenprints or slap fingerprints) in law enforcement databases, and (ii) operational evaluation of fingerprint recognition systems prior to large scale deployment.We develop a feedback paradigm that uses reference print features to dynamically select latent features during matching. The paradigm automatically determines if dynamic latent feature selection would improve recognition performance using a statistical hypothesis test and qualitatively decides the regions in latent and reference prints for applying feedback. The paradigm when used in conjunction with a state-of-the-art latent matcher demonstrates marked improvement (0.5-3.5%) in latent matching accuracy.Further, we develop a framework for crowdsourcing latent print feature markup to a pool of fingerprint examiners. The framework uses a statistical criterion to automatically determine when crowdsourcing is required, and a method to dynamically determine the number of examiners needed for latent feature markup. Significant recognition performance improvements (2.5-11.5%) are obtained using crowdsourced markups in conjunction with a state-of-the-art latent matcher.Finally, we design and fabricate single-finger and whole hand 3D targets for operational evaluation of optical and capacitive fingerprint readers as well as for end-to-end evaluation of fingerprint recognition systems. 2D calibration patterns with known characteristics (e.g. synthetic fingerprints with known features, sine gratings with known orientation and spacing) are projected onto electronic 3D finger and hand surfaces to create electronic 3D single-finger and whole hand targets. A high-resolution 3D printer is used to manufacture physical 3D single-finger and whole hand targets from electronic targets. Other contributions include: (i) a method to chemically clean the 3D printed targets without impacting the engraved target patterns, (ii) a procedure to apply conductive coating of metal/metal oxides on the surface of 3D targets using DC sputtering, (iii) fidelity measurement techniques using optical microscopy to assess the 3D target generation process, and (iv) methods to evaluate fingerprint readers using the fabricated 3D targets. We demonstrate that the 2D calibration pattern features are reproduced with high fidelity both on the electronic and physical 3D single-finger and whole hand targets and that the intra-class variations between images of the 3D targets do not degrade matching accuracy (at 0.01% false accept rate). We evaluate several commercially available single-finger and slap contact-based and contactless optical readers as well as capacitive readers using the generated 3D targets.
Show less

Title: Collaboration based spectrum sharing algorithms in cognitive radio networks
Creator: Hyder, Chowdhury Sayeed
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Radio spectrum assignment to wireless providers using traditional fixed allocation policy will no longer be a viable technique to meet the growing spectrum demand of emerging wireless applications. This is because while the available pool of unassigned radio spectrum is low, the spectrum already assigned to existing applications is also often underutilized in time, frequency, and location. With features like transmission flexibility and adaptability cognitive radio (CR) provides auseful means...
Show moreRadio spectrum assignment to wireless providers using traditional fixed allocation policy will no longer be a viable technique to meet the growing spectrum demand of emerging wireless applications. This is because while the available pool of unassigned radio spectrum is low, the spectrum already assigned to existing applications is also often underutilized in time, frequency, and location. With features like transmission flexibility and adaptability cognitive radio (CR) provides auseful means of spectrum sharing among growing users as an alternative to the current fixed policy. The cognitive radio network (CRN), based on the functionality of CR, consists of two types of users — primary users (PU) and secondary users (SU). Primary users are licensed users who have exclusive access rights of a fixed spectrum range. Secondary users are unlicensed users who opportunistically exploit the spectrum holes or negotiate with primary users to earn transmissionaccess rights.The CRN based efficient spectrum sharing algorithms work on different forms of collaboration between the PUs and the SUs (inter-user collaboration) and among the SUs themselves (intra-user collaboration). In the sensing based collaboration model, the SUs sense licensed spectrum and collaboratively decide about its availability based on the sensing results without any involvements from the PUs. In the relay based collaboration model, the SUs coordinate with the PUs directly,relay primary packets in exchange for transmission opportunities, and thus build a win-win cooperative framework to attainmutual benefits. In the auction based collaborationmodel, the SUs bid for temporary or permanent usage rights of unused licensed spectrum bands that are put into auction for sale by the PUs. Each of these collaboration models faces different sets of challenges towardsachieving high spectrum utilization. In this dissertation, we address some of these challenges and present a set of efficient spectrum sharing algorithms based on these collaboration models.The first work in this dissertation addresses the spectrum sensing data falsification (SSDF) attack in IEEE 802.22 wireless regional area network (WRAN) under the sensing based collaboration model. We discuss different strategies of manipulating sensing reports by one or more malicious users and how these manipulation strategies may affect the spectrum utilization. To defend against such malicious attacks, we present an adaptive reputation based clustering algorithm. The algorithm combines the clustering technique with feedback based reputation adjustment to prevent independent and collaborative SSDF attacks and quarantines the attackers from the decision making process.Our next set of work in this dissertation falls under the relay based collaboration model. We investigate the feasibility of this collaboration model in the case of real-time applications. We quantify the impact of packet deadlines and cooperation overhead on the system performance. We discuss the impact of interference that may cause from secondary transmissions. Based on the analysis, we develop an interference aware reliable cooperative framework which improves the packet reception rate of both users with low overhead. We extend our investigation of this relay based collaboration model from single hop to multiple hops in the form of cooperative routing. We formulate the routing problem as an overlapping coalition formation game where each coalition represents a routing path between primary source and destination consisting of multiple SUs as intermediate relays. The proposed model allows SUs to participate in more than one coalitions and creates more transmission opportunities for them while achieving stable routing paths for PUs.Our final set of work in this dissertation deals with the challenges in the auction based collaboration model. We consider an online setting of spectrum auctions where participation and valuation of both bidders and sellers are stochastic. We analyze the behavior of bidders and sellers in such settings and develop truthful auction mechanisms with respect to bid and time, improving spectrum reuse, auction efficiency, and revenue. The findings from our research will help to understand the underlying challenges in future networks, build a better spectrum ecosystem, and encourage new spectrum sharing models in wireless broadband communications.
Show less

Title: Harnessing evolutionary computation for the design and generation of adaptive embedded controllers within the context of uncertainty
Creator: Byers, Chad Michael
Date: 2015
Collection: Electronic Theses & Dissertations
Description: A critical challenge for the design of embedded controllers is incorporating desirable qualities such as robustness, fault tolerance, and adaptability into the control process in order to respond to dynamic environmental conditions. An embedded controller governs the execution of a task-specific system by monitoring information from its environment via sensors and producing an appropriate response through the system's actuators, often independent of any supervisory control. For a human...
Show moreA critical challenge for the design of embedded controllers is incorporating desirable qualities such as robustness, fault tolerance, and adaptability into the control process in order to respond to dynamic environmental conditions. An embedded controller governs the execution of a task-specific system by monitoring information from its environment via sensors and producing an appropriate response through the system's actuators, often independent of any supervisory control. For a human developer, identifying the set of all possible combinations of conditions a system might experience and designing a solution to accommodate this set is burdensome, costly, and often, infeasible. To alleviate this burden, a variety of techniques have been explored to automate the generation of embedded controller solutions. In this dissertation, we focus on the bio-inspired technique referred to as evolutionary computation where we harness evolution's power as a population-based, global search technique to build up good behavioral components. In this way, evolution naturally selects for these desirable qualities in order for a solution to remain competitive over time in the population. Often, these search techniques operate in the context of uncertainty where aspects of the (1) problem domain, (2) solution space, and (3) search process itself are subject to variation and change. To mitigate issues associated with uncertainty in the problem domain, we propose the digital enzyme, a biologically-inspired model that maps the complexity of both the environment and the system into the space of values rather than instructions. To address uncertainty in the solution space, we remove constraints in our initial digital enzyme model to allow the genome structure to be dynamic and open-ended, accommodating a wider range of evolved solution designs. Finally, to help explore the inherent uncertainty that exists in the search process, we uncover a hidden feature interaction present between the diversity-preserving search operator of a popular evolutionary algorithm and propose a new way to use niching as a means to mitigate its unwanted effects and bias on search.
Show less

Title: Kernel-based clustering of big data
Creator: Chitta, Radha
Date: 2015
Collection: Electronic Theses & Dissertations
Description: There has been a rapid increase in the volume of digital data over the recent years. A study by IDC and EMC Corporation predicted the creation of 44 zettabytes (10^21 bytes) of digital data by the year 2020. Analysis of this massive amounts of data, popularly known as big data, necessitates highly scalable data analysis techniques. Clustering is an exploratory data analysis tool used to discover the underlying groups in the data. The state-of-the-art algorithms for clustering big data sets...
Show moreThere has been a rapid increase in the volume of digital data over the recent years. A study by IDC and EMC Corporation predicted the creation of 44 zettabytes (10^21 bytes) of digital data by the year 2020. Analysis of this massive amounts of data, popularly known as big data, necessitates highly scalable data analysis techniques. Clustering is an exploratory data analysis tool used to discover the underlying groups in the data. The state-of-the-art algorithms for clustering big data sets are linear clustering algorithms, which assume that the data is linearly separable in the input space, and use measures such as the Euclidean distance to define the inter-point similarities. Though efficient, linear clustering algorithms do not achieve high cluster quality on real-world data sets, which are not linearly separable. Kernel-based clustering algorithms employ non-linear similarity measures to define the inter-point similarities. As a result, they are able to identify clusters of arbitrary shapes and densities. However, kernel-based clustering techniques suffer from two major limitations: (i) Their running time and memory complexity increase quadratically with the increase in the size of the data set. They cannot scale up to data sets containing billions of data points. (ii) The performance of the kernel-based clustering algorithms is highly sensitive to the choice of the kernel similarity function. Ad hoc approaches, relying on prior domain knowledge, are currently employed to choose the kernel function, and it is difficult to determine the appropriate kernel similarity function for the given data set.In this thesis, we develop scalable approximate kernel-based clustering algorithms using random sampling and matrix approximation techniques. They can cluster big data sets containing billions of high-dimensional points not only as efficiently as linear clustering algorithms but also as accurately as classical kernel-based clustering algorithms.Our first contribution is based on the premise that the similarity matrices corresponding to big data sets can usually be well-approximated by low-rank matrices built from a subset of the data. We develop an approximate kernel-based clustering algorithm, which uses a low-rank approximate kernel matrix, constructed from a uniformly sampled small subset of the data, to perform clustering. We show that the proposed algorithm has linear running time complexity and low memory requirements, and also achieves high cluster quality, when provided with sufficient number of data samples. We also demonstrate that the proposed algorithm can be easily parallelized to handle distributed data sets. We then employ non-linear random feature maps to approximate the kernel similarity function, and design clustering algorithms which enhance the efficiency of kernel-based clustering, as well as label assignment for previously unseen data points. Our next contribution is an online kernel-based clustering algorithm that can cluster potentially unbounded stream data in real-time. It intelligently samples the data stream and finds the cluster labels using these sampled points. The proposed scheme is more effective than the current kernel-based and linear stream clustering techniques, both in terms of efficiency and cluster quality. We finally address the issues of high dimensionality and scalability to data sets containing a large number of clusters. Under the assumption that the kernel matrix is sparse when the number of clusters is large, we modify the above online kernel-based clustering scheme to perform clustering in a low-dimensional space spanned by the top eigenvectors of the sparse kernel matrix. The combination of sampling and sparsity further reduces the running time and memory complexity. The proposed clustering algorithms can be applied in a number of real-world applications. We demonstrate the efficacy of our algorithms using several large benchmark text and image data sets. For instance, the proposed batch kernel clustering algorithms were used to cluster large image data sets (e.g. Tiny) containing up to 80 million images. The proposed stream kernel clustering algorithm was used to cluster over a billion tweets from Twitter, for hashtag recommendation.
Show less

Title: Divide and Conquer : packet Classification by Smart Division
Creator: Daly, James Edward
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Packet classifiers form the backbone of many networking and security devices. Most packet classifiers are defined by a list of rules that each match a subset of all packets. As new threats and vulnerabilities emerge, these rule lists are getting larger and thus taking longer to search. However, networks have very strict time constraints and delays classifying a packet at one stage can cascade and cause delays and congestion throughout the network. Additionally, with the advent of software...
Show morePacket classifiers form the backbone of many networking and security devices. Most packet classifiers are defined by a list of rules that each match a subset of all packets. As new threats and vulnerabilities emerge, these rule lists are getting larger and thus taking longer to search. However, networks have very strict time constraints and delays classifying a packet at one stage can cascade and cause delays and congestion throughout the network. Additionally, with the advent of software-defined networks, these rule lists are also constantly changing. Packet classifiers thus must support both fast classification time and fast updates.We present four methods to improve packet classification. Each method uses smart division to divide the problem into simpler subproblems that are more easily solved. Diplomat uses dimensional reduction to create a smaller rule list by dividing the problem into several lower dimensional problems and then combines them with as few rules as possible. ByteCuts uses rule list separation to partition the rule list into a small number of trees; this minimizes the rule replication that other tree-based methods such as HyperCuts and HyperSplit require. PartitionSort uses rule list separation to partition the rule list into parts that are sortable; each part can then be binary searched. Finally, TupleMerge uses rule list separation to partition the rule list into parts that are hashable; it requires fewer hash tables than Tuple Space Search which reduces search times.
Show less

Title: Novel Learning Algorithms for Mining Geospatial Data
Creator: Yuan, Shuai
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Geospatial data have a wide range of applicability in many disciplines, including environmental science, urban planning, healthcare, and public administration. The proliferation of such data in recent years have presented opportunities to develop novel data mining algorithms for modeling and extracting useful patterns from the data. However, there are many practical issues remain that must be addressed before the algorithms can be successfully applied to real-world problems. First, the...
Show moreGeospatial data have a wide range of applicability in many disciplines, including environmental science, urban planning, healthcare, and public administration. The proliferation of such data in recent years have presented opportunities to develop novel data mining algorithms for modeling and extracting useful patterns from the data. However, there are many practical issues remain that must be addressed before the algorithms can be successfully applied to real-world problems. First, the algorithms must be able to incorporate spatial relationships and other domain constraints defined by the problem. Second, the algorithms must be able to handle missing values, which are common in many geospatial data sets. In particular, the models constructed by the algorithms may need to be extrapolated to locations with no observation data. Another challenge is to adequately capture the nonlinear relationship between the predictor and response variables of the geospatial data. Accurate modeling of such relationship is not only a challenge, it is also computationally expensive. Finally, the variables may interact at different spatial scales, making it necessary to develop models that can handle multi-scale relationships present in the geospatial data. This thesis presents the novel algorithms I have developed to overcome the practical challenges of applying data mining to geospatial datasets. Specifically, the algorithms will be applied to both supervised and unsupervised learning problems such as cluster analysis and spatial prediction. While the algorithms are mostly evaluated on datasets from the ecology domain, they are generally applicable to other geospatial datasets with similar characteristics. First, a spatially constrained spectral clustering algorithm is developed for geospatial data. The algorithm provides a flexible way to incorporate spatial constraints into the spectral clustering formulation in order to create regions that are spatially contiguous and homogeneous. It can also be extended to a hierarchical clustering setting, enabling the creation of fine-scale regions that are nested wholly within broader-scale regions. Experimental results suggest that the nested regions created using the proposed approach are more balanced in terms of their sizes compared to the regions found using traditional hierarchical clustering methods. Second, a supervised hash-based feature learning algorithm is proposed for modeling nonlinear relationships in incomplete geospatial data. The proposed algorithm can simultaneously infer missing values while learning a small set of discriminative, nonlinear features of the geospatial data. The efficacy of the algorithm is demonstrated using synthetic and real-world datasets. Empirical results show that the algorithm is more effective than the standard approach of imputing the missing values before applying nonlinear feature learning in more than 75% of the datasets evaluated in the study. Third, a multi-task learning framework is developed for modeling multiple response variables in geospatial data. Instead of training the local models independently for each response variable at each location, the framework simultaneously fits the local models for all response variables by optimizing a joint objective function with trace-norm regularization. The framework also leverages the spatial autocorrelation between locations as well as the inherent correlation between response variables to improve prediction accuracy. Finally, a multi-level, multi-task learning framework is proposed to effectively train predictive models from nested geospatial data containing predictor variables measured at multiple spatial scales. The framework enables distinct models to be developed for each coarse- scale region using both its fine-level and coarse-level features. It also allows information to be shared among the models through a common set of latent features. Empirical results show that such information sharing helps to create more robust models especially for regions with limited or no training data. Another advantage of using the multi-level, multi-task learning framework is that it can automatically identify potential cross-scale interactions between the regional and local variables.
Show less

Title: Improving Indoor Positioning Via Mobile Sensing
Creator: Qiu, Chen
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Accurate indoor position and movement information of devices enables numerous opportunities for location based services. Services such as guiding users through buildings, highlighting nearby services within shopping malls, or tracking the number of steps taken are some of the opportunities available when accurate positioning information is computed by devices. GPS provides accurate localization results in an outdoor environment, such as navigation information for vehicles. Unfortunately, GPS...
Show moreAccurate indoor position and movement information of devices enables numerous opportunities for location based services. Services such as guiding users through buildings, highlighting nearby services within shopping malls, or tracking the number of steps taken are some of the opportunities available when accurate positioning information is computed by devices. GPS provides accurate localization results in an outdoor environment, such as navigation information for vehicles. Unfortunately, GPS cannot be applied indoors pervasively due to the various interferences.Indoor localization has been a challenging and significant topic in recent decades. Although extensive research has been dedicated to this field, accurate indoor location information remains a challenge without the incorporation of expensive devices or sophisticated infrastructures within buildings. We explored one practical approach for indoor map construction and four representative resolutions for indoor positioning.Considering most indoor localization approaches are based upon indoor maps, we develop techniques to construct indoor maps. Since indoor maps might be dynamic and updated regularly, we present iFrame, a dynamic approach that uses mobile sensing techniques for constructing 2-dimensional indoor maps. We abstract the unknown map as a matrix and use mobile devices that incorporate three mobile sensing technologies - accelerometers to support dead reckoning, Bluetooth RSSI detection, and WiFi RSSI detection. The layouts of rooms and hallways can be constructed automatically within 5-10 minutes.Based on the indoor map, we propose four indoor localization approaches by leveraging mobile sensing techniques. First, although GPS can not help indoor localization directly, we propose iLoom, which adopts a user's motion behaviors built by GPS information to enhance indoor localization. iLoom leverages an Acceleration Range Box to improve a user's acceleration value used for computing dead reckoning. By transfer learning the information from users' motion behaviors to the Acceleration Range Box, iLoom improves the Acceleration Range Box to achieve more accurate indoor positioning results. Second, we introduce CRISP - a prototype that leverages opportunities of the interaction of multiple smartphones to enhance indoor positioning. When mobile devices cooperate and share position information iteratively, the localization accuracies of mobile devices increases gradually. In addition, based upon the obtained location information, CRISP provide a pedometer that can avoid the accumulative errors caused by accelerometers. Third, we present SilentWhistle, a mobile prototype that incorporates acoustic information and motion traces on smartphones to locate users. When users encounter each other or related beacons, by measuring the relation between sound strength and distance, the initial location information obtained by dead reckoning can be enhanced by triangulations transferred from sound strength. Centralized and distributed models of SilentWhistle can avoid the incorrect location messages spreading based on the fault tolerance property. Finally, by employing mobile robots in indoor scenarios, we propose AirLoc to improve the indoor positioning accuracies on smartphones. When a robot is near a smartphone, the robot sends accurate location information to users' smartphones via Bluetooth. In AirLoc, we design dynamic programming algorithms to generate the optimal serving routes for a single robot. Then, we extend the single robot model to multi-robot model. In our simulation, the multi-robots are organized by an unbalanced tree and serve areas by the Distance/Density First Algorithm.
Show less

Title: Scalable Phylogenetic Analysis and Functional Interpretation of Genomes with Complex Evolutionary Histories
Creator: Hejase, Hussein El Abbass
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Phylogenomics involves the inference of a genome-scale phylogeny. A phylogeny is typically inferred using sequences from multiple loci across a set of genomes of multiple organisms by reconstructing gene trees and then reconciling them into a species phylogeny. Many studies have shown that evolutionary processes such as gene flow, incomplete lineage sorting, recombination, selection, gene duplication and loss have shaped our genomes and played a major role in the evolution of a diverse array...
Show morePhylogenomics involves the inference of a genome-scale phylogeny. A phylogeny is typically inferred using sequences from multiple loci across a set of genomes of multiple organisms by reconstructing gene trees and then reconciling them into a species phylogeny. Many studies have shown that evolutionary processes such as gene flow, incomplete lineage sorting, recombination, selection, gene duplication and loss have shaped our genomes and played a major role in the evolution of a diverse array of metazoans, including humans and ancient hominins, mice, bacteria, and butterflies. The aforementioned evolutionary processes are primary causes of gene tree discordance, which introduce different loci in a genome that exhibit local genealogical variation (i.e. gene trees differing from each other and the species phylogeny in terms of topology and/or branch length).In this dissertation, we develop a method for fast and accurate inference of phylogenetic networks using large-scale sequence data. The advent of high-throughput sequencing technologies has brought about two main scalability challenges: (1) dataset size in terms of the number of taxa and (2) the evolutionary divergence of the taxa in a study. We explore the impact of both dimensions of scale on phylogenetic network inference and then introduce a new phylogenetic divide-and-conquer method which we call FastNet. We show using synthetic and empirical data spanning a range of evolutionary scenarios that FastNet outperforms the state-of-the-art in terms of accuracy and computational requirements.Furthermore, we develop methods that use better and more accurate phylogenies to functionally interpret genomes. One way to study and understand the biological function of genomes is through association mapping, which pinpoints statistical associations between genotypic and phenotypic characters while modeling the relatedness between samples to avoid generating spurious inferences. Many methods have been proposed to perform association mapping while accounting for sample relatedness. However, the state of the art predominantly utilizes the simplifying assumption that sample relatedness is effectively fixed across the genome. Recent studies have shown that sample relatedness can vary greatly across different loci within a genome where gene trees could differ from each other and the species phylogeny. Thus, there is an imminent need for methods to account for local genealogical variation in functional genomic analyses. We address this methodological gap by introducing two methods, Coal-Map and Coal-Miner, which account for sample relatedness locally within loci and globally across the entire genome. We show through simulated and empirical datasets that these newly introduced methods offer comparable or typically better statistical power and type I error control compared to the state-of-the-art.
Show less

Title: Balancing Convergence and Diversity in Evolutionary Single, Multi and Many Objectives
Creator: Seada, Haitham
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Single objective optimization targets only one solution, that is usually the global optimum.On the other hand, the goal of multiobjective optimization is to represent the wholeset of trade-off Pareto-optimal solutions to a problem. For over thirty years, researchershave been developing Evolutionary Multiobjective Optimization (EMO) algorithms forsolving multiobjective optimization problems. Unfortunately, each of these algorithmswere found to work well on a specific range of objective...
Show moreSingle objective optimization targets only one solution, that is usually the global optimum.On the other hand, the goal of multiobjective optimization is to represent the wholeset of trade-off Pareto-optimal solutions to a problem. For over thirty years, researchershave been developing Evolutionary Multiobjective Optimization (EMO) algorithms forsolving multiobjective optimization problems. Unfortunately, each of these algorithmswere found to work well on a specific range of objective dimensionality, i.e. number ofobjectives. Most researchers overlooked the idea of creating a cross-dimensional algorithmthat can adapt its operation from one level of objective dimensionality to the other.One important aspect of creating such algorithm is achieving a careful balance betweenconvergence and diversity. Researchers proposed several techniques aiming at dividingcomputational resources uniformly between these two goals. However, in many situations,only either of them is difficult to attain. Also for a new problem, it is difficult totell beforehand if it will be challenging in terms of convergence, diversity or both. In thisstudy, we propose several extensions to a state-of-the-art evolutionary many-objectiveoptimization algorithm – NSGA-III. Our extensions collectively aim at (i) creating a unifiedoptimization algorithm that dynamically adapts itself to single, multi- and manyobjectives, and (ii) enabling this algorithm to automatically focus on either convergence,diversity or both, according to the problem being considered. Our approach augmentsthe already existing algorithm with a niching-based selection operator. It also utilizes therecently proposed Karush Kuhn Tucker Proximity Measure to identify ill-converged solutions,and finally, uses several combinations of point-to-point single objective local searchprocedures to remedy these solutions and enhance both convergence and diversity. Ourextensions are shown to produce better results than state-of-the-art algorithms over a setof single, multi- and many-objective problems.
Show less

Title: Evolution of cooperation in the light of information theory
Creator: Mirmomeni, Masoud
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Cooperation is ubiquitous in different biological levels and is necessary for evolution to shape the life and create new forms of organization. Genes cooperate in controlling cells; cells efficiently collaborate together to produce cohesive multi-cellular organisms; members of insect colonies and animal clans cooperate in protecting the colony and providing food. Cooperation means that members of a group bear a cost, c, for another individuals to earn a benefit, b. While cooperators of the...
Show moreCooperation is ubiquitous in different biological levels and is necessary for evolution to shape the life and create new forms of organization. Genes cooperate in controlling cells; cells efficiently collaborate together to produce cohesive multi-cellular organisms; members of insect colonies and animal clans cooperate in protecting the colony and providing food. Cooperation means that members of a group bear a cost, c, for another individuals to earn a benefit, b. While cooperators of the group help others by paying a cost, defectors receive the benefits of this altruistic behavior without providing any service in return to the group. To address this dilemma, here we use a game theoretic approach to model and study evolutionary dynamics that can lead to unselfish behavior. Evolutionary game theory is an approach to study frequency-dependent systems. In evolutionary games the fitness of individuals depends on the relative abundance of the various types in the population. We explore different strategies and different games such as iterated games between players with conditional strategies, multi player games, and iterated games between fully stochastic strategies in noisy environments to find the necessity conditions that lead to cooperation. Interestingly, we see that in all of these games communication is the key factor for maintaining cooperation among selfish individuals. We show that communication and information exchange is necessary for the emergence of costly altruism, and to maintain cooperation in the group there should be minimum rate of communication between individuals. We quantify this minimum amount of information exchange, which is necessary for individuals to exhibit cooperative behavior, by defining a noisy communication channel between them in iterated stochastic games and measuring the communication rate (in bits) during the break down of cooperation.
Show less

MSU Libraries

Digital Repository

Pages

Pages

MSU Libraries

Digital Repository

You are here

Search results

Pages

Pages