Probabilistic graphical models compactly represent joint distributions by decomposing them into factors over subsets of random variables. In Bayesian networks, the factors are conditional probability distributions. For many problems, common information exists among those factors. Adding similarity restrictions can be viewed as imposing prior knowledge for model regularization. With proper restrictions, learned models usually generalize better. In this work, we study methods that exploit such high-level similarities to regularize the learning process and apply them to the task of modeling the wave propagation in inhomogeneous media. We propose a novel distribution-based penalization approach that encourages similar conditional probability distribution rather than force the parameters to be similar explicitly. We show in experiment that our proposed algorithm solves the modeling wave propagation problem, which other baseline methods are not able to solve.
Multi-Task Learning (MTL) is a learning paradigm in machine learning and its target is to leverage useful information contained in multiple related tasks to help improve the generalization performance of all the tasks. Consider the wave propagation problem, we can formulize it as finding the distribution @math , where @math denotes the state of all nodes at time @math . The assumption is that the state of each node at time @math is independent of other nodes at time @math given the states of its neighbors at time @math . So the distribution can be decomposed into @math (assume we have @math nodes in total) conditional distributions. Rather than using @math neural networks to approximate those distributions, MTL uses one neural network with @math outputs. The first few hidden layers are shared among nodes, while the following layers are node-specific. @cite_9 shows that such setting greatly reduces the risk of overfitting. This makes sense intuitively: The more factors we are learning simultaneously, the more our model has to find a representation that captures all of the factors and the less is the chance of overfitting. We implement a MTL model as the opponent of our distribution-based penalization model.
@cite_9
2143419558
We study network-design problems with multiple design objectives. In particular, we look at two cost measures to be minimized simultaneously: the total cost of the network and the maximum degree of any node in the network. Our main result can be roughly stated as follows: given an integer @math , we present approximation algorithms for a variety of network-design problems on an @math -node graph in which the degree of the output network is @math and the cost of this network is @math times that of the minimum-cost degree- @math -bounded network. These algorithms can handle costs on nodes as well as edges. Moreover, we can construct such networks so as to satisfy a variety of connectivity specifications including spanning trees, Steiner trees and generalized Steiner forests. The performance guarantee on the cost of the output network is nearly best-possible unless @math . We also address the special case in which the costs obey the triangle inequality. In this case, we obtain a polynomial-time approximation algorithm with a stronger performance guarantee. Given a bound @math on the degree, the algorithm finds a degree- @math -bounded network of cost at most a constant time optimum. There is no algorithm that does as well in the absence of triangle inequality unless @math . We also show that in the case of spanning networks, we can simultaneously approximate within a constant factor yet another objective: the maximum cost of any edge in the network, also called the bottleneck cost of the network. We extend our algorithms to find TSP tours and @math -connected spanning networks for any fixed @math that simultaneously approximate all these three cost measures. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each neighbor with at least 2d+1 fewer tokens, where d is the maximum degree of any node in the network. We show that within @math steps, the algorithm reduces the maximum difference in tokens between any two nodes to at most @math , where @math is the global imbalance in tokens (i.e., the maximum difference between the number of tokens at any node initially and the average number of tokens), n is the number of nodes in the network, and @math is the edge expansion of the network. The time bound is tight in the sense that for any graph with edge expansion @math , and for any value @math , there exists an initial distribution of tokens with imbalance @math for which the time to reduce the imbalance to even @math is at least @math . The bound on the final imbalance is tight in the sense that there exists a class of networks that can be locally balanced everywhere (i.e., the maximum difference in tokens between any two neighbors is at most 2d), while the global imbalance remains @math . Furthermore, we show that upon reaching a state with a global imbalance of @math , the time for this algorithm to locally balance the network can be as large as @math . We extend our analysis to a variant of this algorithm for dynamic and asynchronous networks. We also present tight bounds for a randomized algorithm in which each node sends at most one token in each step. We consider distributed algorithms for approximate maximum matching on general graphs. Our main result is a randomized @math -approximation distributed algorithm for maximum weighted matching, whose running time is @math for any constant @math , where @math is the number of nodes in the graph. This is, to the best of our knowledge, the first log-time distributed algorithm that achieves constant approximation for maximum weighted matching on general graphs. In addition, we consider the dynamic case, where nodes are inserted and deleted one at a time. For unweighted dynamic graphs, we give a distributed algorithm that maintains a @math -approximation in @math time for each node insertion or deletion for any constant @math . For weighted dynamic graphs we give a constant-factor approximation distributed algorithm that runs in constant time for each insertion or deletion. For a pattern graph @math on @math nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of @math in a given large graph @math on @math nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include the following: 1. The number of copies of an @math with an independent set of size @math can be computed exactly in @math time and @math space, or in @math time and @math space. (The @math notation omits @math factors.) To obtain these algorithms we provide fast algorithms for computing the permanent of a @math matrix over rings and semirings. 2. The number of copies of any @math having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in @math time, where @math is the matrix multiplication exponent and @math is divisible by @math . Similar results hold for other values of @math . Also, the number...