This paper presents two approaches to determining estimates of an equivalence relation on the basis of pairwise comparisons with random errors. Obtaining such an estimate requires the solution of a discrete programming problem which minimizes the sum of the differences between the form of the relation and the comparisons. The problem is NP hard and can be solved with the use of exact algorithms for sets of moderate size, i.e. about 50 elements. In the case of larger sets, i.e. at least 200 comparisons for each element, it is necessary to apply heuristic algorithms. The paper presents results (a statistical preprocessing), which enable us to determine the optimal or a near-optimal solution with acceptable computational cost. They include: the development of a statistical procedure producing comparisons with low probabilities of errors and a heuristic algorithm based on such comparisons. The proposed approach guarantees the applicability of such estimators for any size of set.
The problem of estimation of the partial order on the basis of multiple pairwise comparisons in binary and multivalent form, with random errors, is investigated. The estimators are based on the idea of the nearest adjoining order (see Slater, 1961; Klukowski 2011). Two approaches are examined: comparisons indicating the direction of preference (binary) and comparisons indicating the difference of ranks (multivalent) - both with possibility of existence of incomparable elements. The properties of estimators and the optimization problems formulated in order to obtain them are similar to those for the case of complete relation. However, the assumptions about the distributions of comparison errors are different – they comprise the case of incomparable elements.
This paper presents a review of results of the author in the area of estimation of the relations of equivalence, tolerance and preference within a finite set based on multiple, independent (in a stochastic way) pairwise comparisons with random errors, in binary and multivalent forms. These estimators require weaker assumptions than those used in the literature on the subject. Estimates of the relations are obtained based on solutions to problems from discrete optimization. They allow application of both types of comparisons – binary and multivalent (this fact relates to the tolerance and preference relations). The estimates can be verified in a statistical way; in particular, it is possible to verify the type of the relation. The estimates have been applied by the author to problems regarding forecasting, financial engineering and bio-cybernetics.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The problem of estimation of the preference relation in a finite set on the basis of pairwise comparisons, in the form of differences of ranks with random errors, with the use of nearest adjoining order idea (NAO), is investigated in the paper. The results presented are extension and correction of the earlier works of the author; especially the case of multiple independent comparisons of each pair is examined. The comparisons of each pair are aggregated through the average or the median of comparisons. The estimated form of the relation is obtained in both cases on the basis of discrete programming tasks. The properties of the estimators are obtained under weak assumptions about distributions of comparison errors, in particular, the distributions may be unknown.
5
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The methods of tolerance relation estimation on the basis of pairwise comparisons with random errors, in the case of multiple comparisons for each pair, are proposed in the paper. Each comparison expresses the number of common features of both elements or the number of their missing features. The assumptions made about distributions of comparison errors are very weak, in particular they may be unknown. Two approaches are discussed: the first one, based on averaging of comparisons for each pair and the second, based on the median from comparisons. The estimated form of the relation is determined (in both cases) on the basis of the appropriate discrete programming task. The properties of estimators are based on some probabilistic inequalities. An example of application of the estimators proposed is presented.
6
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The statistical procedure for determination of the type of relation - equivalence or tolerance - in a finite set of elements, estimated on the basis of pairwise comparisons with random errors, is presented. The procedure consists of two tests based on Chebyshev's inequality for variance of a random variable; the test statistic is a mixture of some random variables. An example of application of the procedure - determination of relation type in the set of functions expressing profitability of treasury securities sold at auctions in Poland - is presented, too.
The paper presents formulations of optimisation problems for minimisation of servicing cost of government debt instruments (T-bills and T-bonds) issued in Poland and examples of their applications. The first of these problems allows for determining the structure of T-bills with different maturities - from 1 to 52 weeks (sold at multiprice auction), which minimise their servicing cost. This cost (criterion function) is based on T-bills profitability determined by compound rate of return (CRR). The constraints of the task express: * minimum receipts to the State Budget, * maximal profitability, * average maturity, and * minimal and maximal amount for each type of bills. The generalisation of this problem for some series of (consecutive) auctions is also discussed. The second task makes it possible to determine optimal structure of T-bonds using a similar (but more complex) form of the criterion function and more extensive set of constraints. The problems presented are of discrete and non-linear form and in result - rather difficult to solve in real time (during the auction). Therefore, some continuos approximations of these problems based on polynomials determined with the use of least squares method are suggested. Such an approach makes it possible to obtain an optimal solution in several minutes using Excel spreadsheet (package solver) and PC computer. Examples of actual problems for T-bills and T-bonds, based on data for the year 2000 are presented, too. The application of optimisation methods resulted in (relative) gain measured by a criterion function equal to about 1% (annual costs of the domestic debt equals about [3 * 10^9] US$).
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.