Computer Sciences Commons^™

Using Permutations Instead Of Student’S T Distribution For P-Values In Paired-Difference Algorithm Comparisons, Tony R. Martinez, Joshua Menke

Faculty Publications

The paired-difference t-test is commonly used in the machine learning community to determine whether one learning algorithm is better than another on a given learning task. This paper suggests the use of the permutation test instead hecause it calculates the exact p-value instead of an estimate. The permutation test is also distribution free and the time complexity is trivial for the commonly used 10-fold cross-validation paired-difference test. Results of experiments on real-world problems suggest it is not uncommon to see the t-test estimate deviate up to 30-50% from the exact p-value.

Feature Weighting Using Neural Networks, Tony R. Martinez, Xinchuan Zeng

Faculty Publications

In this work we propose a feature weighting method for classification tasks by extracting relevant information from a trained neural network. This method weights an attribute based on strengths (weights) of related links in the neural network, in which an important feature is typically connected to strong links and has more impact on the outputs. This method is applied to feature weighting br the nearest neighbor classifier and is tested on 15 real-world classification tasks. The results show that it can improve the nearest neighbor classifier on 14 of the 15 tested tasks, and also outperforms the neural network on …

Softprop: Softmax Neural Network Backpropagation Learning, Tony R. Martinez, Michael E. Rimer

Faculty Publications

Multi-layer backpropagation, like many learning algorithms that can create complex decision surfaces, is prone to overfitting. Softprop is a novel learning approach presented here that is reminiscent of the softmax explore-exploit Q-learning search heuristic It fits the problem while delaying settling into error minima to achieve better generalization and more robust learning. This is accomplished by blending standard SSE optimization with lazy training, a new objective function well suited to learning classification tasks, to form a more stable learning model. Over several machine learning data sets, softprop reduces classification error by 17.1 percent and the variance in results by 38.6 …

Preserving Trust Across Multiple Sessions In Open Systems, Fuk-Wing Thomas Chan

Theses and Dissertations

Trust negotiation, a new authentication paradigm, enables strangers on the Internet to establish trust through the gradual disclosure of digital credentials and access control policies. Previous research in trust negotiation does not address issues in preserving trust across multiple sessions. This thesis discusses issues in preserving trust between parties who were previously considered strangers. It also describes the design and implementation of trust preservation in TrustBuilder, a prototype trust negotiation system. Preserving trust information can reduce the frequency and cost of renegotiation. A scenario is presented that demonstrates that a server supporting trust preservation can recoup the cost of the …

Grouping Search-Engine Returned Citations For Person-Name Queries, Reema Al-Kamha

Theses and Dissertations

In this thesis we present a technique to group search-engine returned citations for person-name queries, such that the search-engine returned citations in each group belong to the same person. To group the returned citations we use a multi-faceted approach that considers evidence from three facets: (1) attributes, (2) links, and (3) page similarity. For each facet we generate a confidence matrix. Then we construct a final confidence matrix for all facets. Using a threshold, we apply a grouping algorithm on the final confidence matrix. The output is a group of search-engine returned citations, such that the citations in each group …

Learning Multiple Correct Classifications From Incomplete Data Using Weakened Implicit Negatives, Dan A. Ventura, Stephen Whiting

Faculty Publications

Classification problems with output class overlap create problems for standard neural network approaches. We present a modification of a simple feed-forward neural network that is capable of learning problems with output overlap, including problems exhibiting hierarchical class structures in the output. Our method of applying weakened implicit negatives to address overlap and ambiguity allows the algorithm to learn a large portion of the hierarchical structure from very incomplete data. Our results show an improvement of approximately 58% over a standard backpropagation network on the hierarchical problem.

Incremental Policy Learning: An Equilibrium Selection Algorithm For Reinforcement Learning Agents With Common Interests, Nancy Fulda, Dan A. Ventura

Faculty Publications

We present an equilibrium selection algorithm for reinforcement learning agents that incrementally adjusts the probability of executing each action based on the desirability of the outcome obtained in the last time step. The algorithm assumes that at least one coordination equilibrium exists and requires that the agents have a heuristic for determining whether or not the equilibrium was obtained. In deterministic environments with one or more strict coordination equilibria, the algorithm will learn to play an optimal equilibrium as long as the heuristic is accurate. Empirical data demonstrate that the algorithm is also effective in stochastic environments and is able …

Choosing A Starting Configuration For Particle Swarm Optimization, Mark Richards, Dan A. Ventura

Faculty Publications

The performance of Particle Swarm Optimization can be improved by strategically selecting the starting positions of the particles. This work suggests the use of generators from centroidal Voronoi tessellations as the starting points for the swarm. The performance of swarms initialized with this method is compared with the standard PSO algorithm on several standard test functions. Results suggest that CVT initialization improves PSO performance in high-dimensional spaces.

Task-Focused Summarization Of Email, Eric K. Ringger, Richard Campbell, Simon Corston-Oliver, Michael Gamon

Faculty Publications

We describe SmartMail, a prototype system for automatically identifying action items (tasks) in email messages. SmartMail presents the user with a task-focused summary of a message. The summary consists of a list of action items extracted from the message. The user can add these action items to their “to do” list.

Load Balancing Parallel Explicit State Model Checking, Rahul Kumar

Theses and Dissertations

This research first identifies some of the key concerns about the techniques and algorithms developed for distributed and parallel model checking; specifically, the inherent problem with load balancing and large queue sizes resultant in a static partition algorithm. This research then presents a load balancing algorithm to improve the run time performance in distributed model checking, reduce maximum queue size, and reduce the number of states expanded before error discovery. The load balancing algorithm is based on Generalized Dimension Exchange (GDE). This research presents an empirical analysis of the GDE based load balancing algorithm on three different supercomputing architectures---distributed memory …

Solving Large Mdps Quickly With Partitioned Value Iteration, David Wingate

Theses and Dissertations

Value iteration is not typically considered a viable algorithm for solving large-scale MDPs because it converges too slowly. However, its performance can be dramatically improved by eliminating redundant or useless backups, and by backing up states in the right order. We present several methods designed to help structure value dependency, and present a systematic study of companion prioritization techniques which focus computation in useful regions of the state space. In order to scale to solve ever larger problems, we evaluate all enhancements and methods in the context of parallelizability. Using the enhancements, we discover that in many instances the limiting …

Responding To Policies At Runtime In Trustbuilder, Michael D. Jones, Kent E. Seamons, Bryan Smith

Faculty Publications

To preview my talk, I will first give a brief overview of trust negotiation and policy exchange. Third, I will discuss the limitations of current compliance checkers and adaptations needed for trust negotiation. Finally, I will outline the contributions of this research.

Empirical Analysis Of Computational And Accuracy Tradeoffs Using Compactly Supported Radial Basis Functions For Surface Reconstruction, Weiming Liu, Bryan S. Morse, Lauralea Otis

Faculty Publications

Implicit surfaces can be constructed from scattered surface points using radial basis functions (RBFs) to interpolate the surface’s embedding function. Many researchers have used thin-plate spline RBFs for this because of their desirable smoothness properties. Others have used compactly supported RBFs, leading to a sparse matrix solution with lower computational complexity and better conditioning. However, the limited radius of support introduces a free parameter that leads to varying solutions as well as varying computational requirements: a larger radius of support leads to smoother and more accurate solutions but requires more computation. This paper presents an empirical analysis of this radius …

Responding To Policies At Runtime In Trustbuilder, Bryan J. Smith

Theses and Dissertations

Automated trust negotiation is the process of establishing trust between entities with no prior relationship through the iterative disclosure of digital credentials. One approach to negotiating trust is for the participants to exchange access control policies to inform each other of the requirements for establishing trust. When a policy is received at runtime, a compliance checker determines which credentials satisfy the policy so they can be disclosed. In situations where several sets of credentials satisfy a policy and some of the credentials are sensitive, a compliance checker that generates all the sets is necessary to insure that the negotiation succeeds …

Query Rewriting For Extracting Data Behind Html Forms, Xueqi Chen

Theses and Dissertations

Much of the information on the Web is stored in specialized searchable databases and can only be accessed by interacting with a form or a series of forms. As a result, enabling automated agents and Web crawlers to interact with form-based interfaces designed primarily for humans is of great value. This thesis describes a system that can fill out Web forms automatically according to a given user query against a global schema for an application domain and, to the extent possible, extract just the relevant data behind these Web forms. Experimental results on two application domains show that the approach …

Aggressive Telecommunications Overbooking Ratios, Robert Ball, Mark J. Clement, Casey T. Deccio, Feng Huang, Quinn O. Snell

Faculty Publications

The Internet is comprised of vast networks of wires and fiber. A common misconception is that there is an unlimited amount of bandwidth; in reality there exists only a finite amount. Each length of wire and fiber is owned by a company, and every company wants to maximize its profit. One means of improving profit is to overbook existing transmission lines in order to increase income without increasing expenses. If too much overbooking is performed, the Quality of Service (QoS) seen by customers will decline. This paper explains a process to achieve an optimal Overbooking Ratio (OR) for admission control …

A Piecewise Linear Approach To Overbooking, Robert Ball, Mark J. Clement, Casey T. Deccio, Feng Huang, Quinn O. Snell

Faculty Publications

Overbooking is frequently used to increase the revenue generated by a network infrastructure without incurring additional costs. If the overbooking factor is chosen appropriately, additional virtual circuits can be admitted without degrading quality of service for existing customers. Most implementations use a single factor to accept a linear fraction of traffic requests. If a piecewise linear approach is used in admissions, additional traffic can be accepted without causing proportional increases in loss rate and utilization. This additional accepted traffic can significantly improve the profit margin for network service providers.

Fast Registration Of Tabular Document Images Using The Fourier-Mellin Transform, Luke Alexander Daysh Hutchison

Theses and Dissertations

Image registration, the process of finding the transformation that best maps one image to another, is an important tool in document image processing. Having properly-aligned microfilm images can help in manual and automated content extraction, zoning, and batch compression of images. An image registration algorithm is presented that quickly identifies the global affine transformation (rotation, scale, translation and/or shear) that maps one tabular document image to another, using the Fourier-Mellin Transform. Each component of the affine transform is recovered independantly from the others, dramatically reducing the parameter space of the problem, and improving upon standard Fourier-Mellin Image Registration (FMIR), which …

Dynamic Autonomous Transport Selection In Heterogeneous Wireless Environments, Jeffrey M. Brown, Heidi R. Duffin, Charles D. Knutson, Shannon B. Barnes, Ryan W. Woodings

Faculty Publications

In this paper, we introduce Quality of Transport (QoT), an architecture for synergistically and autonomously managing session-layer protocol access to multiple transports in heterogeneous wireless environments. We present an overview of the QoT architecture including: 1) transport discovery, 2) service discovery, 3) object exchange, 4) transport switching, and 5) intelligent transport selection. Preliminary successes with our design and implementation of QoT suggest that dynamic intelligent autonomous transport switching can help to optimize user experience and session layer performance in multi-transport environments.

Prioritized Soft Constraint Satisfaction: A Qualitative Method For Dynamic Transport Selection In Heterogeneous Wireless Environments, Heidi R. Duffin, Michael A. Goodrich, Charles D. Knutson

Faculty Publications

This paper presents Prioritized Soft Constraint Satisfaction (PSCS), a novel approach to selecting the “best” transport in dynamic wireless transport switching systems. PSCS maintains a satisfying connection to another endpoint by choosing transports based on a user-established range of preferences and priority for criteria such as speed, power, range and cost. Additionally, feedback is provided regarding tradeoffs among the criteria, thus enabling the user to adjust inputs according to the capabilities of the system. We also recommend guidelines for setting preferences and priorities.

Guided Model Checking With A Bayesian Meta-Heuristic, Michael D. Jones, Peter Lamborn, Kevin Seppi

Faculty Publications

This paper presents a formal verification algorithm for finding errors in models of complex concurrent systems. The algorithm improves explicit guided model checking by applying the Empirical Bayes method to revise heuristic estimates of the distance from a given state to an error state. Guided search using the revised estimates finds errors with less search effort than the original estimates.

Fast Registration Of Tabular Document Images Using The Fourier-Mellin Transform, William A. Barrett, Luke A. D. Hutchison

Faculty Publications

A new technique is presented for quickly identifying global affine transformations applied to tabular document images, and to correct for those transformations. This technique, based on the Fourier-Mellin transform, is used to register (align) a set of tabular documents to each other. Each component of the affine transform is handled separately, which dramatically reduces the total parameter space of the problem. This method is robust, and deals with all components of the affine transform in a uniform way. The Fourier-Mellin transform is also extended to handle shear, which can approximate a small amount of perspective distortion, and to not need …

Digital Mountain: From Granite Archive To Global Access, William A. Barrett, Luke A. D. Hutchison, Douglas J. Kennard, Heath E. Nielson, Dallan Quass

Faculty Publications

Large-scale, multi-terabyte digital libraries are becoming feasible due to decreasing costs of storage, CPU, and bandwidth. However, costs associated with preparing content for input into the library remain high due to the amount of human labor required. This paper describes the Digital Microfilm Pipeline – a sequence of image processing operations used to populate a large-scale digital library from a “mountain” of microfilm and reduce the human labor involved. Essential parts of the pipeline include algorithms for document zoning and labeling, consensus-based template creation, reversal of geometric transformations and Just-In-Time Browsing, an interactive technique for progressive access of image content …

Integrating Perception, Language And Problem Solving In A Cognitive Agent For A Mobile Robot., Deryle W. Lonsdale, D. Paul Benjamin, Damian M. Lyons

Faculty Publications

We are implementing a unified cognitive architecture for a mobile robot. Our goal is to endow a robot agent with the full range of cognitive abilities, including perception, use of natural language, learning and the ability to solve complex problems. The perspective of this work is that an architecture based on a unified theory of robot cognition has the best chance of attaining human-level performance.

This agent architecture is an integration of three theories: a theory of cognition embodied in the Soar system, the RS formal model of sensorimotor activity and an algebraic theory of decomposition and reformulation.

These three …

A Study Of The Suitability Of Irobex For High-Speed Exchange Of Large Data Objects, Casey T. Deccio, Joseph Ekstrom, Charles D. Knutson, D. Ryan Partridge, Kevin B. Tew

Faculty Publications

This paper demonstrates that careful tuning of the OBEX and IrLAP negotiated parameters allows OBEX to scale well for use with large data objects and high transmission rates. Due to the substantial time overhead inherent in link turnarounds, minimizing turnarounds during the transmission of a large object helps to maximimize link efficiency. The IrLAP window size and OBEX packet size significantly impact the number of required turnarounds during the transmission of a large object. When these parameters are properly tuned, maximum throughput can be achieved, and OBEX performs efficiently at high data rates.

Trust Negotiation For Authentication And Authorization In Healthcare Information Systems, Charles D. Knutson, Kent E. Seamons, Tore L. Sundelin, David K. Vawdrey

Faculty Publications

The expanding availability of health information in an electronic format is strategic for industry-wide efforts to improve the quality and reduce the cnst of health care. The implementation of electronic medical record systems has been hindered by inadequate security provisions. This paper describes the use of frust negotiation as a framework for providing authentication and access control services in healthcare information systems. nust negotiation enables two parties with no pre-existing relationship to establish the trust necessary to perform sensitive transactions via the mutual disclosure of attributes contained within digital credentials. An extension of this system, surrogate irusf negoikiion is introduced …

Schema Matching And Data Extraction Over Html Tables, Cui Tao

Theses and Dissertations

Data on the Web in HTML tables is mostly structured, but we usually do not know the structure in advance. Thus, we cannot directly query for data of interest. We propose a solution to this problem for the case of mostly structured data in the form of HTML tables, based on document-independent extraction ontologies. The solution entails elements of table location and table understanding, data integration, and wrapper creation. Table location and understanding allows us to locate the table of interest, recognize attributes and values, pair attributes with values, and form records. Data-integration techniques allow us to match source records …

Interactive Level-Set Smoothing For Photo Editing, Thomas C. Howard, Bryan S. Morse

Faculty Publications

This paper presents an interactive image-smoothing tool based on properties and manipulation of image level sets. This tool uses PDE-based level-set smoothing to preserve edge sharpness while smoothing noise and jagged contours. Unlike existing approaches using PDEs, the duration and areas of application are controlled interactively with immediate feedback to the user. Interaction issues are addressed, and parameters for adjusting the PDE are automatically estimated based on image characteristics.

Target Sets: A Tool For Understanding And Predicting The Behavior Of Interacting Q-Learners, Nancy Fulda, Dan A. Ventura

Faculty Publications

Reinforcement learning agents that interact in a common environment frequently affect each others’ perceived transition and reward distributions. This can result in convergence of the agents to a sub-optimal equilibrium or even to a solution that is not an equilibrium at all. Several modifications to the Q-learning algorithm have been proposed which enable agents to converge to optimal equilibria under specified conditions. This paper presents the concept of target sets as an aid to understanding why these modifications have been successful and as a tool to assist in the development of new modifications which are applicable in a wider range …

Dynamic Sociometry In Particle Swarm Optimization, Mark Richards, Dan A. Ventura

Faculty Publications

The performance of Particle Swarm Optimization is greatly affected by the size and sociometry of the swarm. This research proposes a dynamic sociometry, which is shown to be more effective on some problems than the standard star and ring sociometries. The performance of various combinations of swarm size and sociometry on six different test functions is qualitatively analyzed.