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.

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 dynamic programming method for estimation of many change-points in univariate autoregressive (AR) sequences with known AR parameters between change-points is investigated. A problem how to use this method for long autoregressive sequences is solved and a constructive solution is given. A simulation experiment illustrates the advantages of the solution obtained.