Search

Best performing approaches for scholarly document quality prediction are based on embedding models, which do not allow direct explanation of classifiers as distinct words no longer correspond to the input features for model training. Although model-agnostic explanation methods such as Local interpretable model-agnostic explanations (LIME) can be applied, these produce results with questionable correspondence to the ML model. We introduce a new feature importance method, Self-model Rated Entities (SMER), for logistic regression-based classification models trained on word embeddings. We show that SMER has theoretically perfect fidelity with the explained model, as its prediction corresponds exactly to the average of predictions for individual words in the text. SMER allows us to reliably determine which words or entities positively contribute to predicting impactful articles. Quantitative and qualitative evaluation is performed through five diverse experiments conducted on 50.000 research papers from the CORD-19 corpus. Through an AOPC curve analysis, we experimentally demonstrate that SMER produces better explanations than LIME for logistic regression.

The categorization of retail products is essential for the business decision-making process. It is a common practice to classify products based on their quantitative and qualitative characteristics. In this paper we use a purely data-driven approach. Our clustering of products is based exclusively on the customer behaviour. We propose a method for clustering retail products using market basket data. Our model is formulated as an optimization problem which is solved by a genetic algorithm. It is demonstrated on simulated data how our method behaves in different settings. The application using real data from a Czech drugstore company shows that our method leads to similar results in comparison with the classification by experts. The number of clusters is a parameter of our algorithm. We demonstrate that if more clusters are allowed than the original number of categories is, the method yields additional information about the structure of the product categorization.

Finding Bertram's optimal trading strategy for a pair of cointegrated assets following the Ornstein--Uhlenbeck price difference process can be formulated as an unconstrained convex optimization problem for maximization of expected profit per unit of time. This model is generalized to the form where the riskiness of profit, measured by its per-time-unit volatility, is controlled (e.g. in case of existence of limits on riskiness of trading strategies imposed by regulatory bodies). The resulting optimization problem need not be convex. In spite of this undesirable fact, it is demonstrated that the problem is still efficiently solvable. In addition, the problem that parameters of the price difference process are never known exactly and are imprecisely estimated from an observed finite sample is investigated (recalling that this problem is critical for practice). It is shown how the imprecision affects the optimal trading strategy by quantification of the loss caused by the imprecise estimate compared to a theoretical trader knowing the parameters exactly. The main results focus on the geometric and optimization-theoretic viewpoint of the risk-bounded trading strategy and the imprecision resulting from the statistical estimates.

We propose an exact iterative algorithm for minimization of a class of continuous cell-wise linear convex functions on a hyperplane arrangement. Our particular setup is motivated by evaluation of so-called rank estimators used in robust regression, where every cell of the underlying arrangement corresponds to a permutation of residuals (and we also show that the class of function for which the method works is more general). The main obstacle in the construction of the algorithm is how to find an improving direction while standing in a point incident with exponentially many cells of the arrangement. We overcome this difficulty using Birkhoff Theorem which allows us to express the cone of improving directions in the exponential number of cells using a linear system with quadratic number of variables only., Comment: 14 pages, 3 figures

We consider the quadratic optimization problem $\max_{x \in C}\ x^T Q x + q^T x$, where $C\subseteq\mathbb{R}^n$ is a box and $r := \mathrm{rank}(Q)$ is assumed to be $\mathcal{O}(1)$ (i.e., fixed). We show that this case can be solved in polynomial time for an arbitrary $Q$ and $q$. The idea is based on a reduction of the problem to enumeration of faces of a certain zonotope in dimension $O(r)$. This paper generalizes previous results where $Q$ had been assumed to be positive semidefinite and no linear term was allowed in the objective function. Positive definiteness was a strong restriction and it is now relaxed. Generally, the problem is NP-hard; this paper describes a new polynomially solvable class of instances, larger than those known previously.

A rank estimator in robust regression is a minimizer of a function which depends (in addition to other factors) on the ordering of residuals but not on their values. Here we focus on the optimization aspects of rank estimators. We distinguish two classes of functions: the class with a continuous and convex objective function (CCC), which covers the class of rank estimators known from statistics, and also another class (GEN), which is far more general. We propose efficient algorithms for both classes. For GEN we propose an enumerative algorithm that works in polynomial time as long as the number of regressors is O(1). The proposed algorithm utilizes the special structure of arrangements of hyperplanes that occur in our problem and is superior to other known algorithms in this area. For the continuous and convex case, we propose an unconditionally polynomial algorithm finding the exact minimizer, unlike the heuristic or approximate methods implemented in statistical packages.

We consider the algorithm by Ferson et al. (Reliable computing 11(3), p. 207-233, 2005) designed for solving the NP-hard problem of computing the maximal sample variance over interval data, motivated by robust statistics (in fact, the formulation can be written as a nonconvex quadratic program with a specific structure). First, we propose a new version of the algorithm improving its original time bound $O(n^2 2^\omega)$ to $O(n \log n+n\cdot 2^\omega)$, where $n$ is number of input data and $\omega$ is the clique number in a certain intersection graph. Then we treat input data as random variables as it is usual in statistics) and introduce a natural probabilistic data generating model. We get $2^\omega = O(n^{1/\log\log n})$ and $\omega = O(\log n / \log\log n)$ on average. This results in average computing time $O(n^{1+\epsilon})$ for $\epsilon > 0$ arbitrarily small, which may be considered as "surprisingly good" average time complexity for solving an NP-hard problem. Moreover, we prove the following tail bound on the distribution of computation time: hard instances, forcing the algorithm to compute in time $2^{\Omega(n)}$, occur rarely, with probability tending to zero at the rate $e^{-n\log\log n}$.

This work connects two mathematical fields - computational complexity and interval linear algebra. It introduces the basic topics of interval linear algebra - regularity and singularity, full column rank, solving a linear system, deciding solvability of a linear system, computing inverse matrix, eigenvalues, checking positive (semi)definiteness or stability. We discuss these problems and relations between them from the view of computational complexity. Many problems in interval linear algebra are intractable, hence we emphasize subclasses of these problems that are easily solvable or decidable. The aim of this work is to provide a basic insight into this field and to provide materials for further reading and research., Comment: Submitted to Mat Triad 2015