Theory and Algorithms Commons^™

A Proof Of Np-Completeness For The K-Means Clustering Algorithm, Brooke C. Feinberg

Scripps Senior Theses

The k-means clustering algorithm is one of the most widely used clustering techniques in data analysis and machine learning, yet its exact computational complexity remains subject to ongoing theoretical investiga- tion. This work establishes the NP-completeness of k-means by proving (1) it is NP-hard and (2) it lies in NP. To demonstrate NP-hardness, we construct a series of polynomial-time reductions from well-known NP-complete problems. Specifically, we reduce 3sat to Vertex Cover, and then reduce Vertex Cover to k-means, thereby establishing the computational hardness of the k-means clustering problem. We then prove k-means is in NP, and thus conclude it is …

Ai For Nuclear Physics: The Exclaim Project, S. Liuti, D. Adams, M. Boër, G. W. Chern, M. Cuic, M. Engelhardt, G. R. Goldstein, B. Kriesten, Y. Li, H. W. Lin, M. Sievert, D. Sivers

Computer Science Faculty Publications

An overview of the recent activity of the newly funded EXCLusives with AI and Machine learning (EXCLAIM) collaboration is presented. The main goal of the collaboration is to develop a framework to implement AI and machine learning techniques in problems emerging from the phenomenology of high energy exclusive scattering processes from nucleons and nuclei, maximizing the information that can be extracted from various sets of experimental data, while implementing theoretical constraints from lattice QCD. A specific perspective embraced by EXCLAIM is to use the methods of theoretical physics to understand the working of ML, beyond its standardized applications to physics …

Fares On Fairness: Using A Total Error Framework To Examine The Role Of Measurement And Representation In Training Data On Model Fairness And Bias, Patrick Oliver Schenk, Christoph Kern, Trent D. Buskirk

Information Technology & Decision Sciences Faculty Publications

Data-driven decisions, often based on predictions from machine learning (ML) models are becoming ubiquitous. For these decisions to be just, the underlying ML models must be fair, i.e., work equally well for all parts of the population such as groups defined by gender or age. What are the logical next steps if, however, a trained model is accurate but not fair? How can we guide the whole data pipeline such that we avoid training unfair models based on inadequate data, recognizing possible sources of unfairness early on? How can the concepts of data-based sources of unfairness that exist in the …

Optimizing Decision-Making In A Cerebral Palsy Model Using Reinforcement Learning, Richard Ampah

Pitzer Senior Theses

This study presents an original interdisciplinary investigation into how reinforcement learning (RL) can model motor and cognitive defects and potentially improve motor and cognitive functions in individuals with cerebral palsy (CP), a non-progressive neurological disorder that impairs movement and adaptability. Integrating computational neuroscience and machine learning, the research applies policy gradient methods and Markov Decision Processes (MDPs) to simulate adaptive learning in agents with and without CP-related constraints.

The central aim is to compare the cumulative rewards of optimal policies, derived from value iteration, and human-like learning policies using the REINFORCE algorithm, both with and without the Bellman baseline. The …

Ripples: An Automated Embedding Generation Algorithm For The Forward-Forward Algorithm, Spencer Connolly

All Graduate Theses, Dissertations, and Other Capstone Projects

The Forward-Forward algorithm (FF) is yet another novel invention by Geoffrey Hinton, the creator of the famous backpropagation algorithm (BP). Since its proposal, many papers have been published exploring its potential, and good progress has been made in increasing its viability. Though FF continually falls short of BP, its purpose is not to replace BP and preliminary research shows that there is plenty of room for growth. In this paper, we present a literature review for FF algorithms applied to Convolution Neural Networks (CNN) for image classification tasks and set the stage for applying FF to more complex datasets. The …

Empirical Analysis Of Political Districting Splitability Via Uniform Spanning Trees In Polynomial Time, Brooke C. Feinberg

Scripps Senior Theses

This work expands a recently proven conjecture that a polynomial fraction of all uniform spanning trees (USTs) are splittable into k balanced partitions on grid graphs to real-world political districting plans. We investigate whether similar structural properties hold for the planar dual graphs of U.S. counties (cnty) and tracts (t), using Wilson’s algorithm to generate uniform random spanning trees and Breadth- First Search (BFS) to check for splitability into balanced partitions. Our empirical findings suggest that real-world districting plans can be split into 2-balanced, connected partitions in a fraction of polynomial time. This result highlights the potential for scalable redistricting …

Analyzing Political Sentiment On Micro-Blogging Data: A Lexicon And Machine Learning Approach To The 2024 U.S. Presidential Election, Ava Grey

CMC Senior Theses

This paper explores the trends in sentiment towards U.S. presidential candidates Kamala Harris and Donald Trump through micro-blogging social media text during the five months leading up to the election. Two datasets of varying sizes and origins were used to contextualize and validate analysis findings. The analyses include both a lexicon-based approach and a machine learning predictive method. Common sentiment analysis techniques like term frequency, term frequency inverse, various lexicons, and n-grams were utilized during the lexicon approach. During the modeling, a random forest was utilized in addition to the methods used during the lexicon approach. Results showed that overall …

A Two-Phase Learning Approach Integrated With Multi-Source Features For Cloud Service Qos Prediction, Fuzan Chen, Jing Yang, Haiyang Feng, Harris Wu, Minqiang Li

Information Technology & Decision Sciences Faculty Publications

Quality of Service (QoS) is a key factor for users when choosing cloud services. However, QoS values are often unavailable due to insufficient user evaluations or provider data. To address this, we propose a new QoS prediction method, Multi-source Feature Two-phase Learning (MFTL). MFTL incorporates multiple sources of features influencing QoS and uses a two-phase learning framework to make effective use of these features. In the first phase, coarse-grained learning is performed using a neighborhood-integrated matrix factorization model, along with a strategy for selecting high-quality neighbors for target users. In the second phase, reinforcement learning through a deep neural network …

Fares On Fairness: Using A Total Error Framework To Examine The Role Of Measurement And Representation In Training Data On Model Fairness And Bias, Patrick Oliver Schenk, Christoph Kern, Trent D. Buskirk

Data Science Faculty Publications

Data-driven decisions, often based on predictions from machine learning (ML) models are becoming ubiquitous. For these decisions to be just, the underlying ML models must be fair, i.e., work equally well for all parts of the population such as groups defined by gender or age. What are the logical next steps if, however, a trained model is accurate but not fair? How can we guide the whole data pipeline such that we avoid training unfair models based on inadequate data, recognizing possible sources of unfairness early on? How can the concepts of data-based sources of unfairness that exist in the …

Quantifying The Transfer Effectiveness Of An Artificial Intelligence-Based Simulator Pre-Training Program For Student Pilots, Ryan Guthridge

Journal of Aviation/Aerospace Education & Research

Since the airline pilot shortage was initially studied in 2016, the pilot hiring model has been significantly impacted, with airlines hiring qualified pilots at unprecedented rates. The COVID-19 pandemic has slowed this hiring rate, however it is expected that airline hiring will soon increase to a rate higher than initially expected (Bureau of Transportation Statistics, 2022). With this dynamic, certified flight instructors are often the most qualified recruits for airlines, due to the number of hours and experience they have gained in the flight training organization. In turn, certified flight instructors are in short supply for flight training organizations worldwide. …

Sampling Balanced High-Quality Data To Train An Automatic Mesh Generator, Jie Pan, Jingwei Huang, Gengdong Cheng, Yong Zeng

Engineering Management & Systems Engineering Faculty Publications

In real-world scenarios, high-quality data are often scarce and imbalanced, yet it is essential for the optimal performance of data-driven algorithmic models. Data synthesis methods are commonly used to address this issue; however, they typically rely heavily on the original dataset, which limits their ability to significantly improve performance. This article presents a quality function-based method for directly generating high-quality data and applies it to a mesh generation algorithm to demonstrate its efficiency and effectiveness. The proposed approach samples input-output pairs of the algorithm based on their feature spaces, selects high-quality samples using a defined quality function that evaluates the …

Large Scale Machine Learning Over Knowledge Graphs, Bedirhan Gergin

Electronic Theses & Dissertations (2024 - present)

Knowledge graphs (KGs) have become popular across various fields, providing convenient access to web-based knowledge while storing and formalizing domain-specific information. By analyzing KGs, patterns, connections, and dependencies can be identified across different data sources, enabling the inference of new knowledge from given facts. As the use of KGs expands, the size of modern KGs has grown significantly, making them impossible to process within the main memory of a single computer. Distributed computing offers a viable solution to this challenge by leveraging the combined capabilities of multiple servers within a cluster. This thesis explores how distributed computing can be effectively …

Visualization Of Paleocurrents On A Web Application Using Gplates, Anjan Sapkota

MS in Computer Science Theses

Paleocurrents are flow directions derived from features of sedimentary rocks that reveal the direction of the current of wind or water that deposited the sediment. In 2015, Brand et al. created a global database of paleocurrents, which contains over 1,000,000 measurements worldwide: North America, South America, Australia, Great Britain, parts of Western Europe, China, Africa are fairly well represented; Antarctica, Eastern Europe, and Asia are modestly represented and Russia is poorly represented. The contribution of this thesis is a web application that uses the GPlates’ Application Programming Interface (API) to visualize global paleocurrents through time in an interactive way based …

Decoding Neural Networks: An Information-Theoretic Guide To Interpretability, Error Analysis And Efficiency, Mackenzie J. Meni

Theses and Dissertations

This dissertation addresses critical challenges in neural network design by leveraging entropy-based techniques to improve model efficiency, interpretability, and bias reduction. Focusing on the unique demands of computer vision applications, particularly object detection and classification for real-time systems, this work introduces a series of innovative methods centered on information theory. At the core of these methods is the Probabilistic Explanations of Entropic Knowledge (PEEK) framework, a tool developed to analyze and visualize entropy distributions across feature maps. PEEK offers insights into information flow within neural networks, making it possible to pinpoint layers that contribute meaningfully to decision-making or identify those …

Holistic Correlation Measure For Enhanced Encapsulation Of Trait Heterogeneity And Discovery Of Co-Expression, Zachary Valleroy

Theses

Large-scale, high-dimensional data analyses can be computationally prohibitive due to combinatorial explosion of the search space for finding complex patterns; a viable alternative is network modeling for abstraction and quantifying intrinsic data associations. Prominent network analysis methods furnish frameworks for model synthesis and validation but rely on standard correlation measures impaired by semi-supervised biases, latent heterogeneity, and uneven discretization techniques. Here we investigate a holistic measure for encapsulating data heterogeneity for enhanced efficacy of revealing complex patterns through network analysis. Our unique correlation metric, K-medoids Utility for Duo Original Similarities (Kudos), exhaustively factors real-valued analyte data to compute …

Competitive Conquest: Charting The Climb To Pokémon Supremacy, Robert Dilworth

BCoE Publications

This manuscript presents a comprehensive exploration of optimizing Pokémon gameplay through data-driven methodologies, aimed at enhancing competitive performance in high-stakes environments. In the first section, we introduce a robust Pokémon teambuilding algorithm that leverages statistical analysis of championship-winning compositions. By employing multiple linear regression techniques, we predict team performance based on critical factors such as Base Stat Totals (BSTs) and various coverage types. This integration of data science principles into Pokémon strategy underscores the importance of offensive capabilities over defensive considerations, ultimately contributing to advancements in teambuilding strategies. Our proficiency in R programming facilitated the development of an efficient codebase …

Review Of Current Trends In Information Technology Concerning Phonetic Similarity”, Zaid Rajih Mohammed, Ahmed H. Aliwy

Al-Bahir

With the increasing availability of textual information in various languages via the Internet in homes and companies through Internet and intranet services, there is an urgent need for the technologies and tools necessary to process this information, phonetic representation, and voice interaction. For example voice to voice machine translation need to phonetic mapping and similarity among the languages especially for names and foreign words. This one example of the importance of phonetic mapping and similarity. This article aims to describe, in detail, the recent surge in interest and advancements in phonetic similarity (PS), phonetic representation, and phonetic mapping researches. PS …

Leveraging Tradespace-Exploration For A Senior Project Team Formation Application, Miguel Saenz

College of Engineering Summer Undergraduate Research Program

This project revolves around the development of an app in MATLAB that leverages the VASSAR rule-based system and a genetic algorithm to form groups of teams for the Mechanical Engineering Senior Design project class. We leveraged the iterative design process to eventually attain a functional app with a reasonable runtime that works provided correctly formatted rulesheets describing student project preference and member preference.

Optimization Strategies To Enhance Performance In Matrix/Tensor Factorization And Multi-Source Data Integration, Mengyuan Zhang

All Dissertations

Optimization in the realm of machine learning constitutes a fundamental process aimed at refining the parameters of models to enhance their performance. It serves as the backbone of various machine learning techniques, encompassing diverse algorithms and methodologies tailored to address specific tasks and objectives.

In machine learning, datasets are commonly structured as matrices or tensors, making techniques like matrix factorization and tensor factorization indispensable for extracting meaningful representations from intricate data. Furthermore, datasets commonly comprise multiple sets of features, which has inspired our exploration of effective strategies for leveraging information from diverse sources during optimization. Additionally, the interconnected nature of …

Riesz Particle Markov Chain Monte Carlo Methods, Xiongming Dai

LSU Doctoral Dissertations

Markov chain Monte Carlo (MCMC) methods are simulations that explore complex statistical distributions, while bypassing the cumbersome requirement of a specific analytical expression for the target. This stochastic exploration of an uncertain parameter space comes at the expense of a large number of ``burn-in'' samples, and the computational complexity leads to the curse of dimensionality. Although at the exploration level, some methods have been proposed to accelerate the convergence of the algorithm, such as tempering, Hamiltonian Monte Carlo, Rao-redwellization, and scalable methods for better performance, they cannot avoid the stochastic nature of this exploration. We develop algorithms for the energy …

Capturing Higher-Order Relationships Through Information Decomposition, Aobo Lyu

McKelvey School of Engineering Graduate Student Theses & Dissertations

Mutual information between two random variables is a well-studied notion, whose understanding is fairly complete. Mutual information between one random variable and a pair of other random variables, however, is a far more involved notion. Specifically, Shannon's mutual information does not capture fine-grained interactions between those three variables, resulting in limited insights in complex systems. To capture these fine-grained higher-order interactions among variables, Williams and Beer proposed a framework called Partial Information Decomposition (PID) to decompose this mutual information to information atoms, called unique, redundant, and synergistic, and proposed several operational axioms that these atoms must satisfy. This conceptual …

Murmurations And Root Numbers, Alexey Pozdnyakov

University Scholar Projects

We report on a machine learning investigation of large datasets of elliptic curves and L-functions. This leads to the discovery of murmurations, an unexpected correlation between the root numbers and Dirichlet coefficients of L-functions. We provide a formal definition of murmurations, describe the connection with 1-level density, and provide three examples for which the murmuration phenomenon has been rigorously proven. Using our understanding of murmurations, we then build new machine learning models in search of a polynomial time algorithm for predicting root numbers. Based on our models and several heuristic arguments, we conclude that it is unlikely for …

Comparative Predictive Analysis Of Stock Performance In The Tech Sector, Asaad Sendi

LSU New Orleans Theses and Dissertations

This study compares the performance of deep learning models, including Long Short-Term Memory (LSTM), Gated Recurrent Unit (GRU), and Transformer, in predicting stock prices across five companies (AAPL, CSCO, META, MSFT, and TSLA) from July 2019 to July 2023. Key findings reveal that GRU models generally exhibit the lowest Mean Absolute Error (MAE), indicating higher precision, particularly notable for CSCO with a remarkably low MAE. While LSTM models often show slightly higher MAE values, they outperform Transformer models in capturing broader trends and variance in stock prices, as evidenced by higher R-squared (R2) values. Transformer models generally exhibit higher MAE …

Subject Analysis Ex Machina: Developing A Subject Heading Recommendation Service For Jmu Libraries, Steven W. Holloway

Libraries

Results of a 2022 evaluation of ANNIF, open-source software designed to generate controlled vocabulary subject headings, using James Madison University Libraries resources.

Techniques To Detect Fake Profiles On Social Media Using The New Age Algorithms – A Survey, A K M Rubaiyat Reza Habib, Edidiong Elijah Akpan

ATU Scholars Symposium

This research explores the growing issue of fake accounts in Online Social Networks [OSNs]. While platforms like Twitter, Instagram, and Facebook foster connections, their lax authentication measures have attracted many scammers and cybercriminals. Fake profiles conduct malicious activities, such as phishing, spreading misinformation, and inciting social discord. The consequences range from cyberbullying to deceptive commercial practices. Detecting fake profiles manually is often challenging and causes considerable stress and trust issues for the users. Typically, a social media user scrutinizes various elements like the profile picture, bio, and shared posts to identify fake profiles. These evaluations sometimes lead users to conclude …

Mathematically Rigorous Deep Learning Paradigms For Data-Driven Scientific Modeling, Owen Nicholas Davis

Mathematics & Statistics ETDs

This dissertation explores the crucial role of data-driven modeling in science and engineering, with a focus on developing surrogate models to accelerate large-scale computational tasks, aiding in both outer-loop functions like uncertainty quantification and expensive inner-loop tasks within broader computational frameworks. Challenges arise with increased problem dimension and sparse, noisy training data, particularly significant when constructing surrogates for very expensive computational models where acquiring sufficient high-fidelity training data is unfeasible. In such scenarios, training surrogates from an ensemble of multifidelity information sources of varying accuracy and cost becomes essential. We emphasize neural network-based modeling paradigms, which are flexible in integrating …

Improving Educational Delivery And Content In Juvenile Detention Centers, Yomna Elmousalami

Undergraduate Research Symposium

Students in juvenile detention centers have the greatest need to receive improvements in educational delivery and content; however, they are one of the “truly disadvantaged” populations in terms of receiving those improvements. This work presents a qualitative data analysis based on a focus group meeting with stakeholders at a local Juvenile Detention Center. The current educational system in juvenile detention centers is based on paper worksheets, single-room style teaching methods, outdated technology, and a shortage of textbooks and teachers. In addition, detained students typically have behavioral challenges that are deemed "undesired" in society. As a result, many students miss classes …

Multi-Modality Transformer For E-Commerce: Inferring User Purchase Intention To Bridge The Query-Product Gap, Srivatsa Mallapragada

Dissertations

The rapid growth of e-commerce has necessitated the development of sophisticated product retrieval systems that can effectively match user queries with relevant products. However, the semantic gap between queries and products remains a significant challenge, as traditional retrieval methods often fail to capture the nuances of user purchase intentions. E-commerce click-stream data and product catalogs offer critical user behavior insights and product knowledge that are untapped in the current product search algorithms. This dissertation presents learning strategies that leverage the query-product transaction logs to enrich the pipeline of our proposed multi-modal transformer model, which transforms initial user queries into pseudo …

Mechanistic Investigation Of C—C Bond Activation Of Phosphaalkynes With Pt(0) Complexes, Roberto M. Escobar, Abdurrahman C. Ateşin, Christian Müller, William D. Jones, Tülay Ateşin

Research Symposium

Carbon–carbon (C–C) bond activation has gained increased attention as a direct method for the synthesis of pharmaceuticals. Due to the thermodynamic stability and kinetic inaccessibility of the C–C bonds, however, activation of C–C bonds by homogeneous transition-metal catalysts under mild homogeneous conditions is still a challenge. Most of the systems in which the activation occurs either have aromatization or relief of ring strain as the primary driving force. The activation of unstrained C–C bonds of phosphaalkynes does not have this advantage. This study employs Density Functional Theory (DFT) calculations to elucidate Pt(0)-mediated C–CP bond activation mechanisms in phosphaalkynes. Investigating the …

Sepsis Treatment: Reinforced Sequential Decision-Making For Saving Lives, Dipesh Tamboli, Jiayu Chen, Kiran Pranesh Jotheeswaran, Denny Yu, Vaneet Aggarwal

Graduate Industrial Research Symposium

Sepsis, a life-threatening condition triggered by the body's exaggerated response to infection, demands urgent intervention to prevent severe complications. Existing machine learning methods for managing sepsis struggle in offline scenarios, exhibiting suboptimal performance with survival rates below 50%. Our project introduces the "PosNegDM: Reinforcement Learning with Positive and Negative Demonstrations for Sequential Decision-Making" framework utilizing an innovative transformer-based model and a feedback reinforcer to replicate expert actions while considering individual patient characteristics. A mortality classifier with 96.7% accuracy guides treatment decisions towards positive outcomes. The PosNegDM framework significantly improves patient survival, saving 97.39% of patients and outperforming established machine learning …