nils-herrmann/clean_scirepeval huggingface dataset:
An O(n^(log log n)) Learning Algorithm for DNT under the Uniform Distribution

We show that a DNF with terms of size at most d can be approximated by a function with at most d O(d log1=") non zero Fourier coeecients such that the expected error squared, with respect to the uniform distribution, is at most ". This property is used to derive a learning algorithm for DNF, under the uniform distribution. The learning algorithm uses queries and learns, with respect to the uniform distribution, a DNF with terms of size at most d in time polynomial in n and d O(dlog 1="). The interesting implications are for the case when " is constant. In this case our algorithm learns a DNF with a polynomial number of terms in time n O(loglog n) , and a DNF with terms of size at most O(log n= log log n) in polynomial time.
Greedy Packet Scheduling

Scheduling packets to be forwarded over a link is an important subtask of the routing process in both parallel computing and in communication networks. This paper investigates the simple class of greedy scheduling algorithms, namely, algorithms that always forward a packet if they can. It is first proved that for various "natural" classes of routes, the time required to complete the transmission of a set of packets is bounded by the number of packets, $k$, and the maximal route length, $d$, for any greedy algorithm (including the arbitrary scheduling policy). Next, tight time bounds of $d+k-1$ are proved for a specific greedy algorithm on the class of shortest paths in $n$-vertex networks. Finally, it is shown that when the routes are arbitrary, the time achieved by various "natural" greedy algorithms can be as bad as $\Omega(d \sqrt{k} + k)$, for any $k$, and even for $d=\Omega(n)$.
Competitive access time via dynamic storage rearrangement

We model the problem of storing items in some warehouse (modeled as an undirected graph) where a server has to visit items over time, with the goal of minimizing the total distance traversed by the server. Special cases of this problem include the management of a real industrial stacker crane warehouse, automatic robot run warehouses, disk track optimization to minimize access time, managing two dimensional memory (bubble memory and mass storage systems), doubly linked list management, and the process migration problem. The static version of this problem assumes some known probability distribution on the access patterns. We initiate the study of the dynamic version of the problem, where the robot may rearrange the warehouse to deal efficiently with future events. We require no statistical assumptions on the access pattern, and give competitive algorithms that rearrange the warehouse over time to deal efficiently with the true access patterns. We give non-trivial upper bounds for the general problem, along with some interesting lower bounds. In addition, we model realistic data access patterns on disk storage by considering two practically significant scenarios: access to some database via dynamically changing alternative indices and access patterns derived from root to leaf traversals of some (unknown) tree structure. In both cases we give greatly improved competitive ratios.
On the Convergence of Rate Based Flow ControlYehuda

Several issues in the design and analysis of rate based ow control algorithms are addressed in this paper. We suggest a new approach for rate based ow control algorithms which may be considered more \optimistic" than traditional approaches. Three variations of the approach are presented and their rate of convergence to an optimal max-min fairness solution is analyzed. Finally, we suggest and analyze approximate rate based ow control algorithms. We show that under certain conditions the approximate algorithms may converge faster. However, in rare conngurations we show that the resulting rates may be substantially diierent than the rates of the max-min vector (this diierence is not necessarily bad).
An experimental and theoretical comparison of model selection methods

We investigate the problem of {\it model\ selection} in the setting of supervised learning of boolean functions from independent random examples. More precisely, we compare methods for finding a balance between the complexity of the hypothesis chosen and its observed error on a random training sample of limited size, when the goal is that of minimizing the resulting generalization error. We undertake a detailed comparison of three well-known model selection methods — a variation of Vapnik‘s {\it Guaranteed\ Risk\ Minimization} (GRM), an instance of Rissanen‘s {\it Minimum\ Description\ Length\ Principle} (MDL), and (hold-out) cross validation (CV). We introduce a general class of model selection methods (called {\it penalty-based} methods) that includes both GRM and MDL, and provide general methods for analyzing such rules. We provide both controlled experimental evidence and formal theorems to support the following conclusions: 
 
\bulletEven on simple model selection problems, the behavior of the methods examined can be both complex and incomparable. Furthermore, no amount of “tuning” of the rules investigated (such as introducing constant multipliers on the complexity penalty terms, or a distribution-specific “effective dimension”) can eliminate this incomparability. 
 
\bulletIt is possible to give rather general bounds on the generalization error, as a function of sample size, for penalty-based methods. The quality of such bounds depends in a precise way on the extent to which the method considered automatically limits the complexity of the hypothesis selected. 
 
\bulletFor {\it any} model selection problem, the additional error of cross validation compared to {\it any} other method can be bounded above by the sum of two terms. The first term is large only if the learning curve of the underlying function classes experiences a phase transition” between (1-\gamma)m andm examples (where \gamma is the fraction saved for testing in CV). The second and competing term can be made arbitrarily small by increasing\gamma . 
 
\bulletThe class of penalty-based methods is fundamentally handicapped in the sense that there exist two types of model selection problems for which every penalty-based method must incur large generalization error on at least one, while CV enjoys small generalization error on both.
Broadcast in radio networks

We show that for any radio network there exists a schedule of a broadcast whose time is O(D + 1og5(n)), where D is the diameter and n is the number of nodes. (This result implies an optimal broadcast to networks with D = R(log5 n).) We present a (centralized) polynomial time algorithm that given a network and a source, outputs a schedule for broadcasting the message from the source to the rest of the network.
Competitive Access Time via Dynamic Storage

We model the problem of storing items in some warehouse (modeled as an undirected graph) where a server has to visit items over time, with the goal of minimizing the total distance traversed by the server. Special cases of this problem include the management of a real industrial stacker crane warehouse [GI , automatic robot run warehouses [Ho], disk track optimization to minimize access time [GS, P, W, YW], managing two dimensional memory (bubble memory and mass storage systems) [KMW, W, YW], doubly linked list management, and the process migration problem. The static version of this problem assumes some known probability distribution on the access patterns. The study of special cases of this static version was first considered by Hardy, Littlewood and P6lya in 1932 [HLP]. In this work we initiate the study of the dynamic version of the problem, where the robot may rearrange the warehouse to deal efficiently with future events. We require no statistical assumptions on the access pattern, and give competitive algorithms that rearrange the warehouse over time to deal efficiently with the true access patterns. We give non-trivial upper bounds for the general problem, along with some interesting lower bounds. In addition, we model realistic data access patterns on disk storage by considering two practically significant scenarios: access to some database via dynam
A parametrization scheme for classifying models of learnability

We present a systematic framework for classifying, comparing, and defining models of PAC learnability. Apart from the obvious "uniformity" parameters, we present a novel "solid learnability" notion that indicates when the class in question can be successfully learned by the most straightforward algorithms, namely, any consistent algorithm. We analyze known models in terms of our new parameterization scheme and investigate the relative strength of notions of learnability that correspond to different parameter values. In addition, we consider "proximity" between concept classes. We define notions of "covering" one class by another and show that, with respect to learnability, they play a role similar to the role of reductions in computational complexity; the learnability of a class implies the learnability of any class it covers. We apply the covering technique to resolve some open questions raised by Benedek and Itai (1991,  1989, Inform. and Comput.82, 247-261) and Linial et al. (1991, Inform. and Comput.90, 33-49). The notions we discuss are information-theoretic: we concentrate on the question of learnability rather than the computational complexity of the learning process.
Optimal Filtering of an Instrument Sound in a Mixed Recording Using Harmonic Model and Score Alignment

In this paper we show a method for optimal filtering (in terms of mean square error) of an instrument in a mixed recording. The filter is based on prior knowledge of the exact pitch played by the instrument and also on the assumption that the instrument is well described within the harmonic model framework. To get the pitch priors, we use alignment of the score information to the real recording. We show how this algorithm can be used to filter a single instrument or voiced singer. We also show how it can be used to substruct an instrument or to balance the volume to several instruments.
Adaptive Nonlinear Auto-Associative Modeling Through Manifold Learning

We propose adaptive nonlinear auto-associative modeling (ANAM) based on Locally Linear Embedding algorithm (LLE) for learning intrinsic principal features of each concept separately and recognition thereby. Unlike traditional supervised manifold learning algorithm, the proposed ANAM algorithm has several advantages: 1) it implicitly embodies discriminant information because the suboptimal parameters of ANAM are determined based on error rate of the validation set. 2) it avoids the curse of dimensionality without loss accuracy because recognition is completed in the original space. Experiments on character and digit databases show that the advantages of the proposed ANAM algorithm.
Ordinal palmprint represention for personal identification [represention read representation]

Palmprint-based personal identification, as a new member in the biometrics family, has become an active research topic in recent years. Although great progress has been made, how to represent palmprint for effective classification is still an open problem. In this paper, we present a novel palmprint representation - ordinal measure, which unifies several major existing palmprint algorithms into a general framework. In this framework, a novel palmprint representation method, namely orthogonal line ordinal features, is proposed. The basic idea of this method is to qualitatively compare two elongated, line-like image regions, which are orthogonal in orientation and generate one bit feature code. A palmprint pattern is represented by thousands of ordinal feature codes. In contrast to the state-of-the-art algorithm reported in the literature, our method achieves higher accuracy, with the equal error rate reduced by 42% for a difficult set, while the complexity of feature extraction is halved.
Jensen-Shannon boosting learning for object recognition

In this paper, we propose a novel learning method, called Jensen-Shannon Boosting (JSBoost) and demonstrate its application to object recognition. JSBoost incorporates Jensen-Shannon (JS) divergence [Y. Bubner et al. (2001)] into AdaBoost learning. JS divergence is advantageous in that it provides more appropriate measure of dissimilarity between two classes and it is numerically more stable than other measures such as Kullback-Leibler (KL) divergence (see [Y. Bubner et al. (2001)]). The best features are iteratively learned by maximizing the projected JS divergence, based on which best weak classifiers are derived. The weak classifiers are combined into a strong one by minimizing the recognition error. JSBoost learning is demonstrated with face object recognition using a local binary pattern (LBP) [M. Pietikainen et al. (2004)] based representation. JSBoost selects the best LBP features from thousands of candidate features and constructs a strong classifier based on the selected features. JSBoost empirically produces better face recognition results than other AdaBoost variants such as RealBoost [R.E. Schapire et al. (1998)], GentleBoost [J. Friedman et al. (2000)] and KL-Boost [C. Liu et al. (2003)], as demonstrated by experiments.
Learning to Fuse 3D+2D Based Face Recognition at Both Feature and Decision Levels

2D intensity images and 3D shape models are both useful for face recognition, but in different ways. While algorithms have long been developed using 2D or 3D data, recently has seen work on combining both into multi-modal face biometrics to achieve higher performance. However, the fusion of the two modalities has mostly been at the decision level, based on scores obtained from independent 2D and 3D matchers. 
 
In this paper, we propose a systematic framework for fusing 2D and 3D face recognition at both feature and decision levels, by exploring synergies of the two modalities at these levels. The novelties are the following. First, we propose to use Local Binary Pattern (LBP) features to represent 3D faces and present a statistical learning procedure for feature selection and classifier learning. This leads to a matching engine for 3D face recognition. Second, we propose a statistical learning approach for fusing 2D and 3D based face recognition at both feature and decision levels. Experiments show that the fusion at both levels yields significantly better performance than fusion at the decision level.
Real-time multiple objects tracking with occlusion handling in dynamic scenes

This work presents a real-time system for multiple objects tracking in dynamic scenes. A unique characteristic of the system is its ability to cope with long-duration and complete occlusion without a prior knowledge about the shape or motion of objects. The system produces good segment and tracking results at a frame rate of 15-20 fps for image size of 320 /spl times/ 240, as demonstrated by extensive experiments performed using video sequences under different conditions indoor and outdoor with long-duration and complete occlusions in changing background.
Advances in Biometric Person Authentication, International Workshop on Biometric Recognition Systems, IWBRS2005, Beijing, China, October 22-23, 2005, Proceedings

Face.- Texture Features in Facial Image Analysis.- Enhance ASMs Based on AdaBoost-Based Salient Landmarks Localization and Confidence-Constraint Shape Modeling.- Face Authentication Using One-Class Support Vector  A Novel Illumination Normalization Method for Face  Using Score Normalization to Solve the Score Variation Problem in Face Authentication.- Gabor Feature Selection for Face Recognition Using Improved AdaBoost Learning.- An Automatic Method of Building 3D Morphable Face Model.- Procrustes Analysis and Moore-Penrose Inverse Based Classifiers for Face Recognition.- Two Factor Face Authentication Scheme with Cancelable Feature.-  Local Feature Extraction in Fingerprints by Complex  A TSVM-Based Minutiae Matching Approach for Fingerprint Verification.- A Robust Orientation Estimation Algorithm for Low Quality  Fingerprint Classification Based on Statistical Features and Singular Point Information.- Iris.- An Iterative Algorithm for Fast Iris Detection.- A Non-linear Normalization Model for Iris  A New Feature Extraction Method Using the ICA Filters for Iris Recognition System.- Iris Recognition Against Counterfeit Attack Using Gradient Based Fusion of Multi-spectral Images.- An Iris Detection Method Based on Structure Information.- Speaker.- Constructing the Discriminative Kernels Using GMM for Text-Independent Speaker Identification.- Individual Dimension Gaussian Mixture Model for Speaker Identification.- Writing.- Sensor Interoperability and Fusion in Signature Verification: A Case Study Using Tablet PC.- Fusion of Local and Regional Approaches for On-Line Signature Verification.- Text-Independent Writer Identification Based on Fusion of Dynamic and Static Features.- Gait.- Combining Wavelet Velocity Moments and Reflective Symmetry for Gait Recognition.- Model-Based Approaches for Predicting Gait Changes over Time.- Other Biometrics.- Using Ear Biometrics for Personal Recognition.- Biometric Identification System Based on Dental Features.- A Secure Multimodal Biometric Verification Scheme.- Automatic Configuration for a Biometrics-Based Physical Access Control System.
Manifold Learning and Applications in Recognition

Great amount of data under varying intrinsic features are empirically thought of as high-dimensional nonlinear manifold in the observation space. With respect to different categories, we present two recognition approaches, i.e. the combination of manifold learning algorithm and linear discriminant analysis (MLA+LDA), and nonlinear auto-associative modeling (NAM). For similar object recognition, e.g. face recognition, MLA + LDA is used. Otherwise, NAM is employed for objects from largely different categories. Experimental results on different benchmark databases show the advantages of the proposed approaches.
Geometrical Probability Covering Algorithm

In this paper, we propose a novel classification algorithm, called geometrical probability covering (GPC) algorithm, to improve classification ability. On the basis of geometrical properties of data, the proposed algorithm first forms extended prototypes through computing means of any two prototypes in the same class. Then Gaussian kernel is employed for covering the geometrical structure of data and used as a local probability measurement. By computing the sum of the probabilities that a new sample to be classified to the set of prototypes and extended prototypes, the classified criterion based on the global probability measurement is achieved. The proposed GPC algorithm is simple but powerful, especially, when training samples are sparse and small size. Experiments on several databases show that the proposed algorithm is promising. Also, we explore other potential applications such as outlier removal with the proposed GPC algorithm.
Learning multiview face subspaces and facial pose estimation using independent component analysis

An independent component analysis (ICA) based approach is presented for learning view-specific subspace representations of the face object from multiview face examples. ICA, its variants, namely independent subspace analysis (ISA) and topographic independent component analysis (TICA), take into account higher order statistics needed for object view characterization. In contrast, principal component analysis (PCA), which de-correlates the second order moments, can hardly reveal good features for characterizing different views, when the training data comprises a mixture of multiview examples and the learning is done in an unsupervised way with view-unlabeled data. We demonstrate that ICA, TICA, and ISA are able to learn view-specific basis components unsupervisedly from the mixture data. We investigate results learned by ISA in an unsupervised way closely and reveal some surprising findings and thereby explain underlying reasons for the emergent formation of view subspaces. Extensive experimental results are presented.
Quantifying Uncertainty in Complex Groundwater Flow Models

A Poster Presentation(H11D-1307) Delivered at the 2005 AGU Fall Meeting, San Francisco, California, 5-9 December 2005 Despite the intensive research over the past decades in the field of stochastic subsurface hydrology, our ability to analyze and model heterogeneous groundwater systems remains limited. Most existing theories are either too restrictive to handle practical complexity or too expensive to be applied to realistic problem sizes. In this study we present a hybrid nonstationary spectral method for predicting uncertainties (e.g., head and velocity variances caused by unmodeled smallscale conductivity variability) in complex groundwater flow models. This method, based on solving stochastic perturbation equations, involves two major computational steps after the deterministic mean flow equation is solved. We first apply a set of closed form formulas to predict the nonstationary variances for the entire modeling area. We then employ first-order numerical spectral method to correct the “regional solution” in localized areas where the variance distribution is highly nonstationary (e.g., around inner boundaries and strong sources/sinks). The boundary conditions for the local numerical solutions are based on the closed form formulas and are implemented on an as-needed basis in a real-time visual software system called Interactive Ground Water (IGW). Since the "regional" closed form solution is instantaneous and the more expensive first-order numerical analysis is only applied locally, the overall hybrid approach can be very efficient, making it possible to model strongly nonstationary variance dynamics in complex flow situations in the presence of general trends and sources and sinks. We demonstrate the accuracy and effectiveness of the hybrid nonstationary spectral method with a number of examples and, when feasible, systematically compare the results with the corresponding single model, nonstationary numerical analysis and Monte Carlo solutions.
Automated feature points management for video mosaic construction

This paper presents a two level automatic feature points management method for constructing a seamless entire panorama from video sequence. In the first level, through fusing the number of tracked feature points and the estimated ratio of lost information of the mosaicing image, a feature point quantity management module is developed to select the key frames. In the second level, a feature points quality management technique is used to choose the key points for mosaicing. This module includes a coarse-to-fine method with two steps: (1) Feature points quality based key point subset creation; and (2) Multi-resolution based key point selection. The main contribution of the algorithm is that it is able to achieve robust and fast mosaicing result while maintain the most valuable information of the scene. Experiments are performed using video sequences under different conditions. The results show that the proposed algorithm could achieve robust and efficient video mosaic image.