Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms

Research Collection School Of Computing and Information Systems

2015

Articles 1 - 18 of 18

Full-Text Articles in Physical Sciences and Mathematics

Differentially Private Subspace Clustering, Yining Wang, Yu-Xiang Wang, Aarti Singh Dec 2015

Differentially Private Subspace Clustering, Yining Wang, Yu-Xiang Wang, Aarti Singh

Research Collection School Of Computing and Information Systems

Subspace clustering is an unsupervised learning problem that aims at grouping data points into multiple “clusters” so that data points in a single cluster lie approximately on a low-dimensional linear subspace. It is originally motivated by 3D motion segmentation in computer vision, but has recently been generically applied to a wide range of statistical machine learning problems, which often involves sensitive datasets about human subjects. This raises a dire concern for data privacy. In this work, we build on the framework of differential privacy and present two provably private subspace clustering algorithms. We demonstrate via both theory and experiments that …

Go to article

Dictionary Pair Learning On Grassmann Manifolds For Image Denoising, Xianhua Zeng, Wei Bian, Wei Liu, Jialie Shen, Dacheng Tao Nov 2015

Dictionary Pair Learning On Grassmann Manifolds For Image Denoising, Xianhua Zeng, Wei Bian, Wei Liu, Jialie Shen, Dacheng Tao

Research Collection School Of Computing and Information Systems

Image denoising is a fundamental problem in computer vision and image processing that holds considerable practical importance for real-world applications. The traditional patch-based and sparse coding-driven image denoising methods convert 2D image patches into 1D vectors for further processing. Thus, these methods inevitably break down the inherent 2D geometric structure of natural images. To overcome this limitation pertaining to the previous image denoising methods, we propose a 2D image denoising model, namely, the dictionary pair learning (DPL) model, and we design a corresponding algorithm called the DPL on the Grassmann-manifold (DPLG) algorithm. The DPLG algorithm first learns an initial dictionary …

Go to article

The Autoproof Verifier: Usability By Non-Experts And On Standard Code, Carlo A. Furia, Christopher M. Poskitt, Julian Tschannen Aug 2015

The Autoproof Verifier: Usability By Non-Experts And On Standard Code, Carlo A. Furia, Christopher M. Poskitt, Julian Tschannen

Research Collection School Of Computing and Information Systems

Formal verification tools are often developed by experts for experts; as a result, their usability by programmers with little formal methods experience may be severely limited. In this paper, we discuss this general phenomenon with reference to AutoProof: a tool that can verify the full functional correctness of object-oriented software. In particular, we present our experiences of using AutoProof in two contrasting contexts representative of non-expert usage. First, we discuss its usability by students in a graduate course on software verification, who were tasked with verifying implementations of various sorting algorithms. Second, we evaluate its usability in verifying code developed …

Go to article

Sails: Hybrid Algorithm For The Team Orienteering Problem With Time Windows, Aldy Gunawan, Hoong Chuin Lau, Kun Lu Aug 2015

Sails: Hybrid Algorithm For The Team Orienteering Problem With Time Windows, Aldy Gunawan, Hoong Chuin Lau, Kun Lu

Research Collection School Of Computing and Information Systems

The Team Orienteering Problem with Time Windows (TOPTW) is the extended version of the Orienteering Problem where each node is limited by a given time window. The objective is to maximize the total collected score from a certain number of paths. In this paper, a hybridization of Simulated Annealing and Iterated Local Search, namely SAILS, is proposed to solve the TOPTW. The efficacy of the proposed algorithm is tested using benchmark instances. The results show that the proposed algorithm is competitive with the state-of-the-art algorithms in the literature. SAILS is able to improve the best known solutions for 19 benchmark …

Go to article

A Comparative Study Between Motivated Learning And Reinforcement Learning, James T. Graham, Janusz A. Starzyk, Zhen Ni, Haibo He, T.-H. Teng, Ah-Hwee Tan Jul 2015

A Comparative Study Between Motivated Learning And Reinforcement Learning, James T. Graham, Janusz A. Starzyk, Zhen Ni, Haibo He, T.-H. Teng, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

This paper analyzes advanced reinforcement learning techniques and compares some of them to motivated learning. Motivated learning is briefly discussed indicating its relation to reinforcement learning. A black box scenario for comparative analysis of learning efficiency in autonomous agents is developed and described. This is used to analyze selected algorithms. Reported results demonstrate that in the selected category of problems, motivated learning outperformed all reinforcement learning algorithms we compared with.

Go to article

Message Passing For Collective Graphical Models, Tao Sun, Daniel Sheldon, Akshat Kumar Jul 2015

Message Passing For Collective Graphical Models, Tao Sun, Daniel Sheldon, Akshat Kumar

Research Collection School Of Computing and Information Systems

Collective graphical models (CGMs) are a formalism for inference and learning about a population of independent and identically distributed individuals when only noisy aggregate data are available. We highlight a close connection between approximate MAP inference in CGMs and marginal inference in standard graphical models. The connection leads us to derive a novel Belief Propagation (BP) style algorithm for collective graphical models. Mathematically, the algorithm is a strict generalization of BP—it can be viewed as an extension to minimize the Bethe free energy plus additional energy terms that are non-linear functions of the marginals. For CGMs, the algorithm is much …

Go to article

Optimizing Selection Of Competing Features Via Feedback-Directed Evolutionary Algorithms, Tian Huat Tan, Yinxing Xue, Manman Chen, Jun Sun, Yang Liu, Jin Song Dong Dong Jul 2015

Optimizing Selection Of Competing Features Via Feedback-Directed Evolutionary Algorithms, Tian Huat Tan, Yinxing Xue, Manman Chen, Jun Sun, Yang Liu, Jin Song Dong Dong

Research Collection School Of Computing and Information Systems

Software that support various groups of customers usually require complicated configurations to attain different functionalities. To model the configuration options, feature model is proposed to capture the commonalities and competing variabilities of the product variants in software family or Software Product Line (SPL). A key challenge for deriving a new product is to find a set of features that do not have inconsistencies or conflicts, yet optimize multiple objectives (e.g., minimizing cost and maximizing number of features), which are often competing with each other. Existing works have attempted to make use of evolutionary algorithms (EAs) to address this problem. In …

Go to article

Solar: Scalable Online Learning Algorithms For Ranking, Jialei Wang, Ji Wan, Yongdong Zhang, Steven C. H. Hoi Jul 2015

Solar: Scalable Online Learning Algorithms For Ranking, Jialei Wang, Ji Wan, Yongdong Zhang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Traditional learning to rank methods learn ranking models from training data in a batch and offline learning mode, which suffers from some critical limitations, e.g., poor scalability as the model has to be retrained from scratch whenever new training data arrives. This is clearly nonscalable for many real applications in practice where training data often arrives sequentially and frequently. To overcome the limitations, this paper presents SOLAR- a new framework of Scalable Online Learning Algorithms for Ranking, to tackle the challenge of scalable learning to rank. Specifically, we propose two novel SOLAR algorithms and analyze their IR measure bounds theoretically. …

Go to article

Adviser: A Web-Based Algorithm Portfolio Deviser, Mustafa Misir, Stephanus Daniel Handoko, Hoong Chuin Lau May 2015

Adviser: A Web-Based Algorithm Portfolio Deviser, Mustafa Misir, Stephanus Daniel Handoko, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

The basic idea of algorithm portfolio [1] is to create a mixture of diverse algorithms that complement each other’s strength so as to solve a diverse set of problem instances. Algorithm portfolios have taken on a new and practical meaning today with the wide availability of multi-core processors: from an enterprise perspective, the interest is to make best use of parallel machines within the organization by running different algorithms simultaneously on different cores to solve a given problem instance. Parallel execution of a portfolio of algorithms as suggested by [2, 3] a number of years …

Go to article

Oscar: Online Selection Of Algorithm Portfolios With Case Study On Memetic Algorithms, Mustafa Misir, Stephanus Daniel Handoko, Hoong Chuin Lau May 2015

Oscar: Online Selection Of Algorithm Portfolios With Case Study On Memetic Algorithms, Mustafa Misir, Stephanus Daniel Handoko, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

This paper introduces an automated approach called OSCAR that combines algorithm portfolios and online algorithm selection. The goal of algorithm portfolios is to construct a subset of algorithms with diverse problem solving capabilities. The portfolio is then used to select algorithms from for solving a particular (set of) instance(s). Traditionally, algorithm selection is usually performed in an offline manner and requires the need of domain knowledge about the target problem; while online algorithm selection techniques tend not to pay much attention to a careful construction of algorithm portfolios. By combining algorithm portfolios and online selection, our hope is to design …

Go to article

Beyond Traits: Social Context Based Personality Model, Jaroslaw Kochanowicz, Ah-Hwee Tan, Daniel Thalmann May 2015

Beyond Traits: Social Context Based Personality Model, Jaroslaw Kochanowicz, Ah-Hwee Tan, Daniel Thalmann

Research Collection School Of Computing and Information Systems

The relation between individual’s personality and environmental context is a key issue in psychology, recently also in character simulations. This paper contributes to both domains by proposing a socio-cognitive, contextual personality model - a new voice in a century old problem of personality, but also an approach to simulating groups of more humanlike agents. After analyzing the influence of popularity of ‘trait personality models’ on psychology and computer simulation, we propose Social Context based Personality model - a continuation and specification of the Cognitive-Affective Personality System theory. The discussion, model and implementation are provided, followed by an example application in …

Go to article

Map: A Computational Model For Adaptive Persuasion, Yilin Kang, Ah-Hwee Tan May 2015

Map: A Computational Model For Adaptive Persuasion, Yilin Kang, Ah-Hwee Tan

Research Collection School Of Computing and Information Systems

While a variety of persuasion agents have been created and applied in different domains such as marketing, military training and health industry, there is a lack of a model which provides a unified framework for different persuasion strategies. Specifically, persuasion is not adaptable to the individuals’ personal states in different situations. Grounded in the Elaboration Likelihood Model (ELM), this paper presents a computational model called Model for Adaptive Persuasion (MAP) for virtual agents. MAP is a semi-connected network model which enables an agent to adapt its persuasion strategies through feedback. We have implemented and evaluated a MAP-based virtual nurse agent …

Go to article

An Iterated Local Search Algorithm For Solving The Orienteering Problem With Time Windows, Aldy Gunawan, Hoong Chuin Lau, Kun Lu Apr 2015

An Iterated Local Search Algorithm For Solving The Orienteering Problem With Time Windows, Aldy Gunawan, Hoong Chuin Lau, Kun Lu

Research Collection School Of Computing and Information Systems

The Orienteering Problem with Time Windows (OPTW) is a variant of the Orienteering Problem (OP). Given a set of nodes including their scores, service times and time windows, the goal is to maximize the total of scores collected by a particular route considering a predefined time window during which the service has to start. We propose an Iterated Local Search (ILS) algorithm to solve the OPTW, which is based on several LocalSearch operations, such as swap, 2-opt, insert and replace. We also implement the combination between AcceptanceCriterion and Perturbation mechanisms to control the balance between diversification and intensification of the …

Go to article

Reconstruction Privacy: Enabling Statistical Learning, Ke Wang, Chao Han, Ada Waichee Fu, Raymond C. Wong, Philip S. Yu Mar 2015

Reconstruction Privacy: Enabling Statistical Learning, Ke Wang, Chao Han, Ada Waichee Fu, Raymond C. Wong, Philip S. Yu

Research Collection School Of Computing and Information Systems

Non-independent reasoning (NIR) allows the information about one record in the data to be learnt from the information of other records in the data. Most posterior/prior based privacy criteria consider NIR as a privacy violation and require to smooth the distribution of published data to avoid sensitive NIR. The drawback of this approach is that it limits the utility of learning statistical relationships. The differential privacy criterion considers NIR as a non-privacy violation, therefore, enables learning statistical relationships, but at the cost of potential disclosures through NIR. A question is whether it is possible to (1) allow learning statistical relationships, …

Go to article

On Processing Reverse K-Skyband And Ranked Reverse Skyline Queries, Yunjun Gao, Qing Liu, Baihua Zheng, Mou Li, Gang Chen, Qing Li Feb 2015

On Processing Reverse K-Skyband And Ranked Reverse Skyline Queries, Yunjun Gao, Qing Liu, Baihua Zheng, Mou Li, Gang Chen, Qing Li

Research Collection School Of Computing and Information Systems

In this paper, for the first time, we identify and solve the problem of efficient reverse k-skyband (RkSB) query processing. Given a set P of multi-dimensional points and a query point q, an RkSB query returns all the points in P whose dynamic k-skyband contains q. We formalize RkSB retrieval, and then propose five algorithms for computing the RkSB of an arbitrary query point efficiently. Our methods utilize a conventional data-partitioning index (e.g., R-tree) on the dataset, and employ pre-computation, reuse and pruning techniques to boost the query efficiency. In addition, we extend our solutions to tackle an interesting variant …

Go to article

Algorithm Selection Via Ranking, Jayadi Oentaryo Richard, Handoko Stephanus Daniel, Hoong Chuin Lau Jan 2015

Algorithm Selection Via Ranking, Jayadi Oentaryo Richard, Handoko Stephanus Daniel, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

The abundance of algorithms developed to solve different problems has given rise to an important research question: How do we choose the best algorithm for a given problem? Known as algorithm selection, this issue has been prevailing in many domains, as no single algorithm can perform best on all problem instances. Traditional algorithm selection and portfolio construction methods typically treat the problem as a classification or regression task. In this paper, we present a new approach that provides a more natural treatment of algorithm selection and portfolio construction as a ranking task. Accordingly, we develop a Ranking-Based Algorithm Selection (RAS) …

Go to article

Designing A Portfolio Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir Jan 2015

Designing A Portfolio Of Parameter Configurations For Online Algorithm Selection, Aldy Gunawan, Hoong Chuin Lau, Mustafa Misir

Research Collection School Of Computing and Information Systems

Algorithm portfolios seek to determine an effective set of algorithms that can be used within an algorithm selection framework to solve problems. A limited number of these portfolio studies focus on generating different versions of a target algorithm using different parameter configurations. In this paper, we employ a Design of Experiments (DOE) approach to determine a promising range of values for each parameter of an algorithm. These ranges are further processed to determine a portfolio of parameter configurations, which would be used within two online Algorithm Selection approaches for solving different instances of a given combinatorial optimization problem effectively. We …

Go to article

An Adaptive Gradient Method For Online Auc Maximization, Yi Ding, Peilin Zhao, Steven C. H. Hoi, Yew-Soon Ong Jan 2015

An Adaptive Gradient Method For Online Auc Maximization, Yi Ding, Peilin Zhao, Steven C. H. Hoi, Yew-Soon Ong

Research Collection School Of Computing and Information Systems

Learning for maximizing AUC performance is an important research problem in machine learning. Unlike traditional batch learning methods for maximizing AUC which often suffer from poor scalability, recent years have witnessed some emerging studies that attempt to maximize AUC by single-pass online learning approaches. Despite their encouraging results reported, the existing online AUC maximization algorithms often adopt simple stochastic gradient descent approaches, which fail to exploit the geometry knowledge of the data observed in the online learning process, and thus could suffer from relatively slow convergence. To overcome the limitation of the existing studies, in this paper, we propose a …

Go to article