Theory and Algorithms Commons^™

Core Determining Class And Inequality Selection, Ye Luo, Hai Wang

Research Collection School Of Computing and Information Systems

The relations between unobserved events and observed outcomes can be characterized by a bipartite graph. We propose an algorithm that explores the structure of the graph to construct the "exact Core Determining Class," i.e., the set of irredudant inequalities. We prove that in general the exact Core Determining Class does not depend on the probability measure of the outcomes but only on the structure of the graph. For more general linear inequalities selection problems, we propose a statistical procedure similar to the Dantzig Selector to select the truly informative constraints. We demonstrate performances of our procedures in Monte-Carlo experiments.

Stop Nuclear Smuggling Through Efficient Container Inspection, Xinrun Wang, Qingyu Guo, Bo An

Research Collection School Of Computing and Information Systems

Since 2003, the U.S. government has spent $850 million on the Megaport Initiative which aims at stopping the nuclear smuggling in international container shipping through advanced inspection facilities including Non-Intrusive Inspection (NII) and Mobile Radiation Detection and Identification System (MRDIS). Unfortunately, it remains a significant challenge to efficiently inspect more than 11.7 million containers imported to the U.S. due to the limited inspection resources. Moreover, existing work in container inspection neglects the sophisticated behavior of the smuggler who can surveil the inspector’s strategy and decide the optimal (sequential) smuggling plan. This paper is the first to tackle this challenging container …

Exploiting Anonymity And Homogeneity In Factored Dec-Mdps Through Pre-Computed Binomial Distributions, Rajiv Ranjan Kumar, Pradeep Varakantham

Research Collection School Of Computing and Information Systems

Recent work in decentralized stochastic planning for cooperative agents has focussed on exploiting omogeneity of agents and anonymity in interactions to solve problems with large numbers of agents. Due to a linear optimization formulation that computes joint policy and an objective that indirectly approximates joint expected reward with reward for expected number of agents in all state, action pairs, these approaches have ensured improved scalability. Such an objective closely approximates joint expected reward when there are many agents, due to law of large numbers. However, the performance deteriorates in problems with fewer agents. In this paper, we improve on the …

Collaborative Topic Regression For Online Recommender Systems: An Online And Bayesian Approach, Chenghao Liu, Tao Jin, Steven C. H. Hoi, Peilin Zhao, Jianling Sun

Research Collection School Of Computing and Information Systems

Collaborative Topic Regression (CTR) combines ideas of probabilistic matrix factorization (PMF) and topic modeling (such as LDA) for recommender systems, which has gained increasing success in many applications. Despite enjoying many advantages, the existing Batch Decoupled Inference algorithm for the CTR model has some critical limitations: First of all, it is designed to work in a batch learning manner, making it unsuitable to deal with streaming data or big data in real-world recommender systems. Secondly, in the existing algorithm, the item-specific topic proportions of LDA are fed to the downstream PMF but the rating information is not exploited in discovering …

A Parallelized Method For Solving Large Scale Integer Linear Optimization Problems Using Cut-And-Solve With Applications To Cgwas, John Brandenburg

Theses

The commercial solver CPLEX has been one of the top solvers of mixed-integer and purely integer linear problems for some time. Its method of solving, Branch-and-Cut, has been shown to be highly effective, but has its limits in terms of input sizes which are tractable, and cannot be effectively parallelized beyond a small number. Here we present a different method of solution, Cut-and-Solve, which utilizes the power of CPLEX to effectively parallelize any mixed-integer or integer linear problem. We have utilized Cut-and-Solve in a novel way to offer optimal solution guarantees more quickly. We will show comparisons of Cut-and-Solve to …

A Predictor Analysis Framework For Surface Radiation Budget Reprocessing Using Design Of Experiments, Patricia Allison Quigley

Engineering Management & Systems Engineering Theses & Dissertations

Earth’s Radiation Budget (ERB) is an accounting of all incoming energy from the sun and outgoing energy reflected and radiated to space by earth’s surface and atmosphere. The National Aeronautics and Space Administration (NASA)/Global Energy and Water Cycle Experiment (GEWEX) Surface Radiation Budget (SRB) project produces and archives long-term datasets representative of this energy exchange system on a global scale. The data are comprised of the longwave and shortwave radiative components of the system and is algorithmically derived from satellite and atmospheric assimilation products, and acquired atmospheric data. It is stored as 3-hourly, daily, monthly/3-hourly, and monthly averages of 1°x1° …

A Robust And Secure Video Steganography Method In Dwt-Dct Domains Based On Multiple Object Tracking And Ecc, Ramadhan J. Mstafa, Khaled M. Elleithy, Eman Abdelfattah

School of Computer Science & Engineering Faculty Publications

Over the past few decades, the art of secretly embedding and communicating digital data has gained enormous attention because of the technological development in both digital contents and communication. The imperceptibility, hiding capacity, and robustness against attacks are three main requirements that any video steganography method should take into consideration. In this paper, a robust and secure video steganographic algorithm in discrete wavelet transform (DWT) and discrete cosine transform (DCT) domains based on the multiple object tracking (MOT) algorithm and error correcting codes is proposed. The secret message is preprocessed by applying both Hamming and Bose, Chaudhuri, and Hocquenghem codes …

On Analyzing User Topic-Specific Platform Preferences Across Multiple Social Media Sites, Roy Ka Wei Lee, Tuan Anh Hoang, Ee Peng Lim

Research Collection School Of Computing and Information Systems

Topic modeling has traditionally been studied for single text collections and applied to social media data represented in the form of text documents. With the emergence of many social media platforms, users find themselves using different social media for posting content and for social interaction. While many topics may be shared across social media platforms, users typically show preferences of certain social media platform(s) over others for certain topics. Such platform preferences may even be found at the individual level. To model social media topics as well as platform preferences of users, we propose a new topic model known as …

Learning Personalized Preference Of Strong And Weak Ties For Social Recommendation, Xin Wang, Steven C. H. Hoi, Martin Ester, Jiajun Bu, Chun Chen

Research Collection School Of Computing and Information Systems

Recent years have seen a surge of research on social recommendation techniques for improving recommender systems due to the growing influence of social networks to our daily life. The intuition of social recommendation is that users tend to show affinities with items favored by their social ties due to social influence. Despite the extensive studies, no existing work has attempted to distinguish and learn the personalized preferences between strong and weak ties, two important terms widely used in social sciences, for each individual in social recommendation. In this paper, we first highlight the importance of different types of ties in …

Certifying Loop Pipelining Transformations In Behavioral Synthesis, Disha Puri

Dissertations and Theses

Due to the rapidly increasing complexity in hardware designs and competitive time to market trends in the industry, there is an inherent need to move designs to a higher level of abstraction. Behavioral Synthesis is the process of automatically compiling such Electronic System Level (ESL) designs written in high-level languages such as C, C++ or SystemC into Register-Transfer Level (RTL) implementation in hardware description languages such as Verilog or VHDL. However, the adoption of this flow is dependent on designers' faith in the correctness of behavioral synthesis tools.

Loop pipelining is a critical transformation employed in behavioral synthesis process, and …

Optimizing Campus Mobility With A Focus On Sustainability: A Graph Theory Approach To Intra-Campus Transportation Networks, Quinn M. Nelson

UNO Student Research and Creative Activity Fair

The idea of public transportation is supported by most in theory but often heavily criticized by users when put into application. There are common tensions that are related to public transportation, as described by frequent users: unreliable, too crowded, and slow. The University of Nebraska-Omaha (UNO) is a growing metropolitan institution that uses a shuttle system to transport students among their three campuses daily. As of 2015, the current total student enrollment is approximately 16,000; UNO plans to enroll 20,000 students by 2020. The expected student growth is also reflected by the current construction of new buildings and expansion of …

Efficient Motif Discovery In Spatial Trajectories Using Discrete Fréchet Distance, Bo Tang, Man Lung Yiu, Kyriakos Mouratidis, Kai Wang

Research Collection School Of Computing and Information Systems

The discrete Fréchet distance (DFD) captures perceptual and geographical similarity between discrete trajectories. It has been successfully adopted in a multitude of applications, such as signature and handwriting recognition, computer graphics, as well as geographic applications. Spatial applications, e.g., sports analysis, traffic analysis, etc. require discovering the pair of most similar subtrajectories, be them parts of the same or of different input trajectories.The identified pair of subtrajectories is called a motif.The adoption of DFD as the similarity measure in motif discovery,although semantically ideal, is hindered by the high computational complexity of DFD calculation. In this paper, we propose a suite …

Metric Similarity Joins Using Mapreduce, Yunjun Gao, Keyu Yang, Lu Chen, Baihua Zheng, Gang Chen, Chun Chen

Research Collection School Of Computing and Information Systems

Given two object sets Q and O , a metric similarity join finds similar object pairs according to a certain criterion. This operation has a wide variety of applications in data cleaning, data mining, to name but a few. However, the rapidly growing volume of data nowadays challenges traditional metric similarity join methods, and thus, a distributed method is required. In this paper, we adopt a popular distributed framework, namely, MapReduce, to support scalable metric similarity joins. To ensure the load balancing, we present two sampling based partition methods. One utilizes the pivot and the space-filling curve mappings to cluster …

Effective K-Vertex Connected Component Detection In Large-Scale Networks, Yuan Li, Yuha Zhao, Guoren Wang, Feida Zhu, Yubao Wu, Shenglei Shi

Research Collection School Of Computing and Information Systems

Finding components with high connectivity is an important problem in component detection with a wide range of applications, e.g., social network analysis, web-page research and bioinformatics. In particular, k-edge connected component (k-ECC) has recently been extensively studied to discover disjoint components. Yet many real applications present needs and challenges for overlapping components. In this paper, we propose a k-vertex connected component (k-VCC) model, which is much more cohesive and therefore allows overlapping between components. To find k-VCCs, a top-down framework is first developed to find the exact k-VCCs. To further reduce the high computational cost for input networks of large …

An Efficient Approach To Model-Based Hierarchical Reinforcement Learning, Zhuoru Li, Akshay Narayan, Tze-Yun Leong

Research Collection School Of Computing and Information Systems

We propose a model-based approach to hierarchical reinforcement learning that exploits shared knowledge and selective execution at different levels of abstraction, to efficiently solve large, complex problems. Our framework adopts a new transition dynamics learning algorithm that identifies the common action-feature combinations of the subtasks, and evaluates the subtask execution choices through simulation. The framework is sample efficient, and tolerates uncertain and incomplete problem characterization of the subtasks. We test the framework on common benchmark problems and complex simulated robotic environments. It compares favorably against the stateof-the-art algorithms, and scales well in very large problems.

Soal: Second-Order Online Active Learning, Shuji Hao, Peilin Zhao, Jing Lu, Steven C. H. Hoi, Chunyan Miao, Chi Zhang

Research Collection School Of Computing and Information Systems

This paper investigates the problem of online active learning for training classification models from sequentially arriving data. This is more challenging than conventional online learning tasks since the learner not only needs to figure out how to effectively update the classifier but also needs to decide when is the best time to query the label of an incoming instance given limited label budget. The existing online active learning approaches are often based on first-order online learning methods which generally fall short in slow convergence rate and suboptimal exploitation of available information when querying the labeled data. To overcome the limitations, …

Seapot-Rl: Selective Exploration Algorithm For Policy Transfer In Rl, Akshay Narayan, Zhuoru Li, Tze-Yun Leong

Research Collection School Of Computing and Information Systems

We propose a new method for transferring a policy from a source task to a target task in model-based reinforcement learning. Our work is motivated by scenarios where a robotic agent operates in similar but challenging environments, such as hospital wards, differentiated by structural arrangements or obstacles, such as furniture. We address problems that require fast responses adapted from incomplete, prior knowledge of the agent in new scenarios. We present an efficient selective exploration strategy that maximally reuses the source task policy. Reuse efficiency is effected through identifying sub-spaces that are different in the target environment, thus limiting the exploration …

Combinatorial Polynomial Hirsch Conjecture, Sam Miller

HMC Senior Theses

The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the …

Impact Of Reviewer Social Interaction On Online Consumer Review Fraud Detection, Kunal Goswami, Younghee Park, Chungsik Song

Faculty Publications

Background Online consumer reviews have become a baseline for new consumers to try out a business or a new product. The reviews provide a quick look into the application and experience of the business/product and market it to new customers. However, some businesses or reviewers use these reviews to spread fake information about the business/product. The fake information can be used to promote a relatively average product/business or can be used to malign their competition. This activity is known as reviewer fraud or opinion spam. The paper proposes a feature set, capturing the user social interaction behavior to identify fraud. …

Network Analytics For The Mirna Regulome And Mirna-Disease Interactions, Joseph Jayakar Nalluri

Theses and Dissertations

miRNAs are non-coding RNAs of approx. 22 nucleotides in length that inhibit gene expression at the post-transcriptional level. By virtue of this gene regulation mechanism, miRNAs play a critical role in several biological processes and patho-physiological conditions, including cancers. miRNA behavior is a result of a multi-level complex interaction network involving miRNA-mRNA, TF-miRNA-gene, and miRNA-chemical interactions; hence the precise patterns through which a miRNA regulates a certain disease(s) are still elusive. Herein, I have developed an integrative genomics methods/pipeline to (i) build a miRNA regulomics and data analytics repository, (ii) create/model these interactions into networks and use optimization techniques, motif …

Data Mining By Grid Computing In The Search For Extrasolar Planets, Oisin Creaner [Thesis]

Doctoral

A system is presented here to provide improved precision in ensemble differential photometry. This is achieved by using the power of grid computing to analyse astronomical catalogues. This produces new catalogues of optimised pointings for each star, which maximise the number and quality of reference stars available. Astronomical phenomena such as exoplanet transits and small-scale structure within quasars may be observed by means of millimagnitude photometric variability on the timescale of minutes to hours. Because of atmospheric distortion, ground-based observations of these phenomena require the use of differential photometry whereby the target is compared with one or more reference stars. …

Triple Non-Negative Matrix Factorization Technique For Sentiment Analysis And Topic Modeling, Alexander A. Waggoner

CMC Senior Theses

Topic modeling refers to the process of algorithmically sorting documents into categories based on some common relationship between the documents. This common relationship between the documents is considered the “topic” of the documents. Sentiment analysis refers to the process of algorithmically sorting a document into a positive or negative category depending whether this document expresses a positive or negative opinion on its respective topic. In this paper, I consider the open problem of document classification into a topic category, as well as a sentiment category. This has a direct application to the retail industry where companies may want to scour …

Normal Surfaces And 3-Manifold Algorithms, Josh D. Hews

Honors Theses

This survey will develop the theory of normal surfaces as they apply to the S3 recognition algorithm. Sections 2 and 3 provide necessary background on manifold theory. Section 4 presents the theory of normal surfaces in triangulations of 3-manifolds. Section 6 discusses issues related to implementing algorithms based on normal surfaces, as well as an overview of the Regina, a program that implements many 3-manifold algorithms. Finally section 7 presents the proof of the 3-sphere recognition algorithm and discusses how Regina implements the algorithm.

Xic Clustering By Baseyian Network, Kyle J. Handy

Graduate Student Theses, Dissertations, & Professional Papers

No abstract provided.

An Introduction To The Theory And Applications Of Bayesian Networks, Anant Jaitha

CMC Senior Theses

Bayesian networks are a means to study data. A Bayesian network gives structure to data by creating a graphical system to model the data. It then develops probability distributions over these variables. It explores variables in the problem space and examines the probability distributions related to those variables. It conducts statistical inference over those probability distributions to draw meaning from them. They are good means to explore a large set of data efficiently to make inferences. There are a number of real world applications that already exist and are being actively researched. This paper discusses the theory and applications of …

Special Issue: Neutrosophic Theories Applied In Engineering, Florentin Smarandache, Jun Ye

Branch Mathematics and Statistics Faculty and Staff Publications

Neutrosophic sets and logic are generalizations of fuzzy and intuitionistic fuzzy sets and logic. Neutrosophic sets and logic are gaining significant attention in solving many real life decision making problems that involve uncertainty, impreciseness, vagueness, incompleteness, inconsistent, and indeterminacy. They have been applied in computational intelligence, multiple criteria decision making, image processing, medical diagnoses, etc. This Special Issue presents original research papers that report on state-of-the-art and recent advancements in neutrosophic sets and logic in soft computing, artificial intelligence, big and small data mining, decision making problems, and practical achievements.

Anomaly Detection In Rfid Networks, Alaa Alkadi

UNF Graduate Theses and Dissertations

Available security standards for RFID networks (e.g. ISO/IEC 29167) are designed to secure individual tag-reader sessions and do not protect against active attacks that could also compromise the system as a whole (e.g. tag cloning or replay attacks). Proper traffic characterization models of the communication within an RFID network can lead to better understanding of operation under “normal” system state conditions and can consequently help identify security breaches not addressed by current standards. This study of RFID traffic characterization considers two piecewise-constant data smoothing techniques, namely Bayesian blocks and Knuth’s algorithms, over time-tagged events and compares them in the context …

Discovering Historic Traffic-Tolerant Paths In Road Networks, Pui Hang Li, Man Lung Yiu, Kyriakos Mouratidis

Research Collection School Of Computing and Information Systems

Historic traffic information is valuable in transportation analysis and planning, e.g., evaluating the reliability of routes for representative source-destination pairs. Also, it can be utilized to provide efficient and effective route-search services. In view of these applications, we propose the k traffic-tolerant paths (TTP) problem on road networks, which takes a source-destination pair and historic traffic information as input, and returns k paths that minimize the aggregate (historic) travel time. Unlike the shortest path problem, the TTP problem has a combinatorial search space that renders the optimal solution expensive to find. First, we propose an exact algorithm with effective pruning …

Exploring Representativeness And Informativeness For Active Learning, Bo Du, Zengmao Wang, Lefei Zhang, Liangpei Zhang, Wei Liu, Jialie Shen, Dacheng Tao

Research Collection School Of Computing and Information Systems

How can we find a general way to choose the most suitable samples for training a classifier? Even with very limited prior information? Active learning, which can be regarded as an iterative optimization procedure, plays a key role to construct a refined training set to improve the classification performance in a variety of applications, such as text analysis, image recognition, social network modeling, etc. Although combining representativeness and informativeness of samples has been proven promising for active sampling, state-of-the-art methods perform well under certain data structures. Then can we find a way to fuse the two active sampling criteria without …