Ústav informatiky

Nejnovější přírůstky:
2019-11-25
10:16
Sort Program for Real Keys with Linear Time Complexity
Jiřina, Marcel
In this report we present a program for sorting data structures with sorting keys as real numbers, i.e. of type "real" or "float". The basis of the program is a modification of the countingsort algorithm for reals (instead of integers). It uses a comparision-type sorting for small part of data set given. The time complexity of this part of program can be bounded by linear function of n and thus, the total time complexity is also O(n) for n data items.

Úplný záznam
2019-11-25
10:15
A Robustified Metalearning Procedure for Regression Estimators
Kalina, Jan ; Neoral, A.
Metalearning represents a useful methodology for selecting and recommending a suitable algorithm or method for a new dataset exploiting a database of training datasets. While metalearning is potentially beneficial for the analysis of economic data, we must be aware of its instability and sensitivity to outlying measurements (outliers) as well as measurement errors. The aim of this paper is to robustify the metalearning process. First, we prepare some useful theoretical tools exploiting the idea of implicit weighting, inspired by the least weighted squares estimator. These include a robust coefficient of determination, a robust version of mean square error, and a simple rule for outlier detection in linear regression. We perform a metalearning study for recommending the best linear regression estimator for a new dataset (not included in the training database). The prediction of the optimal estimator is learned over a set of 20 real datasets with economic motivation, while the least squares are compared with several (highly) robust estimators. We investigate the effect of variable selection on the metalearning results. If the training as well as validation data are considered after a proper robust variable selection, the metalearning performance is improved remarkably, especially if a robust prediction error is used.

Úplný záznam
2019-10-19
16:35
Implicitly weighted robust estimation of quantiles in linear regression
Kalina, Jan ; Vidnerová, Petra
Estimation of quantiles represents a very important task in econometric regression modeling, while the standard regression quantiles machinery is well developed as well as popular with a large number of econometric applications. Although regression quantiles are commonly known as robust tools, they are vulnerable to the presence of leverage points in the data. We propose here a novel approach for the linear regression based on a specific version of the least weighted squares estimator, together with an additional estimator based only on observations between two different novel quantiles. The new methods are conceptually simple and comprehensible. Without the ambition to derive theoretical properties of the novel methods, numerical computations reveal them to perform comparably to standard regression quantiles, if the data are not contaminated by outliers. Moreover, the new methods seem much more robust on a simulated dataset with severe leverage points.

Úplný záznam
2019-10-19
16:35
A Nonparametric Bootstrap Comparison of Variances of Robust Regression Estimators.
Kalina, Jan ; Tobišková, Nicole ; Tichavský, Jan
While various robust regression estimators are available for the standard linear regression model, performance comparisons of individual robust estimators over real or simulated datasets seem to be still lacking. In general, a reliable robust estimator of regression parameters should be consistent and at the same time should have a relatively small variability, i.e. the variances of individual regression parameters should be small. The aim of this paper is to compare the variability of S-estimators, MM-estimators, least trimmed squares, and least weighted squares estimators. While they all are consistent under general assumptions, the asymptotic covariance matrix of the least weighted squares remains infeasible, because the only available formula for its computation depends on the unknown random errors. Thus, we take resort to a nonparametric bootstrap comparison of variability of different robust regression estimators. It turns out that the best results are obtained either with MM-estimators, or with the least weighted squares with suitable weights. The latter estimator is especially recommendable for small sample sizes.

Úplný záznam
2019-08-26
09:04
Generalization of a Theorem on Eigenvalues of Symmetric Matrices
Rohn, Jiří
We prove that the product of a symmetric positive semide nite matrix and a symmetric matrix has all eigenvalues real.
Plný text: Stáhnout plný textPDF

Úplný záznam
2019-07-25
09:14
Does a Singular Symmetric Interval Matrix Contain a Symmetric Singular Matrix?
Rohn, Jiří
We consider the conjecture formulated in the title concerning existence of a symmetric singular matrix in a singular symmetric interval matrix. We show by means of a counterexample that it is generally not valid, and we prove that it becomes true under an additional assumption of positive semide niteness of the midpoint matrix. The proof is constructive.
Plný text: Stáhnout plný textPDF

Úplný záznam
2019-07-25
09:13
A Logical Characteristic of Read-Once Branching Programs
Žák, Stanislav
We present a mathematical model of the intuitive notions such as the knowledge or the information arising at different stages of computations on branching programs (b.p.). The model has two appropriate properties: i) The ”knowledge” arising at a stage of computation in question is derivable from the ”knowledge” arising at the previous stage according to the rules of the model and according to the local arrangement of the b.p. ii) The model confirms the intuitively well-known fact that the knowledge arising at a node of a computation depends not only on it but in some cases also on a ”mystery” information. (I. e. different computations reaching the same node may have different knowledge(s) arisen at it.) We prove that with respect to our model no such information exists in read-once b.p.‘s but on the other hand in b. p.‘s which are not read-once such information must be present. The read-once property forms a frontier. More concretely, we may see the instances of our models as a systems S = (U,D) where U is a universe of knowledge and D are derivation rules. We say that a b.p. P is compatible with a system S iff along each computation in P S derives F (false) or T (true) at the end correctly according to the label of the reached sink. This key notion modifies the classic paradigm which takes the computational complexity with respect to different classes of restricted b.p.‘s (e.g. read-once b.p.‘s, k-b.p.‘s, b.p.‘s computing in limited time etc.). Now, the restriction is defined by a subset of systems and only these programs are taken into account which are compatible with at least one of the chosen systems. Further we understand the sets U of knowledge(s) as a sets of admissible logical formulae. It is clear that more rich sets U‘s imply the large restrictions on b.p.‘s and consequently the smaller complexities of Boolean functions are detected. More rich logical equipment implies stronger computational effectiveness. Another question arises: given a set of Boolean functions (e.g. codes of some graphs) what logical equipment is optimal from the point of complexity?

Úplný záznam
2019-07-25
09:13
Rozhodování za neurčitosti: Pohled matematika na plánované hospodářství
Rohn, Jiří
V práci jsou popsány hlavní výsledky neoficiálního ekonomicko-matematického výzkumu provedeného v letech 1973-1980 pracovníky Ekonomicko-matematické laboratoře Ekonomického ústavu ČSAV a MFF (J. Bouška, J. Rohn a B. Kalendovský).

Úplný záznam
2019-06-11
07:50
Hybrid Methods for Nonlinear Least Squares Problems
Lukšan, Ladislav ; Matonoha, Ctirad ; Vlček, Jan
This contribution contains a description and analysis of effective methods for minimization of the nonlinear least squares function F(x) = (1=2)fT (x)f(x), where x ∈ Rn and f ∈ Rm, together with extensive computational tests and comparisons of the introduced methods. All hybrid methods are described in detail and their global convergence is proved in a unified way. Some proofs concerning trust region methods, which are difficult to find in the literature, are also added. In particular, the report contains an analysis of a new simple hybrid method with Jacobian corrections (Section 8) and an investigation of the simple hybrid method for sparse least squares problems proposed previously in [33] (Section 14).
Plný text: Stáhnout plný textPDF

Úplný záznam
2019-05-16
18:17
Application of the Infinitely Many Times Repeated BNS Update and Conjugate Directions to Limited-Memory Optimization Methods
Vlček, Jan ; Lukšan, Ladislav
To improve the performance of the L-BFGS method for large scale unconstrained optimization, repeating of some BFGS updates was proposed. Since this can be time consuming, the extra updates need to be selected carefully. We show that groups of these updates can be repeated infinitely many times under some conditions, without a noticeable increase of the computational time. The limit update is a block BFGS update. It can be obtained by solving of some Lyapunov matrix equation whose order can be decreased by application of vector corrections for conjugacy. Global convergence of the proposed algorithm is established for convex and sufficiently smooth functions. Numerical results indicate the efficiency of the new method.

Úplný záznam