Theory and Algorithms Commons^™

A Fully Dynamic Algorithm For K-Regret Minimizing Sets, Yanhao Wang, Yuchen Li, Raymond Chi-Wing Wong, Kian-Lee Tan

Research Collection School Of Computing and Information Systems

Selecting a small set of representatives from a large database is important in many applications such as multi-criteria decision making, web search, and recommendation. The k-regret minimizing set (k-RMS) problem was recently proposed for representative tuple discovery. Specifically, for a large database P of tuples with multiple numerical attributes, the k-RMS problem returns a size-r subset Q of P such that, for any possible ranking function, the score of the top-ranked tuple in Q is not much worse than the score of the kth-ranked tuple in P. Although the k-RMS problem has been extensively studied in the literature, existing methods …

Urban Perception: Sensing Cities Via A Deep Interactive Multi-Task Learning Framework, Weili Guan, Zhaozheng Chen, Fuli Feng, Weifeng Liu, Liqiang Nie

Research Collection School Of Computing and Information Systems

Social scientists have shown evidence that visual perceptions of urban attributes, such as safe, wealthy, and beautiful perspectives of the given cities, are highly correlated to the residents' behaviors and quality of life. Despite their significance, measuring visual perceptions of urban attributes is challenging due to the following facts: (1) Visual perceptions are subjectively contradistinctive rather than absolute. (2) Perception comparisons between image pairs are usually conducted region by region, and highly related to the specific urban attributes. And (3) the urban attributes have both the shared and specific information. To address these problems, in this article, we present a …

Toward A Quantum Neural Network: Proposing The Qaoa Algorithm To Replace A Feed Forward Neural Network, Erick Serrano

Undergraduate Research Symposium Posters

With a surge in popularity of machine learning as a whole, many researchers have sought optimization methods to reduce the complexity of neural networks; however, only recent attempts have been made to optimize neural networks via quantum computing methods. In this paper, we describe the training process of a feed forward neural network (FFNN) and the time complexity of the training process. We highlight the inefficiencies of the FFNN training process, particularly when implemented with gradient descent, and introduce a call to action for optimization of a FFNN. Afterward, we discuss the strides made in quantum computing to improve the …

Network-Based Analysis Of Early Pandemic Mitigation Strategies: Solutions, And Future Directions, Pegah Hozhabrierdi, Raymond Zhu, Maduakolam Onyewu, Sucheta Soundarajan

Northeast Journal of Complex Systems (NEJCS)

Despite the large amount of literature on mitigation strategies for pandemic spread, in practice, we are still limited by naive strategies, such as lockdowns, that are not effective in controlling the spread of the disease in long term. One major reason behind adopting basic strategies in real-world settings is that, in the early stages of a pandemic, we lack knowledge of the behavior of a disease, and so cannot tailor a more sophisticated response. In this study, we design different mitigation strategies for early stages of a pandemic and perform a comprehensive analysis among them. We then propose a novel …

Optimizing Networking Topologies With Shortest Path Algorithms, Jordan Sahs

UNO Student Research and Creative Activity Fair

Communication networks tend to contain redundant devices and mediums of transmission, thus the need to locate, document, and optimize networks is increasingly becoming necessary. However, many people do not know where to start the optimization progress. What is network topology? What is this “Shortest Path Problem”, and how can it be used to better my network? These questions are presented, taught, and answered within this paper. To supplement the reader’s understanding there are thirty-eight figures in the paper that are used to help convey and compartmentalize the learning process needed to grasp the materials presented in the ending sections.

In …

Evaluation Of Algorithms For Randomizing Key Item Locations In Game Worlds, Caleb Johnson

LSU Master's Theses

In the past few years, game randomizers have become increasingly popular. In general, a game randomizer takes some aspect of a game that is usually static and shuffles it somehow. In particular, in this paper we will discuss the type of randomizer that shuffles the locations of items in a game where certain key items are needed to traverse the game world and access some of these locations. Examples of these types of games include series such as The Legend of Zelda and Metroid.

In order to accomplish this shuffling in such a way that the player is able to …

Quantum Simulation Of Schrödinger's Equation, Mohamed Eltohfa

Capstone and Graduation Projects

Quantum computing is one of the promising active areas in physics research. This is because of the potential of quantum algorithms to outperform their classical counterparts. Grover’s search algorithm has a quadratic speed-up compared to the classical linear search. The quantum simulation of Schrödinger’s equation has an exponential memory save-up compared to the classical simulation. In this thesis, the ideas and tools of quantum computing are reviewed. Grover’s algorithm is studied and simulated as an example. Using the Qiskit quantum computing library, a code to simulate Schrödinger’s equation for a particle in one dimension is developed, simulated locally, and run …

An Efficient Algorithm To Test Potential Bipartiteness Of Graphical Degree Sequences, Kai Wang

Theory & Applications of Graphs

As a partial answer to a question of Rao, a deterministic and customizable efficient algorithm is presented to test whether an arbitrary graphical degree sequence has a bipartite realization. The algorithm can be configured to run in polynomial time, at the expense of possibly producing an erroneous output on some ``yes'' instances but with very low error rate.

Efficient Algorithms For Trajectory-Aware Mobile Crowdsourcing, Chung-Kyun Han

Dissertations and Theses Collection (Open Access)

Mobile crowdsourcing, a subclass of crowdsourcing dealing with location-specific tasks, is prevalent in our daily life. From sensing urban environment such as noise, air pollution to package delivery, various location-specific tasks are posted on mobile crowdsourcing platforms to tap on the pool of crowdsourced workers. Many digital platforms compete with each other to expand and retain their pool of crowdsourced workers. Comparing with the traditional workforce, crowdsourced workers do not dedicate their time to do tasks fully and have strong spatiotemporal preferences. The ignorance of crowdsourced workers’ mobility patterns and the lack of personalization would lead to crowdsourced workers’ exodus, …

Wg2An: Synthetic Wound Image Generation Using Generative Adversarial Network, Salih Sarp, Murat Kuzlu, Emmanuel Wilson, Ozgur Guler

Engineering Technology Faculty Publications

In part due to its ability to mimic any data distribution, Generative Adversarial Network (GAN) algorithms have been successfully applied to many applications, such as data augmentation, text-to-image translation, image-to-image translation, and image inpainting. Learning from data without crafting loss functions for each application provides broader applicability of the GAN algorithm. Medical image synthesis is also another field that the GAN algorithm has great potential to assist clinician training. This paper proposes a synthetic wound image generation model based on GAN architecture to increase the quality of clinical training. The proposed model is trained on chronic wound datasets with various …

Improving Multi-Hop Knowledge Base Question Answering By Learning Intermediate Supervision Signals, Gaole He, Yunshi Lan, Jing Jiang, Wayne Xin Zhao, Ji Rong Wen

Research Collection School Of Computing and Information Systems

Multi-hop Knowledge Base Question Answering (KBQA) aims to find the answer entities that are multiple hops away in the Knowledge Base (KB) from the entities in the question. A major challenge is the lack of supervision signals at intermediate steps. Therefore, multi-hop KBQA algorithms can only receive the feedback from the final answer, which makes the learning unstable or ineffective. To address this challenge, we propose a novel teacher-student approach for the multi-hop KBQA task. In our approach, the student network aims to find the correct answer to the query, while the teacher network tries to learn intermediate supervision signals …

Laser Illuminated Imaging: Beam And Scene Deconvolution Algorithm, Benjamin W. Davis

Theses and Dissertations

Laser illuminated imaging systems deal with several physical challenges that must be overcome to achieve high-resolution images of the target. Noise sources like background noise, photon counting noise, and laser speckle noise will all greatly affect the imaging systems ability to produce a high-resolution image. An even bigger challenge to laser illuminated imaging systems is atmospheric turbulence and the effect that it will have on the imaging system. The illuminating beam will experience tilt, causing the beam to wander off the center of the target during propagation. The light returning to the detector will similarly be affected by turbulence, and …

Amplitude Estimation For The Large Clutter Discrete Removal Algorithm, Hannah Gjermo Chomitz

Theses and Dissertations

A large clutter discrete (LCD) is spectrally bright localized clutter that can cause a false alarm or missed target detection in space-time adaptive processing (STAP) radar data. For passive bistatic STAP, the four step LCD removal (LCDR) algorithm estimates the spatial/Doppler frequency and complex amplitude of the LCD and then removes it from the data. Once the LCD is removed from the data, homogeneous clutter suppression techniques can be used to process the data and search for targets. This research focuses on reducing the complexity of estimating the LCDs complex amplitude. This research proposes a method that directly solves for …

Optimizing Large-Scale Hyperparameters Via Automated Learning Algorithm, Bin Gu, Guodong Liu, Yanfu Zhang, Xiang Geng, Heng Huang

Machine Learning Faculty Publications

Modern machine learning algorithms usually involve tuning multiple (from one to thousands) hyperparameters which play a pivotal role in terms of model generalizability. Black-box optimization and gradient-based algorithms are two dominant approaches to hyperparameter optimization while they have totally distinct advantages. How to design a new hyperparameter optimization technique inheriting all benefits from both approaches is still an open problem. To address this challenging problem, in this paper, we propose a new hyperparameter optimization method with zeroth-order hyper-gradients (HOZOG). Specifically, we first exactly formulate hyperparameter optimization as an A-based constrained optimization problem, where A is a black-box optimization algorithm (such …

Unsupervised Data Mining Technique For Clustering Library In Indonesia, Robbi Rahim, Joseph Teguh Santoso, Sri Jumini, Gita Widi Bhawika, Daniel Susilo, Danny Wibowo

Library Philosophy and Practice (e-journal)

Organizing school libraries not only keeps library materials, but helps students and teachers in completing tasks in the teaching process so that national development goals are in order to improve community welfare by producing quality and competitive human resources. The purpose of this study is to analyze the Unsupervised Learning technique in conducting cluster mapping of the number of libraries at education levels in Indonesia. The data source was obtained from the Ministry of Education and Culture which was processed by the Central Statistics Agency (abbreviated as BPS) with url: bps.go.id/. The data consisted of 34 records where the attribute …

Modeling And Analysis Of Affiliation Networks With Subsumption, Alexey Nikolaev

Dissertations, Theses, and Capstone Projects

An affiliation (or two-mode) network is an abstraction commonly used for representing systems with group interactions. It consists of a set of nodes and a set of their groupings called affiliations. We introduce the notion of affiliation network with subsumption, in which no affiliation can be a subset of another. A network with this property can be modeled by an abstract simplicial complex whose facets are the affiliations of the network.

We introduce a new model for generating affiliation networks with and without subsumption (represented as simplicial complexes and hypergraphs, respectively). In this model, at each iteration, a constant number …

Visual Analysis Of Discrimination In Machine Learning, Qianwen Wang, Zhenghua Xu, Zhutian Chen, Yong Wang, Shixia Liu, Huamin Qu

Research Collection School Of Computing and Information Systems

The growing use of automated decision-making in critical applications, such as crime prediction and college admission, has raised questions about fairness in machine learning. How can we decide whether different treatments are reasonable or discriminatory? In this paper, we investigate discrimination in machine learning from a visual analytics perspective and propose an interactive visualization tool, DiscriLens, to support a more comprehensive analysis. To reveal detailed information on algorithmic discrimination, DiscriLens identifies a collection of potentially discriminatory itemsets based on causal modeling and classification rules mining. By combining an extended Euler diagram with a matrix-based visualization, we develop a novel set …

Divide And Capture: An Improved Cryptanalysis Of The Encryption Standard Algorithm Rsa, Willy Susilo, Joseph Tonien, Guomin Yang

Research Collection School Of Computing and Information Systems

RSA is a well known standard algorithm used by modern computers to encrypt and decrypt messages. In some applications, to save the decryption time, it is desirable to have a short secret key d compared to the modulus N. The first significant attack that breaks RSA with short secret key given by Wiener in 1990 is based on the continued fraction technique and it works with d < 1/4 root 18 N-.(25). A decade later, in 2000, Boneh and Durfee presented an improved attack based on lattice technique which works with d < N-.(292). Until this day, Boneh-Durfee attack remain as the best attack on RSA with short secret key. In this paper, we revisit the continued fraction technique and propose a new attack on RSA. Our main result shows that when d < root t (2 root 2 + 8/3) N-.(75)/root e, where e is the public exponent and t is a chosen parameter, our attack can break the RSA with the running time of O(tlog (N)). Our attack is especially well suited for the case where e is much smaller than N. When e approximate to N, the Boneh-Durfee attack outperforms ours. As a result, we could simultaneously run both attacks, our new attack and the classical Boneh-Durfee attack as a backup.

Norm-Based Generalisation Bounds For Deep Multi-Class Convolutional Neural Networks, Antoine Ledent, Waleed Mustafa, Yunwen Lei, Marius Kloft

Research Collection School Of Computing and Information Systems

We show generalisation error bounds for deep learning with two main improvements over the state of the art. (1) Our bounds have no explicit dependence on the number of classes except for logarithmic factors. This holds even when formulating the bounds in terms of the Frobenius-norm of the weight matrices, where previous bounds exhibit at least a squareroot dependence on the number of classes. (2) We adapt the classic Rademacher analysis of DNNs to incorporate weight sharing—a task of fundamental theoretical importance which was previously attempted only under very restrictive assumptions. In our results, each convolutional filter contributes only once …

Fine-Grained Generalization Analysis Of Vector-Valued Learning, Liang Wu, Antoine Ledent, Yunwen Lei, Marius Kloft

Research Collection School Of Computing and Information Systems

Many fundamental machine learning tasks can be formulated as a problem of learning with vector-valued functions, where we learn multiple scalar-valued functions together. Although there is some generalization analysis on different specific algorithms under the empirical risk minimization principle, a unifying analysis of vector-valued learning under a regularization framework is still lacking. In this paper, we initiate the generalization analysis of regularized vector-valued learning algorithms by presenting bounds with a mild dependency on the output dimension and a fast rate on the sample size. Our discussions relax the existing assumptions on the restrictive constraint of hypothesis spaces, smoothness of loss …