bluuebunny/crossref_metadata_2025 huggingface dataset:
Achieving Envy-freeness and Equitability with Monetary Transfers
Authors: Aziz Haris
Published: September 2022

When allocating indivisible resources or tasks, an envy-free allocation or equitable allocation may not exist. We present a sufficient condition and an algorithm to achieve envy-freeness and equitability when monetary transfers are allowed. The approach works for any agent valuation functions (positive or negative) as long as they satisfy superadditivity. For the case of additive utilities, we present a characterization of allocations that can simultaneously be made equitable and envy-free via payments. Our study shows that superadditive valuations constitute the largest class of valuations for which an envy-free and equitable outcome exists for all instances. We then present a distributed algorithm to compute an approximately envy-free outcome for any class of valuations.
Fair and Truthful Mechanisms for Dichotomous Valuations
Authors: Babaioff Moshe , Ezra Tomer , Feige Uriel
Published: September 2022

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties ex-post. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations.
Bayesian Persuasion under Ex Ante and Ex Post Constraints
Authors: Babichenko Yakov , Talgam-Cohen Inbal , Zabarnyi Konstantin
Published: September 2022

Bayesian persuasion, as introduced by Kamenica and Gentzkow in 2011, is the study of information sharing policies among strategic agents. A prime example is signaling in online ad auctions: what information should a platform signal to an advertiser regarding a user when selling the opportunity to advertise to her? Practical considerations such as preventing discrimination, protecting privacy or acknowledging limited attention of the information receiver impose constraints on information sharing. We propose a simple way to mathematically model such constraints as restrictions on Receiver's admissible posterior beliefs. We consider two families of constraints - ex ante and ex post; the latter limits each instance of Sender-Receiver communication, while the former more general family can also pose restrictions in expectation. For the ex ante family, a result of Doval and Skreta (2018) establishes the existence of an optimal signaling scheme with a small number of signals - at most the number of constraints plus the number of states of nature - and we show this result is tight. For the ex post family, we tighten the previous bound of Vølund (2018), showing that the required number of signals is at most the number of states of nature, as in the original Kamenica-Gentzkow setting. As our main algorithmic result, we provide an additive bi-criteria FPTAS for an optimal constrained signaling scheme assuming a constant number of states of nature; we improve the approximation to single-criteria under a Slater-like regularity condition. The FPTAS holds under standard assumptions, and more relaxed assumptions yield a PTAS. We then establish a bound on the ratio between Sender's optimal utility under convex ex ante constraints and the corresponding ex post constraints. We demonstrate how this result can be applied to find an approximately welfare-maximizing constrained signaling scheme in ad auctions.
Achieving Proportionality up to the Maximin Item with Indivisible Goods
Authors: Baklanov Artem , Garimidi Pranav , Gkatzelis Vasilis , Schoepflin Daniel
Published: September 2022

We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fairness, and a very vibrant line of research has aimed to circumvent them using appropriate notions of approximate fairness. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances, while the best known achievable approximations (PROP1) are much weaker. We introduce the notion of proportionality up to the maximin item (PROPm) and show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations. PROPm provides a well-motivated middle-ground between PROP1 and PROPx, while also capturing some elements of the well-studied maximin share (MMS) benchmark: another relaxation of proportionality that has attracted a lot of attention.
Welfare Guarantees in Schelling Segregation
Authors: Bullinger Martin , Suksompong Warut , Voudouris Alexandros A.
Published: September 2022

Schelling's model is an influential model that reveals how individual perceptions and incentives can lead to racial segregation. Inspired by a recent stream of work, we study welfare guarantees and complexity in this model with respect to several welfare measures. First, we show that while maximizing the social welfare is NP-hard, computing an assignment with approximately half of the maximum welfare can be done in polynomial time. We then consider Pareto optimality and introduce two new optimality notions, and establish mostly tight bounds on the worst-case welfare loss for assignments satisfying these notions. In addition, we show that for trees, it is possible to decide whether there exists an assignment that gives every agent a positive utility in polynomial time; moreover, when every node in the topology has degree at least 2, such an assignment always exists and can be found efficiently.
Computational Analyses of the Electoral College: Campaigning Is Hard But Approximately Manageable
Authors: Dehghani Sina , Saleh Hamed , Seddighin Saeed , Teng Shang-Hua
Published: September 2022

In the classical discrete Colonel Blotto game—introduced
by Borel in 1921—two colonels simultaneously distribute
their troops across multiple battlefields. The winner of each
battlefield is determined by a winner-take-all rule, independently
of other battlefields. In the original formulation, each
colonel’s goal is to win as many battlefields as possible. The
Blotto game and its extensions have been used in a wide
range of applications from political campaign—exemplified
by the U.S presidential election—to marketing campaign,
from (innovative) technology competition to sports competition.
Despite persistent efforts, efficient methods for finding
the optimal strategies in Blotto games have been elusive
for almost a century—due to exponential explosion in
the organic solution space—until Ahmadinejad, Dehghani,
Hajiaghayi, Lucier, Mahini, and Seddighin developed the
first polynomial-time algorithm for this fundamental gametheoretical
problem in 2016. However, that breakthrough
polynomial-time solution has some structural limitation. It
applies only to the case where troops are homogeneous with
respect to battlegruounds, as in Borel’s original formulation:
For each battleground, the only factor that matters to the winner’s
payoff is how many troops as opposed to which sets of
troops are opposing one another in that battleground.

In this paper, we consider a more general setting of the
two-player-multi-battleground game, in which multifaceted
resources (troops) may have different contributions to different
battlegrounds. In the case of U.S presidential campaign,
for example, one may interpret this as different types
of resources—human, financial, political—that teams can invest
in each state. We provide a complexity-theoretical evidence
that, in contrast to Borel’s homogeneous setting, finding
optimal strategies in multifaceted Colonel Blotto games
is intractable. We complement this complexity result with
a polynomial-time algorithm that finds approximately optimal
strategies with provable guarantees. We also study a further
generalization when two competitors do not have zerosum/
constant-sum payoffs. We show that optimal strategies
in these two-player-multi-battleground games are as hard to
compute and approximate as Nash equilibria in general noncooperative
games and economic equilibria in exchange markets.
Incentivizing Truthfulness Through Audits in Strategic Classification
Authors: Estornell Andrew , Das Sanmay , Vorobeychik Yevgeniy
Published: September 2022

In many societal resource allocation domains, machine learning methods are increasingly used to either score or rank agents in order to decide which ones should receive either resources (e.g., homeless services) or scrutiny (e.g., child welfare investigations) from social services agencies. An agency's scoring function typically operates on a feature vector that contains a combination of self-reported features and information available to the agency about individuals or households.
This can create incentives for agents to misrepresent their self-reported features in order to receive resources or avoid scrutiny, but agencies may be able to selectively audit agents to verify the veracity of their reports.

We study the problem of optimal auditing of agents in such settings. When decisions are made using a threshold on an agent's score, the optimal audit policy has a surprisingly simple structure, uniformly auditing all agents who could benefit from lying.
While this policy can, in general be hard to compute because of the difficulty of identifying the set of agents who could benefit from lying given a complete set of reported types, we also present sufficient conditions under which it is tractable.
We show that the scarce resource setting is more difficult, and exhibit an approximately optimal audit policy in this case.
In addition, we show that in either setting verifying whether it is possible to incentivize exact truthfulness is hard even to approximate.
However, we also exhibit sufficient conditions for solving this problem optimally, and for obtaining good approximations.
Condorcet Relaxation In Spatial Voting
Authors: Filtser Arnold , Filtser Omrit
Published: September 2022

Consider a set of voters V, represented by a multiset in a metric space (X,d). The voters have to reach a decision - a point in X. A choice p∈ X is called a β-plurality point for V, if for any other choice q∈ X it holds that |{v∈ V ∣  β⋅ d(p,v)≤ d(q,v)}| ≥|V|/2 . In other words, at least half of the voters ``prefer'' over q, when an extra factor of β is taken in favor of p.

For β=1, this is equivalent to Condorcet winner, which rarely exists. The concept of β-plurality was suggested by Aronov, de Berg, Gudmundsson, and Horton [SoCG 2020] as a relaxation of the Condorcet criterion.

Denote by β*(X,d) the value sup{ β ∣  every finite multiset V in X admits a β-plurality point}}.
The parameter β* determines the amount of relaxation required in order to reach a stable decision.
Aronov et al. showed that for the Euclidean plane β*(ℝ2,\|⋅\|2)=√3/2 , and more generally, for d-dimensional Euclidean space, 1/√d ≤ β*(ℝd,\|⋅\|2)≤√3/2 .

In this paper, we show that 0.557≤ β*(ℝd,\|⋅\|2) for any dimension d (notice that 1/√d
Infinite-Dimensional Fisher Markets: Equilibrium, Duality and Optimization
Authors: Gao Yuan , Kroer Christian
Published: September 2022

This paper considers a linear Fisher market with n buyers and a continuum of items. In order to compute market equilibria, we introduce (infinite-dimensional) convex programs over Banach spaces, thereby generalizing the Eisenberg-Gale convex program and its dual. Regarding the new convex programs, we establish existence of optimal solutions, KKT conditions, as well as strong duality. All these properties are established via non-standard arguments, which circumvent the limitations of duality theory in optimization over infinite-dimensional vector spaces. Furthermore, we show that there exists a pure equilibrium allocation, i.e., a division of the item space. Similar to the finite-dimensional case, a market equilibrium under the infinite-dimensional Fisher market is Pareto optimal, envy-free and proportional. We also show how to obtain the (a.e. unique) equilibrium prices and a pure equilibrium allocation from the (unique) equilibrium utility prices. When the item space is the unit interval [0,1] and buyers have piecewise linear utilities, we show that approximate equilibrium prices can be computed in polynomial time. This is achieved by solving a finite-dimensional convex program using the ellipsoid method. To this end, we give nontrivial and efficient subgradient and separation oracles. For general buyer valuations, we propose computing market equilibrium using stochastic dual averaging, which finds approximate equilibrium prices with high probability.
Aggregating Binary Judgments Ranked by Accuracy
Authors: Halpern Daniel , Kehne Gregory , Peters Dominik , Procaccia Ariel D. , Shah Nisarg , Skowron Piotr
Published: September 2022

We revisit the fundamental problem of predicting a binary ground truth based on independent binary judgments provided by experts. When the accuracy levels of the experts are known, the problem can be solved easily through maximum likelihood estimation. We consider, however, a setting in which we are given only a ranking of the experts by their accuracy. Motivated by the worst-case approach to handle the missing information, we consider three objective functions and design efficient algorithms for optimizing them. In particular, the recently popular distortion objective leads to an intuitive new rule. We show that our algorithms perform well empirically using real and synthetic data in collaborative filtering and political prediction domains.
Multi-Party Campaigning
Authors: Koutecký Martin , Talmon Nimrod
Published: September 2022

We study a social choice setting of manipulation in elections and extend the usual model in two major ways: first, instead of considering a single manipulating agent, in our setting there are several, possibly competing ones; second, instead of evaluating an election after the first manipulative action, we allow several back-and-forth rounds to take place. We show that in certain situations, such as in elections with only a few candidates, optimal strategies for each of the manipulating agents can be computed efficiently. Our algorithmic results rely on formulating the problem of finding an optimal strategy as sentences of Presburger arithmetic that are short and only involve small coefficients, which we show is fixed-parameter tractable -- indeed, one of our contributions is a general result regarding fixed-parameter tractability of Presburger arithmetic that might be useful in other settings. Following our general theorem, we design quite general algorithms; in particular, we describe how to design efficient algorithms for various settings, including settings in which we model diffusion of opinions in a social network, complex budgeting schemes available to the manipulating agents, and various realistic restrictions on adversary actions.
On the PTAS for Maximin Shares in an Indivisible Mixed Manna
Authors: Kulkarni Rucha , Mehta Ruta , Taki Setareh
Published: September 2022

We study fair allocation of indivisible items, both goods and chores, under the popular fairness notion of maximin share (MMS). The problem is well-studied when there are only goods (or chores), where a PTAS to compute the MMS values of agents is well-known.

In contrast, for the mixed manna, a recent result showed that finding even an approximate MMS value of an agent up to any approximation factor in (0,1] is NP-hard for general instances. In this paper, we complement the hardness result by obtaining a PTAS to compute the MMS value when its absolute value is at least 1/p times either the total value of all the goods or total cost of all the chores, for some constant p valued at least 1.
Trembling-Hand Perfection and Correlation in Sequential Games
Authors: Marchesi Alberto , Gatti Nicola
Published: September 2022

We initiate the study of trembling-hand perfection in sequential (i.e., extensive-form) games with correlation. We introduce the extensive-form perfect correlated equilibrium (EFPCE) as a refinement of the classical extensive-form correlated equilibrium (EFCE) that amends its weaknesses off the equilibrium path. This is achieved by accounting for the possibility that the players may make mistakes while following recommendations independently at each information set of the game. After providing an axiomatic definition of EFPCE, we show that one always exists since any perfect (Nash) equilibrium constitutes an EFPCE, and that it is a refinement of EFCE, as any EFPCE is also an EFCE. Then, we prove that, surprisingly, computing an EFPCE is not harder than finding an EFCE, since the problem can be solved in polynomial time for general n-player extensive-form games (also with chance). This is achieved by formulating the problem as that of finding a limit solution (as $\epsilon \rightarrow 0$) to a suitably defined trembling LP parametrized by $\epsilon$, featuring exponentially-many variables and polynomially-many constraints. To this end, we show how a recently developed polynomial-time algorithm for trembling LPs can be adapted to deal with problems having an exponential number of variables. This calls for the solution of a sequence of (non-trembling) LPs with exponentially-many variables and polynomially-many constraints, which is possible in polynomial time by applying an ellipsoid against hope approach.
Scarce Societal Resource Allocation and the Price of (Local) Justice
Authors: Nguyen Quan , Das Sanmay , Garnett Roman
Published: September 2022

We consider the allocation of scarce societal resources, where a central authority decides which individuals receive which resources under capacity or budget constraints. Several algorithmic fairness criteria have been proposed to guide these
procedures, each quantifying a notion of local justice to ensure the allocation is aligned with the principles of the local institution making the allocation. For example, the efficient allocation maximizes overall social welfare, whereas the leximin assignment seeks to help the “neediest first.” Although the “price of fairness” (PoF) of leximin has been studied in prior work, we expand on these results by exploiting the structure inherent in real-world scenarios to provide tighter bounds. We further propose a novel criterion – which we term LoINC (leximin over individually normalized costs) – that maximizes a different but commonly used notion of local justice: prioritizing those benefiting the most from receiving the resources. We derive analogous PoF bounds for LoINC, showing that the price of LoINC is typically much lower than that of leximin. We provide extensive experimental results using both synthetic data and in a real-world setting considering the efficacy of different homelessness interventions. These results show that the empirical PoF tends to be substantially lower than worst-case bounds would imply and allow us to characterize situations where the price of LoINC fairness can be high.
Targeted Negative Campaigning: Complexity and Approximations
Authors: Zagoury‬‏ ‪Avishai , Keller Orgad , Hassidim Avinatan , Hazon Noam
Published: September 2022

Given the ubiquity of negative campaigning in recent political elections, we find it important to study its properties from a computational perspective. To this end, we present a model where elections can be manipulated by convincing voters to demote specific non-favored candidates, and study its properties in the classic setting of scoring rules.

When the goal is constructive (making a preferred candidate win), we prove that finding such a demotion strategy is easy for Plurality and Veto, while generally hard for t-approval and Borda. We also provide a t-factor approximation for t-approval for every fixed t, and a 3-factor approximation algorithm for Borda. Interestingly enough - following recent trends in political science that show that the effectiveness of negative campaigning depends on the type of candidate and demographic - when assigning varying prices to different possible demotion operations, we are able to provide inapproximability results.

When the goal is destructive (making the leading opponent lose), we show that the problem is easy for a broad class of scoring rules.
Teaching Active Human Learners
Authors: Wang Zizhe , Sun Hailong
Published: September 2022

Teaching humans is an important topic under the umbrella of machine teaching, and its core problem is to design an algorithm for selecting teaching examples. Existing work typically regards humans as passive learners, where an ordered set of teaching examples are generated and fed to learners sequentially. However, such a mechanism is inconsistent with the behavior of human learners in practice. A real human learner can actively choose whether to review a historical example or to receive a new example depending on the belief of her learning states. In this work,
we propose a model of active learners and design an efficient teaching algorithm accordingly. Experimental results with both simulated learners and real crowdsourcing workers demonstrate that our teaching algorithm has better teaching performance compared to existing methods.
Classification Under Human Assistance
Authors: De Abir , Okati Nastaran , Zarezade Ali , Gomez Rodriguez Manuel
Published: September 2022

Most supervised learning models are trained for full automation. However, their predictions are sometimes worse than those by human experts on some specific instances. Motivated by this empirical observation, our goal is to design classifiers that are optimized to operate under different automation levels. More specifically, we focus on convex margin-based classifiers and first show that the problem is NP-hard. Then, we further show that, for support vector machines, the corresponding objective function can be expressed as the difference of two functions f = g - c, where g is monotone, non-negative and gamma-weakly submodular, and c is non-negative and modular. This representation allows a recently introduced deterministic greedy algorithm, as well as a more efficient randomized variant of the algorithm, to enjoy approximation guarantees at solving the problem. Experiments on synthetic and real-world data from several applications in medical diagnosis illustrate our theoretical findings and demonstrate that, under human assistance, supervised learning models trained to operate under different automation levels can outperform those trained for full automation as well as humans operating alone.
Uncertain Graph Neural Networks for Facial Action Unit Detection
Authors: Song Tengfei , Chen Lisha , Zheng Wenming , Ji Qiang
Published: September 2022

Capturing the dependencies among different facial action units (AU) is extremely important for the AU detection task. Many studies have employed graph-based deep learning methods to exploit the dependencies among AUs. However, the dependencies among AUs in real world data are often noisy and the uncertainty is essential to be taken into consideration. Rather than employing a deterministic mode, we propose an uncertain graph neural network (UGN) to learn the probabilistic mask that simultaneously captures both the individual dependencies among AUs and the uncertainties. Further, we propose an adaptive weighted loss function based on the epistemic uncertainties to adaptively vary the weights of the training samples during the training process to account for unbalanced data distributions among AUs. We also provide an insightful analysis on how the uncertainties are related to the performance of AU detection. Extensive experiments, conducted on two benchmark datasets, i.e., BP4D and DISFA, demonstrate our method achieves the state-of-the-art performance.
Living Without Beth and Craig: Definitions and Interpolants in Description Logics with Nominals and Role Inclusions
Authors: Artale Alessandro , Jung Jean Christoph , Mazzullo Andrea , Ozaki Ana , Wolter Frank
Published: September 2022

The Craig interpolation property (CIP) states that an interpolant for an implication exists iff it is valid. The projective Beth definability property (PBDP) states that an explicit definition exists iff a formula stating implicit definability is valid. Thus, the CIP and PBDP transform potentially hard existence problems into deduction problems in the underlying logic. Description Logics with nominals and/or role inclusions do not enjoy the CIP nor PBDP, but interpolants and explicit definitions have many potential applications in ontology engineering and ontology-based data management. In this article we show the following: even without Craig and Beth, the existence of interpolants and explicit definitions is decidable in description logics with nominals and/or role inclusions such as ALCO, ALCH and ALCHIO. However, living without Craig and Beth makes this problem harder than deduction: we prove that the existence problems become 2EXPTIME-complete, thus one exponential harder than validity. The existence of explicit definitions is 2EXPTIME-hard even if one asks for a definition of a nominal using any symbol distinct from that nominal, but it becomes EXPTIME-complete if one asks for a definition of a concept name using any symbol distinct from that concept name.
Algebra of Modular Systems: Containment and Equivalence
Authors: Bulatov Andrei , Ternovska Eugenia
Published: September 2022

The Algebra of Modular System is a KR formalism that allows for combinations of modules written in multiple languages. Informally, a module represents a piece of knowledge. It can be given by a knowledge base, be an agent, an ASP, ILP, CP program, etc. Formally, a module is a class of structures over the same vocabulary. Modules are combined declaratively, using, essentially, operations of Codd's relational algebra.
In this paper, we address the problem of checking modular system containment, which we relate to a homomorphism problem. We prove that, for a large class of modular systems, the containment problem (and thus equivalence) is in the complexity class NP, and therefore is solvable by, e.g., SAT solvers. We discuss conditions under which the problem is polynomial time solvable.
Preferred Explanations for Ontology-Mediated Queries under Existential Rules
Authors: Ceylan İsmail İlkan , Lukasiewicz Thomas , Malizia Enrico , Molinaro Cristian , Vaicenavičius Andrius
Published: September 2022

Recently, explanations for query answers under existential rules have been investigated, where an explanation is an inclusion-minimal subset of a given database that, together with the ontology, entails the query. In this paper, we take a step further and study explanations under different minimality criteria. In particular, we first study cardinality-minimal explanations and hence focus on deriving explanations of minimum size. We then study a more general preference order induced by a weight distribution. We assume that every database fact is annotated with a (penalization) weight, and we are interested in explanations with minimum overall weight. For both preference orders, we study a variety of explanation problems, such as recognizing a preferred explanation, all preferred explanations, a relevant or necessary fact, and the existence of a preferred explanation not containing forbidden sets of facts. We provide a detailed complexity analysis for all the aforementioned problems, thereby providing a more complete picture for explaining query answers under existential rules.
Recursion in Abstract Argumentation is Hard --- On the Complexity of Semantics Based on Weak Admissibility
Authors: Dvořák Wolfgang , Ulbricht Markus , Woltran Stefan
Published: September 2022

We study the computational complexity of abstract argumentation
semantics based on weak admissibility, a recently introduced concept
to deal with arguments of self-defeating nature.
Our results reveal that semantics based
on weak admissibility are of much higher complexity
(under typical assumptions) compared to all
argumentation semantics which have been analysed in
terms of complexity so far. In fact, we show
PSPACE-completeness of
all non-trivial standard decision problems for weak-admissible based semantics.
We then investigate potential tractable fragments and show that
restricting the frameworks under consideration to certain graph-classes
significantly reduces the complexity.
As a strategy for implementation we also provide a polynomial-time reduction
to DATALOG with stratified negation.
Constraint Logic Programming for Real-World Test Laboratory Scheduling
Authors: Geibinger Tobias , Mischek Florian , Musliu Nysret
Published: September 2022

The Test Laboratory Scheduling Problem (TLSP) and its subproblem TLSP-S are real-world industrial scheduling problems that are extensions of the Resource-Constrained Project Scheduling Problem (RCPSP). Besides several additional constraints, TLSP includes a grouping phase where the jobs to be scheduled have to be assembled from smaller tasks and derive their properties from this grouping. For TLSP-S such a grouping is already part of the input.

In this work, we show how TLSP-S can be solved by Answer-set Programming extended with ideas from other constraint solving paradigms. We propose a novel and efficient encoding and apply an answer-set solver for constraint logic programs called clingcon. Additionally, we utilize our encoding in a Very Large Neighborhood Search framework and compare our methods with the state of the art approaches. Our approach provides new upper bounds and optimality proofs for several existing benchmark instances in the literature.
Commonsense Knowledge Augmentation for Low-Resource Languages via Adversarial Learning
Authors: Kim Bosung , Kim Juae , Ko Youngjoong , Seo Jungyun
Published: September 2022

Commonsense reasoning is one of the ultimate goals of artificial intelligence research because it simulates the human thinking process. However, most commonsense reasoning studies have focused on English because available commonsense knowledge for low-resource languages is scarce due to high construction costs. Translation is one of the typical methods for augmenting data for low-resource languages; however, translation entails ambiguity problems, where one word can be translated into multiple words due to polysemes and homonyms. Previous studies have suggested methods to measure the validity of translated multiple triples by using additional metadata and manually labeled data. However, such handcrafted datasets are not available for many low-resource languages. In this paper, we propose a knowledge augmentation method using adversarial networks that does not require any labeled data. Our adversarial networks can transfer knowledge learned from a resource-rich language to low-resource languages and thus measure the validity score of translated triples even without labeled data. We designed experiments to demonstrate that high-scoring triples obtained by the proposed model can be considered augmented knowledge. The experimental results show that our proposed method for a low-resource language, Korean, achieved 93.7% precision@1 on a manually labeled benchmark. Furthermore, to verify our model for other low-resource languages, we introduced new test sets for knowledge validation in 16 different languages. Our adversarial model obtains strong results for all language test sets. We will release the augmented Korean knowledge and test sets for 16 languages.
Parameterized Complexity of Small Decision Tree Learning
Authors: Ordyniak Sebastian , Szeider Stefan
Published: September 2022

We study the NP-hard problem of learning a decision tree (DT) of smallest depth or size from data. We provide the first parameterized complexity analysis of the problem and draw a detailed parameterized complexity map for the natural parameters: size or depth of the DT, maximum domain size of all features, and the maximum Hamming distance between any two examples. Our main result shows that learning DTs of smallest depth or size is fixed-parameter tractable (FPT) parameterized by the combination of all three of these parameters. We contrast this FPT-result by various hardness results that underline the algorithmic significance of the considered parameters.
Focused Inference and System P
Authors: Wilhelm Marco , Kern-Isberner Gabriele
Published: September 2022

We bring in the concept of focused inference into the field of qualitative nonmonotonic reasoning by applying focused inference to System P. The idea behind drawing focused inferences is to concentrate on knowledge which seems to be relevant for answering a query while completely disregarding the remaining knowledge even at the risk of missing some meaningful information. Focused inference is motivated by mimicking snap decisions of human reasoners and aims on rapidly drawing still reasonable inferences from large sets of knowledge. In this paper, we define a series of query-dependent, syntactically-driven focused inference relations, elaborate on their formal properties, and show that the series converges against System P. We take advantage of this result in form of an anytime algorithm for drawing inferences which is accompanied by a thorough complexity analysis.
Computing an Efficient Exploration Basis for Learning with Univariate Polynomial Features
Authors: Amballa Chaitanya , Gupta Manu K. , Bhat Sanjay P.
Published: September 2022

Barycentric spanners have been used as an efficient exploration basis in online linear optimization problems in a bandit framework. We characterise the barycentric spanner for decision problems in which the cost (or reward) is a polynomial in a single decision variable. Our characterisation of the barycentric spanner is two-fold: we show that the barycentric spanner under a polynomial cost function is the unique solution to a set of nonlinear algebraic equations, as well as the solution to a convex optimization problem. We provide numerical results to show that our method computes the barycentric spanner for the polynomial case significantly faster than the only other known algorithm for the purpose. As an application, we consider a dynamic pricing problem in which the revenue is an unknown polynomial function of the price. We then empirically show that the use of a barycentric spanner to initialise the prior distribution in a Thompson sampling setting leads to lower cumulative regret as compared to standard initialisations. We also illustrate the importance of barycentric spanners in adversarial settings by showing, both theoretically and empirically, that a barycentric spanner achieves the minimax value in a static adversarial linear regression problem where the learner selects the training points while an adversary selects the testing points and controls the variance of the noise corrupting the training samples
Correlative Channel-Aware Fusion for Multi-View Time Series Classification
Authors: Bai Yue , Wang Lichen , Tao Zhiqiang , Li Sheng , Fu Yun
Published: September 2022

Multi-view time series classification (MVTSC) aims to improve the performance by fusing the distinctive temporal information from multiple views. Existing methods for MVTSC mainly aim to fuse multi-view information at an early stage, e.g., by extracting a common feature subspace among multiple views. However, these approaches may not fully explore the unique temporal patterns of each view in complicated time series. Additionally, the label correlations of multiple views, which are critical to boosting, are usually under-explored for the MVTSC problem. To address the aforementioned issues, we propose a Correlative Channel-Aware Fusion (C$^2$AF) network. First, C$^2$AF extracts comprehensive and robust temporal patterns by a two-stream structured encoder for each view, and derives the intra-view/inter-view label correlations with a concise correlation matrix. Second, a channel-aware learnable fusion mechanism is implemented through CNN to further explore the global correlative patterns. Our C$^2$AF is an end-to-end framework for MVTSC. Extensive experimental results on three real-world datasets demonstrate the superiority of our C$^2$AF over the state-of-the-art methods. A detailed ablation study is also provided to illustrate the indispensability of each model component.
Ordinal Historical Dependence in Graphical Event Models with Tree Representations
Authors: Bhattacharjya Debarun , Gao Tian , Subramanian Dharmashankar
Published: September 2022

Graphical event models are representations that capture process independence between different types of events in multivariate temporal point processes. The literature consists of various parametric models and approaches to learn them from multivariate event stream data. Since these models are interpretable, they are often able to provide beneficial insights about event dynamics. In this paper, we show how to compactly model the situation where the order of occurrences of an event’s causes in some recent historical time interval impacts its occurrence rate; this sort of historical dependence is common in several real-world applications. To overcome the practical challenge of parameter explosion due to the number of potential orders that is super-exponential in the number of parents, we introduce a novel graphical event model based on a parametric tree representation for capturing ordinal historical dependence. We present an approach to learn such a model from data, demonstrating that the proposed model fits several real-world datasets better than relevant baselines. We also showcase the potential advantages of such a model to an analyst during the process of knowledge discovery.
Characterizing the Loss Landscape in Non-Negative Matrix Factorization
Authors: Bjorck Johan , Kabra Anmol , Weinberger Kilian Q. , Gomes Carla
Published: September 2022

Non-negative matrix factorization (NMF) is a highly celebrated algorithm for matrix decomposition that guarantees non-negative factors. The underlying optimization problem is computationally intractable, yet in practice, gradient-descent-based methods often find good solutions. In this paper, we revisit the NMF optimization problem and analyze its loss landscape in non-worst-case settings. It has recently been observed that gradients in deep networks tend to point towards the final minimizer throughout the optimization procedure. We show that a similar property holds (with high probability) for NMF, provably in a non-worst case model with a planted solution, and empirically across an extensive suite of real-world NMF problems. Our analysis predicts that this property becomes more likely with growing number of parameters, and experiments suggest that a similar trend might also hold for deep neural networks---turning increasing dataset sizes and model sizes into a blessing from an optimization perspective.
A Blind Block Term Decomposition of High Order Tensors
Authors: Cai Yunfeng , Li Ping
Published: September 2022

Tensor decompositions have found many applications in signal processing, data mining, machine learning, etc.
In particular, the block term decomposition (BTD), which is a generalization of CP decomposition and Tucker decomposition/HOSVD,
has been successfully used for the compression and acceleration of neural networks.
However, computing BTD is NP-hard, and optimization based methods usually suffer from slow convergence or even fail to converge, which limits the applications of BTD.
This paper considers a “blind” block term decomposition (BBTD) of high order tensors, in which the block diagonal structure of the core tensor is unknown.
Our contributions include:
1) We establish the necessary and sufficient conditions for the existence of BTD, characterize the condition when a BTD solves the BBTD problem, and show that the BBTD is unique under a “low rank” assumption.
2) We propose an algebraic method to compute the BBTD.
This method transforms the problem of determining the block diagonal structure of the core tensor into a clustering problem of complex numbers, in polynomial time.
And once the clustering problem is solved, the BBTD can be obtained via computing several matrix decompositions.
Numerical results show that our method is able to compute the BBTD, even in the presence of noise to some extent,
whereas optimization based methods (e.g., MINF and NLS in TENSORLAB) may fail to converge.
A Multi-step-ahead Markov Conditional Forward Model with Cube Perturbations for Extreme Weather Forecasting
Authors: Chang Chia-Yuan , Lu Cheng-Wei , Wang Chuan-Ju
Published: September 2022

Predicting extreme weather events such as tropical and extratropical cyclones
is of vital scientific and societal importance. Of late, machine learning methods have found their way to weather analysis and prediction, but mostly, these methods use machine learning merely as a complement to traditional numerical weather prediction models. Although some pure machine learning and data-driven approaches for weather prediction have been developed, they mainly formulate the problem similar to pattern recognition or follow the train of thought of traditional time-series models for extreme weather event forecasting; for the former, this usually yields only single-step ahead prediction, and for the latter, this lacks the flexibility to account for observed weather features as such methods concern only the patterns of the extreme weather occurrences. In this paper, we depart from the typical practice of pattern recognition and time-series approaches and focus on employing machine learning to estimate the probabilities of extreme weather occurrences in a multi-step-ahead (MSA) fashion given information on both weather features and the realized occurrences of extreme weather. Specifically, we propose a Markov conditional forward (MCF) model that adopts the Markov property between the occurrences of extreme weather for MSA extreme weather forecasting. Moreover, for better long-term prediction, we propose three novel cube perturbation methods to address error accumulation in our model. Experimental results on a real-world extreme weather dataset show the superiority of the proposed MCF model in terms of prediction accuracy for both short-term and long-term forecasting; moreover, the three cube perturbation methods successfully increase the fault tolerance and generalization ability of the MCF model, yielding significant improvements for long-term prediction.
Distributed Ranking with Communications: Approximation Analysis and Applications
Authors: Chen Hong , Wang Yingjie , Wang Yulong , Zheng Feng
Published: September 2022

Learning theory of distributed algorithms has recently attracted enormous attention in the machine learning community. However, most of existing works focus on learning problem with pointwise loss and does not consider the communication among local processors. In this paper, we propose a new distributed pairwise ranking with communication (called DLSRank-C) based on the Newton-Raphson iteration, and establish its learning rate analysis in probability. Theoretical and empirical assessments demonstrate the effectiveness of DLSRank-C under mild conditions.
THOR, Trace-based Hardware-driven Layer-Oriented Natural Gradient Descent Computation
Authors: Chen Mengyun , Gao Kaixin , Liu Xiaolei , Wang Zidong , Ni Ningxi , Zhang Qian , Chen Lei , Ding Chao , Huang Zhenghai , Wang Min , Wang Shuangling , Yu Fan , Zhao Xinyuan , Xu Dachuan
Published: September 2022

It is well-known that second-order optimizer can accelerate the training of deep neural networks, however, the huge computation cost of second-order optimization makes it impractical to apply in real practice. In order to reduce the cost, many methods have been proposed to approximate a second-order matrix. Inspired by KFAC, we propose a novel Trace-based Hardware-driven layer-ORiented Natural Gradient Descent Computation method, called THOR, to make the second-order optimization applicable in the real application models. Specifically, we gradually increase the update interval and use the matrix trace to determine which blocks of Fisher Information Matrix (FIM) need to be updated. Moreover, by resorting the power of hardware, we have designed a Hardware-driven approximation method for computing FIM to achieve better performance. To demonstrate the effectiveness of THOR, we have conducted extensive experiments. The results show that training ResNet-50 on ImageNet with THOR only takes 66.7 minutes to achieve a top-1 accuracy of 75.9 % under an 8 Ascend 910 environment with MindSpore, a new deep learning computing framework. Moreover, with more computational resources, THOR can only takes 2.7 minutes to 75.9 % with 256 Ascend 910.
A One-Size-Fits-All Solution to Conservative Bandit Problems
Authors: Du Yihan , Wang Siwei , Huang Longbo
Published: September 2022

In this paper, we study a family of conservative bandit problems (CBPs) with sample-path reward constraints, i.e., the learner's reward performance must be at least as well as a given baseline at any time. We propose a One-Size-Fits-All solution to CBPs and present its applications to three encompassed problems, i.e. conservative multi-armed bandits (CMAB), conservative linear bandits (CLB) and conservative contextual combinatorial bandits (CCCB). Different from previous works which consider high probability constraints on the expected reward, we focus on a sample-path constraint on the actually received reward, and achieve better theoretical guarantees (T-independent additive regrets instead of T-dependent) and empirical performance. Furthermore, we extend the results and consider a novel conservative mean-variance bandit problem (MV-CBP), which measures the learning performance with both the expected reward and variability. For this extended problem, we provide a novel algorithm with O(1/T) normalized additive regrets (T-independent in the cumulative form) and validate this result through empirical evaluation.
Semi-Supervised Metric Learning: A Deep Resurrection
Authors: Dutta Ujjal Kr , Harandi Mehrtash , Chandra Shekhar C
Published: September 2022

Distance Metric Learning (DML) seeks to learn a discriminative embedding where similar examples are closer, and dissimilar examples are apart. In this paper, we address the problem of Semi-Supervised DML (SSDML) that tries to learn a metric using a few labeled examples, and abundantly available unlabeled examples. SSDML is important because it is infeasible to manually annotate all the examples present in a large dataset. Surprisingly, with the exception of a few classical approaches that learn a linear Mahalanobis metric, SSDML has not been studied in the recent years, and lacks approaches in the deep SSDML scenario. In this paper, we address this challenging problem, and revamp SSDML with respect to deep learning. In particular, we propose a stochastic, graph-based approach that first propagates the affinities between the pairs of examples from labeled data, to that of the unlabeled pairs. The propagated affinities are used to mine triplet based constraints for metric learning. We impose orthogonality constraint on the metric parameters, as it leads to a better performance by avoiding a model collapse.