Search results

Title: Some contributions to semi-supervised learning
Creator: Mallapragada, Paven Kumar
Date: 2010
Collection: Electronic Theses & Dissertations

Title: Semi=supervised learning with side information : graph-based approaches
Creator: Liu, Yi
Date: 2007
Collection: Electronic Theses & Dissertations

Title: Network Reachability : Quantification, Verification, Troubleshooing, and Optimization
Creator: Khakpour, Amir Reza
Date: 2011
Collection: Electronic Theses & Dissertations
Description: Quantifying, verifying, troubleshooting, and optimizing the network reachability is essential for network management and network security monitoring as well as various aspects of network auditing, maintenance, and design. Although attempts to model network reachability have been made, feasible solutions for computing, maintaining and optimally designing network reachability have remained unknown. Network reachability control is very critical because, on one hand, reachability errors can cause...
Show moreQuantifying, verifying, troubleshooting, and optimizing the network reachability is essential for network management and network security monitoring as well as various aspects of network auditing, maintenance, and design. Although attempts to model network reachability have been made, feasible solutions for computing, maintaining and optimally designing network reachability have remained unknown. Network reachability control is very critical because, on one hand, reachability errors can cause network security breaches or service outages, leading to millions of dollars of revenue loss for an enterprise network. On the other hand, network operators suffer from lack of tools that thoroughly examine network access control configurations and audit them to avoid such errors. Besides, finding reachability errors is by no means easy. The access control rules, by which network reachability is restricted, are often very complex and manually troubleshooting them is extremely difficult. Hence, having a tool that finds the reachability errors and fix them automatically can be very useful. Furthermore, flawed network reachability design and deployment can degrade the network performance significantly. Thus, it is crucial to have a tool that designs the network configurations such that they have the least performance impact on the enterprise network.In this dissertation, we first present a network reachability model that considers connectionless and connection-oriented transport protocols, stateless and stateful routers/firewalls, static and dynamic NAT, PAT, IP tunneling, etc. We then propose a suite of algorithms for quantifying reachability based on network configurations (mainly access control lists (ACLs)) as well as solutions for querying network reachability. We further extend our algorithms and data structures for detecting reachability errors, pinpointing faulty access control lists, and fixing them automatically and efficiently. Finally, we propose algorithms to place rules on network devices optimally so that they satisfy the networks central access policies. To this end, we define correctness and performance criteria for rule placement and in turn propose cost-based algorithms with adjustable parameters (for the network operators) to place rules such that the correctness and performance criteria are satisfied.We implemented the algorithms in our network reachability tool called Quarnet and conducted experiments on a university network. Experimental results show that the offline computation of reachability matrices takes a few hours and the online processing of a reachability query takes 75 milliseconds on average. We also examine our reachability error detection and correction algorithms on a few real-life networks to examine their performance and ensure that Quarnet is efficient enough to be practically useful. The results indicate that we can find reachability errors in order of minutes and fix them in order of seconds depending on the size of network and number of ACLs. Finally, we added the rule placement suite of algorithms to Quarnet, which can design a network ACL in based on the network central policies in order of tens of minutes for an enterprise network. We compare it with Purdue ACL placement, the state-of-the-art access policy design technique, and explain its pros and cons.
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: A robust method for addressing pupil dilation in iris recognition
Creator: Pasula, Raghunandan
Date: 2016
Collection: Electronic Theses & Dissertations
Description: The rich texture of the iris is being used as a biometric cue in several human recognition systems. Iris recognition systems are fairly robust to small changes in illumination and pose. However there are a number of factors that still adversely affect the performance of an iris matcher. These include occlusion, large deviation in gaze, low image resolution, long acquisition distance and pupil dilation. Large differences in pupil size increases thedissimilarity between iris images of the same...
Show moreThe rich texture of the iris is being used as a biometric cue in several human recognition systems. Iris recognition systems are fairly robust to small changes in illumination and pose. However there are a number of factors that still adversely affect the performance of an iris matcher. These include occlusion, large deviation in gaze, low image resolution, long acquisition distance and pupil dilation. Large differences in pupil size increases thedissimilarity between iris images of the same eye.In this work, the degradation of match scores due to pupil dilation is systematically studied using Hamming Distance histograms. A novel rule-based fusion technique based on the aforementioned study is proposed to alleviate the effect of pupil dilation. The proposed method computes a new distance score at every pixel location based on the similarities between IrisCode bits that were generated using Gabor Filters at different resolutions.Experiments show that the proposed method increases the genuine accept rate from 76% to 90% at 0.0001% false accept rate when comparing images with large differences in pupil sizes in the WVU-PLR dataset. The proposed method is also shown to improve the performance of iris recognition on other non-ideal iris datasets. In summary, the use of multi-resolution Gabor Filters in conjunction with a rule-based integration of decisions at the pixel (bit) level is observed to improve the resilience of iris recognition to differences in pupil size.
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: 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: Robust Global Motion Compensation and Its Applications
Creator: Safdarnejad, Seyed Morteza
Date: 2017
Collection: Electronic Theses & Dissertations
Description: This thesis presents algorithms for robust global motion compensation (GMC). GMC algorithms are used to remove camera motion and transform the video such that in the resultant video, the background appears static and the only motion rises from foreground objects. Many computer vision algorithms are tailored for static camera, and using GMC, it is possible to apply these algorithms on videos from moving cameras. For instance, motion-based video analysis is strongly affected by camera motion....
Show moreThis thesis presents algorithms for robust global motion compensation (GMC). GMC algorithms are used to remove camera motion and transform the video such that in the resultant video, the background appears static and the only motion rises from foreground objects. Many computer vision algorithms are tailored for static camera, and using GMC, it is possible to apply these algorithms on videos from moving cameras. For instance, motion-based video analysis is strongly affected by camera motion. If camera motion is not compensated, it interferes with the motion of interest, such as motion of human, and renders the analysis problem to be more challenging.Generally, in sequential schemes, GMC estimates the homography transformation between two consecutive frames by matching keypoints on the frames, and maps the second frame to a global coordinate. Then, by accumulating these transformations, a composite transformation is calculated which maps each frame to the global coordinate. However, existing GMC algorithms are sensitive to existence of foreground motion and fail easily in the case of considerable foreground motion or ambiguous and low texture background.To address the challenges in GMC, first, we propose a Robust Global Motion Compensation (RGMC) algorithm which explicitly suppresses the foreground effect and utilizes a comprehensive probabilistic verification model to find the best mappings between consecutive frames. Despite the robustness offered by RGMC, we further identified the problem of temporal drift of the estimation, due to accumulation of errors in estimation of mappings between consecutive coordinates. Furthermore, to address the issues of sequential GMC, we propose a Temporally Robust Global Motion Compensation (TRGMC) algorithm which by joint alignment of input frames, estimates accurate and temporally consistent transformations to the global coordinates. Joint alignment not only leads to the temporal consistency of GMC, but also improves GMC stability by using redundancy of the information.Many applications can benefit from a reliable and accurate GMC algorithm. We first briefly look into these applications. Then, among the many applications, we further investigate the problem of sequence alignment, and propose an alignment algorithm for non-overlapping sequences, enabled by performance of TRGMC. Given the transformation to a global coordinate, offered by TRGMC, and capability of background reconstruction using TRGMC result, we are able to align sequences even if the spatial overlap between the sequences is minimal or nonexistent. To this end, we first spatially align the sequences such that extrapolated backgrounds are aligned well and trajectory of moving objects are spatially smooth in the global coordinate. Next, we temporally align the sequences based on the smoothness of spatio-temporal trajectory of moving objects across field of view of different cameras.
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: TRADE-OFFS AMONG DATA SECURITY, USABILITY AND COMPLEXITY IN MOBILE CLOUD COMPUTING
Creator: Zhou, Kai
Date: 2018
Collection: Electronic Theses & Dissertations
Description: The proliferation of mobile cloud computing changes the way that data is utilized. Huge volume of data is collected at the network edge, transmitted through the network, gathered in the cloud, and utilized by various end-users. Data security, usability, and complexity are among the most important design issues in mobile computing environment. Trade- offs generally exist among these issues. While data encryption is a primary mechanism to ensure data security, it will inevitably introduce some...
Show moreThe proliferation of mobile cloud computing changes the way that data is utilized. Huge volume of data is collected at the network edge, transmitted through the network, gathered in the cloud, and utilized by various end-users. Data security, usability, and complexity are among the most important design issues in mobile computing environment. Trade- offs generally exist among these issues. While data encryption is a primary mechanism to ensure data security, it will inevitably introduce some computational overhead to the data owners. Also, data encryption will reduce data usability since typically it is hard to conduct computations over encrypted data.In this thesis, we focus on designing secure, efficient and versatile protocols that can achieve trade-offs among data security, data usability, and computational complexity, featuring the mobile cloud computing environment. In particular, we explore the trade-offs from two aspects. First, we design secure computation outsourcing schemes for a wide variety of computational problems such as general scientific computation and cryptographic computation, trying to alleviate the computational overhead at the user side while preserving the security of the outsourced data. Our proposed scheme is cost-aware in that it provides different levels of security protection for the outsourced problem with different computational overhead. Second, we design a specific encryption scheme that enables certain computations to be conducted directly over encrypted data. In this way, data users can directly utilize encrypted data to meet the demands of various applications without compromising datasecurity. More specifically, our proposed encryption scheme encrypts two vectors in such a manner that the inner product of the vectors can be evaluated and compared to a pre-defined threshold. We show that an encryption scheme can be utilized as an essential building block to construct various privacy-preserving applications such as an online biometric authentication system. Our proposed schemes are highly efficient and suitable for resource-constrained devices in the mobile cloud computing environment to greatly expand the computational capacity and/or extend battery life.
Show less

Title: An Analysis of Fitness in Long-Term Asexual Evolution Experiments
Creator: Wiser, Michael J.
Date: 2015
Collection: Electronic Theses & Dissertations
Description: Evolution is the central unifying concept of modern biology. Yet it can be hard to study in natural system, as it unfolds across generations. Experimental evolution allows us to ask questions about the process of evolution itself: How repeatable is the evolutionary process? How predictable is it? How general are the results? To address these questions, my collaborators and I carried out experiments both within the Long-Term Evolution Experiment (LTEE) in the bacteria Escherichia coli, and the...
Show moreEvolution is the central unifying concept of modern biology. Yet it can be hard to study in natural system, as it unfolds across generations. Experimental evolution allows us to ask questions about the process of evolution itself: How repeatable is the evolutionary process? How predictable is it? How general are the results? To address these questions, my collaborators and I carried out experiments both within the Long-Term Evolution Experiment (LTEE) in the bacteria Escherichia coli, and the digital evolution software platform Avida. In Chapter 1, I focused on methods. Previous research in the LTEE has relied on one particular way of measuring fitness, which we know becomes less precise as fitness differentials increase. I therefore decided to test whether two alternate ways of measuring fitness would improve precision, using one focal population. I found that all three methods yielded similar results in both fitness and coefficient of variation, and thus we should retain the traditional method.In Chapter 2, I turned to measuring fitness in each of the populations. Previous work had considered fitness to change as a hyperbola. A hyperbolic function is bounded, and predicts that fitness will asymptotically approach a defined upper bound; however, we knew that fitness in these populations routinely exceeded the asymptotic limit calculated from a hyperbola fit to the earlier data. I instead used to a power law, a mathematical function that does not have an upper bound. I found that this function substantially better describes fitness in this system, both among the whole set of populations, and in most of the individual populations. I also found that the power law models fit on just early subsets of the data accurately predict fitness far into the future. This implies that populations, even after 50,000 generations of evolution in consistent environment, are so far from the tops of fitness peaks that we cannot detect evidence of those peaks.In Chapter 3, I examined to how variance in fitness changes over long time scales. The among-population variance over time provides us information about the adaptive landscape on which the populations have been evolving. I found that among-population variance remains significant. Further, competitions between evolved pairs of populations reveal additional details about fitness trajectories than can be seen from competitions against the ancestor. These results demonstrate that our populations have been evolving on a complex adaptive landscape.In Chapter 4, I examined whether the patterns found in Chapter 2 apply to a very different evolutionary system, Avida. This system incorporates many similar evolutionary pressures as the LTEE, but without the details of cellular biology that underlie nearly all organic life. I find that in both the most complex and simplest environments in Avida, fitness also follows the same power law dynamics as seen in the LTEE. This implies that power law dynamics may be a general feature of evolving systems, and not dependent on the specific details of the system being studied.
Show less

Title: Multi-Task Learning and Its Application to Geospatio-Temporal Data
Creator: Xu, Jianpeng
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Multi-task learning (MTL) is a data mining and machine learning approach for modeling multiple prediction tasks simultaneously by exploiting the relatedness among the tasks. MTL has been successfully applied to various domains, including computer vision, healthcare, genomics, recommender systems, and natural language processing. The goals of this thesis are: (1) to investigate the feasibility of applying MTL to geospatio-temporal prediction problems, particularly those encountered in the...
Show moreMulti-task learning (MTL) is a data mining and machine learning approach for modeling multiple prediction tasks simultaneously by exploiting the relatedness among the tasks. MTL has been successfully applied to various domains, including computer vision, healthcare, genomics, recommender systems, and natural language processing. The goals of this thesis are: (1) to investigate the feasibility of applying MTL to geospatio-temporal prediction problems, particularly those encountered in the climate and environmental science domains and (2) to develop novel MTL frameworks that address the challenges of building effective predictive models from geospatio-temporal data.The first contribution of this thesis is to develop an online temporal MTL framework called ORION for ensemble forecasting problems. Ensemble forecasting uses a numerical method to simulate the evolution of nonlinear dynamic systems, such as climate and hydrological systems. ORION aims to effectively aggregate the forecasts generated by different ensemble members for a future time window, where each forecast is obtained by perturbing the starting condition of the computer model or using a different model representation. ORION considers the prediction for each time point in the forecast window as a distinct prediction task, where the task relatedness is achieved by imposing temporal smoothness and mean regularization constraints. A novel, online update with restart strategy is proposed to handle missing observations in the training data. ORION can also be optimized for different objectives, such as ε -insensitive and quantile loss functions.The second contribution of this thesis is to propose a MTL framework named GSpartan that can perform inferences at multiple locations simultaneously while allowing the local models for different locations to be jointly trained. GSpartan assumes that the local models share a common, low-rank representation and employs a graph Laplacian regularization to enforce constraints due to the inherent spatial autocorrelation of the data. Sparsity and non-negativity constraints are also incorporated into the formulation to ensure interpretability of the models.GSpartan is a MTL framework that considers only the spatial autocorrelation of the data. It is also a batch learning algorithm, which makes it difficult to scale up to global-scale data. To address these limitations, a new framework called WISDOM is proposed, which can incorporate the task relatedness across both space and time. WISDOM encodes the geospatio-temporal data as a tensor and performs supervised tensor decomposition to identify the latent factors that capture the inherent spatial and temporal variabilities of the data as well as the relationship between the predictor and target variables. The framework is unique in that it trains distinct spatial and temporal prediction models from the latent factors of the decomposed tensor and aggregates the outputs of these models to obtain the final prediction. WISDOM also employs an incremental learning algorithm that can systematically update the models when training examples are available for a new time period or for a new location.Finally, the geospatio-temporal data for many scientific applications are often available at varying spatial scales. For example, they can be generated by computer models simulated at different grid resolutions (e.g., the global and regional models used in climate modeling). A simple way to handle the predictor variables generated from the multi-scale data is to concatenate them into a single feature vector and train WISDOM using the concatenated vectors. However, this strategy may not be effective as it ignores the inherent dependencies between variables at different scales. To overcome this limitation, this thesis presents an extension of WISDOM called MUSCAT for handling multi-scale geospatio-temporal data. MUSCAT considers the consistency of the latent factors extracted from the spatio-temporal tensors at different scales while inheriting the benefits of WISDOM. Given the massive size of the multi-scale spatio-temporal tensors, a novel, supervised, incremental multi-tensor decomposition algorithm is develop to efficiently learn the model parameters.
Show less

Title: Hybrid Structural and Behavioral Diversity Techniques for Effective Genetic Programming
Creator: Burks, Armand Rashad
Date: 2017
Collection: Electronic Theses & Dissertations
Description: Sustaining the diversity of evolving populations is a fundamental issue in genetic programming. We describe a novel measure of structural diversity for tree-based genetic programming, and we demonstrate its utility compared to other diversity techniques. We demonstrate our technique on the real-world application of tuberculosis screening from X-ray images. We then introduce a new paradigm of genetic programming that involves simultaneously maintaining structural and behavioral diversity in...
Show moreSustaining the diversity of evolving populations is a fundamental issue in genetic programming. We describe a novel measure of structural diversity for tree-based genetic programming, and we demonstrate its utility compared to other diversity techniques. We demonstrate our technique on the real-world application of tuberculosis screening from X-ray images. We then introduce a new paradigm of genetic programming that involves simultaneously maintaining structural and behavioral diversity in order to further improve the efficiency of genetic programming.Our results show that simultaneously promoting structural and behavioral diversity improves genetic programming by leveraging the benefits of both aspects of diversity while overcoming the shortcomings of either technique in isolation. The hybridization increases the behavioral diversity of our structural diversity technique, and increases the structural diversity of the behavioral diversity techniques. This increased diversity leads to performance gains compared to either technique in isolation.We found that in many cases, our structural diversity technique provides significant performance improvement compared to other state-of-the-art techniques. Our results from the experiments comparing the hybrid techniques indicate that the largest performance gain was typically attributed to our structural diversity technique. The incorporation of the behavioral diversity techniques provide additional improvement in many cases.
Show less

Title: Example-Based Parameterization of Linear Blend Skinning for Skinning Decomposition (EP-LBS
Creator: Hopkins, Kayra M.
Date: 2017
Collection: Electronic Theses & Dissertations
Description: This thesis presents Example-based Parameterization of Linear Blend Skinning for Skinning Decomposition (EP-LBS), a unified and robust method for using example data to simplify and improve the development and parameterization of high quality 3D models for animation. Animation and three-dimensional (3D) computer graphics have quickly become a popular medium for education, entertainment and scientific simulation. In addition to film, gaming and research applications, recent advancements in...
Show moreThis thesis presents Example-based Parameterization of Linear Blend Skinning for Skinning Decomposition (EP-LBS), a unified and robust method for using example data to simplify and improve the development and parameterization of high quality 3D models for animation. Animation and three-dimensional (3D) computer graphics have quickly become a popular medium for education, entertainment and scientific simulation. In addition to film, gaming and research applications, recent advancements in augmented reality (AR) and virtual reality (VR) are driving additional demand for 3D content. However, the success of graphics in these arenas depends greatly on the efficiency of model creation and the realism of the animation or 3D image.A common method for figure animation is skeletal animation using linear blend skinning (LBS). In this method, vertices are deformed based on a weighted sum of displacements due to an embedded skeleton. This research addresses the problem that LBS animation parameter computation, including determining the rig (the skeletal structure), identifying influence bones (which bones influence which vertices), and assigning skinning weights (amounts of influence a bone has on a vertex), is a tedious process that is difficult to get right. Even the most skilled animators must work tirelessly to design an effective character model and often find themselves repeatedly correcting flaws in the parameterization. Significant research, including the use of example-data, has focused on simplifying and automating individual components of the LBS deformation process and increasing the quality of resulting animations. However, constraints on LBS animation parameters makes automated analytic computation of the values equally as challenging as traditional 3D animation methods. Skinning decomposition is one such method of computing LBS animation LBS parameters from example data. Skinning decomposition challenges include constraint adherence and computationally efficient determination of LBS parameters.The EP-LBS method presented in this thesis utilizes example data as input to a least-squares non-linear optimization process. Given a model as a set of example poses captured from scan data or manually created, EP-LBS institutes a single optimization equation that allows for simultaneous computation of all animation parameters for the model. An iterative clustering methodology is used to construct an initial parameterization estimate for this model, which is then subjected to non-linear optimization to improve the fitting to the example data. Simultaneous optimization of weights and joint transformations is complicated by a wide range of differing constraints and parameter interdependencies. To address interdependent and conflicting constraints, parameter mapping solutions are presented that map the constraints to an alternative domain more suitable for nonlinear minimization. The presented research is a comprehensive, data-driven solution for automatically determining skeletal structure, influence bones and skinning weights from a set of example data. Results are presented for a range of models that demonstrate the effectiveness of the method.
Show less

Title: Distance Preserving Graphs
Creator: Zahedi, Emad
Date: 2017
Collection: Electronic Theses & Dissertations
Description: The computational complexity of exploring distance properties of large graphs such as real-world social networks which consist of millions of nodes is extremely expensive. Recomputing distances in subgraphs of the original graph will add to the cost. One way to avoid this is to use subgraphs where the distance between any pair of vertices is the same as in the original graph. Such a subgraph is called {\em isometric}. A connected graph is {\em distance preserving}, for which we use the...
Show moreThe computational complexity of exploring distance properties of large graphs such as real-world social networks which consist of millions of nodes is extremely expensive. Recomputing distances in subgraphs of the original graph will add to the cost. One way to avoid this is to use subgraphs where the distance between any pair of vertices is the same as in the original graph. Such a subgraph is called {\em isometric}. A connected graph is {\em distance preserving}, for which we use the abbreviation dp, if it has an isometric subgraph of every order. In this framework we study dp graphs from both the structural and algorithmic perspectives. First, we study the structural nature of dp graphs. This involves classifying graphs based on the dp property and the relation between dp graphs to other graph classes. Second, we study the recognition problem of dp graphs. We intend to develop efficient algorithms for finding isometric subgraphs as well as deciding whether a graph is dp or not.
Show less

Title: Capturing Bluetooth Traffic in the Wild : Practical Systems and Privacy Implications
Creator: ALBAZRQAOE, WAHHAB
Date: 2018
Collection: Electronic Theses & Dissertations
Description: Bluetooth wireless technology is today present in billions of smartphones, mobile devices, and portable electronics. With the prevalence of personal Bluetooth devices, a practical Bluetooth traffic sniffer is of increasing interest due to the following. First, it has been reported that a traffic sniffer is an essential, day-to-day tool for Bluetooth engineers and applications developers; and second, as the communication between Bluetooth devices is privacy-sensitive in nature, exploring the...
Show moreBluetooth wireless technology is today present in billions of smartphones, mobile devices, and portable electronics. With the prevalence of personal Bluetooth devices, a practical Bluetooth traffic sniffer is of increasing interest due to the following. First, it has been reported that a traffic sniffer is an essential, day-to-day tool for Bluetooth engineers and applications developers; and second, as the communication between Bluetooth devices is privacy-sensitive in nature, exploring the possibility of Bluetooth traffic sniffing in practical settings sheds lights into potential user privacy leakage. To date, sniffing Bluetooth traffic has been widely considered an extremely intricate task due to wideband spread spectrum of Bluetooth, pseudo-random frequency hopping adopted by Bluetooth at baseband, and the interference in the open 2.4 GHz band.This thesis addresses these challenges by introducing novel traffic sniffers that capture Bluetooth packets in practical environments. In particular, we present the following systems. (i) BlueEar, the first practical Bluetooth traffic sniffing system only using general, inexpensive wireless platforms. BlueEar features a novel dual-radio architecture where two inexpensive, Bluetooth-compliant radios coordinate with each other to eavesdrop on hopping subchannels in indiscoverable mode. Statistic models and lightweight machine learning tools are integrated to learn the adaptive hopping behavior of the target. Our results show that BlueEar maintains a packet capture rate higher than 90% consistently in dynamic settings. In addition, we discuss the implications of the BlueEar approach on Bluetooth LE sniffing and present a practical countermeasure that effectively reduces the packet capture rate of sniffer by 70%, which can be easily implemented on the Bluetooth master while requiring no modification to slave devices like keyboards and headsets.
Show less

MSU Libraries

Digital Repository

Pages

Pages

MSU Libraries

Digital Repository

You are here

Search results

Pages

Pages