One of the most important queries in knowledge compilation is weighted model counting (WMC), which has been applied to probabilistic inference on various models, such as Bayesian networks. In practical situations on inference tasks, the model's parameters have uncertainty because they are often learned from data, and thus we want to compute the degree of uncertainty in the inference outcome. One possible approach is to regard the inference outcome as a random variable by introducing distributions for the parameters and evaluate the variance of the outcome. Unfortunately, the tractability of computing such a variance is hardly known. Motivated by this, we consider the problem of computing the variance of WMC and investigate this problem's tractability. First, we derive a polynomial time algorithm to evaluate the WMC variance when the input is given as a structured d-DNNF. Second, we prove the hardness of this problem for structured DNNFs, d-DNNFs, and FBDDs, which is intriguing because the latter two allow polynomial time WMC algorithms. Finally, we show an application that measures the uncertainty in the inference of Bayesian networks. We empirically show that our algorithm can evaluate the variance of the marginal probability on real-world Bayesian networks and analyze the impact of the variances of parameters on the variance of the marginal.

Knowledge compilation is a method of transforming knowledge into a compressed and tractable form for permitting more efficient operations. For Boolean functions, numerous representations have been proposed that enhance succinctness and tractability. In this paper, we introduce a new representation named structured Decomposable And-Sum Circuit (st-DASC), which employs AND and SUM nodes with signed edges, in place of the standard AND and OR nodes with unsigned edges. Notably, incorporating negative signs permits polytime logical negation. By following a knowledge compilation map, we show that st-DASCs are more succinct than Sentential Decision Diagrams (SDDs) while maintaining support for every operation on the knowledge compilation map that SDD supports. Furthermore, st-DASCs are even more succinct than structured d-DNNFs (st-d-DNNFs), which are more succinct than SDDs although they support fewer operations than SDDs. Accordingly, st-DASCs break the traditional trade-off between succinctness and tractability over SDDs and st-d-DNNFs.

A knowledge compilation map analyzes tractable operations in Boolean function representations and compares their succinctness. This enables the selection of appropriate representations for different applications. In the knowledge compilation map, all representation classes are subsets of the negation normal form (NNF). However, Boolean functions may be better expressed by a representation that is different from that of the NNF subsets. In this study, we treat tensor trains as Boolean function representations and analyze their succinctness and tractability. Our study is the first to evaluate the expressiveness of a tensor decomposition method using criteria from knowledge compilation literature. Our main results demonstrate that tensor trains are more succinct than ordered binary decision diagrams (OBDDs) and support the same polytime operations as OBDDs. Our study broadens their application by providing a theoretical link between tensor decomposition and existing NNF subsets.

Evaluating network reliability is crucial for designing communication infrastructures, particularly for such next-generation networks as 6 G, which require extremely high reliability levels, often reaching seven 9's (99.99999 %). However, network reliability evaluation is computationally tough, making it computationally intractable to achieve accurate results for large-scale networks within a reasonable time. Consequently, existing methods either sacrifice computational efficiency or lack guaranteed error bounds. This paper presents an efficient approximation method for network reliability evaluation that guarantees that the approximation error remains within a specified bound. Our proposed method first determines the maximum degree of simultaneous link failures that can be safely ignored without exceeding the bound. With binary decision diagrams, our method efficiently computes both the lower and upper bounds of network reliability. We validate our method through numerical experiments on real-world networks. Our method, which outperformed existing methods by several orders of magnitude, evaluated a network with 434 links in just 7 seconds; an existing method required more than 28 hours.

We present an efficient construction of variable-to-fixed-length (VF) codes under conditions where encoding delay is allowed. We introduce a generalized form of parsetree sets representing a class of codes broader than the almost instantaneous VF (AIVF) codes, which are the conventional VF codes that allow one symbol of an encoding delay. Using Huffman trees, we can optimally construct the codes and guarantee that the compression efficiency is at least compatible with Huffman codes. Numerical evaluations show that we can make efficient VF codes that outperform Huffman codes even for input sources that are disadvantageous to conventional VF codes.

This paper presents an optimal construction ofN-bit-delay almost instantaneous fixed-to-variable-length (AIFV) codes, the general form of binary codes we can make when finite bits of decoding delay are allowed. The presented method enables us to optimize lossless codes among a broader class of codes compared to the conventional FV and AIFV codes. The paper first discusses the problem of code construction, which contains some essential partial problems, and defines three classes of optimality to clarify how far we can solve the problems. The properties of the optimal codes are analyzed theoretically, showing the sufficient conditions for achieving the optimum. Then, we propose an algorithm for constructingN-bit-delay AIFV codes for given stationary memory-less sources. The optimality of the constructed codes is discussed both theoretically and empirically. They showed shorter expected code lengths whenN≥ 3 than the conventional AIFV-mand extended Huffman codes. Moreover, in the random numbers simulation, they performed higher compression efficiency than the 32-bit-precision range codes under reasonable conditions.

We constructed JaParaPat (Japanese-English Parallel Patent Application Corpus), a bilingual corpus of more than 300 million Japanese-English sentence pairs from patent applications published in Japan and the United States from 2000 to 2021. We obtained the publication of unexamined patent applications from the Japan Patent Office (JPO) and the United States Patent and Trademark Office (USPTO). We also obtained patent family information from the DOCDB, that is a bibliographic database maintained by the European Patent Office (EPO). We extracted approximately 1.4M Japanese-English document pairs, which are translations of each other based on the patent families, and extracted about 350M sentence pairs from the document pairs using a translation-based sentence alignment method whose initial translation model is bootstrapped from a dictionary-based sentence alignment. We experimentally improved the accuracy of the patent translations by 20 bleu points by adding more than 300M sentence pairs obtained from patent applications to 22M sentence pairs obtained from the web.

Modern society is underpinned by several network infrastructures, such as telecommunications and transportation. In these network infrastructures, every node pair should remain connected even if some network components fail. Thus, network operators must accurately evaluate the reliability between each node pair and effectively enhance unreliable pairs. Unfortunately, network reliability evaluation is known to be computationally difficult even for a single pair, and no accurate and efficient algorithm for all pairs has been developed. This paper introduces the problem of 2-NR++, evaluating network reliability for all node pairs, and proposes an efficient and exact algorithm. Unlike the previous algorithms, the proposed algorithm constructs only one data structure to compute the reliability of all node pairs. Numerical evaluation using real network benchmarks shows that our algorithm is faster than the state-of-the-art by an order of magnitude; e.g., our algorithm solves 2-NR++ in less than one hour even for a large network with 240 nodes, whereas the state-of-the-art requires more than one day. As an application of our algorithm, we also introduce a link augmentation problem to improve the least unreliable pair. We demonstrate that our algorithm reduces the computation time by around 30–90 times compared to the state-of-the-art.

As the reliability requirements increase for communication networks, e.g., the seven 9’s reliability for 6G, network operators must evaluate the reliability of their networks more accurately. Since public-communication networks are designed to be less prone to large-scale outages, their (un)reliability should be evaluated per outage scale (the number of disconnected nodes). Traditionally, scale-wise unreliability has been evaluated approximately or requires several hours due to its computational hardness. This paper proposes an efficient algorithm that exactly evaluates scale-wise unreliability by leveraging the given reliability requirements for computation acceleration. We first define a sub-problem that computes the probability of disconnecting x or more nodes and introduce a core algorithm that solves this problem with binary decision diagrams. The core algorithm is used to evaluate the scale-wise unreliability according to the given requirements, e.g., the outage probability or outage scale. The time complexity is theoretically analyzed, and its performance is experimentally verified. The proposed algorithm successfully evaluates in 82 minutes large benchmark networks with 400 links and the seven 9’s requirements; the state-of-the-art algorithm fails to evaluate it within 12 hours.

Since machine learning technologies are being used in various practical situations, models with merely low prediction errors might not be satisfactory; prediction errors occurring with a low probability might yield dangerous results in some applications. Therefore, there are attempts to achieve an ML model whose input-output pairs are guaranteed to satisfy given constraints. Among such attempts, many previous works chose the approach of modifying the outputs of an ML model at the inference time to satisfy the constraints. Such a strategy is handy because we can control its output without expensive training or fine-tuning. However, it is unclear whether using constraints only in the inference time degrades a model's predictive performance. This paper analyses how the generalization error bounds change when we only put constraints in the inference time. Our main finding is that a class of loss functions preserves the relative generalization error, i.e., the difference in generalization error compared with the best model will not increase by imposing constraints at the inference time on multi-class classification. Some popular loss functions preserve the relative error, including the softmax cross-entropy loss. On the other hand, we also show that some loss functions do not preserve relative error when we use constraints. Our results suggest the importance of choosing a suitable loss function when we only use constraints in the inference time.

In communication networks, the significance of an outage is measured mainly by its scale (number of disconnected nodes). To avoid serious outages, operators design their networks so that the reliability meets the specification for each outage scale, where the more significant the outage, the less likely it is to occur. Although scale-wise unreliability has been evaluated with rough approximation, sixth-generation (6G) mobile communication requires more accurate reliability evaluation with seven 9's accuracy. Unfortunately, accurate scale-wise reliability evaluation is a computationally very tough problem, so no previous literature has studied evaluation methods rigorous enough for 6G. This paper proposes an efficient algorithm to exactly compute the probability for each number of disconnected nodes. Our algorithm performs the scale-wise unreliability evaluation in a dynamic programming manner without redundant repetition for each outage scale. Numerical experiments using real network topologies show its great efficiency, e.g., our algorithm computes exact probabilities for every outage scale in just two hours for a network with nearly 200 links. We also provide several interesting insights on the reliability of real topologies from the scale-wise perspective, since our work is the first to present the scale-wise unreliability of real large topologies.

Contemporary society survives on several network infrastructures, such as communication and transportation. These network infrastructures are required to keep all nodes connected, although these nodes are occasionally disconnected due to failures. Thus, the expected number of connected node pairs (ECP) during an operation period is a reasonable reliability measure in network design. However, no work has studied ECP due to its computational hardness; we have to solve the reliability evaluation problem, which is a computationally tough problem, for O(n2) times where n is the number of nodes in a network. This paper proposes an efficient method that exactly computes ECP. Our method performs dynamic programming just once without explicit repetition for each node pair and obtains an exact ECP value weighted by the number of users at each node. A thorough complexity analysis reveals that our method is faster than an existing reliability evaluation method, which can be transferred to ECP computation, by O(n). Numerical experiments using real topologies show great efficiency; e.g., our method computes the ECP of an 821-link network in ten seconds; the existing method cannot complete it in an hour. This paper also presents two applications: critical link identification and optimal resource (e.g., a server) placement.

Network reliability, that is, the probability of con-necting specified nodes under link failures, is a key metric of network infrastructure. Because network reliability evaluation is a computationally heavy task, past research has relied on unre-alistically simple failure models such as the independent failure model, wherein each link fails stochastically and independently, ignoring large-scale failures such as disasters, or the deterministic-correlated failure model, wherein all links within a disaster area always fail. However, actual networks follow the probabilistic-correlated (PC) failure model, wherein links in a disaster area fail stochastically with respect to each disaster. This paper proposes an efficient method to accurately compute network reliability under the PC model. Following a conventional method for the independent model, the proposed method uses binary decision diagrams (BDDs) to efficiently handle an exponential number of failure states. Additionally, it employs a probabilistic inference technique to support probabilistic correlation, which is represented as another BDD for integration with the conventional method. The computational complexity was theoretically analyzed, and its performance was experimentally verified; it can compute the network reliability within 1 h for a large network with nearly 200 links and 100 potential disasters.

Since modern society largely depends on several network infrastructures such as telecommunications and various types of power, the reliability of networked systems needs to be accurately evaluated. Traditionally, network reliability has been evaluated on the assumption that the availability of each link is precisely given. However, in reality, it may be given with a degree of uncertainty, e.g., with variance, which must be propagated into the network reliability. To the best of our knowledge, no literature has investigated this issue because, since even computing the reliability itself belongs to a computationally tough class, computing the variance seems much harder.This paper proposes an efficient algorithm to compute the variance of the network reliability given the variance in link availability. We experimentally verify the performance of our algorithm and show that it can compute the variance of network reliability within 0.1 seconds for real topologies with nearly 200 links. We also perform extensive analyses on the variance of network reliability and reveal that network reliability tends to be accurate and that the variance in reliability does not significantly exceed the variance in link availability. Even when some links have a substantial variance in availability, the impact on network reliability is marginal.

Machine learning technologies have been used in a wide range of practical systems.In practical situations, it is natural to expect the input-output pairs of a machine learning model to satisfy some requirements.However, it is difficult to obtain a model that satisfies requirements by just learning from examples.A simple solution is to add a module that checks whether the input-output pairs meet the requirements and then modifies the model's outputs. Such a module, which we call a {\em concurrent verifier} (CV), can give a certification, although how the generalizability of the machine learning model changes using a CV is unclear. This paper gives a generalization analysis of learning with a CV. We analyze how the learnability of a machine learning model changes with a CV and show a condition where we can obtain a guaranteed hypothesis using a verifier only in the inference time.We also show that typical error bounds based on Rademacher complexity will be no larger than that of the original model when using a CV in multi-class classification and structured prediction settings.

Network reliability, i.e., the probability of connecting a set of specified nodes under stochastic link failure, is a key indicator of network infrastructure, such as communication and power. Since network reliability evaluation is a computationally heavy task, several methods have been proposed to efficiently perform it. However, modern network infrastructures follow the client-server model, where many clients are served independently, so we have to evaluate the network reliability for every set consisting of the servers and each client. This evaluation process involves repetitive evaluations while changing the set, which imposes a heavy burden on network operators. This paper proposes a method that efficiently performs network reliability evaluation for the client-server model. Since our method is designed to evaluate reliability for multiple clients without explicit repetition, the computational complexity does not increase compared to the case where existing methods evaluate reliability for a single client. Numerical experiments using datasets of various topologies, including real communication networks, reveal great efficiency. Our method is more than 100 times faster than an existing method that requires repeated evaluation, e.g., it takes only 27 seconds to compute the reliability for 670 clients on a large network with 821 links.

Exact cover refers to the problem of finding subfamily F of a given family of sets S whose universe is D, where F forms a partition of D. Knuth’s Algorithm DLX is a state-of-the-art method for solving exact cover problems. Since DLX’s running time depends on the cardinality of input S, it can be slow if S is large. Our proposal can improve DLX by exploiting a novel data structure, DanceDD, which extends the zero-suppressed binary decision diagram (ZDD) by adding links to enable efficient modifications of the data structure. With DanceDD, we can represent S in a compressed way and perform search in linear time with the size of the structure by using link operations. The experimental results show that our method is an order of magnitude faster when the problem is highly compressed.

Communication networks are an essential infrastructure and must be designed carefully to ensure high reliability. Identifying a fully reliable design is, however, computationally very tough since it requires that a reliability evaluation, which is known to be #P-complete, be repeated an exponential number of times. Existing studies, therefore, attempt to avoid exact optimization to reduce the computational burden by applying heuristics. Due to the importance of communication networks and to better assess the accuracy of heuristic approaches, exact optimization remains a key goal. This paper proposes an exact method for two network design problems: reliability maximization under budget constraints and cost minimization with assurance of reliability. Our method employs a common idea to solve these problems, i.e., a best-first search algorithm that runs on decision diagrams. Our method employs just a single binary decision diagram (BDD) to compute the reliability for any solution and is also used as the basis of a novel heuristic function, called the cost-aware BDD heuristic function, as a search guide. Numerical experiments show that our method scales well; it successfully optimizes a network with 189 links. In addition, our method reveals the poor performance of existing heuristic approaches; a well-known existing heuristic method is shown to yield a solution that offers less than half the optimal reliability.

Exact cover is the problem of finding subfamilies, S*, of a family of sets, S, over universe U, where S* forms a partition of U. It is a popular NP-hard problem appearing in a wide range of computer science studies. Knuth's algorithm DLX, a backtracking-based depth-first search implemented with the data structure called dancing links, is known as state-of-the-art for finding all exact covers. We propose a method to accelerate DLX. Our method constructs a Zero-suppressed Binary Decision Diagram (ZDD) that represents the set of solutions while running depth-first search in DLX. Constructing ZDDs enables the efficient use of memo cache to speed up the search. Moreover, our method has a virtue that it outputs ZDDs; we can perform several useful operations with them. Experiments confirm that the proposed method is up to several orders of magnitude faster than DLX.

The Zero-suppressed Sentential Decision Diagram (ZSDD) is a recentlydiscovered tractable representation of Boolean functions. ZSDD subsumes theZero-suppressed Binary Decision Diagram (ZDD) as a strict subset, andsimilar to ZDD, it can perform several useful operations like model countingand Apply operations. We propose a top-down compilation algorithmfor ZSDD that represents sets of specific graph substructures, e.g.,matchings and simple paths of a graph. We experimentally confirm that theproposed algorithm is faster than other construction methods includingbottom-up methods and top-down methods for ZDDs, and the resulting ZSDDsare smaller than ZDDs representing the same graph substructures. We alsoshow that the size constructed ZSDDs can be bounded by the branch-width of thegraph. This bound is tighter than that of ZDDs.

The Sentential Decision Diagram (SDD) is a prominent knowledge representation language that subsumes the Ordered Binary Decision Diagram (OBDD) as a strict subset. Like OBDDs, SDDs have canonical forms and support bottom-up operations for combining SDDs, but they are more succinct than OBDDs. In this paper we introduce an SDD variant, called the Zero-suppressed Sentential Decision Diagram (ZSDD). The key idea of ZSDD is to employ new trimming rules for obtaining a canonical form. As a result, ZSDD subsumes the Zero-suppressed Binary Decision Diagram (ZDD) as a strict subset. ZDDs are known for their effectiveness on representing sparse Boolean functions. Likewise, ZSDDs can be more succinct than SDDs when representing sparse Boolean functions. We propose several polytime bottom-up operations over ZSDDs, and a technique for reducing ZSDD size, while maintaining applicability to important queries. We also specify two distinct upper bounds on ZSDD sizes; one is derived from the treewidth of a CNF and the other from the size of a family of sets. Experiments show that ZSDDs are smaller than SDDs or ZDDs for a standard benchmark dataset.

Dynamic programming (DP) is a fundamental tool used to obtain exact, optimal solutions for many combinatorial optimization problems. Among these problems, important ones including the knapsack problems and the computation of edit distances between string pairs can be solved with a kind of DP that corresponds to solving the shortest path problem on a directed acyclic graph (DAG). These problems can be solved efficiently with DP, however, in practical situations, we want to solve the customized problems made by adding logical constraints to the original problems. Developing an algorithm specifically for each combination of a problem and a constraint set is unrealistic. The proposed method, BDD-Constrained Search (BCS), exploits a Binary Decision Diagram (BDD) that represents the logical constraints in combination with the DAG that represents the problem. The BCS runs DP on the DAG while using the BDD to check the equivalence and the validity of intermediate solutions to efficiently solve the problem. The important feature of BCS is that it can be applied to problems with various types of logical constraints in a unified way once we represent the constraints as a BDD. We give a theoretical analysis on the time complexity of BCS and also conduct experiments to compare its performance to that of a state-of-the-art integer linear programming solver.

Masaaki Nishino, Norihito Yasuda, Tsutomu Hirao, Shin-ichi Minato, Masaaki Nagata. Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2015.

Recent studies on extractive text summarization formulate it as a combinatorial optimization problem, extracting the optimal subset from a set of the textual units that maximizes an objective function without violating the length constraint. Although these methods successfully improve automatic evaluation scores, they do not consider the discourse structure in the source document. Thus, summaries generated by these methods may lack logical coherence. In previous work, we proposed a method that exploits a discourse tree structure to produce coherent summaries. By transforming a traditional discourse tree, namely a rhetorical structure theory-based discourse tree (RST-DT), into a dependency-based discourse tree (DEP-DT), we formulated the summarization procedure as a Tree Knapsack Problem whose tree corresponds to the DEP-DT. This paper extends the work with a detailed discussion of the approach together with a novel efficient dynamic programming algorithm for solving the Tree Knapsack Problem. Experiments show that our method not only achieved the highest score in both automatic and human evaluation, but also obtained good performance in terms of the linguistic qualities of the summaries.

We propose a method for accelerating matrix multiplications that are iteratively performed with a sparse adjacency matrix. These operations appear in a wide range of data analyses and data mining situations, which include the computation of Personalized PageRank (PPR) and Nonnegative Matrix Factorization (NMF). We exploit the fact that the intermediate computational results for the matrix multiplication of equivalent partial row vectors of a matrix are the same. Our new data structure, the adjacency forest, uses this property and represents an adjacency matrix as a rooted tree that is made by sharing the common suffixes of the row vectors of the matrix. By exploiting the structure of the tree, we can perform a matrix multiplication while sharing intermediate computational results to reduce the number of required operations. We also show that we can further accelerate computation by dividing a matrix into several sub-matrices and representing the original matrix as a forest. We confirm experimentally that our approach can speed up the computation of Personalized PageRank and NMF up to 300%.

Recent studies on extractive text summarization formulate it as a combinatorial optimization problem such as a Knapsack Problem, a Maximum Coverage Problem or a Budgeted Median Problem.These methods successfully improved summarization quality, but they did not consider the rhetorical relations between the textual units of a source document.Thus, summaries generated by these methods may lack logical coherence.This paper proposes a single document summarization method based on the trimming of a discourse tree.This is a two-fold process.First, we propose rules for transforming a rhetorical structure theorybased discourse tree into a dependency-based discourse tree, which allows us to take a treetrimming approach to summarization.Second, we formulate the problem of trimming a dependency-based discourse tree as a Tree Knapsack Problem, then solve it with integer linear programming (ILP).Evaluation results showed that our method improved ROUGE scores.

This paper proposes a highly effective geographic information retrieval method. It assesses the extent implied by place names in documents and then emphasizes place names that are highly specific in terms of identifying locations. Furthermore, the method also assesses the proximity between place names and keywords in each document and adjusts the document score based on the proximity between place name associated with user's geographic intention and keywords associated with user's query. Evaluation results show that the two methods proposed herein offer improved performance according to some TREC-style evaluation metrics.

This paper proposes a novel Geo-IR ranking method that realizes effective searches that emphasize the user's immediate surroundings. It assesses the extent implied by place names in documents and then emphasizes place names that are highly specific in terms of identifying locations.