In recent years, the proliferation of smart mobile devices has lead to the gradual integration of search functionality within mobile platforms. This has created an incentive to move away from the "ten blue links" metaphor, as mobile users are less likely to click on them, expecting to get the answer directly from the snippets. In turn, this has revived the interest in Question Answering. Then, along came chatbots, conversational systems, and messaging platforms, where the user needs could be better served with the system asking follow-up questions in order to better understand the user's intent. While typically a user would expect a single response at any utterance, a system could also return multiple options for the user to select from, based on different system understandings of the user's intent. However, this possibility should not be overused, as this practice could confuse and or annoy the user. How to produce good variable-length lists, given the conflicting objectives of staying short while maximizing the likelihood of having a correct answer included in the list, is an underexplored problem. It is also unclear how to evaluate a system that tries to do that. Here we aim to bridge this gap. In particular, we define some necessary and some optional properties that an evaluation measure fit for this purpose should have. We further show that existing evaluation measures from the IR tradition are not entirely suitable for this setup, and we propose novel evaluation measures that address it satisfactorily.
As we define a set of properties that need to be satisfied by an evaluation measure for variable-length output, our work is closely related to the properties of truncated evaluation measures introduced in @cite_17 . Their property is similar to our , except that imposes strict monotonicity. The property is similar to our , but it discounts for irrelevant documents at the end of the list only.
@cite_17
1775912700 2038521541 2091126969 2950427777
The primary problem in property testing is to decide whether a given function satisfies a certain property or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the uniform distribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this article, we provide simple and optimal testers for bounded derivative properties over arbitrary product distributions. Bounded derivative properties include fundamental properties, such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing over arbitrary ranges. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show that this sum-of-depths is also a lower bound. A technical contribution of our work is an optimal dimension reduction theorem for all bounded derivative properties that relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity, and our theorem is an exponential improvement to the previous best-known result. The field of property testing studies algorithms that distinguish, using a small number of queries, between inputs which satisfy a given property, and those that are far' from satisfying the property. Testing properties that are defined in terms of monotonicity has been extensively investigated, primarily in the context of the monotonicity of a sequence of integers, or the monotonicity of a function over the n-dimensional hypercube 1,l,m n. These works resulted in monotonicity testers whose query complexity is at most polylogarithmic in the size of the domain.We show that in its most general setting, testing that Boolean functions are close to monotone is equivalent, with respect to the number of required queries, to several other testing problems in logic and graph theory. These problems include: testing that a Boolean assignment of variables is close to an assignment that satisfies a specific 2-CNF formula, testing that a set of vertices is close to one that is a vertex cover of a specific graph, and testing that a set of vertices is close to a clique.We then investigate the query complexity of monotonicity testing of both Boolean and integer functions over general partial orders. We give algorithms and lower bounds for the general problem, as well as for some interesting special cases. In proving a general lower bound, we construct graphs with combinatorial properties that may be of independent interest. Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally defined by Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems: Given a fixed property P and an input f, distinguish between the case that f satisfies P, and the case that no input that differs from f in less than some fixed fraction of the places satisfies P. An (e, q)-test for P is a randomized algorithm that queries at most q places of an input f and distinguishes with probability 2 3 between the case that f has the property and the case that at least an e-fraction of the places of f need to be changed in order for it to have the property. Here we concentrate on labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e. as a product order of total orders). The main result here presents an (e, poly(1 e))-test for every property of 0 1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets. Such properties include the “monotonicity” property studied in [9,8,13], other more complicated forbidden chain patterns, and general forbidden poset patterns. We also present a (less efficient) test for such properties of labeled grids with larger fixed size alphabets. All the above tests have in addition a 1-sided error probability. This class of properties is related to properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations. We also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of O(n 1 4) (for a small enough fixed e) exists. The above results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. They also lay out a platform that bridges some previous results. We characterize the set of properties of Boolean-valued functions on a finite domain @math that are testable with a constant number of samples. Specifically, we show that a property @math is testable with a constant number of samples if and only if it is (essentially) a @math -part symmetric property for some constant @math , where a property is @math -part symmetric if there is a partition @math of @math such that whether @math satisfies the property is determined solely by the densities of @math on @math . We use this characterization to obtain a number of corollaries, namely: (i) A graph property @math is testable with a constant number of samples if and only if whether a graph @math satisfies @math is (essentially) determined by the edge density of @math . (ii) An affine-invariant property @math of functions @math is testable with a constant number of samples if and only if whether @math satisfies @math is (essentially) determined by the density of @math . (iii) For every constant @math , monotonicity of functions @math on the @math -dimensional hypergrid is testable with a constant number of samples.