1,721,108 research outputs found
Accounting for real world phenomena in machine learning and mechanism design
No full textAs data becomes more readily available, individuals and organisations are increasingly relying on automated systems to make decisions on their behalf. Both machine learning and mechanism design play key roles in the design of such systems. Machine learning is often deployed to learn complex decision rules that mimic or improve upon those adopted by humans. Meanwhile, mechanism design is often deployed to ensure that decision rules satisfy certain axiomatic properties of interest to the designer, such as fairness and incentive compatibility. Unfortunately, many real world settings fall outside the scope of traditional machine learning and mechanism design frameworks. This thesis investigates how approaches from mechanism design and machine learning can be rigorously extended and adapted for such settings to yield meaningful theoretical guarantees.In particular, we investigate three problem domains; 1) linear regression in the presence of strategic agents, 2) sequential resource deployment with reusable resources and 3) repeated matching with reusable resources. For the first problem domain, we provide a theoretical framework based on Stackelberg predictions games. When the incentives of agents can be captured by a square loss function, we provide a polynomial time algorithm minimising Stackelberg risk, a natural analog to risk in classical supervised learning. For the second problem domain, we introduce a new multi-armed bandit model, called the adversarial blocking bandit problem, which incorporates nonstationary reward sequences and resource unavailability. In particular, we provide finite-time regret guarantees for this setting, by benchmarking against an oracle algorithm which approximates the optimal arm pulling policy. Lastly, for the third problem domain, we introduce a new sequential matching setting, in which a central planner is tasked with constructing matchings repeatedly through time under the assumption that some goods or services may become temporarily unavailable once assigned. Motivated by the random serial dictatorship algorithm, we construct an algorithm for the setting which is approximately truthful and approximately maximises social welfare
Explicit Explore, Exploit, or Escape (): near-optimal safety-constrained reinforcement learning in polynomial time
Get PDFIn reinforcement learning (RL), an agent must explore an initially unknown
environment in order to learn a desired behaviour. When RL agents are deployed
in real world environments, safety is of primary concern. Constrained Markov
decision processes (CMDPs) can provide long-term safety constraints; however,
the agent may violate the constraints in an effort to explore its environment.
This paper proposes a model-based RL algorithm called Explicit Explore,
Exploit, or Escape (), which extends the Explicit Explore or Exploit
() algorithm to a robust CMDP setting. explicitly separates
exploitation, exploration, and escape CMDPs, allowing targeted policies for
policy improvement across known states, discovery of unknown states, as well as
safe return to known states. robustly optimises these policies on the
worst-case CMDP from a set of CMDP models consistent with the empirical
observations of the deployment environment. Theoretical results show that
finds a near-optimal constraint-satisfying policy in polynomial time whilst
satisfying safety constraints throughout the learning process. We then discuss
as a practical algorithmic framework, including robust-constrained
offline optimisation algorithms, the design of uncertainty sets for the
transition dynamics of unknown states, and how to further leverage empirical
observations and prior knowledge to relax some of the worst-case assumptions
underlying the theory.Comment: Accepted at Machine Learnin
More on the lead seal of bishop Nicholas from Pliska
No full textUnearthed more than 20 years ago during archaeological excavations and research of Prince Boris' Large Basilica in the capital centre of Pliska, the seal of Bishop Nicholas raises interesting questions about the first
Archbishopric of the Bulgarian church. This discovery stimulated the appearance of a number of publications about it.
The author was the first one to write short communications about this important sphragistic monument in two daily newspapers after its discovery. The present article is its first analysis on the pages of a scholarly publication.
The lead form has a diameter of 25-26 mm and is 1-1,5 mm thick. On the obverse within a pointed circle is represented St. Nicholas in a bishop's
attire with his right hand raised for blessing. With his left hand he holds a Gospels book in front of him. Above the image there is a Greek inscription which begins with a cross: +ΑΓ’ΝΚWΛ’Β’Τ’ΔΟ meaning: +˝Αγ(ιε) Νηχολ(άω) β(οήθει) τ(ῶ) δο(ύλω σού).
On the reverse there is also a pointed ring. The inscription follows divided into four lines. Above the first line in the upper part of the pictorial field is placed a four-arm cross with a "foliate" base of the vertical arm. The
inscription reads:
ΗΚΟΛΑW — Νηχολάω, ΕΠΙCΚΟΠW — έπισϰόπω,
ΘΕΟΒΟΥΛ — Θεο(σεβεί) Βουλ-, ΕΙΑC — (γαρ)είας
+˝Αγιε Νηχολάω βοήθει τῶ δούλω σού Νηχολάω έπισϰόπω Θεοσεβεί Βουλγαρείας.
Since it is impossible to specify a place name Theoboul'ta, I fill in the missing parts in the last fourth and fifth lines and read the inscription as follows: + Saint Nicholas, help thy servant Nicholas, the pious Bishop of Bulgaria. The seal can be dated between 865 and 880 AD
Optimal learning from verified training data
Get PDFStandard machine learning algorithms typically assume that data is sampled independently from the distribution of interest. In attempts to relax this assumption, fields such as adversarial learning typically assume that data is provided by an adversary, whose sole objective is to fool a learning algorithm. However, in reality, it is often the case that data comes from self-interested agents, with less malicious goals and intentions which lie somewhere between the two settings described above. To tackle this problem, we present a Stackelberg competition model for least squares regression, in which data is provided by agents who wish to achieve specific predictions for their data. Although the resulting optimisation problem is nonconvex, we derive an algorithm which converges globally, outperforming current approaches which only guarantee convergence to local optima. We also provide empirical results on two real-world datasets, the medical personal costs dataset and the red wine dataset, showcasing the performance of our algorithm relative to algorithms which are optimal under adversarial assumptions, outperforming the state of the art
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
Adversarial blocking bandits
Get PDFWe consider a general adversarial multi-armed blocking bandit setting where each played arm can be blocked (unavailable) for some time periods and the reward per arm is given at each time period adversarially without obeying any distribution. The setting models scenarios of allocating scarce limited supplies (e.g., arms) where the supplies replenish and can be reused only after certain time periods. We first show that, in the optimization setting, when the blocking durations and rewards are known in advance, finding an optimal policy (e.g., determining which arm per round) that maximises the cumulative reward is strongly NP-hard, eliminating the possibility of a fully polynomial-time approximation scheme (FPTAS) for the problem unless P = NP. To complement our result, we show that a greedy algorithm that plays the best available arm at each round provides an approximation guarantee that depends on the blocking durations and the path variance of the rewards. In the bandit setting, when the blocking durations and rewards are not known, we design two algorithms, RGA and RGA-META, for the case of bounded duration an path variation. In particular, when the variation budget B_T is known in advance, RGA can achieve O(\sqrt{T(2\tilde{D}+K)B_{T}}) dynamic approximate regret. On the other hand, when B_T is not known, we show that the dynamic approximate regret of RGA-META is at most O((K+\tilde{D})^{1/4}\tilde{B}^{1/2}T^{3/4}) where \tilde{B} is the maximal path variation budget within each batch of RGA-META (which is provably in order of o(\sqrt{T}). We also prove that if either the variation budget or the maximal blocking duration is unbounded, the approximate regret will be at least Theta(T). We also show that the regret upper bound of RGA is tight if the blocking durations are bounded above by an order of O(1)
- …
