The Lindstrom marking algorithm uses bounded workspace. Its time complexity is O(n^2) in all cases, but it has been assumed that the average case time complexity O(n lg n). It is proven that the average case time complexity is H(n^2). Similarly, the average size of the Wegbreit bit stack is shown to be H(n).

# Your search: "author:Hirschberg, D. S."

## filters applied

## Type of Work

Article (14) Book (0) Theses (0) Multimedia (0)

## Peer Review

Peer-reviewed only (14)

## Supplemental Material

Video (0) Audio (0) Images (0) Zip (0) Other files (0)

## Publication Year

## Campus

UC Berkeley (0) UC Davis (0) UC Irvine (14) UCLA (0) UC Merced (0) UC Riverside (0) UC San Diego (0) UCSF (0) UC Santa Barbara (0) UC Santa Cruz (0) UC Office of the President (0) Lawrence Berkeley National Laboratory (0) UC Agriculture & Natural Resources (0)

## Department

Donald Bren School of Information and Computer Sciences (14)

## Journal

## Discipline

Physical Sciences and Mathematics (14)

## Reuse License

## Scholarly Works (14 results)

The least weight subsequence (LWS) problem is introduced, and is shown to be equivalent to the classic minimum path problem for directed graphs. A special case of the LWS problem is shown to be solvable in O(n log n) time generally and, for certain weight functions, in linear time. A number of applications are given, including an optimum paragraph formation problem and the problem of finding a minimum height B-tree, whose solutions realize improvement in asymptotic time complexity.

Several methods (independent subsamples, leave-one-out, cross-validation, and bootstrapping) have been proposed for estimating the error rates of classifiers. The rationale behind the various estimators and the causes ofthe sometimes conflicting claims regarding their bias and precision are explored in this paper. The biases and variances of each of the estimators are examined empirically. Cross-validation, 10-fold or greater, seems to be the best approach, the other methods are biased, have poorer precision, or are inconsistent. (Though unbiased for linear discriminant classifiers, the 632b bootstrap estimator is biased for nearest neighbors classifiers, more so for single nearest neighbor than for three nearest neighbors. The 632b estimator is also biased for CART-style decision trees. Weiss' LOO* estimator is unbiased and has better precision than cross-validation for discriminant and nearest neighbors classifiers, but its lack of bias and improved precision for those classifiers do not carry over to decision trees for nominal attributes.

Let I be the set of intervals with end points in the integers 1 ... n. Associated with each element in I is a value from a commutative semigroup S. Two operations are to be implemented: update of the value associated with an interval and query of the sum of the values associated with the intervals which include an integer.

If the values are from a commutative group (i.e., inverses exist) then there is a data structure which enables both update and query algorithms of time complexity O(log n). For the semigroup problem, the use of range trees enables both update and query algorithms of time complexity O(log^2 n).

Data structures are presented with (update,query) algorithms of complexities (log^2 n, log n), (log n, log^2 n), (log n log log n, log n log log n).

Several methods (independent subsamples, leave-one-out, cross-validation, and bootstrapping) have been proposed for estimating the error rates of classifiers. The rationale behind the various estimators and the causes of the sometimes conflicting claims regarding their bias and precision are explored in this paper. The biases and variances of each of the estimators are examined empirically. Cross-validation, 10-fold or greater, seems to be the best approach, the other methods are biased, have poorer precision, or are inconsistent. (Though unbiased for linear discriminant classifiers, the 632b bootstrap estimator isbiased for nearest neighbors classifiers, more so for single nearest neighbor than for three nearest neighbors. The 632b estimator is also biased for CART-style decision trees. Weiss LOO* estimator is unbiased and has better precision than cross-validation for discriminant and nearest neighbors classifiers, but its lack of bias and improved precision for those classifiers do not carry over to decision trees for nominal attributes.

Several techniques for estimating the range of uncertainty of estimated error rates and for estimating the significance of observed differences in error rates are explored in this paper. Textbook formulas which assume a large test set (i.e., a normal distribution) are commonly used to approximate the confidence limits of error rates or as an approximate significance test for comparing error rates. Expressions for determining more exact limits and significance levels for small samples are given here, and criteria are also given for determining when these more exact methods should be used. The assumed normal distribution gives a poor approximation to the confidence interval in most cases, but is usually useful for significance tests when the proper mean and variance expressions are used. A commonly used ±2

Diehr and Faaland developed an algorithm that finds the minimum sum of key length pagination of a scroll of n items, and which uses O(n lg n) time and O(n) space, solving a problem posed by McCreight. An improved algorithm is given which uses O(n) time and O(n) space.

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.

Several methods (independent subsamples, cross-validation, and bootstrapping) have been proposed for estimating the error rates of classifiers. The power of the various estimators (i.e., their variances and confidence limits, their ability to test the null hypothesis) has received relatively little attention in the machine learning literature. The biases and variances of each of the estimators are examined empirically. Cross-validation, 10-fold or greater, is seen to be superior, the other methods are biased, have poorer variance, or are prohibitively time-consuming. Textbook formulas which assume a large test set (i.e., a normal distribution) are commonly used to approximate the confidence limits of error rates or as an approximate significance test for comparing error rates. Expressions for determining more exact limits and significance levels for small samples are given here, and criteria are also given for determining when these more exact methods should be used. The normal distribution is a poor approximation to the confidence interval in most cases, but is usually useful for significance tests when the proper mean and variance expressions are used. A commonly used ±2? test uses an improper expression for ?, which is too low and leads to a high likelihood of Type I errors.

Several algorithms are presented whose operations are governed by a principle of failure functions: when searching for an extremal value within a sequence, it suffices to consider only the subsequence of items each of which is the first possible improvement of its predecessor. These algorithms are more efficient than their more traditional counterparts.