日本ソフトウェア科学会第 34 回大会 (2017 年度) 講演論文集

Non-negative Tri-factorization with a Dynamic
Laplacian Constraint for Associating Features
Hongjie Zhai

Makoto Haraguchi

We deal with the problem of embedding features from two diﬀerent data sets into a common space forfinding associated features. In the previous works, we have proposed a embedding framework based on
Non-negative Tri-factorization and a laplacian constraint. In this framework, features are embedded into acommon space where associated ones will have the same vector representation. However, the experiments
we have conducted show that many unrelated features are also near to each other in the common space. The
reason is that we can not use negative samples because of the limitation of Non-negative Tri-factorization.
In this paper, to address this issue, we introduce the Dynamic Laplacian Constraint. That is, during the optimization process, we dynamically find new associated features and add them into the laplacian constraint.
By this way, we can refine the common space step by step. Furthermore, when finding new associated features, we can introduce extra constraints to explicitly excluded the unrelated features. Experiments show
the Dynamic Lapalcian Constraint can deliver quality improvements over our previous framework.

Once new associations are detected, they can be

1 Introduction

added to known association set. Thus, we are able

In this paper, we study a problem of guess-to use the new known association set to furtherly

ing feature association. That is, considering two

find new associations. By repeating this process,object sets O1 = {o11 , o12 , . . . , o1n } and O2 =finally all the possible associated feature pairs can{o21 , o22 , . . . , o2m }, where objects in O1 are described

be detected. For the performance and scalability,jects in OF2={f11 , f21 , . . . , fu1 }and ob-we formulize this clustering-based methed by Non-are described by another feature set

negative Tri-factorization with a dynamic laplacianby feature set F2

1={f12 , f22 , . . . , fv2 }.

Some “hints” of associa-constraint.

tions, which are partial associations between two

2 Basic Idea and Algorithm

feature sets, are assumed already known. The tar-

The basic idea of our method is illustrated in

get to finding the association between remaining

Figure 4. Here, we have two object-feature rela-features.

tion tables, where f11 , f21 , f31 , . . . are the features ofWe proposed a novel method for finding the fea-

objects o11 , o12 , o13 , . . .. If a object contains the fea-

ture associations. To guess the missing associa-

ture, the corresponding position will be 1 as showntions, our method tries to find new associationsin Figure 1. Additionally, we also have two asso-

by the knowledge from known associations (hints).

ciated feature pairs: f11 − f12 and f21 − f22 . Firstly,
we merge the associated features into one. AfterThis is an unrefereed paper. Copyrights belong tothe Author(s).
ジェイ 泓杰, 原口 誠, 北海道大学情報科学研究科, Graduate School of IST, Hokkaido University.

that, by only focus on the merged ones, we canconstruct the vector representation of objects withthe same dimensions. For example, in Figure 2, f11and f12 are merged as f1 as well as that f12 and f22
are merged into f2 . With these constructed vectors,Conclusively speaking, our method can be concluded as the following two-phase process:we perform clustering on objects. As the result, the• Use associated features to build the commonobjects in diﬀerent sets may be clustered into one

space, clustering objects in this common fea-

object cluster just like Figure 2. Here, cluster c1

ture space.

contains object o11 , o13 and o23 while cluster c2 contains object o12 and o22 .

Moreover, by representing

features with object clusters, we can perform clus-• Use object clusters to build the commonspace, clustering features in this common object space.

tering on features to find new associations. This is

To improve the performance for large scale data,illustrated in Figure 3. It is easy to find that underinstead of the two-phases algorithm, we embed fea-

the object cluster representation, f41

havetures into a common space by tri-factorization pro-the same vector. Thus, we found a new association

posed by [3]. In this common space, the associatedf41 −f42 . Once new associations are found, we merge

features are guarantee to have the same vector rep-

into one and repeat the whole process until no newresentation. Furthermore, we adapted a “dynamic”

associations can be found.

laplacian scheme to extend the hint set dynami-and f42cally. We show the details in the algorithm 1.
1122Here, D1 ∈ R+|O |×|F | , D2 ∈ R+|O |×|F | are
the relation matrix, where dij = 1 if object oi
1212contains feature fj . W ∈ R|F |+|F |×|F |+|F | iscalled feature relation matrix (laplacian). It is constructed from the following rules:
図1

Merge associated features• if i ≤ |F 1 |andj ≤ |F 1 |, wij = 0• if i ≥ |F 1 |andj ≥ |F 1 |, wij = 0• if i ≤ |F 1 |andj ≥ |F 1 |, if fi and fj are associated, wij = 1, else wij = 0• if i ≥ |F 1 |andj ≤ |F 1 |, wij = wji
By considering each feature as a vertex and connect the associated feature pairs, we can get a bigraph G. It is easy to know that the matrix K is the

図2

Clustering in common
feature space

laplacian matrix of graph G. According to [2], thelaplacian constraint can make sure the associatedfeatures always have similar vector representationin the common space. We should point out thatthe relation matrix (laplacian) will change according to the optimization. In each epoch, we selectthe nearest features pairs as the new association
and add them to the laplacian. Thus, the lapla-

図3

Mining new associations incommon object cluster space
図4

Illustration of Idea

cian is extended during optimization until all thefeature are associated.

Data: Object-feature relation matrix: D1 ,D2 , feature relation matrix: W ,feature set F 1 and F 2 , object set O1 ,O2 , Dimension Parameter: N ,MResult: Associated feature pairs
Initialize random non-negative matrix L1 ,C 1 , R1 , L2 , C 2 , R2 , where

Italian and vice versa. We randomly selected several pairs as the hints. Because of the time limitation, the experiment result is still under preparation. We would like to report the details in oralrepresentation.

4 Conclusion and Future Works

C {1,2} ∈ R+N ×M ;while features are remaining to beThis paper proposed a general method for featureassociation guessing and give a tri-factorization for-associated do
K = D − W , where dii =∑j wij ;Solve the following tri-factorization
problem: argminL1 ,C 1 ,R1 ,L2 ,C 2 ,R2 |D1 −
L1 C 1 R1 | + |D2 − L2 C 2 R2 | +1late service. Each Spanish noun is translated into

1R TR
λ( R2 ) K( R2 );Find f1 ∈ F 1 and f2 ∈ F 2 where|f1 − f2 |2F is minimum. Setwi,|F 1 |+j = 1.
endAssign column vector in R1 and R2 to eachfeature in order;
for each vector vj1 in R1 do
Find the nearest vector vj2 in R2 ;Print (Fi1 , Fj2 ) as associated feature pair.
end
Algorithm 1: Tri-factorization for AssociationLearning

3 Experiment
To validate the ability of proposed method, weperformed a preliminary experiment. We take theSpanish/Italian news articles between 1996-08-20
and 1996-08-25 from Reuters Corpora [1]. We randomly selected 4, 000 from both Spanish and Italianarticles as the objects. After morphological analysis by tree-tagger [5], we only keep nouns as features. To generate the hints, we used google trans-mulation of the method. Our algorithm adapts adynamic laplacian approach which dynamically extend the set of hints. This scheme allow us startingfrom a small set of known associations and extend
them to all the dataset. However, there are still several problems remaining to be solved: (1) The convergence of Tri-factorization with dynamic laplacian still need to be investgated. (2) Experimentson large dataset (e.g. 20, 000 documents) still need
to be done. (3) Dynamic laplacian needs selecting new associations during optimization. Thus, aguideline for selecting now associations should bedesigned.
参 考 文 献[1] Lewis David D., et al. ”Rcv1: A new benchmark
collection for text categorization research.” Journalof machine learning research 5.Apr (2004): 361-397.
[2] Cai Deng, et al. ”Graph regularized nonnegative
matrix factorization for data representation.” IEEE
Transactions on Pattern Analysis and Machine Intelligence 33.8 (2011): 1548-1560.
[3] Long Bo, Zhongfei Mark Zhang and Philip S. Yu.
”Co-clustering by block value decomposition.” Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data
mining. ACM, 2005.
[4] Lee Daniel D. and H. Sebastian Seung. ”Algorithms for non-negative matrix factorization.” Advances in neural information processing systems.
2001.
[5] Schmid, Helmut. ”Probabilistic part-ospeech tagging using decision trees.” New methods in language
processing. Routledge, 2013.