Deep Neural Networks (DNNs) are very popular in many machine learning domains. To achieve higher accuracy, DNNs have become deeper and larger. However, the improvement in accuracy comes with the price of the longer inference time and energy consumption. The marginal cost to increase a unit of accuracy has become higher as the accuracy itself is rising.The Branchynet, known as early exits, is an architecture to address increasing marginal cost for improving accuracy. The Branchynet adds extra side classifiers to a DNN model. The inference on a significant portion of the samples can exit from the network earlier via these side branches if they already have high confidence in the results.The Branchynet requires manually tuning the learning hyperparameters, e.g., the locations of branches and the confidence threshold for early exiting. The effectiveness of this manual tuning dramatically impacts the efficiency of the tuned networks. To the best of our knowledge, there are no efficient algorithms to find the best branch location, which is a trade-off between the accuracy and inference time on the Branchynet.We propose an algorithm to find the optimal branch locations for the Branchynet. We formulate the problem of finding the optimal branch location for the branchynet as an optimization problem, and prove that the branch placement problem is an NPcomplete problem. We then derive dynamic programming that runs in pseudo-polynomial time and solves the branch placement problem optimally.We also implement our algorithm and solve the branch placement problems on four types of VGG networks. The experiment results indicate that our dynamic programming can find the optimal branch locations for generating the maximum number of correct classifications within a given time budget. We also run the four VGG models on a GeForce RTX-3090 GPU with the branch combination found by the dynamic programming. The experiment results show that our dynamic programming accurately predicts the number of correct classifications and the execution time on the GPU.

Agent-based stochastic simulation is an established approach to study infectious diseases. Its advantage is the flexibility to incorporate important concepts. The effect of various mitigation strategies has been demonstrated using simulation models. Most of the previous studies compared a few options with a few selected scenarios. We propose to use genetic algorithms to search for the best vaccination strategy for a given scenario with the simulation program as fitness scorer. Vaccination efficacy varies significantly. Therefore, the real challenge is to find a good strategy without the knowledge of it. The simulation software is efficient, yet still takes three minutes to complete a simulation run with Taiwan population. We use surrogate to speed up the search about 1000 times. The surrogate has the average of the absolute value of error around 0.284 percent and the rank correlation coefficient is greater than 0.98 for all the scenarios except one. The optimal solution with surrogate has fitness value very close to use simulations. The difference is generally less than one percent. We envision that an autonomous software searches through the huge scenario space with the help of surrogate function and adaptively executes simulation program to revise the surrogate function to produce higher fidelity surrogate and better search results.

The household structure is an important aspect of population based simulation. How to generate a mock population with specific household structure characteristics is thus an important question. The network structure is one of the dominant factors for contact-based disease transmission. And household structure is the most important source of close contact among small groups. We identify the percentage of elderly-children households as an important character and study the process to generate mock population with specified percentage of elderly-children households. The generated mock populations are fed into the agent-based simulation module to study the impact of household structure on vaccination policy.

A large variety of data mining and machine learning techniques are applied to a wide range of applications today. There- fore, there is a real need to develop technologies that allows data analysis while preserving the confidentiality of the data. Secure multi-party computation (SMC) protocols allows participants to cooperate on various computations while retaining the privacy of their own input data, which is an ideal solution to this issue. Although there is a number of frameworks developed in SMC to meet this challenge, but they are either tailored to perform only on specific tasks or provide very limited precision. In this paper, we have developed protocols for floating point arithmetic based on secure scalar product protocols, which is re- quired in many real world applications. Our protocols follow most of the IEEE-754 standard, supporting the four fundamental arithmetic operations, namely addition, subtraction, multiplication, and division. We will demonstrate the practicality of these protocols through performing various statistical calculations that is widely used in most data analysis tasks. Our experiments show the performance of our framework is both practical and promising.

Many real-world data mining applications need varying cost for different types of classification errors and thus call for cost-sensitive classification algorithms. Existing algorithms for cost-sensitive classification are successful in terms of minimizing the cost, but can result in a high error rate as the trade-off. The high error rate holds back the practical use of those algorithms. In this paper, we propose a novel cost-sensitive classification methodology that takes both the cost and the error rate into account. The methodology, called soft cost-sensitive classification, is established from a multicriteria optimization problem of the cost and the error rate, and can be viewed as regularizing cost-sensitive classification with the error rate. The simple methodology allows immediate improvements of existing cost-sensitive classification algorithms. Experiments on the benchmark and the real-world data sets show that our proposed methodology indeed achieves lower test error rates and similar (sometimes lower) test costs than existing cost-sensitive classification algorithms.

We propose a pathogen-classification system using the Surface-Enhanced Raman Scattering (SERS) platform. The system differentiates the pathogens based on their SERS spectra, which are believed to be related to the surface chemical components. The specialty of the system is to not only consider the usual classification accuracy, but also pay attention to the different types of costs during misclassification. For instance, due to the effectiveness of treatments, the cost of classifying a Gram-positive bacterium as another Gram-positive one should be lower than the cost of classifying a Gram-positive bacterium as a Gram-negative one. We express the task as the cost-sensitive classification problem, and take state-of-the-art cost-sensitive classification algorithms from the machine learning community to conquer the task. Our experimental study validates the usefulness of those algorithms on building the system.

Bacterial meningitis is still a life-threatening disease, and early diagnosis of pathogen can be crucial to improving survival rate. Using the surface-enhanced Raman scattering (SERS) platform developed by our group, the pathogens can be differentiated on the basis of their SERS spectra which are believed to related to their surface chemical components. We collected the SERS spectra of ten pathogens: Streptococcus pneumoniae(Spn), Streptococcus agalactiae (group B streptococcus, GBS), Staphylococcus aureus (Sa), Pseudomonas aeruginosae (Psa), Acinetobacter baumannii (Ab), Klebsiella pneumoniae (Kp), Neisseria meningitidis (Nm), Listeria monocy-togenes (Lm), Haemophilus influenzae (Hi), and Escherichia coli (E. coli). These samples were obtained from patients in National Taiwan University Hospital, and were believed to represent the real diversity of clinical pathogens. Using the support vector machine (SVM) method, the classification accuracy can achieve around 88%. However, we noted that SVM cannot distinguish between [E. coli, Kp] and [Sa, Hi] due to the fact that the global features of these two groups of pathogens are very similar. We therefore incorporated a classification tree method that can focus on local differences in classification rules. This improved the accuracy to 90%. To get a better understanding of the SERS signals, we also compared several other classification methods. In addition, rule extraction method which attempts to explain why classifier fail or succeed is also discussed. Our preliminary results are interesting, encouraging, and await more thorough investigation.

Collaborative recommender systems use various types of information to help customers find products of personalized interest. To increase the usefulness of collaborative recommender systems in certain circumstances, it could be desirable to merge recommender system databases between companies, thus expanding the data pool. This can lead to privacy disclosure hazards during the merging process. This paper addresses how to avoid privacy disclosure in collaborative recommender systems by comparing with major cryptology approaches and constructing a more efficient privacy-preserving collaborative recommender system based on the scalar product protocol.

There is a fair amount of research about privacy, but few empirical studies about its cost have been conducted. In the area of secure multiparty computation, the scalar product has long been reckoned as one of the most promising alternatives to classic logic gates. The reason for this is that the scalar product is not only complete, which is as good as logic gates, but also much more efficient than logic gates. As a result, we set out to study the computation and communication resources needed for some of the most well-known and frequently referenced secure scalar product protocols, including the composite residuosity, the invertible matrix, the polynomial sharing, and the commodity-based approaches. In addition to the implementation details of these approaches, we analyze and compare their execution time, computation time, and memory and random number consumption. Moreover, Fairplay, the benchmark approach that implements Yao's circuit evaluation protocol, is also included in our experiments in order to demonstrate the potential for the scalar products to replace logic gates.

The IEEE 802.16 standard for wireless metropolitan area networks (WMAN) has been created to meet the need of wide-range broadband wireless access at low cost. The objective of this paper is to study how to exploit spectral reuse in an IEEE 802.16 mesh network through timeslot allocation, bandwidth adaptation, hierarchical scheduling, and routing. To the best of our knowledge, this is the first work which formally quantifies spectral reuse in IEEE 802.16 mesh networks and which exploits spectral efficiency under an integrated framework. Simulation results show that the proposed spectral reuse scheduling and load-aware routing significantly enhance the network throughput performance in IEEE 802.16 mesh networks.

Social network analysis is an important methodology in sociological research. Though social network data is very useful to researchers and policy makers, releasing such data to the public may cause an invasion of privacy. We generalize the techniques for protecting personal privacy in tabulated data, and propose some metrics of anonymity for assessing the risk of breaching confidentiality by disclosing social network data. We assume a situation of data publication, where data is released to the general public. We adopt description logic as the underlying knowledge representation formalism, and consider the metrics of anonymity in open world and closed world contexts respectively.

This paper introduces a new graph theory problem called generalized edge coloring (g.e.c). A generalized edge coloring is similar to traditional edge coloring, with the difference that a vertex can be adjacent to up to k edges that share the same color. The concept of generalized edge coloring can be used to formulate the channel assignment problem in multi-channel multi-interface wireless networks. We provide theoretical analysis for this problem. Our theoretical findings can be useful for system developers of wireless networks. We show that when k = 3, there are graphs that do not have generalized edge coloring that could achieve the minimum number of colors for every vertex. On the contrary, when k = 2 we show that if we are given one extra color, we can find a generalized edge coloring that uses the minimum number of colors for each vertex. In addition, we show that for certain classes of graphs we are able to find a generalized edge coloring that uses the minimum number of colors for every vertex without the extra color. These special classes of graphs include bipartite graph, graphs with a power of 2 maximum degree, or graphs with maximum degree no more than 4

A query on the distribution of a sensitive field within a selected population in a database can be submitted to the data center, and the answer to this query can leak private information, even though no identification information is provided. Inspired by decision theory, we present a quantitative model of the privacy protection problem in such a database query environment. In our model, the user information states are defined as classes of probability distributions on the set of possible confidential values. These states can be modified and refined by knowledge acquisition actions. The data confidentiality is guaranteed by ensuring that misusing private information is more costly than any possible gain. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

We investigate the problem of scheduling parallel I/O operations on systems that provide data replication. The objective is to direct each compute node to access data from an I/O node where the data is duplicated, in such a way that requests for data are evenly distributed among I/O nodes. We identify a necessary and sufficient condition on whether the current data request pattern can be improved, in terms of the maximum number of data requests on any I/O node. We propose an augmenting path algorithm that examines this necessary and sufficient condition, and adjusts the current data request pattern accordingly. Using network flow technique, we show that the augmenting path algorithm finds an optimal assignment in O(nmlogn+n/sup 2/Iog/sup 3/2/n) time.

Switch-based clusters -- Network of Workstations/PCs connected by commodity switches, have been an appealing vehicle for high-performance computing. Despite their attractive features, cluster systems still have some limits when compared with traditional massively parallel machines. First, cluster systems usually have limited number of processing nodes, making full utilization of the computing power provided by each processing node a critical issue. Secondly, cluster systems are usually constructed with slower interconnects, making the network speed, not the disk speed, the limiting factor for parallel I/O performance.The notion of part-time I/O is commonly used for I/O in clusters, where a subset of processing nodes become I/O nodes at I/O time and return to computation after finishing the I/O operation. Careful assignment of part-time I/O nodes is the key to overcoming the above two limiting factors. Prior work reported an optimal assignment strategy for cluster systems with shared-media interconnects, based on an optimization that minimizes total amount of remote data transfers in parallel I/O. In this paper, we show that load balance on the I/O nodes, not the total amount of remote data transfers, is the key optimization criteria for assigning part-time I/O nodes for switch-based clusters. We formulate the assignment problem as a weighed bipartite matching with the goal to balance workload on the I/O nodes. We then propose an O(n3over2m(logn + logm)) algorithm to find optimal solution for this problem, where n is the number of compute nodes and m the number of I/O nodes. Experimental results on a 16-node PC cluster and simulation results for larger clusters are reported.

Network of workstation (NOW) is a cost-effective alternative to massively parallel supercomputers. As commercially available off-the-shelf processors become cheaper and faster, it is now possible to build a cluster that provides high computing power within a limited budget. However, a cluster may consist of different types of processors and this heterogeneity complicates the design of efficient collective communication protocols. For example, it is a very hard combinatorial problem to find an optimal reduction schedule for such heterogeneous clusters. Nevertheless, we show that a simple technique called slowest-node-first (SNF) is very effective in designing efficient reduction protocols for heterogeneous clusters. First, we show that SNF is actually an approximation algorithm with competitive ratio two. In addition, we show that SNF does give the optimal reduction time when the cluster consists of two types of processors, anal the ratio of communication speed between them is at least two.

Layered communicationprotocols frequently implement a FIFO message fiacility cm top of an unrehable non-FIFO serwce such as that provided hy a packet-swltchmg network.This paper investigates the possibdity of Implementing a reliable message layer on top of an underlying layer that can low packets and deliver them out of order, with the addltlonzd restriction that the implementatmn uses only a fixed fimte number of different packets.A new formalism is presented to spcclfy communication layers and their properties, the notion of their implementation by 1/0 automata.and the properties of such implementations.An 1/0 automaton that Implements a rellable layer over an unreliable layer is presented In this implementation, tbe number ot packets needed to deliver each succeeding message increases permanently as additional packet-loss and reordering faults occur.A proof is gwen that no protocol can avoid such performance degradatmn.