Computer Science
http://hdl.handle.net/10012/9930
2021-11-19T08:47:08ZGeodesic Convex Analysis of Group Scaling for the Paulsen Problem and the Tensor Normal Model
http://hdl.handle.net/10012/17710
Geodesic Convex Analysis of Group Scaling for the Paulsen Problem and the Tensor Normal Model
Ramachandran, Akshay
The framework of scaling problems has recently had much interest in the theoretical computer science community due to its variety of applications, from algebraic complexity to machine learning. In this thesis, our main motivation will be two new applications: the Paulsen problem from frame theory, and the tensor normal model in statistical estimation. In order to give new results for these problems, we provide novel convergence analyses for matrix scaling and tensor scaling. Specifically, we will use the framework of geodesic convex optimization presented in Bürgisser et al. [20] and analyze two sufficient conditions (called strong convexity and pseudorandomness) for fast convergence of the natural gradient flow algorithm in this setting. This allows us to unify and improve many previous results [62], [63], and [36] for special cases of tensor scaling.
In the first half of the thesis, we focus on the Paulsen problem where we are given a set of n vectors in d dimensions that ε-approximately satisfy two balance conditions, and asked whether there is a nearby set of vectors that exactly satisfy those balance conditions. This is an important question from frame theory [24] for which very little was known despite considerable attention. We are able to give optimal distance bounds for the Paulsen problem in both the worst-case and the average-case by improving the smoothed analysis approach of Kwok et al. [62]. Specifically, we analyze certain strong convergence conditions for frame scaling, and then show that a random perturbation of the input frame satisfies these conditions and can be scaled to a nearby solution.
In the second half of the thesis, we study the matrix and tensor normal models, which are a family of Gaussian distributions on tensor data where the covariance matrix respects this tensor product structure. We are able to generalize our scaling results to higher- order tensors and give error bounds for the maximum likelihood estimator (MLE) of the tensor normal model with a number of samples only a single dimension factor above the existence threshold. This result relies on some spectral properties of random Gaussian tensors shown by Pisier [80]. We also give the first rigorous analysis of the Flip-Flop algorithm, showing that it converges exponentially to the MLE with high probability. This explains the empirical success of this well-studied heuristic for computing the MLE.
2021-11-18T00:00:00ZUsers, Queries, and Bad Abandonment in Web Search
http://hdl.handle.net/10012/17709
Users, Queries, and Bad Abandonment in Web Search
Abualsaud, Mustafa
After a user submits a query and receives a list of search results, the user may abandon their query without clicking on any of the search results. A bad query abandonment is when a searcher abandons the SERP because they were dissatisfied with the quality of the search results, often making the user reformulate their query in the hope of receiving better search results. As we move closer to understanding when and what causes a user to abandon their query under different qualities of search results, we move forward in an overall understanding of user behavior with search engines. In this thesis, we describe three user studies to investigate bad query abandonment.
First, we report on a study to investigate the rate and time at which users abandon their queries at different levels of search quality. We had users search for answers to questions, but showed users manipulated SERPs that contain one relevant document placed at different ranks. We show that as the quality of search results decreases, the probability of abandonment increases, and that users quickly decide to abandon their queries. Users make their decisions fast, but not all users are the same. We show that there appear to be two types of users that behave differently, with one group more likely to abandon their query and are quicker in finding answers than the group less likely to abandon their query.
Second, we describe an eye-tracking experiment that focuses on understanding possible causes of users' willingness to examine SERPs and what motivates users to continue or discontinue their examination. Using eye-tracking data, we found that a user deciding to abandon a query is best understood by the user's examination pattern not including a relevant search result. If a user sees a relevant result, they are very likely to click it. However, users' examination of results are different and may be influenced by other factors. The key factors we found are the rank of search results, the user type, and the query quality. For example, we show that regardless of where the relevant document is placed in the SERP, the type of query submitted affects examination, and if a user enters an ambiguous query, they are likely to examine fewer results.
Third, we show how the nature of non-relevant material affects users' willingness to further explore a ranked list of search results. We constructed and showed participants manipulated SERPs with different types of non-relevant documents. We found that user examination of search results and time to query abandonment is influenced by the coherence and type of non-relevant documents included in the SERP. For SERPs coherent on off-topic results, users spend the least amount of time before abandoning and are less likely to request to view more results. The time they spend increases as the SERP quality improves, and users are more likely to request to view more results when the SERP contains diversified non-relevant results on multiple subtopics.
2021-11-18T00:00:00ZAre machine learning corpora “fair dealing” under Canadian law?
http://hdl.handle.net/10012/17708
Are machine learning corpora “fair dealing” under Canadian law?
Brown, Dan; Byl, Lauren; Grossman, Maura R.
We consider the use of large corpora for training compuationally creative systems, particularly those that write new text based on the style of an existing author or genre. Under Canadian copyright law, a key concern for whether this is “fair dealing” is whether this usage will result in new creations that compete with those in the corpus. While recent law review articles in the United States suggest that training models on such corpora would be “fair use” in the United States, we argue that Canadian law may, in fact, forbid this use when the new products compete with works in the original corpus
2021-09-01T00:00:00ZDowsing for Math Answers: Exploring MathCQA with a Math-aware Search Engine
http://hdl.handle.net/10012/17696
Dowsing for Math Answers: Exploring MathCQA with a Math-aware Search Engine
Ng, Yin Ki
Solving math problems can be challenging. It is so challenging that one might wish to seek insights from the internet, looking for related references to understand more about the problems. Even more, one might wish to actually search for the answer, believing that some wise people have already solved the problem and shared their intelligence selflessly. However, searching for relevant answers for a math problem effectively from those sites is itself not trivial.
This thesis details how a math-aware search engine Tangent-L---which adopts a traditional text retrieval model (Bag-of-Words scored by BM25+ using formulas' symbol pairs and other features as "words''---tackles the challenge of finding answers to math questions. Various adaptations for Tangent-L to this challenge are explored, including query conversion, weighting scheme of math features, and result re-ranking.
In a recent workshop series named Answer Retrieval for Questions on Math (ARQMath), and with math problems from Math StackExchange, the submissions based on these adaptations of Tangent-L achieved the best participant run for two consecutive years, performing better than many participating models designed with machine learning and deep learning models. The major contributions of this thesis are the design and implementation of the three-stage approach to adapting Tangent-L to the challenge, and the detailed analyses of many variants to understand which aspects are most beneficial. The code repository is available, as is a data exploration too built for interested participants to view the math questions in this ARQMath challenge and check the performance of their answer rankings.
2021-11-09T00:00:00Z