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

Physical Sciences and Mathematics Commons™

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

Singapore Management University

2011

Theory and Algorithms

Articles 1 - 15 of 15

Full-Text Articles in Physical Sciences and Mathematics

Mobile Phone Graph Evolution: Findings, Model And Interpretation, Siyuan Liu, Lei Li, Christos Faloutsos, Lionel M. Ni Dec 2011

Mobile Phone Graph Evolution: Findings, Model And Interpretation, Siyuan Liu, Lei Li, Christos Faloutsos, Lionel M. Ni

LARC Research Publications

What are the features of mobile phone graph along the time? How to model these features? What are the interpretation for the evolutional graph generation process? To answer the above challenging problems, we analyze a massive who-call-whom networks as long as a year, gathered from records of two large mobile phone communication networks both with 2 million users and 2 billion of calls. We examine the calling behavior distribution at multiple time scales (e.g. day, week, month and quarter), and find that the distribution is not only skewed with a heavy tail, but also changing at different time scales. How …

Go to article

Exploring Tweets Normalization And Query Time Sensitivity For Twitter Search, Zhongyu Wei, Wei Gao, Lanjun Zhou, Binyang Li, Kam-Fai Wong Nov 2011

Exploring Tweets Normalization And Query Time Sensitivity For Twitter Search, Zhongyu Wei, Wei Gao, Lanjun Zhou, Binyang Li, Kam-Fai Wong

Research Collection School Of Computing and Information Systems

This paper presents our work for the Realtime Adhoc Task of TREC 2011 Microblog Track. Microblog texts like tweets are generally characterized by the inclusion of a large proportion of irregular expressions, such as ill-formed words, which can lead to significant mismatch between query terms and tweets. In addition, Twitter queries are distinguished from Web queries with many unique characteristics, one of which reflects the clearly distinct temporal aspects of Twitter search behavior. In this study, we deal with the first problem by normalizing tweet texts and the second by capturing the temporal characteristics of topic. We divided topics into …

Go to article

Beyond Search: Event-Driven Summarization For Web Videos, Richard Hong, Jinhui Tang, Hung-Khoon Tan, Chong-Wah Ngo, Shuicheng Yan, Tat-Seng Chua Nov 2011

Beyond Search: Event-Driven Summarization For Web Videos, Richard Hong, Jinhui Tang, Hung-Khoon Tan, Chong-Wah Ngo, Shuicheng Yan, Tat-Seng Chua

Research Collection School Of Computing and Information Systems

The explosive growth of Web videos brings out the challenge of how to efficiently browse hundreds or even thousands of videos at a glance. Given an event-driven query, social media Web sites usually return a large number of videos that are diverse and noisy in a ranking list. Exploring such results will be time-consuming and thus degrades user experience. This article presents a novel scheme that is able to summarize the content of video search results by mining and threading "key" shots, such that users can get an overview of main content of these videos at a glance. The proposed …

Go to article

Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang Jul 2011

Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang

Research Collection School Of Computing and Information Systems

Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for …

Go to article

Online Auc Maximization, Peilin Zhao, Steven C. H. Hoi, Rong Jin, Tianbo Yang Jul 2011

Online Auc Maximization, Peilin Zhao, Steven C. H. Hoi, Rong Jin, Tianbo Yang

Research Collection School Of Computing and Information Systems

Most studies of online learning measure the performance of a learner by classification accuracy, which is inappropriate for applications where the data are unevenly distributed among different classes. We address this limitation by developing online learning algorithm for maximizing Area Under the ROC curve (AUC), a metric that is widely used for measuring the classification performance for imbalanced data distributions. The key challenge of online AUC maximization is that it needs to optimize the pairwise loss between two instances from different classes. This is in contrast to the classical setup of online learning where the overall loss is a sum …

Go to article

Smoothly Varying Affine Stitching, Wen-Yan Lin, Siying Liu, Yasuyuki Matsuhita, Tian-Tsong Ng, Loong-Fah Cheong Jun 2011

Smoothly Varying Affine Stitching, Wen-Yan Lin, Siying Liu, Yasuyuki Matsuhita, Tian-Tsong Ng, Loong-Fah Cheong

Research Collection School Of Computing and Information Systems

Traditional image stitching using parametric transforms such as homography, only produces perceptually correct composites for planar scenes or parallax free camera motion between source frames. This limits mosaicing to source images taken from the same physical location. In this paper, we introduce a smoothly varying affine stitching field which is flexible enough to handle parallax while retaining the good extrapolation and occlusion handling properties of parametric transforms. Our algorithm which jointly estimates both the stitching field and correspondence, permits the stitching of general motion source images, provided the scenes do not contain abrupt protrusions.

Go to article

A Feature Based Frequency Domain Analysis Algorithm For Fault Detection Of Induction Motors, Zhaoxia Wang, C. S. Chang, Zhang Yifan Jun 2011

A Feature Based Frequency Domain Analysis Algorithm For Fault Detection Of Induction Motors, Zhaoxia Wang, C. S. Chang, Zhang Yifan

Research Collection School Of Computing and Information Systems

This paper studies the stator currents collected from several inverter-fed laboratory induction motors and proposes a new feature based frequency domain analysis method for performing the detection of induction motor faults, such as the broken rotor-bar or bearing fault. The mathematical formulation is presented to calculate the features, which are called FFT-ICA features in this paper. The obtained FFT-ICA features are normalized by using healthy motor as benchmarks to establish a feature database for fault detection. Compare with conventional frequency-domain analysis method, no prior knowledge of the motor parameters or other measurements are required for calculating features. Only one phase …

Go to article

Adaptive Decision Support For Structured Organizations: A Case For Orgpomdps, Pradeep Reddy Varakantham, Nathan Schurr, Alan Carlin, Christopher Amato May 2011

Adaptive Decision Support For Structured Organizations: A Case For Orgpomdps, Pradeep Reddy Varakantham, Nathan Schurr, Alan Carlin, Christopher Amato

Research Collection School Of Computing and Information Systems

In today's world, organizations are faced with increasingly large and complex problems that require decision-making under uncertainty. Current methods for optimizing such decisions fall short of handling the problem scale and time constraints. We argue that this is due to existing methods not exploiting the inherent structure of the organizations which solve these problems. We propose a new model called the OrgPOMDP (Organizational POMDP), which is based on the partially observable Markov decision process (POMDP). This new model combines two powerful representations for modeling large scale problems: hierarchical modeling and factored representations. In this paper we make three key contributions: …

Go to article

Double Updating Online Learning, Peilin Zhao, Steven C. H. Hoi, Rong Jin May 2011

Double Updating Online Learning, Peilin Zhao, Steven C. H. Hoi, Rong Jin

Research Collection School Of Computing and Information Systems

In most kernel based online learning algorithms, when an incoming instance is misclassified, it will be added into the pool of support vectors and assigned with a weight, which often remains unchanged during the rest of the learning process. This is clearly insufficient since when a new support vector is added, we generally expect the weights of the other existing support vectors to be updated in order to reflect the influence of the added support vector. In this paper, we propose a new online learning method, termed Double Updating Online Learning, or DUOL for short, that explicitly addresses this problem. …

Go to article

A Family Of Simple Non-Parametric Kernel Learning Algorithms From Pairwise Constraints, Jinfeng Zhuang, Ivor W. Tsang, Steven C. H. Hoi Apr 2011

A Family Of Simple Non-Parametric Kernel Learning Algorithms From Pairwise Constraints, Jinfeng Zhuang, Ivor W. Tsang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Previous studies of Non-Parametric Kernel Learning (NPKL) usually formulate the learning task as a Semi-Definite Programming (SDP) problem that is often solved by some general purpose SDP solvers. However, for N data examples, the time complexity of NPKL using a standard interior-point SDP solver could be as high as O(N6.5), which prohibits NPKL methods applicable to real applications, even for data sets of moderate size. In this paper, we present a family of efficient NPKL algorithms, termed "SimpleNPKL", which can learn non-parametric kernels from a large set of pairwise constraints efficiently. In particular, we propose two efficient SimpleNPKL algorithms. One …

Go to article

Two-Layer Multiple Kernel Learning, Jinfeng Zhuang, Ivor W. Tsang, Steven C. H. Hoi Apr 2011

Two-Layer Multiple Kernel Learning, Jinfeng Zhuang, Ivor W. Tsang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Multiple Kernel Learning (MKL) aims to learn kernel machines for solving a real machine learning problem (e.g. classification) by exploring the combinations of multiple kernels. The traditional MKL approach is in general “shallow” in the sense that the target kernel is simply a linear (or convex) combination of some base kernels. In this paper, we investigate a framework of Multi-Layer Multiple Kernel Learning (MLMKL) that aims to learn “deep” kernel machines by exploring the combinations of multiple kernels in a multi-layer structure, which goes beyond the conventional MKL approach. Through a multiple layer mapping, the proposed MLMKL framework offers higher …

Go to article

Multi-Objective Zone Mapping In Large-Scale Distributed Virtual Environments, Nguyen Binh Duong Ta, Suiping Zhou, Wentong Cai, Xueyan Tang, Rassul Avani Mar 2011

Multi-Objective Zone Mapping In Large-Scale Distributed Virtual Environments, Nguyen Binh Duong Ta, Suiping Zhou, Wentong Cai, Xueyan Tang, Rassul Avani

Research Collection School Of Computing and Information Systems

In large-scale distributed virtual environments (DVEs), the NP-hard zone mapping problem concerns how to assign distinct zones of the virtual world to a number of distributed servers to improve overall interactivity. Previously, this problem has been formulated as a single-objective optimization problem, in which the objective is to minimize the total number of clients that are without QoS. This approach may cause considerable network traffic and processing overhead, as a large number of zones may need to be migrated across servers. In this paper, we introduce a multi-objective approach to the zone mapping problem, in which both the total number …

Go to article

Enhancing Bag-Of-Words Models By Efficient Semantics-Preserving Metric Learning, Lei Wu, Steven C. H. Hoi Jan 2011

Enhancing Bag-Of-Words Models By Efficient Semantics-Preserving Metric Learning, Lei Wu, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

The authors present an online semantics preserving, metric learning technique for improving the bag-of-words model and addressing the semantic-gap issue. This article investigates the challenge of reducing the semantic gap for building BoW models for image representation; propose a novel OSPML algorithm for enhancing BoW by minimizing the semantic loss, which is efficient and scalable for enhancing BoW models for large-scale applications; apply the proposed technique for large-scale image annotation and object recognition; and compare it to the state of the art.

Go to article

Fine-Tuning Algorithm Parameters Using The Design Of Experiments Approach, Aldy Gunawan, Hoong Chuin Lau, Linda Lindawati Jan 2011

Fine-Tuning Algorithm Parameters Using The Design Of Experiments Approach, Aldy Gunawan, Hoong Chuin Lau, Linda Lindawati

Research Collection School Of Computing and Information Systems

Optimizing parameter settings is an important task in algorithm design. Several automated parameter tuning procedures/configurators have been proposed in the literature, most of which work effectively when given a good initial range for the parameter values. In the Design of Experiments (DOE), a good initial range is known to lead to an optimum parameter setting. In this paper, we present a framework based on DOE to find a good initial range of parameter values for automated tuning. We use a factorial experiment design to first screen and rank all the parameters thereby allowing us to then focus on the parameter …

Go to article

Solving The Teacher Assignment Problem By Two Metaheuristics, Aldy Gunawan, Kien Ming Ng Jan 2011

Solving The Teacher Assignment Problem By Two Metaheuristics, Aldy Gunawan, Kien Ming Ng

Research Collection School Of Computing and Information Systems

The timetabling problem arising from a university in Indonesia is addressed in this paper.It involves the assignment of teachers to the courses and course sections. We formulate theproblem as a mathematical programming model. Two different algorithms, mainly basedon simulated annealing (SA) and tabu search (TS) algorithms, are proposed for solving theproblem. The proposed algorithms consist of two phases. The first phase involves allocatingthe teachers to the courses and determining the number of courses to be assigned to eachteacher. The second phase involves assigning the teachers to the course sections in order tobalance the teachers’ load. The performance of the proposed …

Go to article