Arrow Research search

Author name cluster

Tom Bylander

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

16 papers
2 author rows

Possible papers

16

AAAI Conference 1999 Conference Paper

Estimating Generalization Error Using Out-of-Bag Estimates

  • Tom Bylander
  • Dennis Hanzlik
  • University of Texas at San Antonio

We provide a method for estimating the generalization error of a bag using out-of-bag estimates. In bagging, each predictor (single hypothesis) is learned from a bootstrap sample of the training examples; the output of a bag (a set of predictors) on an example is determined by voting. The outof-bag estimate is based on recording the votes of each predictor on those training examples omitted from its bootstrap sample. Because no additional predictors are generated, the out-of-bag estimate requires considerably less time than 10fold cross-validation. We address the question of how to use the out-of-bag estimate to estimate generalization error. Our experiments on several datasets show that the out-of-bag estimate and 10-fold cross-validation have very inaccurate (much too optimistic) confidence levels. We can improve the out-of-bag estimate by incorporating a correction.

PDF Details

AIJ Journal 1998 Journal Article

Worst-case analysis of the perception and exponentiated update algorithms

  • Tom Bylander

The absolute loss is the absolute difference between the desired and predicted outcome. This paper demonstrates worst-case upper bounds on the absolute loss for the Perception learning algorithm and the Exponentiated Update learning algorithm, which is related to the Weighted Majority algorithm. The bounds characterize the behavior of the algorithms over any sequence of trials, where each trial consists of an example and a desired outcome interval (any value in the interval is an acceptable outcome). The worst-case absolute loss of both algorithms is bounded by: the absolute loss of the best linear function in a comparison class, plus a constant dependent on the initial weight vector, plus a per-trial loss. The per-trial loss can be eliminated if the learning algorithm is allowed a tolerance from the desired outcome. For concept learning, the worst-case bounds lead to mistake bounds that are comparable to past results.

Details DOI

AAAI Conference 1997 Conference Paper

A Linear Programming Heuristic for Optimal Planning

  • Tom Bylander

I introduce a new search heuristic for propositional STRIPS planning that is based on transforming planning instances to linear programming instances. The linear programming heuristic is admissible for finding minimum length plans and can be used by partial-order planning algorithms. This heuristic appears to be the first non-trivial admissible heuristic for partial-order planning. An empirical study compares Lplan, a partial-order planner incorporating the heuristic, to Graphplan, Satplan, and UCPOP on the tower of Hanoi domain, random blocks-world instances, and random planning instances. Graphplan is far faster in the study than the other algorithms. Lplan is often slower because the heuristic is time-consuming, but Lplan shows promise because it often performs a small search.

PDF Details

AAAI Conference 1997 Conference Paper

Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases

  • Tom Bylander

We have found the first optimal solutions to random instances of Rubik’s Cube. The median optimal solution length appears to be 18 moves. The algorithm used is iterative-deepening-A* (IDA*), with a lowerbound heuristic function based on large memory-based lookup tables, or “pattern databases” (Culberson and Schaeffer 1996). These tables store the exact number of moves required to solve various subgoals of the problem, in this case subsets of the individual movable cubies. We characterize the effectiveness of an admissible heuristic function by its expected value, and hypothesize that the overall performance of the program obeys a relation in which the product of the time and space used equals the size of the state space. Thus, the speed of the program increases linearly with the amount of memory available. As computer memories become larger and cheaper, we believe that this approach will become increasingly cost-effective.

PDF Details

AIJ Journal 1996 Journal Article

A probabilistic analysis of prepositional STRIPS planning

  • Tom Bylander

I present a probabilistic analysis of prepositional STRIPS planning. The analysis considers two assumptions. One is that each possible precondition (likewise postcondition) of an operator is selected independently of other pre- and postconditions. The other is that each operator has a fixed number of preconditions (likewise postconditions). Under both assumptions, I derive bounds for when it is highly likely that a planning instance can be efficiently solved, either by finding a plan or proving that no plan exists. Roughly, if planning instances under either assumption have n propositions (ground atoms) and g goals, and the number of operators is less than an O(n In g) bound, then a simple, efficient algorithm can prove that no plan exists for most instances. If the number of operators is greater than an Ω(n In g) bound, then a simple, efficient algorithm can find a plan for most instances. The two bounds differ by a factor that is exponential in the number of pre- and postconditions. A similar result holds for plan modification, i. e. , solving a planning instance that is close to another planning instance with a known plan. Thus it appears that prepositional STRIPS planning, a PSPACE-complete problem, exhibits a easy-hard-easy pattern as the number of available operators increases with a narrow range of hard problems. An empirical study demonstrates this pattern for particular parameter values. Because prepositional STRIPS planning is PSPACE-complete, this extends previous phase transition analyses, which have focused on NP-complete problems. Also, the analysis shows that surprisingly simple algorithms can solve a large subset of the planning problem.

Details DOI

AIJ Journal 1994 Journal Article

The computational complexity of propositional STRIPS planning

  • Tom Bylander

I present several computational complexity results for propositional STRIPS planning, i. e. , STRIPS planning restricted to ground formulas. Different planning problems can be defined by restricting the type of formulas, placing limits on the number of pre-and postconditions, by restricting negation in pre- and postconditions, and by requiring optimal plans. For these types of restrictions, I show when planning is tractable (polynomial) and intractable (NP-hard). In general, it is PSPACE-complete to determine if a given planning instance has any solutions. Extremely severe restrictions on both the operators and the formulas are required to guarantee polynomial time or even NP-completeness. For example, when only ground literals are permitted, determining plan existence is PSPACE-complete even if operators are limited to two preconditions and two postconditions. When definite Horn ground formulas are permitted, determining plan existence is PSPACE-complete even if operators are limited to zero preconditions and one postcondition. One of the interesting tractable problems is if each operator is restricted to positive preconditions and one postcondition (only ground literals). The blocks-world problem, slightly modified, is a subproblem of this restricted planning problem. These results in combination with previous analyses are not encouraging for domain-independent planning.

Details DOI

AAAI Conference 1993 Conference Paper

An Average Case Analysis of Planning

  • Tom Bylander

I present an average case analysis of propositional STRIPS planning. The analysis assumes that each possible precondition (likewise postcondition) is equally likely to appear within an operator. Under this assumption, I derive bounds for when it is highly likely that a planning instance can be efficiently solved, either by finding a plan or proving that no plan exists. Roughly, if planning instances have n conditions (ground atoms), g goals, and O(nfi) p o erators, then a simple, efficient algorithm can prove that no plan exists for at least 1 - 6 of the instances. If instances have St(n(ln g)(ln g/S)) operators, then a simple, efficient algorithm can find a plan for at least 1 - 6 of the instances. A similar result holds for plan modification, i. e. , solving a planning instance that is close to another planning instance with a’ known plan. Thus it would appear that propositional STRIPS planning, a PSPACE-complete problem, is hard only for narrow parameter ranges, which complements previous average-case analyses for NP-complete problems. Future work is needed to narrow the gap between the bounds and to consider more realistic distributional assumptious and more sophisticated algorithms.

PDF Details

AAAI Conference 1992 Conference Paper

Complexity Results for Serial Decomposability

  • Tom Bylander

Korf (1985) presents a method for learning macro-operators and shows that the method is applicable to serially decomposable problems. In this paper I analyze the computational complexity of serial decomposability. Assuming that operators take polynomial time, it is NP-complete to determine if an operator (or set of operators) is not serially decomposable, whether or not an ordering of state variables is given. In addition to serial decomposability of operators, a serially decomposable probIem requires that the set of solvable states is closed under the operators. It is PSPACEcomplete to determine if a given "finite state-variable problem" is serially decomposable. In fact, every solvable instance of a PSPACE problem can be converted to a serially decomposable problem. Furthermore, given a bound on the size of the input, every problem in PSPACE can be transformed to a probIem that is nearly serially-decomposable, i.e., the problem is serially decomposable except for closure of solvable states or a unique goal state.

PDF Details

AIJ Journal 1991 Journal Article

The computational complexity of abduction

  • Tom Bylander
  • Dean Allemang
  • Michael C. Tanner
  • John R. Josephson

The problem of abduction can be characterized as finding the best explanation of a set of data. In this paper we focus on one type of abduction in which the best explanation is the most plausible combination of hypotheses that explains all the data. We then present several computational complexity results demonstrating that this type of abduction is intractable (NP-hard) in general. In particular, choosing between incompatible hypotheses, reasoning about cancellation effects among hypotheses, and satisfying the maximum plausibility requirement are major factors leading to intractability. We also identify a tractable, but restricted, class of abduction problems.

Details DOI

AAAI Conference 1991 Conference Paper

The Qualitative Difference Resolution Rule

  • Tom Bylander

Consolidation is inferring the behavioral description of a device by composing the behavioral descriptions of its components, e. g. , deriving the qualitative differential equations (QDEs) of a device from those of its components. In previous work, Dormoy and Raiman described the qualitative resolution rule, which is a general rule for deriving QDEs of combinations of components. However, the qualitative resolution rule is intractable in general. As a step toward understanding tractable qualitative reasoning, I present a new QDE resolution rule, the qualitative difference resolution rule, that supports the tractable consolidation of components in which direction of flow is dependent on the signs of pressure differences. Pipes and containers are general types of components that match this rule. The pressure regulator example also matches this rule.

PDF Details

AIIM Journal 1990 Journal Article

Some causal models are deeper than others

  • Tom Bylander

The effort within AI to improve the robustness of expert systems has led to increasing interest in ‘deep’ reasoning, which is representing and reasoning about the knowledge that underlies the ‘shallow’ knowledge of traditional expert systems. One view is that deep reasoning is equivalent to causal reasoning. By analyzing the causal reasoning of a particular medical AI system, we show that this view is naive. Specifically, we show that causal networks omit information relating structure and behavior, and that this information is needed for deeper reasoning. Our conclusion is that deepness is relative to the phenomena of interest, i. e. whether the representation describes the properties and relationships that mediate interactions among the phenomena and whether the reasoning method takes this information into account.

Details DOI
v2026.09.13