Search

We study the problem of stochastic combinatorial pure exploration (CPE), where an agent sequentially pulls a set of single arms (a.k.a. a super arm) and tries to find the best super arm. Among a variety of problem settings of the CPE, we focus on the full-bandit setting, where we cannot observe the reward of each single arm, but only the sum of the rewards. Although we can regard the CPE with full-bandit feedback as a special case of pure exploration in linear bandits, an approach based on linear bandits is not computationally feasible since the number of super arms may be exponential. In this paper, we first propose a polynomial-time bandit algorithm for the CPE under general combinatorial constraints and provide an upper bound of the sample complexity. Second, we design an approximation algorithm for the 0-1 quadratic maximization problem, which arises in many bandit algorithms with confidence ellipsoids. Based on our approximation algorithm, we propose novel bandit algorithms for the top-k selection problem, and prove that our algorithms run in polynomial time. Finally, we conduct experiments on synthetic and real-world datasets, and confirm the validity of our theoretical analysis in terms of both the computation time and the sample complexity., 21 pages

Effective utilization of unused heat below 200 °C is essential for a sustainable society. In this study, we propose a thermally driven water pump using fixed oblique beam structures with bubbles in the nucleate boiling region (approximately, 100–130 °C). Here, the oblique beam structure breaks the symmetry of the bubble force, and thus, they provide a net flow. Specifically, by using six fixed oblique beams along a circular fluidic channel, we observed a net flow of an average flow velocity of ∼40 mm/s and an average volume flow rate of ∼10 000 mm3/s (∼0.01 l/s) at the superheat of ∼22 K. Our findings should contribute to the effective use of unused heat such as factory waste heat and environmental energy.

Many social phenomena are triggered by public opinion that is formed in the process of opinion exchange among individuals. To date, from the engineering point of view, a large body of work has been devoted to studying how to manipulate individual opinions so as to guide public opinion towards the desired state. Recently, Abebe et al. (KDD 2018) have initiated the study of the impact of interventions at the level of susceptibility rather than the interventions that directly modify individual opinions themselves. For the model, Chan et al. (The Web Conference 2019) designed a local search algorithm to find an optimal solution in polynomial time. However, it can be seen that the solution obtained by solving the above model might not be implemented in real-world scenarios. In fact, as we do not consider the amount of changes of the susceptibility, it would be too costly to change the susceptibility values for agents based on the solution. In this paper, we study an opinion optimization model that is able to limit the amount of changes of the susceptibility in various forms. First we introduce a novel opinion optimization model, where the initial susceptibility values are given as additional input and the feasible region is defined using the $\ell_p$-ball centered at the initial susceptibility vector. For the proposed model, we design a projected gradient method that is applicable to the case where there are millions of agents. Finally we conduct thorough experiments using a variety of real-world social networks and demonstrate that the proposed algorithm outperforms baseline methods., CIKM 2021

Background Eosinophilic granulomatosis with polyangiitis (EGPA) is an anti-neutrophil antibody (ANCA)-associated necrotizing vasculitis, which predominantly affects small to medium vessels, and is associated with asthma and eosinophilia. EGPA has two different pathogenic aspects: eosinophilic granulomatous inflammation and ANCA-associated inflammation. A recent histological study of peripheral nerves showed that not only ANCA-associated inflammation but also eosinophil-associated vascular occlusion leads to ischemia. Endobronchial involvement is relatively common especially in the patients with granulomatosis with polyangiitis but rare in patients with EGPA. Central nervous system (CNS) involvement is also rare in patients with EGPA, the pathogenesis and relationship between these two rare conditions have not been elucidated. Case presentation A 62-year-old woman was admitted with numbness, purpura, and eosinophilia. She had a 3-year-history of bronchial asthma. Chest computed tomography showed left lower lobe collapse, and brain magnetic resonance imaging indicated occipital lobe infarction. Skin biopsy findings led to the diagnosis of EGPA. ANCA test results were negative. All symptoms improved after initiating glucocorticoids. However, atelectasis and brain infarction relapsed with increasing eosinophil counts. Atelectasis quickly disappeared with increasing glucocorticoid dose, and glucocorticoid could be reduced to a maintenance dose after the initiation of mepolizumab. Conclusion Both atelectasis and brain infarction might develop not only via ANCA-associated inflammation but also via eosinophilic inflammation.

A hypergraph is a useful combinatorial object to model ternary or higher-order relations among entities. Clustering hypergraphs is a fundamental task in network analysis. In this study, we develop two clustering algorithms based on personalized PageRank on hypergraphs. The first one is local in the sense that its goal is to find a tightly connected vertex set with a bounded volume including a specified vertex. The second one is global in the sense that its goal is to find a tightly connected vertex set. For both algorithms, we discuss theoretical guarantees on the conductance of the output vertex set. Also, we experimentally demonstrate that our clustering algorithms outperform existing methods in terms of both the solution quality and running time. To the best of our knowledge, ours are the first practical algorithms for hypergraphs with theoretical guarantees on the conductance of the output set., KDD 2020

Background Studies using quantitative experimental methods have shown that intracellular spatial distribution of molecules plays a central role in many cellular systems. Spatially resolved computer simulations can integrate quantitative data from these experiments to construct physically accurate models of the systems. Although computationally expensive, microscopic resolution reaction-diffusion simulators, such as Spatiocyte can directly capture intracellular effects comprising diffusion-limited reactions and volume exclusion from crowded molecules by explicitly representing individual diffusing molecules in space. To alleviate the steep computational cost typically associated with the simulation of large or crowded intracellular compartments, we present a parallelized Spatiocyte method called pSpatiocyte. Results The new high-performance method employs unique parallelization schemes on hexagonal close-packed (HCP) lattice to efficiently exploit the resources of common workstations and large distributed memory parallel computers. We introduce a coordinate system for fast accesses to HCP lattice voxels, a parallelized event scheduler, a parallelized Gillespie’s direct-method for unimolecular reactions, and a parallelized event for diffusion and bimolecular reaction processes. We verified the correctness of pSpatiocyte reaction and diffusion processes by comparison to theory. To evaluate the performance of pSpatiocyte, we performed a series of parallelized diffusion runs on the RIKEN K computer. In the case of fine lattice discretization with low voxel occupancy, pSpatiocyte exhibited 74% parallel efficiency and achieved a speedup of 7686 times with 663552 cores compared to the runtime with 64 cores. In the weak scaling performance, pSpatiocyte obtained efficiencies of at least 60% with up to 663552 cores. When executing the Michaelis-Menten benchmark model on an eight-core workstation, pSpatiocyte required 45- and 55-fold shorter runtimes than Smoldyn and the parallel version of ReaDDy, respectively. As a high-performance application example, we study the dual phosphorylation-dephosphorylation cycle of the MAPK system, a typical reaction network motif in cell signaling pathways. Conclusions pSpatiocyte demonstrates good accuracies, fast runtimes and a significant performance advantage over well-known microscopic particle methods in large-scale simulations of intracellular reaction-diffusion systems. The source code of pSpatiocyte is available at https://spatiocyte.org.