zbMATH — the first resource for mathematics

Easy and optimal queries to reduce set uncertainty. (English) Zbl 1394.90212
Summary: In this paper, we address the problem of optimally querying a single expert to reduce set (interval) uncertainty. We propose optimal querying strategies for two particular query formats (local bound and pairwise comparisons) based on two main selection criteria (the minimax and the Bayesian rules). We study the computational aspects of the optimal solution in the general case and for the specific functions of practical interest (monotonic and multi-linear). The use of the proposed approach is illustrated through numerical simulations on a common estimation problem in reliability analysis.
90B25 Reliability, availability, maintenance, inspection in operations research
90C40 Markov and semi-Markov decision processes
90C30 Nonlinear programming
Full Text: DOI
[1] Aboalkhair, A. M.; Coolen, F. P.; MacPhee, I. M., Nonparametric predictive reliability of series of voting systems, European Journal of Operational Research, 226, 1, 77-84, (2013) · Zbl 1292.91059
[2] Ambati, V.; Vogel, S.; Carbonell, J., Active learning-based elicitation for semi-supervised word alignment, Proceedings of the Acl 2010 Conference Short Papers, 365-370, (2010), Association for Computational Linguistics
[3] Aspinall, W.; Cooke, R., Quantifying scientific uncertainty from expert judgement elicitation, (Rougier, J.; etal., Risk and Uncertainty Assessment for Natural Hazards, (2013), Cambridge: Cambridge University Press), 64-99
[4] Baraldi, P.; Zio, E.; Compare, M., A method for ranking components importance in presence of epistemic uncertainties, Journal of Loss Prevention in the Process Industries, 22, 5, 582-592, (2009)
[5] Beccacece, F.; Borgonovo, E.; Buzzard, G.; Cillo, A.; Zionts, S., Elicitation of multiattribute value functions through high dimensional model representations: monotonicity and interactions, European Journal of Operational Research, 246, 2, 517-527, (2015) · Zbl 1346.91079
[6] Ben Abdallah, N.; Destercke, S., Optimal expert elicitation to reduce interval uncertainty, Uncertainty in Artificial Intelligence (UAI 2015), 12-22, (2015), AUAI press Amsterdam, Netherlands
[7] Benabbou, N.; Perny, P.; Viappiani, P., Incremental elicitation of Choquet capacities for multicriteria decision making, Proceedings of ECAI’14, 87-92, (2014) · Zbl 1366.91044
[8] Boland, P. J.; El-Neweihi, E., Measures of component importance in reliability theory, Computers & Operations Research, 22, 4, 455-463, (1995) · Zbl 0822.90070
[9] Boutilier, C., A POMDP formulation of preference elicitation problems, Proceedings of AAAI Conference, 1, 3, 321-323, (2002)
[10] Boutilier, C.; Filmus, Y.; Oren, J., Efficient vote elicitation under candidate uncertainty, IJCAI, (2013)
[11] Boutilier, C.; Patrascu, R.; Poupart, P.; Schuurmans, D., Constraint-based optimization and utility elicitation using the minimax decision criterion., Artificial Intelligence, 170, 8-9, 686-713, (2006) · Zbl 1131.91317
[12] Campodonico, S.; Singpurwalla, N., Expert opinion in reliability, Technical Report, (1993), DTIC Document
[13] Dempster, A., Upper and lower probabilities induced by a multivalued mapping, Annals of Mathematical Statistics, 38, 325-339, (1967) · Zbl 0168.17501
[14] Drenick, R., Multilinear programming: duality theories, Journal of optimization theory and applications, 72, 3, 459-486, (1992) · Zbl 0808.90092
[15] Drenick, R., Multilinear programming: duality theories, Journal of Optimization Theory and Applications, 81, 2, 421-422, (1994) · Zbl 0810.90116
[16] Dyer, M.; Frieze, A., On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing, 17, 5, 967-975, (1988) · Zbl 0668.68049
[17] Fedorov, V., Optimal experimental design, Wiley Interdisciplinary Reviews: Computational Statistics, 2, 5, 581-589, (2010)
[18] Ferson, S.; Ginzburg, L. R., Different methods are needed to propagate ignorance and variability, Reliability Engineering & System Safety, 54, 2, 133-144, (1996)
[19] Fortin, J.; Dubois, D.; Fargier, H., Gradual numbers and their application to fuzzy interval analysis, Fuzzy Systems, IEEE Transactions on, 16, 2, 388-402, (2008)
[20] Grabisch, M.; Labreuche, C., On the extension of pseudo-Boolean functions for the aggregation of interacting criteria, European Journal of Operational Research, 148, 28-47, (2003), Elsevier · Zbl 1035.90033
[21] Greco, S.; Mousseau, V.; Słowiński, R., Ordinal regression revisited: multiple criteria ranking using a set of additive value functions, European Journal of Operational Research, 191, 2, 416-436, (2008) · Zbl 1147.90013
[22] Hammer, P.; Rudeanu, S., Boolean Methods in Operations Research and Related Areas, (1968), Springer, Berlin Heidelberg New York · Zbl 0155.28001
[23] Khachiyan, L., Complexity of polytope volume computation, (1993), Springer · Zbl 0789.52016
[24] Kreinovich, V.; Lakeyev, A.; Rohn, J., Computational complexity of interval algebraic problems: some are feasible and some are computationally intractable-a survey, Mathematical Research, 90, 293-306, (1996) · Zbl 0849.65023
[25] Laneve, C.; Luscu, T.; Vania, S., The interval analysis of multilinear expressions, Electronic Notes in Theroretical Computer Science, 267, 2, 43-53, (2010)
[26] Lin, P.; Leon, B.; Huang, T., A new algorithm for symbolic system reliability analysis, Reliability, IEEE Transactions on, R-25, 1, 2-15, (1976) · Zbl 0348.90077
[27] Marichal, J.-L. (2014). Structure functions and minimal path sets. arXiv preprint arXiv:1401.0803.
[28] McCormick, G., Computability of global solutions to factorable nonconvex programs: part i - convex underestimating problems, Mathematical Programming, 10, 147-175, (1976) · Zbl 0349.90100
[29] O’Hagan, A.; Buck, C. E.; Daneshkhah, A.; Eiser, J. R.; Garthwaite, P. H.; Jenkinson, D. J.; Oakley, J. E.; Rakow, T., Uncertain judgements: eliciting experts’ probabilities, (2006), John Wiley & Sons · Zbl 1269.62009
[30] Owen, G., Multilinear extensions of games, Management Sciences, 18, 64-79, (1972) · Zbl 0239.90049
[31] Rikun, A., A convex envelope formula for multilinear functions, Journal of Global Optimization, 10, 4, 425-437, (1997) · Zbl 0881.90099
[32] Sallak, M.; Schon, W.; Aguirre, F., Extended component importance measures considering aleatory and epistemic uncertainties, Reliability, IEEE Transactions on, 62, 1, 49-65, (2013)
[33] Sandri, S.; Dubois, D.; Kalfsbeek, H., Elicitation, assessment, and pooling of expert judgments using possibility theory, Fuzzy Systems, IEEE Transactions on, 3, 3, 313-335, (1995)
[34] Shafer, G., A Mathematical Theory of Evidence, (1976), Princeton University Press Princeton, N. J · Zbl 0359.62002
[35] Sherali, H., Convex envelopes of multilinear functions over a unit hypercube and over special discrete sets, Acta Mathematica Vietnamica, 22, 1, 245-270, (1997) · Zbl 0914.90205
[36] Tehrani, A. F.; Cheng, W.; Dembczyński, K.; Hüllermeier, E., Learning monotone nonlinear models using the Choquet integral, Machine Learning, 89, 1-2, 183-211, (2012) · Zbl 1260.68348
[37] Van Noortwijk, J. M.; Dekker, R.; Cooke, R. M.; Mazzuchi, T. A., Expert judgment in maintenance optimization, Reliability, IEEE Transactions on, 41, 3, 427-432, (1992)
[38] Viappiani, P.; Kroer, C., Robuts optimization of recommendation sets with the maximin utility criterion, Proceedings of the Third Algorithmic Decision Theory International Conference, 411-424, (2013) · Zbl 1406.91091
[39] Wald, A., Statistical decision functions which minimize the maximum risk, Annals of Mathematics, Second Series, 46, 2, 265-280, (1945) · Zbl 0063.08126
[40] Wang, T.; Boutilier, C., Incremental utility elicitation with the minimax regret decision criterion, Ijcai, 309-318, (2003)
[41] Warshall, S., A theorem on Boolean matrices, Journal of the ACM (JACM), 9, 1, 11-12, (1962) · Zbl 0118.33104
[42] Yannakakis, M., Expressing combinatorial optimization problems by linear programs, Journal of Computer and System Sciences, 43, 3, 441-466, (1991) · Zbl 0748.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.