Tad Hogg

TIST Journal 2012 Journal Article

Using Stochastic Models to Describe and Predict Social Dynamics of Web Users

• Kristina Lerman
• Tad Hogg

The popularity of content in social media is unequally distributed, with some items receiving a disproportionate share of attention from users. Predicting which newly-submitted items will become popular is critically important for both the hosts of social media content and its consumers. Accurate and timely prediction would enable hosts to maximize revenue through differential pricing for access to content or ad placement. Prediction would also give consumers an important tool for filtering the content. Predicting the popularity of content in social media is challenging due to the complex interactions between content quality and how the social media site highlights its content. Moreover, most social media sites selectively present content that has been highly rated by similar users, whose similarity is indicated implicitly by their behavior or explicitly by links in a social network. While these factors make it difficult to predict popularity a priori, stochastic models of user behavior on these sites can allow predicting popularity based on early user reactions to new content. By incorporating the various mechanisms through which web sites display content, such models improve on predictions that are based on simply extrapolating from the early votes. Specifically, for one such site, the news aggregator Digg, we show how a stochastic model distinguishes the effect of the increased visibility due to the network from how interested users are in the content. We find a wide range of interest, distinguishing stories primarily of interest to users in the network (“niche interests”) from those of more general interest to the user community. This distinction is useful for predicting a story’s eventual popularity from users’ early reactions to the story.

ICRA Conference 2008 Conference Paper

Modeling and analysis of DNA hybridization dynamics at microarray surface in moving fluid

• Tad Hogg
• Mingjun Zhang
• Ruoting Yang

This paper proposes a dynamic model of DNA microarray hybridization properties in moving fluid. Prior experimental studies indicate hybridization efficiency is closely related to fluid dynamics, temperature, DNA probe density and microarray surface properties. Simulation results using the model proposed here agree well with practical observations. The model may be used to improve and manipulate performance of DNA microarray hybridization, and implement as a control model for hybridization automation to improve reliability and robustness of microarray hybridization process.

JAAMAS Journal 2006 Journal Article

Coordinating microscopic robots in viscous fluids

• Tad Hogg

Abstract Multiagent control provides strategies for aggregating microscopic robots (“nanorobots”) in fluid environments relevant for medical applications. Unlike larger robots, viscous forces and Brownian motion dominate the behavior. Examples range from modified microorganisms (programmable bacteria) to future robots using ongoing developments in molecular computation, sensors and motors. We evaluate controls for locating a cell-sized area emitting a chemical into a moving fluid with parameters corresponding to chemicals released in response to injury or infection in small blood vessels. These control methods are passive Brownian motion, following the chemical concentration gradient, and cooperative behaviors in which some robots use acoustic signals to guide others to the chemical source. Control performance is evaluated using diffusion equations to describe the robot motions and control state transitions. The quantitative results show these control techniques are feasible approaches to the task with trade-offs among fabrication difficulty, response speed, false positive detection rate and energy use. Controlled aggregation at chemically distinctive locations could be useful for sensitive diagnosis, selective changes to biological tissues and forming structures using previous proposals for multiagent control of modular robots.

AAAI Conference 2005 Conference Paper

Controlling Tiny Multi-Scale Robots for Nerve Repair

• Tad Hogg

We designed and evaluated multiagent control for microscopic robots (“nanorobots”) aiding the surgical repair of damaged nerve cells. This repair operates on both nerves as a whole, at scales of hundreds of microns, and individual nerve cell axons, at scales of about a micron. We match the robots to these sizes using a combination of microelectomechanical (MEMS) machines for the larger operations and nanorobots for operations on individual cells. Multiagent control allows accurate and rapid repair with such robots, with only modest computational and communication requirements for the nanorobots, a significant benefit due to their physical limitations. Our simulations, using physical parameters dictated by nerve biology and plausible nanorobotic capabilities, show how specific control choices lead to trade-offs in clinical outcome. Beyond the specific example of nerve repair treated here, multi-scale robots could aid a variety of medical and biological tasks involving both the large scale of organs or tissues and the microscopic scale of individual cells.

AIJ Journal 2002 Journal Article

Multiagent control of self-reconfigurable robots

• Hristo Bojinov
• Arancha Casal
• Tad Hogg

We demonstrate how multiagent systems provide useful control techniques for modular self-reconfigurable (metamorphic) robots. Such robots consist of many modules that can move relative to each other, thereby changing the overall shape of the robot to suit different tasks. Multiagent control is particularly well-suited for tasks involving uncertain and changing environments. We illustrate this approach through simulation experiments of Proteo, a metamorphic robot system currently under development.

ICRA Conference 2001 Conference Paper

Complex Behaviors From Local Rules In Modular Self-Reconfigurable Robots

• Jeremy Kubica
• Arancha Casal
• Tad Hogg

We demonstrate how simple local rules, inspired by social insects, produce complex dynamic behaviors required for locomotion and navigation in modular self-reconfigurable robots. We show how systems made up of many modules respond dynamically to their environment, such as obstacles during navigation. We present control algorithms tested on simulation experiments of TeleCube, a new modular robot developed at Xerox PARC.

ICRA Conference 2000 Conference Paper

Emergent Structures in Modular Self-Reconfigurable Robots

• Hristo Bojinov
• Arancha Casal
• Tad Hogg

We demonstrate how simple local sensing and control rules achieve useful emergent behaviors in modular self-reconfigurable (metamorphic) robots. Our biologically inspired approach grows structures with the desired functionality even though the final shapes have some unspecified random variation. By contrast, other self-reconfiguration algorithms require an a-priori exact description of a target shape for the given task, which may be difficult when a robot operates in uncertain environments. We present and evaluate several control algorithms through simulation experiments of Proteo, a metamorphic robot system.

AAAI Conference 1998 Conference Paper

Which Search Problems Are Random?

• Tad Hogg

The typical difficulty of various NP-hard problems varies with simple parameters describing their structure. This behavior is largely independent of the search algorithm, but depends on the choice of problem ensemble. A given problem instance belongs to many different ensembles, so applying these observations to individual problems requires identifying which ensemble is most appropriate for predicting its search behavior, e. g. , cost or solubility. To address this issue, we introduce a readily computable measure of randomness for search problems called “approximate entropy”. This new measure is better suited to search than other approaches, such as algorithmic complexity and information entropy. Experiments with graph coloring and 3–SAT show how this measure can be applied.

AAAI Conference 1997 Conference Paper

Exploiting the Deep Structure of Constraint Satisfaction Problems with Quantum Computers

• Tad Hogg

AIJ Journal 1996 Journal Article

Phase transitions and the search problem

• Tad Hogg
• Bernardo A. Huberman
• Colin P. Williams

We describe how techniques that were originally developed in statistical mechanics can be applied to search problems that arise commonly in artificial intelligence. This approach is useful for understanding the typical behavior of classes of problems. In particular, these techniques predict that abrupt changes in computational cost, analogous to physical phase transitions, should occur universally, as heuristic effectiveness or search space topology is varied. We also present a number of open questions raised by these studies.

AIJ Journal 1996 Journal Article

Problem structure heuristics and scaling behavior for genetic algorithms

• Scott H. Clearwater
• Tad Hogg

Recent empirical and theoretical studies have shown that simple parameters characterizing the structure of many constraint satisfaction problems also predict the cost to solve them, on average. We apply these observations as a heuristic to improve the performance of genetic algorithms for some constraint satisfaction problems. In particular, we use a simple cost measure to evaluate the likely solution difficulty of the different unsolved subproblems appearing in the population. This is used to determine which individuals contribute to subsequent generations and improves upon the traditional direct use of the underlying cost function. As a specific test case, we used the GENESIS genetic algorithm to search for the optimum of a class of random Walsh polynomials and identified the improvement due to this new heuristic. We describe how this improvement depends on the population size and accuracy of the underlying theory. Finally, we discuss extensions to other types of machine learning and problem solving systems.

AIJ Journal 1996 Journal Article

Refining the phase transition in combinatorial search

• Tad Hogg

Many recent studies have identified phase transitions from under- to overconstrained instances in classes of constraint satisfaction search problems, and their relation to search cost. For example, cases that are difficult to solve with a variety of search methods are concentrated near these transitions. These studies show that a simple parameter describing the problem structure predicts the difficulty of solving the problem, on average. However, this prediction is associated with a large variance and depends on the somewhat arbitrary choice of the problem class. Thus these results are of limited direct use for individual instances. To help address this limitation, additional parameters, describing problem structure as well as heuristic effectiveness, are introduced. These are shown to reduce the variation in some cases. This also provides further insight into the nature of intrinsically hard search problems.

IJCAI Conference 1995 Conference Paper

Social Dilemmas in Computational Ecosystems

• Tad Hogg

AAAI Conference 1994 Conference Paper

Expected Gains from Parallelizing Constraint Solving for Hard Problems

• Tad Hogg

A number of recent studies have examined how the difficulty of various NP-hard problems varies with simple parameters describing their structure. In particular, they have identified parameter values that distinguish regions with many hard problem instances from relatively easier ones. In this paper we continue this work by examining independent parallel search. SpecificalIy, we evaluate the speedup as function of connectivity and search difficulty for the particular case of graph coloring with a standard heuristic search method. This requires examining the full search cost distribution rather than just the more commonly reported mean and variance. We also show similar behavior for a single-agent search strategy in which the search is restarted whenever it fails to complete within a specified cost bound.

AIJ Journal 1994 Journal Article

Exploiting the deep structure of constraint problems

• Colin P. Williams
• Tad Hogg

We introduce a technique for analyzing the behavior of sophisticated AI search programs working on realistic, large-scale problems. This approach allows us to predict where, in a space of problem instances, the hardest problems are to be found and where the fluctuations in difficulty are greatest. Our key insight is to shift emphasis from modelling sophisticated algorithms directly to modelling a search space that captures their principal effects. We compare our model's predictions with actual data on real problems obtained independently and show that the agreement is quite good. By systematically relaxing our underlying modelling assumptions we identify their relative contribution to the remaining error and then remedy it. We also discuss further applications of our model and suggest how this type of analysis can be generalized to other kinds of AI problems.

AIJ Journal 1994 Journal Article

The hardest constraint problems: A double phase transition

• Tad Hogg
• Colin P. Williams

The distribution of hard graph coloring problems as a function of graph connectivity is shown to have two distinct transition behaviors. The first, previously recognized, is a peak in the median search cost near the connectivity at which half the graphs have solutions. This region contains a high proportion of relatively hard problem instances. However, the hardest instances are in fact concentrated at a second, lower, transition point. Near this point, most problems are quite easy, but there are also a few very hard cases. This region of exceptionally hard problems corresponds to the transition between polynomial and exponential scaling of the average search cost, whose location we also estimate theoretically. These behaviors also appear to arise in other constraint problems. This work also shows the limitations of simple measures of the cost distribution, such as mean or median, for identifying outlying cases.

AAAI Conference 1993 Conference Paper

Solving the Really Hard Problems with Cooperative Search

• Tad Hogg

NeurIPS Conference 1987 Conference Paper

A Dynamical Approach to Temporal Pattern Processing

• W. Stornetta
• Tad Hogg
• Bernardo Huberman

Recognizing patterns with temporal context is important for such tasks as speech recognition, motion detection and signature verification. We propose an architecture in which time serves as its own representation, and temporal context is encoded in the state of the nodes. We contrast this with the approach of replicating portions of the architecture to represent time. As one example of these ideas, we demonstrate an architecture with capacitive inputs serving as temporal feature detectors in an otherwise standard back propagation model. Experiments involving motion detection and word discrimination serve to illustrate novel features of the system. Finally, we discuss possible extensions of the architecture.

AIJ Journal 1987 Journal Article

Phase transitions in artificial intelligence systems

• Bernardo A. Huberman
• Tad Hogg

We predict that large-scale artificial intelligence systems and cognitive models will undergo sudden phase transitions from disjointed parts into coherent structures as their topological connectivity increases beyond a critical value. These situations, ranging from production systems to semantic net computations, are characterized by event horizons in space-time that determine the range of causal connections between processes. At transition, these event horizons undergo explosive changes in size. This phenomenon, analogous to phase transitions in nature, provides a new paradigm with which to analyze the behavior of large-scale computation and determine its generic features.