BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Takanori Maehara

Takanori Maehara appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computation and LanguageMachine LearningData Structures and Algorithmsmath.COmath.OCArtificial IntelligenceComputer Science and Game TheoryDiscrete MathematicsNeural and Evolutionary Computingphysics.soc-phSocial and Information Networks

Catalog footprint

What is connected

14works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

14 published item(s)

preprint2021arXiv

Abelian Neural Networks

We study the problem of modeling a binary operation that satisfies some algebraic requirements. We first construct a neural network architecture for Abelian group operations and derive a universal approximation property. Then, we extend it to Abelian semigroup operations using the characterization of associative symmetric polynomials. Both models take advantage of the analytic invertibility of invertible neural networks. For each case, by repeating the binary operations, we can represent a function for multiset input thanks to the algebraic structure. Naturally, our multiset architecture has size-generalization ability, which has not been obtained in existing methods. Further, we present modeling the Abelian group operation itself is useful in a word analogy task. We train our models over fixed word embeddings and demonstrate improved performance over the original word2vec and another naive learning method.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Graph Homomorphism Convolution

In this paper, we study the graph classification problem from the graph homomorphism perspective. We consider the homomorphisms from $F$ to $G$, where $G$ is a graph of interest (e.g. molecules or social networks) and $F$ belongs to some family of graphs (e.g. paths or non-isomorphic trees). We show that graph homomorphism numbers provide a natural invariant (isomorphism invariant and $\mathcal{F}$-invariant) embedding maps which can be used for graph classification. Viewing the expressive power of a graph classifier by the $\mathcal{F}$-indistinguishable concept, we prove the universality property of graph homomorphism vectors in approximating $\mathcal{F}$-invariant functions. In practice, by choosing $\mathcal{F}$ whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Learning Directly from Grammar Compressed Text

Neural networks using numerous text data have been successfully applied to a variety of tasks. While massive text data is usually compressed using techniques such as grammar compression, almost all of the previous machine learning methods assume already decompressed sequence data as their input. In this paper, we propose a method to directly apply neural sequence models to text data compressed with grammar compression algorithms without decompression. To encode the unique symbols that appear in compression rules, we introduce composer modules to incrementally encode the symbols into vector representations. Through experiments on real datasets, we empirically showed that the proposal model can achieve both memory and computational efficiency while maintaining moderate performance.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rank axiom of modular supermatroids: A connection with directional DR submodular functions

A matroid has been one of the most important combinatorial structures since it was introduced by Whitney as an abstraction of linear independence. As an important property of a matroid, it can be characterized by several different (but equivalent) axioms, such as the augmentation, the base exchange, or the rank axiom. A supermatroid is a generalization of a matroid defined on lattices. Here, the central question is whether a supermatroid can be characterized by several equivalent axioms similar to a matroid. Barnabei, Nicoletti, and Pezzoli characterized supermatroids on distributive lattices, and Fujishige, Koshevoy, and Sano generalized the results for cg-matroids (supermatroids on lower locally distributive lattices). In this study, we focus on modular lattices, which are an important superclass of distributive lattices, and provide equivalent characterizations of supermatroids on modular lattices. We characterize supermatroids on modular lattices using the rank axiom in which the rank function is a directional DR-submodular function, which is a generalization of a submodular function introduced by the authors. Using a characterization based on rank functions, we further prove the strong exchange property of a supermatroid, which has application in optimization. We also reveal the relation between the axioms of a supermatroid on lower semimodular lattices, which is a common superclass of a lower locally distributive lattice and a modular lattice.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stochastic Monotone Submodular Maximization with Queries

We study a stochastic variant of monotone submodular maximization problem as follows. We are given a monotone submodular function as an objective function and a feasible domain defined on a finite set, and our goal is to find a feasible solution that maximizes the objective function. A special part of the problem is that each element in the finite set has a random hidden state, active or inactive, only the active elements contribute to the objective value, and we can conduct a query to an element to reveal its hidden state. The goal is to obtain a feasible solution having a large objective value by conducting a small number of queries. This is the first attempt to consider nonlinear objective functions in such a stochastic model. We prove that the problem admits a good query strategy if the feasible domain has a uniform exchange property. This result generalizes Blum et al.'s result on the unweighted matching problem and Behnezhad and Reyhani's result on the weighted matching problem in both objective function and feasible domain.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Tightly Robust Optimization via Empirical Domain Reduction

Data-driven decision-making is performed by solving a parameterized optimization problem, and the optimal decision is given by an optimal solution for unknown true parameters. We often need a solution that satisfies true constraints even though these are unknown. Robust optimization is employed to obtain such a solution, where the uncertainty of the parameter is represented by an ellipsoid, and the scale of robustness is controlled by a coefficient. In this study, we propose an algorithm to determine the scale such that the solution has a good objective value and satisfies the true constraints with a given confidence probability. Under some regularity conditions, the scale obtained by our algorithm is asymptotically $O(1/\sqrt{n})$, whereas the scale obtained by a standard approach is $O(\sqrt{d/n})$. This means that our algorithm is less affected by the dimensionality of the parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Finding Alternate Features in Lasso

We propose a method for finding alternate features missing in the Lasso optimal solution. In ordinary Lasso problem, one global optimum is obtained and the resulting features are interpreted as task-relevant features. However, this can overlook possibly relevant features not selected by the Lasso. With the proposed method, we can provide not only the Lasso optimal solution but also possible alternate features to the Lasso solution. We show that such alternate features can be computed efficiently by avoiding redundant computations. We also demonstrate how the proposed method works in the 20 newsgroup data, which shows that reasonable features are found as alternate features.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Pricing for Submodular Valuations with Bounded Curvature

The optimal pricing problem is a fundamental problem that arises in combinatorial auctions. Suppose that there is one seller who has indivisible items and multiple buyers who want to purchase a combination of the items. The seller wants to sell his items for the highest possible prices, and each buyer wants to maximize his utility (i.e., valuation minus payment) as long as his payment does not exceed his budget. The optimal pricing problem seeks a price of each item and an assignment of items to buyers such that every buyer achieves the maximum utility under the prices. The goal of the problem is to maximize the total payment from buyers. In this paper, we consider the case that the valuations are submodular. We show that the problem is computationally hard even if there exists only one buyer. Then we propose approximation algorithms for the unlimited budget case. We also extend the algorithm for the limited budget case when there exists one buyer and multiple buyers collaborate with each other.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Embedding Semantic Relations into Word Representations

Learning representations for semantic relations is important for various tasks such as analogy detection, relational search, and relation classification. Although there have been several proposals for learning representations for individual words, learning word representations that explicitly capture the semantic relations between words remains under developed. We propose an unsupervised method for learning vector representations for words such that the learnt representations are sensitive to the semantic relations that exist between two words. First, we extract lexical patterns from the co-occurrence contexts of two words in a corpus to represent the semantic relations that exist between those two words. Second, we represent a lexical pattern as the weighted sum of the representations of the words that co-occur with that lexical pattern. Third, we train a binary classifier to detect relationally similar vs. non-similar lexical pattern pairs. The proposed method is unsupervised in the sense that the lexical pattern pairs we use as train data are automatically sampled from a corpus, without requiring any manual intervention. Our proposed method statistically significantly outperforms the current state-of-the-art word representations on three benchmark datasets for proportional analogy detection, demonstrating its ability to accurately capture the semantic relations among words.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Joint Word Representation Learning using a Corpus and a Semantic Lexicon

Methods for learning word representations using large text corpora have received much attention lately due to their impressive performance in numerous natural language processing (NLP) tasks such as, semantic similarity measurement, and word analogy detection. Despite their success, these data-driven word representation learning methods do not consider the rich semantic relational structure between words in a co-occurring context. On the other hand, already much manual effort has gone into the construction of semantic lexicons such as the WordNet that represent the meanings of words by defining the various relationships that exist among the words in a language. We consider the question, can we improve the word representations learnt using a corpora by integrating the knowledge from semantic lexicons?. For this purpose, we propose a joint word representation learning method that simultaneously predicts the co-occurrences of two words in a sentence subject to the relational constrains given by the semantic lexicon. We use relations that exist between words in the lexicon to regularize the word representations learnt from the corpus. Our proposed method statistically significantly outperforms previously proposed methods for incorporating semantic lexicons into word representations on several benchmark datasets for semantic similarity and word analogy.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Unsupervised Cross-Domain Word Representation Learning

Meaning of a word varies from one domain to another. Despite this important domain dependence in word semantics, existing word representation learning methods are bound to a single domain. Given a pair of \emph{source}-\emph{target} domains, we propose an unsupervised method for learning domain-specific word representations that accurately capture the domain-specific aspects of word semantics. First, we select a subset of frequent words that occur in both domains as \emph{pivots}. Next, we optimize an objective function that enforces two constraints: (a) for both source and target domain documents, pivots that appear in a document must accurately predict the co-occurring non-pivots, and (b) word representations learnt for pivots must be similar in the two domains. Moreover, we propose a method to perform domain adaptation using the learnt word representations. Our proposed method significantly outperforms competitive baselines including the state-of-the-art domain-insensitive word representations, and reports best sentiment classification accuracies for all domain-pairs in a benchmark dataset.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficient SimRank Computation via Linearization

SimRank, proposed by Jeh and Widom, provides a good similarity measure that has been successfully used in numerous applications. While there are many algorithms proposed for computing SimRank, their computational costs are very high. In this paper, we propose a new computational technique, "SimRank linearization," for computing SimRank, which converts the SimRank problem to a linear equation problem. By using this technique, we can solve many SimRank problems, such as single-pair compuation, single-source computation, all-pairs computation, top k searching, and similarity join problems, efficiently.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Existence of outsiders as a characteristic of online communication networks

Online social networking services (SNSs) involve communication activities between large number of individuals over the public Internet and their crawled records are often regarded as proxies of real (i.e., offline) interaction structure. However, structure observed in these records might differ from real counterparts because individuals may behave differently online and non-human accounts may even participate. To understand the difference between online and real social networks, we investigate an empirical communication network between users on Twitter, which is perhaps one of the largest SNSs. We define a network of user pairs that send reciprocal messages. Based on the mixing pattern observed in this network, we argue that this network differs from conventional understandings in the sense that there is a small number of distinctive users that we call outsiders. Outsiders do not belong to any user groups but they are connected with different groups, while not being well connected with each other. We identify outsiders by maximizing the degree assortativity coefficient of the network via node removal, thereby confirming that local structural properties of outsiders identified are consistent with our hypothesis. Our findings suggest that the existence of outsiders should be considered when using Twitter communication networks for social network analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Learning Word Representations from Relational Graphs

Attributes of words and relations between two words are central to numerous tasks in Artificial Intelligence such as knowledge representation, similarity measurement, and analogy detection. Often when two words share one or more attributes in common, they are connected by some semantic relations. On the other hand, if there are numerous semantic relations between two words, we can expect some of the attributes of one of the words to be inherited by the other. Motivated by this close connection between attributes and relations, given a relational graph in which words are inter- connected via numerous semantic relations, we propose a method to learn a latent representation for the individual words. The proposed method considers not only the co-occurrences of words as done by existing approaches for word representation learning, but also the semantic relations in which two words co-occur. To evaluate the accuracy of the word representations learnt using the proposed method, we use the learnt word representations to solve semantic word analogy problems. Our experimental results show that it is possible to learn better word representations by using semantic semantics between words.

0 citations0 reviewsNo code linkedOpen access