Browsing by Author "Whitley, Darrell, advisor"

Now showing 1 - 12 of 12

Open Access
Automatic question detection from prosodic speech analysis
(Colorado State University. Libraries, 2019) Hirsch, Rachel, author; Draper, Bruce, advisor; Whitley, Darrell, advisor; Kirby, Michael, committee member
Human-agent spoken communication has become ubiquitous over the last decade, with assistants such as Siri and Alexa being used more every day. An AI agent needs to understand exactly what the user says to it and respond accurately. To correctly respond, the agent has to know whether it is being given a command or asked a question. In Standard American English (SAE), both word choice and intonation of the speaker are necessary to discern the true sentiment of an utterance. Much Natural Language Processing (NLP) research has been done into automatically determining these sentence types using word choice alone. However, intonation is ultimately the key to understanding the sentiment of a spoken sentence. This thesis uses a series of attributes to characterize vocal prosody of utterances to train classifiers to detect questions. The dataset used to train these classifiers is a series of hearings by the Supreme Court of the United States (SCOTUS). Prosody-trained classifier results are compared against a text-based classifier, using Google Speech-to-Text transcriptions of the same dataset.
Open Access
Constructing subtle higher order mutants from Java and AspectJ programs
(Colorado State University. Libraries, 2015) Omar, Elmahdi, author; Ghosh, Sudipto, advisor; Whitley, Darrell, advisor; Bieman, James M., committee member; Turk, Daniel E., committee member
Mutation testing is a fault-based testing technique that helps testers measure and improve the fault-detection effectiveness of their test suites. However, a majority of traditional First Order Mutants (FOMs), which are created by making a single syntactic change to the source code, represent trivial faults that are often easily detected (i.e. killed). Research has shown that the majority of real faults not detected during testing are complex faults that cannot be simulated with FOMs because fixing these faults requires making multiple changes to the source code. Higher Order Mutants (HOMs), which are created by making multiple syntactic changes to the source code, can be used to simulate such faults. The majority of HOMs of a given program are killed by any test suite that kills all the FOMs. We refer to HOMs that are not killed as subtle HOMs. They represent cases where single faults interact by masking each other with respect to the given test suite and produce complex faulty behavior that cannot be simulated with FOMs. The fault-detection effectiveness of the given test suite can be improved by adding test cases that detect the faults denoted by subtle HOMs. Because subtle HOMs are rare in the exponentially large space of candidate HOMs, the cost of finding them can be high even for small programs. A brute force approach that evaluates every HOM in the search space by constructing, compiling, and executing the HOM against the given test suite is unrealistic. We developed a set of search techniques for finding subtle HOMs in the context of Java and AspectJ programming languages. We chose Java because of its popularity, and the availability of experimental tools and open source programs. We chose AspectJ because of its unique concepts and constructs and their consequent testing challenges. We developed four search-based software engineering techniques: (1)~Genetic Algorithm, (2)~Local Search, (3)~Test-Case Guided Local Search, (4)~Data-Interaction Guided Local Search. We also developed a Restricted Random Search technique and a Restricted Enumeration Search technique. Each search technique explores the search space in a different way and that affects the type of subtle HOMs that can be found by each technique. Each of the guided local search techniques uses a heuristic to improve the ability of Local Search to find subtle HOMs. Due to the unavailability of higher order mutation testing tools for AspectJ and Java programs, we developed HOMAJ, a Higher Order Mutation Testing tool for AspectJ and Java programs for finding subtle HOMs. HOMAJ implements the developed search techniques and automates the process of creating, compiling, and executing both FOMs and HOMs. The results of our empirical studies show that all of the search techniques were able to find subtle HOMs. However, Local Search and both the Guided Local Search techniques were more effective than the other techniques in terms of their ability to find subtle HOMs. The search techniques found more subtle HOMs by combining faults created by primitive Java mutation operators than by combining faults created by Java class level operators and AspectJ operators. Composing subtle HOMs of lower degrees generated by Restricted Enumeration Search is an effective way to find new subtle HOMs of higher degrees because such HOMs are likely to exist as compositions of multiple subtle HOMs of lower degrees. However, the search-based software engineering techniques were able to find subtle HOMs of higher degrees that could not be found by combining subtle HOMs of lower degrees.
Open Access
Exploring the bias of direct search and evolutionary optimization
(Colorado State University. Libraries, 2008) Lunacek, Monte, author; Whitley, Darrell, advisor
There are many applications in science that yield the following optimization problem: given an objective function, which set of input decision variables produce the largest or smallest result? Optimization algorithms attempt to answer this question by searching for competitive solutions within an application's domain. But every search algorithm has some particular bias. Our results show that search algorithms are more effective when they cope with the features that make a particular application difficult. Evolutionary algorithms are stochastic population-based search methods that are often designed to perform well on problems containing many local optima. Although this is a critical feature, the number of local optima in the search space is not necessarily indicative of problem difficulty. The objective of this dissertation is to investigate how two relatively unexplored problem features, ridges and global structure, impact the performance of evolutionary parameter optimization. We show that problems containing these features can cause evolutionary algorithms to fail in unexpected ways. For example, the condition number of a problem is one way to quantify a ridge feature. When a simple unimodal surface has a high condition number, we show that the resulting narrow ridge can make many evolutionary algorithms extremely inefficient. Some even fail. Similarly, funnels are one way of categorizing a problem's global structure. A single-funnel problem is one where the local optima are clustered together such that there exists a global trend toward the best solution. This trend is less predicable on problems that contain multiple funnels. We describe a metric that distinguishes problems based on this characteristic. Then we show that the global structure of the problem can render successful global search strategies ineffective on relatively simple multi-modal surfaces. Our proposed strategy that performs well on problems with multiple funnels is counter-intuitive. These issues impact two real-world applications: an atmospheric science inversion model and a configurational chemistry problem. We find that exploiting ridges and global structure results in more effective solutions on these difficult real-world problems. This adds integrity to our perspective on how problem features interact with search algorithms, and more clearly exposes the bias of direct search and evolutionary algorithms.
Open Access
Helping humans and agents avoid undesirable consequences with models of intervention
(Colorado State University. Libraries, 2021) Weerawardhana, Sachini Situmini, author; Whitley, Darrell, advisor; Ray, Indrajit, committee member; Pallickara, Sangmi, committee member; Ortega, Francisco, committee member; Seger, Carol, committee member
When working in an unfamiliar online environment, it can be helpful to have an observer that can intervene and guide a user toward a desirable outcome while avoiding undesirable outcomes or frustration. The Intervention Problem is deciding when to intervene in order to help a user. The Intervention Problem is similar to, but distinct from, Plan Recognition because the observer must not only recognize the intended goals of a user but also when to intervene to help the user when necessary. In this dissertation, we formalize a family of intervention problems to address two sub-problems: (1) The Intervention Recognition Problem, and (2) The Intervention Recovery Problem. The Intervention Recognition Problem views the environment as a state transition system where an agent (or a human user), in order to achieve a desirable outcome, executes actions that change the environment from one state to the next. Some states in the environment are undesirable and the user does not have the ability to recognize them and the intervening agent wants to help the user in the environment avoid the undesirable state. In this dissertation, we model the environment as a classical planning problem and discuss three intervention models to address the Intervention Recognition Problem. The three models address different dimensions of the Intervention Recognition Problem, specifically the actors in the environment, information hidden from the intervening agent, type of observations and noise in the observations. The first model: Intervention by Recognizing Actions Enabling Multiple Undesirable Consequences, is motivated by a study where we observed how home computer users practice cyber-security and take action to unwittingly put their online safety at risk. The model is defined for an environment where three agents: the user, the attacker and the intervening agent are present. The intervening agent helps the user reach a desirable goal that is hidden from the intervening agent by recognizing critical actions that enable multiple undesirable consequences. We view the problem of recognizing critical actions as a multi-factor decision problem of three domain-independent metrics: certainty, timeliness and desirability. The three metrics simulate the trade-off between the safety and freedom of the observed agent when selecting critical actions to intervene. The second model: Intervention as Classical Planning, we model scenarios where the intervening agent observes a user and a competitor attempting to achieve different goals in the same environment. A key difference in this model compared to the first model is that the intervening agent is aware of the user's desirable goal and the undesirable state. The intervening agent exploits the classical planning representation of the environment and uses automated planning to project the possible outcomes in the environment exactly and approximately. To recognize when intervention is required, the observer analyzes the plan suffixes leading to the user's desirable goal and the undesirable state and learns the differences between the plans that achieve the desirable goal and plans that achieve the undesirable state using machine learning. Similar to the first model, learning the differences between the safe and unsafe plans allows the intervening agent to balance specific actions with those that are necessary for the user to allow some freedom. The third model: Human-aware Intervention, we assume that the user is a human solving a cognitively engaging planning task. When human users plan, unlike an automated planner, they do not have the ability to use heuristics to search for the best solution. They often make mistakes and spend time exploring the search space of the planning problem. The complication this adds to the Intervention Recognition Problem is that deciding to intervene by analyzing plan suffixes generated by an automated planner is no longer feasible. Using a cognitively engaging puzzle solving task (Rush Hour) we study how human users solve the puzzle as a planning task and develop the Human-aware Intervention model combining automated planning and machine learning. The intervening agent uses a domain specific feature set more appropriate for human behavior to decide in real time whether to intervene the human user. Our experiments using the benchmark planning domains and human subject studies show that the three intervention recognition models out performs existing plan recognition algorithms in predicting when intervention is required. Our solution to address the Intervention Recovery Problem goes beyond the typical preventative measures to help the human user recover from intervention. We propose the Interactive Human-aware Intervention where a human user solves a cognitively engaging planning task with the assistance of an agent that implements the Human-aware Intervention. The Interactive Human-aware Intervention is different from typical preventive measures where the agent executes actions to modify the domain such that the undesirable plan can not progress (e.g., block an action). Our approach interactively guides the human user toward the solution to the planning task by revealing information about the remaining planning task. We evaluate the Interactive Human-aware Intervention using both subjective and objective measures in a human subject study.
Open Access
In pursuit of industrial like MAXSAT with reduced MAX-3SAT random generation
(Colorado State University. Libraries, 2024) Floyd, Noah R., author; Whitley, Darrell, advisor; Sreedharan, Sarath, committee member; Aristoff, David, committee member
In the modern landscape of MAXSAT, there are two broad classifications of problems: Random MAX-3SAT and Industrial SAT. Random MAX-3SAT problems by randomly sampling variables with a uniform probability and randomly assigning signs to the variable, one clause at a time. Industrial MAX-SAT consists of MAX-3SAT problems as encountered in the real world, and generally have a lower nonlinearity than random MAX-3SAT instances. One of the goals of recent research has been to figure out which rules and structures these industrial problems follow and how to replicate them randomly. This paper builds off of the paper" Reduction-Based MAX-3SAT with Low Nonlinearity and Lattices Under Recombination", implementing its approach to MAX-3SAT clause generation and determining what it can reveal about industrial MAX-13SAT and random MAX-3SAT. This builds off of the transformation from SAT to MAX-SAT problems and hopes to create random MAXSAT problems that are more representative of industrial MAXSAT problems. All this would be in the pursuit of random MAX-3SAT that more accurately maps onto real-world MAX-3SAT instances so that more efficient MAX-3SAT solvers can be produced.
Open Access
Late residual neural networks: an approach to combat the dead ReLU problem
(Colorado State University. Libraries, 2022) Ernst, Matthew Frederick, author; Whitley, Darrell, advisor; Anderson, Chuck, committee member; Buchanan, Norm, committee member
The rectified linear unit (ReLU) activation function has been a staple tool in deep learning to increase the performance of deep neural network architectures. However, the ReLU activation function has trade-offs with its performance, specifically the dead ReLU problem caused by vanishing gradients. In this thesis, we introduce "late residual connections" a type of residual neural network with connections from each hidden layer connected directly to the output layer of a network. These residual connections improve convergence for neural networks by allowing more gradient flow to the hidden layers of a network.
Open Access
Pruning visual transformers to increase model compression and decrease inference time
(Colorado State University. Libraries, 2024) Yost, James E., author; Whitley, Darrell, advisor; Ghosh, Sudipto, committee member; Betten, Anton, committee member
We investigate the efficacy of pruning a visual transformer during training to reduce inference time while maintaining accuracy. Various training techniques were explored, including epoch-based training, fixed-time training, and training to achieve a specific accuracy threshold. Results indicate that pruning from the inception of training offers significant reductions in inference time without sacrificing model accuracy. Different pruning rates were evaluated, demonstrating a trade-off between training speed and model compression. Slower pruning rates allowed for better convergence to higher accuracy levels and more efficient model recovery. Furthermore, we examine the cost of pruning and the recovery time of pruned models. Overall, the findings suggest that early-stage pruning strategies can effectively produce smaller, more efficient models with comparable or improved performance compared to non-pruned counterparts, offering insights into optimizing model efficiency and resource utilization in AI applications.
Open Access
Structure in combinatorial optimization and its effect on heuristic performance
(Colorado State University. Libraries, 2013) Hains, Doug, author; Whitley, Darrell, advisor; Howe, Adele, advisor; Bohm, Wim, committee member; Chong, Edwin, committee member
The goal in combinatorial optimization is to find a good solution among a finite set of solutions. In many combinatorial problems, the set of solutions scales at an exponential or greater rate with the instance size. The maximum boolean satisfiability (MAX-SAT) is one such problem that has many important theoretical and practical applications. Due to the exponential growth of the search space, sufficiently large instances of MAX-SAT are intractable for complete solvers. Incomplete solvers, such as stochastic local search (SLS) algorithms are necessary to find solutions in these cases. Many SLS algorithms for MAX-SAT have been developed on randomly generated benchmarks using a uniform distribution. As a result, SLS algorithms for MAX-SAT perform exceptionally well on uniform random instances. However, instances from real-world applications of MAX-SAT have a structure that is not captured in expectation by uniform random problems. The same SLS algorithms that perform well on uniform instances have a drastic drop in performance on structured instances. To better understand the performance drop on structured instances, we examine three characteristics commonly found in real-world applications of MAX-SAT: a power-law distribution of variables, clause lengths following a power-law distribution, and a community structure similar to that found in small-world models. We find that those instances with a community structure and clause lengths following a power-law distribution have a significantly more rugged search space and larger backbones than uniform random instances. These search space properties make it more difficult for SLS algorithms to find good solutions and in part explains the performance drop on industrial instances. In light of these findings, we examine two ways of improving the performance of SLS algorithms on industrial instances. First, we present a method of tractably computing the average evaluation of solutions in a subspace that we call a hyperplane. These averages can be used to estimate the correct setting of the backbone variables, with as high as 90% accuracy on industrial-like instances. By initializing SLS algorithms with these solutions, the search is able to find significantly better solutions than using standard initialization methods. Second, we re-examine the trade-offs between first and best improving search. We find that in many cases, the evaluation of solutions found by SLS algorithms using first improving search are no worse, and sometimes better, than those found by best improving. First improving search is significantly faster; using first improving search with AdaptG2WSAT, a state-of-the-art SLS algorithm for MAX-SAT, gives us more than a 1,000x speedup on large industrial instances. Finally, we use our hyperplane averages to improve the performance of complete solvers of the satisfiability problem (SAT), the decision version of MAX-SAT. We use the averages to heuristically select a promising hyperplane and perform a reduction of the original problem based on the chosen hyperplane. This significantly reduces the size of the space that must be searched by the complete solver. Using hyperplane reduction as a preprocessing step, a standard complete SAT solver is able to outperform many state-of-the-art complete solvers. Our contributions have advanced the understanding of structured instances and the performance of both SLS algorithms and complete solvers on these instances. We also hope that this work will serve as a foundation for developing better heuristics and complete solvers for real-world applications of SAT and MAX-SAT.
Open Access
Subnetwork ensembles
(Colorado State University. Libraries, 2023) Whitaker, Timothy J., author; Whitley, Darrell, advisor; Anderson, Charles, committee member; Krishnaswamy, Nikhil, committee member; Kirby, Michael, committee member
Neural network ensembles have been effectively used to improve generalization by combining the predictions of multiple independently trained models. However, the growing scale and complexity of deep neural networks have led to these methods becoming prohibitively expensive and time consuming to implement. Low-cost ensemble methods have become increasingly important as they can alleviate the need to train multiple models from scratch while retaining the generalization benefits that traditional ensemble learning methods afford. This dissertation introduces and formalizes a low-cost framework for constructing Subnetwork Ensembles, where a collection of child networks are formed by sampling, perturbing, and optimizing subnetworks from a trained parent model. We explore several distinct methodologies for generating child networks and we evaluate their efficacy through a variety of ablation studies and established benchmarks. Our findings reveal that this approach can greatly improve training efficiency, parametric utilization, and generalization performance while minimizing computational cost. Subnetwork Ensembles offer a compelling framework for exploring how we can build better systems by leveraging the unrealized potential of deep neural networks.
Open Access
The anteater analysis: a comparison of traveling salesman tour construction methods and their global frequencies
(Colorado State University. Libraries, 2022) Ourada, Shannon A., author; Whitley, Darrell, advisor; Ghosh, Sudipto, committee member; Clegg, Benjamin, committee member
For the Traveling Salesman Problem (TSP), many algorithms have been developed. These include heuristic solvers, such as nearest neighbors and ant colony optimization algorithms. In this work, the ATT48 and EIL101 instances are examined to better understand the difference between biased and unbiased methods of tour construction algorithms when combined with the 2-opt local search operator. First, a sample of tours are constructed. Then, we examine the frequencies of global edges of different sizes using n-grams. Using 2-opt as the tour improvement algorithm, we analyze randomly initialized local optima compared to nearest neighbors local optima as well as ant colony solutions with and without 2-opt. This comparison serves to better understand the nature of these different methods in their relation to the global optimum. We also provide some ways the algorithms may be adapted to take advantage of the global frequencies, particularly the ant colony optimization algorithm.
Open Access
The mixing genetic algorithm for traveling salesman problem
(Colorado State University. Libraries, 2022) Varadarajan, Swetha, author; Whitley, Darrell, advisor; Böhm, Wim, committee member; Beveridge, Ross, committee member; Chong, Edwin, committee member; Pouchet, Louis-Noël, committee member
The Traveling Salesman Problem (TSP) is one of the most intensively studied NP-Hard problems. The TSP solvers are well-suited for multi-core CPU-based architectures. With the decline in Moore's law, there is an increasing need to port the codes to parallel architectures such as the GPU massively. This thesis focuses on the Genetic Algorithm (GA) based TSP solvers. The major drawback in porting the state-of-the-art GA based TSP solver (called the Edge Assembly Crossover (EAX)) are (a) the memory per crossover operation is large and limits the scalability of the solver (b) the communication per crossover operation is random and not favorable for the SIMD machines. We designed a new solver, the Mixing Genetic Algorithm (MGA), using the Generalized Partition Crossover (GPX) operator to overcome these aspects. The GPX consumes 4 x lesser memory and does not access the memory during crossover operation. The MGA is used in three different modes. (1) MGA can converge fast on problems smaller than 2,000 cities as a single solver. (2) As a hybrid solver, together with EAX, it speeds up the convergence rate for problems up to 85,900 cities. (3) In an ensemble setting, together with EAX and an iterated local search (called the Lin-Kernighan Helsgaun (LKH) heuristic), it increases the success rate of some of the hard TSP instances. The MGA is parallelized on shared memory (using OpenMP), distributed memory (using MPI), and GPU (using CUDA). A combination of OpenMP and MPI parallelization is examined on problems ranging between 5,000 to 85,900 cities. We show near-linear speedup (proportional to the number of parallel units) on these instances. Preliminary results on GPU parallelization of the GPX crossover operator partition phase show a 48x to 625x speedup over the naive sequential implementation. This is the first step towards the fine-grain parallelization of GA operators for TSP. The results are tested on problems ranging from 10,000 to 2M cities.
Open Access
Use of traveling salesman problem solvers in the construction of genetic linkage maps
(Colorado State University. Libraries, 2015) Allen, Zachariah A., author; Whitley, Darrell, advisor; McConnell, Ross M., committee member; McKay, John, committee member
Construction of genetic linkage maps is an important tool for Biology. Researchers use a variety of laboratory techniques to extract genetic marker data from an experimental cross of a species of interest and then use these data to group the markers into chromosomes, and then construct maps of the locations of the markers within the chromosomes. This in turn allows them to determine which sections of the chromosomes are responsible for variation in agricultural, medical or other traits of interest. The current methods of constructing genetic linkage maps are tedious and time-consuming. This thesis presents a method of utilizing the Hamiltonian path problem (HPP) to solve the problem of genetic linkage mapping. Since solvers already exist for the traveling salesman problem (LKH and Concorde), by casting the linkage mapping problem as a HPP we can use these solvers to efficiently find the solution. To do this, the recombination frequencies between genetic markers are treated as internode weights and the TSP solution gives the lowest-cost path through the markers. By adding a dummy marker with zero weight to all other markers, the TSP solution is made equivalent to a HPP. The primary difficulty in constructing a linkage map is the fact that all data sets are noisy: errors in laboratory techniques create uncertainty in the relationships between genetic markers, so a straightforward HPP solution is not sufficient. This thesis describes a method of using the HPP to separate the raw data into clusters so that the researcher can be sure that the chromosomes are well-separated, the clusters can then be assembled into complete chromosomes using existing TSP solvers. The results show that this method produces results which are equally as good as the prevalent software in the field, while drastically decreasing the time required to run an analysis.