Relatedness determination device, non-transitory tangible computer-readable medium for the same, and relatedness determination method

Patent metadata

Field	Value
Publication number	US-2015278156-A1
Application number	US-201314432592-A
Country	US
Kind code	A1
Filing date	Nov 1, 2013
Priority date	Nov 5, 2012
Publication date	Oct 1, 2015
Grant date	—

Abstract

A relatedness determination device includes: a feature vector acquisition portion that acquires a binarized feature vector; a basis vector acquisition portion that acquires a plurality of basis vectors obtained by decomposing a real vector into a linear sum of the basis vectors, which have a plurality of elements including only binary or ternary discrete values; and a vector operation portion that sequentially performs inner product calculation between the binarized feature vector and each of the basis vectors to determine relatedness between the real vector and the binarized feature vector.

First claim

1 . A relatedness determination device comprising:
a feature vector acquisition portion that acquires a binarized feature vector; a basis vector acquisition portion that acquires a plurality of basis vectors obtained by decomposing a real vector into a linear sum of the basis vectors, which have a plurality of elements including only binary or ternary discrete values; and a vector operation portion that sequentially performs inner product calculation between the binarized feature vector and each of the basis vectors to determine relatedness between the real vector and the binarized feature vector.

2 . The relatedness determination device according to claim 1 ,
wherein the inner product calculation between the binarized feature vector and each of the basis vectors includes inner product calculation between a first binary vector having only −1 and 1 as an element and a plurality of second binary vectors having only −1 and 1 as an element.

3 . The relatedness determination device according to claim 2 ,
wherein the first binary vector corresponds to the binarized feature vector.

4 . The relatedness determination device according to claim 2 ,
wherein the first binary vector corresponds to a vector obtained by dividing each element of the binarized feature vector by a predetermined coefficient.

5 . The relatedness determination device according to claim 2 ,
wherein the binarized feature vector is obtained by linearly transforming each element of the first binary vector.

6 . The relatedness determination device according to claim 2 ,
wherein the second binary vector corresponds to the basis vector.

7 . The relatedness determination device according to claim 2 ,
wherein the second binary vector corresponds to a vector obtained by dividing each element of the basis vector by a predetermined coefficient.

8 . The relatedness determination device according to claim 2 ,
wherein the basis vector is obtained by linearly transforming each element of the second binary vector.

9 . The relatedness determination device according to claim 1 ,
wherein the inner product calculation between the binarized feature vector and each of the basis vectors includes inner product calculation between a binary vector having only −1 and 1 as an element and a plurality of ternary vectors having only −1, 0, and 1 as an element.

10 . The relatedness determination device according to claim 9 ,
wherein the binary vector corresponds to the binarized feature vector.

11 . The relatedness determination device according to claim 9 ,
wherein the binary vector corresponds to a vector obtained by dividing each element of the binarized feature vector by a predetermined coefficient.

12 . The relatedness determination device according to claim 9 ,
wherein the binarized feature vector is obtained by linearly transforming each element of the binary vector.

13 . The relatedness determination device according to claim 9 ,
wherein the ternary vectors correspond to the basis vectors, respectively.

14 . The relatedness determination device according to claim 9 ,
wherein the ternary vectors correspond to vectors obtained by dividing each element of the basis vectors by a predetermined coefficient.

15 . The relatedness determination device according to claim 9 ,
wherein the plurality of basis vectors are obtained by linearly transforming each element of the ternary vectors.

16 . The relatedness determination device according to claim 2 ,
wherein the vector operation portion performs exclusive-or operation between the first binary vector and the second binary vector to calculate an inner product between the first binary vector and the second binary vector.

17 . The relatedness determination device according to claim 9 ,
wherein, in the inner product calculation between the binary vector and the ternary vectors, the vector operation portion:
replaces an element of 0 in the ternary vector with any one of −1 and 1 to generate a zero-permutation vector;
replaces an element of 0 in the ternary vector with −1, and replaces an element other than 0 with 1 to generate a filter vector;
performs a conjunction operation between the filter vector and an exclusive-or operation, which is performed between the binary vector and the zero-permutation vector, to obtain the number of different elements other than 0 between the binary vector and the ternary vector;
subtracts the number of different elements and the number of elements other than 0 from the number of elements of the binary vector to obtain the number of same elements other than 0 between the binary vector and the ternary vector; and
subtracts the number of different elements other than 0 between the binary vector and the ternary vector from the number of same elements other than 0 between the binary vector and the ternary vector to obtain an inner product between the binary vector and the ternary vector.

18 . The relatedness determination device according to claim 1 ,
wherein the basis vectors are obtained so as to minimize a decomposition error, which is a difference between the real vector and a linear sum of the basis vectors.

19 . The relatedness determination device according to claim 1 ,
wherein the basis vectors are obtained so as to minimize a decomposition error being a difference between an inner product, which is performed between the real vector and the feature vector, and an inner product, which is performed between a linear sum of the basis vectors and the feature vector.

20 . The relatedness determination device according to claim 18 ,
wherein the plurality of basis vectors together with a plurality of coefficients are obtained by repeatedly performing a first update and a second update, the first update fixing each element of the basis vectors and updating the plurality of coefficients related to the basis vectors so as to minimize the decomposition error, and the second update fixing the plurality of coefficients and updating each element of the basis vectors so as to minimize the decomposition error.

21 . The relatedness determination device according to claim 20 ,
wherein the basis vectors are obtained by repeating the first update and the second update until a reduction amount of the decomposition error is equal to or smaller than a predetermined value.

22 . The relatedness determination device according to claim 18 ,
wherein the basis vectors are obtained by changing initial values of the basis vectors and the coefficients to obtain a plurality of combinations of the basis vectors and the coefficients, and selecting one of combinations of the basis vectors and the coefficients that minimizes the decomposition error.

23 . The relatedness determination device according to claim 18 ,
wherein a plurality of coefficients related to the basis vectors are discrete values.

24 . The relatedness determination device according to claim 18 ,
wherein the basis vectors are obtained by subtracting an average value of elements of the real vector from each element of the real vector to generate an offset real vector, and decomposing the offset real vector into a linear sum of the basis vectors.

25 . The relatedness determination device according to claim 1 ,
wherein the vector operation portion obtains a sum of results of the inner product calculation each time the inner product calculation is performed between the feature vector and

Assignees

• Denso Corp

Inventors

• Ambai Mitsuru
• Shimizu Mikio

Classifications

• G06V10/764

  using classification, e.g. of video objects · CPC title

• G06F18/24

  Classification techniques · CPC title

• G06N20/00

  Machine learning · CPC title

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title