Theory and Algorithms Commons^™

خوارزمية لاستخراج أسماء رواة الحديث النبوي آليا اعتمادا على صيغ الإخبار في السند, Omar Koussa, Moustafa Alhajj, Amani Sabra

Al Jinan الجنان

لمّا كان للحديث النبوي الشريف ولعلم الرواية الأثر الواضح في اللغة العربية؛ آثرنا أن نضع بصمتنا في هذا المجال، فقمنا بعمل تطبيق للتعرّف الآلي على أسماء الرواة عبر الاستعانة باللسانيات الحاسوبية. تكمن أهمية هذا العمل في تسهيله استخراج أسماء الرواة خدمة للدارسين في علم الحديث، كذلك سيُشكل هذا العمل نواة لأعمال لاحقة في التصنيف الآلي للرواة، طبقا للتصانيف المقررة في هذا العلم

Reinforcement Learning For Zone Based Multiagent Pathfinding Under Uncertainty, Jiajing Ling, Tarun Gupta, Akshat Kumar

Research Collection School Of Computing and Information Systems

We address the problem of multiple agents finding their paths from respective sources to destination nodes in a graph (also called MAPF). Most existing approaches assume that all agents move at fixed speed, and that a single node accommodates only a single agent. Motivated by the emerging applications of autonomous vehicles such as drone traffic management, we present zone-based path finding (or ZBPF) where agents move among zones, and agents' movements require uncertain travel time. Furthermore, each zone can accommodate multiple agents (as per its capacity). We also develop a simulator for ZBPF which provides a clean interface from the …

Efficient Sampling Algorithms For Approximate Temporal Motif Counting, Jingjing Wang, Yanhao Wang, Wenjun Jiang, Yuchen Li, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

A great variety of complex systems ranging from user interactions in communication networks to transactions in financial markets can be modeled as temporal graphs, which consist of a set of vertices and a series of timestamped and directed edges. Temporal motifs in temporal graphs are generalized from subgraph patterns in static graphs which take into account edge orderings and durations in addition to structures. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal network analysis. However, existing methods either cannot support temporal motifs or suffer from performance issues. In this paper, we focus on approximate …

F-Measure Optimisation And Label Regularisation For Energy-Based Neural Dialogue State Tracking Models, Anh Duong Trinh, Robert J. Ross, John D. Kelleher

Conference papers

In recent years many multi-label classification methods have exploited label dependencies to improve performance of classification tasks in various domains, hence casting the tasks to structured prediction problems. We argue that multi-label predictions do not always satisfy domain constraint restrictions. For example when the dialogue state tracking task in task-oriented dialogue domains is solved with multi-label classification approaches, slot-value constraint rules should be enforced following real conversation scenarios.

To address these issues we propose an energy-based neural model to solve the dialogue state tracking task as a structured prediction problem. Furthermore we propose two improvements over previous methods with respect …

Artificial Intelligence In Pursuit-Evasion Games, Specifically In The Scotland Yard Game, Arif M. Alamri

Theses and Dissertations

This research provides a heuristic algorithm for the detectives, who try to collectively capture a criminal known as Mr. X, in the Scotland Yard pursuer-evasion game. In Scotland Yard, a team of detectives attempts to converge on and capture a criminal known as Mr. X. The heuristic algorithm developed in this thesis is designed to emulate human strategies when playing the game. The algorithm uses the current state of the board at each time step, including the current positions of the detectives as well as the last known position of Mr. X. The heuristic algorithm then analyses all of the …

Unclonable Secret Keys, Marios Georgiou

Dissertations, Theses, and Capstone Projects

We propose a novel concept of securing cryptographic keys which we call “Unclonable Secret Keys,” where any cryptographic object is modified so that its secret key is an unclonable quantum bit-string whereas all other parameters such as messages, public keys, ciphertexts, signatures, etc., remain classical. We study this model in the authentication and encryption setting giving a plethora of definitions and positive results as well as several applications that are impossible in a purely classical setting.

In the authentication setting, we define the notion of one-shot signatures, a fundamental element in building unclonable keys, where the signing key not only …

Set Operators, Xiaojin Ye

Dissertations, Theses, and Capstone Projects

My research is centered on set operators. These are universally applicable regardless of the internal structure (numeric or non-numeric) of each individual observed datum. In our research, we have developed the theory of set operators to fill holes and gaps in observed data and eliminate paper shred garbage, thereby changing the observed symbolic data set into one whose pattern is closer to the pattern in the underlying population from which the observed data set was sampled with perturbations.

We describe different set operators including increasing operators, decreasing operators, ex- pansive operators, contractive operators, union preserving operators, intersection preserving op- erators, …

Improving Closely Spaced Dim Object Detection Through Improved Multiframe Blind Deconvolution, Ronald M. Aung

Theses and Dissertations

This dissertation focuses on improving the ability to detect dim stellar objects that are in close proximity to a bright one, through statistical image processing using short exposure images. The goal is to improve the space domain awareness capabilities with the existing infrastructure. Two new algorithms are developed. The first one is through the Neighborhood System Blind Deconvolution where the data functions are separated into the bright object, the neighborhood system, and the background functions. The second one is through the Dimension Reduction Blind Deconvolution, where the object function is represented by the product of two matrices. Both are designed …

A Hybrid Framework Using A Qubo Solver For Permutation-Based Combinatorial Optimization, Siong Thye Goh, Sabrish Gopalakrishnan, Jianyuan Bo, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

In this paper, we propose a hybrid framework to solve large-scale permutation-based combinatorial problems effectively using a high-performance quadratic unconstrained binary optimization (QUBO) solver. To do so, transformations are required to change a constrained optimization model to an unconstrained model that involves parameter tuning. We propose techniques to overcome the challenges in using a QUBO solver that typically comes with limited numbers of bits. First, to smooth the energy landscape, we reduce the magnitudes of the input without compromising optimality. We propose a machine learning approach to tune the parameters for good performance effectively. To handle possible infeasibility, we introduce …

A Genetic Algorithm To Minimise Number Of Vehicles In An Electric Vehicle Routing Problem, Kiian Leong Bertran Queck, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

Electric Vehicles (EVs) and charging infrastructure are starting to become commonplace in major cities around the world. For logistics providers to adopt an EV fleet, there are many factors up for consideration, such as route planning for EVs with limited travel range as well as long-term planning of fleet size. In this paper, we present a genetic algorithm to perform route planning that minimises the number of vehicles required. Specifically, we discuss the challenges on the violations of constraints in the EV routing problem (EVRP) arising from applying genetic algorithm operators. To overcome the challenges, techniques specific to addressing the …

Vehicle Routing Problem With Reverse Cross-Docking: An Adaptive Large Neighborhood Search Algorithm, Aldy Gunawan, Audrey Tedja Widjaja, Pieter Vansteenwegen, Vincent F. Yu

Research Collection School Of Computing and Information Systems

Cross-docking is a logistics strategy that aims at less transportation costs and fast customer deliveries. Incorporating an efficient vehicle routing could increase the benefits of the cross-docking. In this paper, the vehicle routing problem with reverse cross-docking (VRP-RCD) is studied. Reverse logistics has attracted more attention due to its ability to gain more profit and maintain the competitiveness of a company. VRP-RCD includes a four-level supply chain network: suppliers, cross-dock, customers, and outlets, with the objective of minimizing vehicle operational and transportation costs. A two-phase heuristic that employs an adaptive large neighborhood search (ALNS) with various destroy and repair operators …

Querying Recurrent Convoys Over Trajectory Data, Munkh-Erdene Yadamjav, Zhifeng Bao, Baihua Zheng, Farhana M. Choudhury, Hanan Samet

Research Collection School Of Computing and Information Systems

Moving objects equipped with location-positioning devices continuously generate a large amount of spatio-temporal trajectory data. An interesting finding over a trajectory stream is a group of objects that are travelling together for a certain period of time. Existing studies on mining co-moving objects do not consider an important correlation between co-moving objects, which is the reoccurrence of the movement pattern. In this study, we define a problem of finding recurrent pattern of co-moving objects from streaming trajectories and propose an efficient solution that enables us to discover recent co-moving object patterns repeated within a given time period. Experimental results on …

An Effective Method For Attribute Subset Selection, Considering The Resource In Pattern Recognition, Bakhtiyorjon Bakirovich Akbaraliev

Chemical Technology, Control and Management

An analytical method for determining informative sets of features (INP) is developed, taking into account the resource for criteria based on the use of a measure of dispersion of classified objects. The areas of existence of the solution are defined. The statements and properties for the Fischer-type information criterion are proved, using which the proposed analytical method for determining the INP guarantees optimal results in the sense of maximizing the selected functional. The appropriateness of choosing this type of informative criterion is justified. A method for transforming attributes is proposed. The universality of the method in relation to the type …

Find Me If You Can: Aligning Users In Different Social Networks, Priyanka Kasbekar, Katerina Potika, Chris Pollett

Faculty Publications, Computer Science

Online Social Networks allow users to share experiences with friends and relatives, make announcements, find news and jobs, and more. Several have user bases that number in the hundred of millions and even billions. Very often many users belong to multiple social networks at the same time under possibly different user names. Identifying a user from one social network on another social network gives information about a user's behavior on each platform, which in turn can help companies perform graph mining tasks, such as community detection and link prediction. The process of identifying or aligning users in multiple networks is …

Machine Learning Corrected Quantum Dynamics Calculations, A. Jasinski, J. Montaner, R. C. Forrey, B. H. Yang, P. C. Stancil, Naduvalath Balakrishnan, J. Dai, A. Vargas-Hernandez, R. V. Krems

Chemistry and Biochemistry Faculty Research

Quantum scattering calculations for all but low-dimensional systems at low energies must rely on approximations. All approximations introduce errors. The impact of these errors is often difficult to assess because they depend on the Hamiltonian parameters and the particular observable under study. Here, we illustrate a general, system- and approximation-independent, approach to improve the accuracy of quantum dynamics approximations. The method is based on a Bayesian machine learning (BML) algorithm that is trained by a small number of exact results and a large number of approximate calculations, resulting in ML models that can generalize exact quantum results to different dynamical …

Self-Stabilizing Token Distribution On Trees With Constant Space, Yuichi Sudo, Ajoy K. Datta, Lawrence L. Larmore, Toshimitsu Masuzawa

Computer Science Faculty Research

Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most l tokens. Our goal is to distribute the tokens uniformly in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be nk where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of …

Modified Surrogate Cutting Plane Algorithm (Mscpa) For Integer Linear Programming Problems, Israa Hasan

Emirates Journal for Engineering Research

This work concerned with introducing a new algorithm for solving integer linear programming problems. The improved algorithm can help by decreasing a calculation the complexity of these problems, an advantages of the proposed method are to reduce the solution time and to decrease algorithmic complexity. Some specific numerical examples are discussed to demonstrate the validity and applicability of the proposed method. The numerical results are compared with the solution of integer linear programming problems by using cutting plane method (Gomory method).

A 3d Image-Guided System To Improve Myocardial Revascularization Decision-Making For Patients With Coronary Artery Disease, Haipeng Tang

Dissertations

OBJECTIVES. Coronary artery disease (CAD) is the most common type of heart disease and kills over 360,000 people a year in the United States. Myocardial revascularization (MR) is a standard interventional treatment for patients with stable CAD. Fluoroscopy angiography is real-time anatomical imaging and routinely used to guide MR by visually estimating the percent stenosis of coronary arteries. However, a lot of patients do not benefit from the anatomical information-guided MR without functional testing. Single-photon emission computed tomography (SPECT) myocardial perfusion imaging (MPI) is a widely used functional testing for CAD evaluation but limits to the absence of anatomical information. …

Adaptive Task Sampling For Meta-Learning, Chenghao Liu, Zhihao Wang, Doyen Sahoo, Yuan Fang, Kun Zhang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Meta-learning methods have been extensively studied and applied in computer vision, especially for few-shot classification tasks. The key idea of meta-learning for few-shot classification is to mimic the few-shot situations faced at test time by randomly sampling classes in meta-training data to construct fewshot tasks for episodic training. While a rich line of work focuses solely on how to extract meta-knowledge across tasks, we exploit the complementary problem on how to generate informative tasks. We argue that the randomly sampled tasks could be sub-optimal and uninformative (e.g., the task of classifying “dog” from “laptop” is often trivial) to the meta-learner. …

An Exact Algorithm For Agile Earth Observation Satellite Scheduling With Time-Dependent Profits, Guansheng Peng, Guopeng Song, Lining Xing, Aldy Gunawan, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

The scheduling of an Agile Earth Observation Satellite (AEOS) consists of selecting and scheduling a subset of possible targets for observation in order to maximize the collected profit related to the images while satisfying its operational constraints. In this problem, a set of candidate targets for observation is given, each with a time-dependent profit and a visible time window. The exact profit of a target depends on the start time of its observation, reaching its maximum at the midpoint of its visible time window. This time dependency stems from the fact that the image quality is determined by the look …