Informatica

We propose a new hybrid approach to solve the unbounded integer knapsack problem (UKP), where valid inequalities are generated based on intermediate solutions of an equivalent forward dynamic programming formulation. These inequalities help tighten the initial LP relaxation of the UKP, and therefore improve the overall computational efficiency. We also extended this approach to solve the multi-dimensional unbounded knapsack problem (d-UKP). Computational results demonstrate the effectiveness of our approach on both problems.

In this paper, we describe a model for aligning books and documents from bilingual corpus with a goal to create “perfectly” aligned bilingual corpus on word-to-word level. Presented algorithms differ from existing algorithms in consideration of the presence of human translator which usage we are trying to minimize. We treat human translator as an oracle who knows exact alignments and the goal of the system is to optimize (minimize) the use of this oracle. The effectiveness of the oracle is measured by the speed at which he can create “perfectly” aligned bilingual corpus. By “Perfectly” aligned corpus we mean zero entropy corpus because oracle can make alignments without any probabilistic interpretation, i.e., with 100% confidence. Sentence level alignments and word-to-word alignments, although treated separately in this paper, are integrated in a single framework. For sentence level alignments we provide a dynamic programming algorithm which achieves low precision and recall error rate. For word-to-word level alignments Expectation Maximization algorithm that integrates linguistic dictionaries is suggested as the main tool for the oracle to build “perfectly” aligned bilingual corpus. We show empirically that suggested pre-aligned corpus requires little interaction from the oracle and that creation of perfectly aligned corpus can be achieved almost with the speed of human reading. Presented algorithms are language independent but in this paper we verify them with English–Lithuanian language pair on two types of text: law documents and fiction literature.

The paper deals with the use of dynamic programming for word endpoint detection in isolated word recognition. Endpoint detection is based on likelihood maximization. Expectation maximization approach is used to deal with the problem of unknown parameters. Speech signal and background noise energy is used as features for making decision. Performance of the proposed approach was evaluated using isolated Lithuanian words speech corpus.

This paper deals with maximum likelihood and least square segmentation of autoregressive random sequences with abruptly changing parameters. Conditional distribution of the observations has been derived. Objective function was modified to the form suitable to apply dynamic programming method for its optimization. Expressions of Bellman functions for this case were obtained. Performance of presented approach is illustrated with simulation examples and segmentation of speech signals examples.

The problem of determination of a change point in the properties of autoregressive sequences with unknown distribution is analysed. Two robust algorithms for the estimation of a change point when the distribution is symmetric and asymmetric are presented.