Pointwise HSIC: A Linear-Time Kernelized Co-occurrence Normfor Sparse Linguistic Expressions [EMNLP2018]
Sho Yokoi (Tohoku U./AIP)*, Sosuke Kobayashi (PFN), Kenji Fukumizu (ISM), Jun Suzuki *, Kentaro. Inui *1809.00800

https://bit.ly/2SfpZmv

github.com/cl-tohoku/phsic

pip install phsic-cli

Computing Co-occurrence Strength in NLP
observed: paired data ! = #$ , &$ ~ ()*task: compute “co-occurrence/association/relation strength” of #, & ∈ , × .
Collocation Extraction

Dialogue Response SelectionNewYorkI've lost my …

I saw it at …

intheI've lost my …

I don’t know

Pointwise HSIC: A Linear-Time Kernelized Co-occurrence Normfor Sparse Linguistic Expressions [EMNLP2018]
Sho Yokoi (Tohoku U./AIP)*, Sosuke Kobayashi (PFN), Kenji Fukumizu (ISM), Jun Suzuki *, Kentaro. Inui *1809.00800

https://bit.ly/2SfpZmv

github.com/cl-tohoku/phsic

pip install phsic-cli

Computing Co-occurrence Strength in NLP
observed: paired data ! = #$ , &$ ~ ()*task: compute “co-occurrence/association/relation strength” of #, & ∈ , × .
Collocation Extraction
NewYork

I've lost my …

I saw it at …

intheI've lost my …

I don’t know

De facto Measure: Pointwise Mutual Information
co-occurrence
actualPMI(𝑥, 𝑦) = log

𝐏 (𝑥, 𝑦)𝐏 (𝑥)𝐏 (𝑦)PMI(𝑥, 𝑦) = log<latexit sha1_base64="(null)">(null)</latexit>

Dialogue Response Selection

using
RNNs

just
counting𝑛 ⋅ #(𝑥, 𝑦)#(𝑥, ⋅)#(⋅, 𝑦)

PMI(𝑥, 𝑦) = log<latexit sha1_base64="8J8nlmkRzEYQ/hGx73TYH8/olB0=">AAAC6HicbVLLahRBFK1pH4nta6JLN4XDQAIxdItgNkIgLnQRmICTBKaHobr69kyl60VVtXFoGn/Bnbj1J/wWF271N6zuaWEm8ULB4Zx769a9p1LNmXVR9LMX3Lp95+7W9r3w/oOHjx73d56cWVUaCmOquDIXKbHAmYSxY47DhTZARMrhPC2OG/38IxjLlPzglhqmgswlyxklzlOz/mlyxTJYEFclgriFEdXo5H1d737aX+7hNzjhap7khtBK4oRmyuFk0Gp11YKW2/OwBQ0fzvqD6CBqA98EcQcGqIvRbKf3OckULQVIRzmxdhJH2k0rYhyjHOowKS1oQgsyh4mHkgiw06qdvcZDz2Q4V8Yf6XDLrldURFi7FKnPbAa017WG/J82KV1+OK2Y1KUDSVeN8pJjp3CzSJwxA9TxpQeEGubfiumC+FU5v+6NLqVkVGXwYtVqQ2rebDVQP6QFJwiTDVMdewMNIyvWEmk7ljNP/8t1i/VcfNLcHuIh1uoKjFas3YbQ3mj/GcIhXu9bNOX7uABTMFt7y+LrBt0EZy8PYo9PXw2O3nbmbaNn6DnaRTF6jY7QOzRCY0TRD/QL/UZ/gsvgS/A1+LZKDXpdzVO0EcH3v4Ts7LQ=</latexit>
sha1_base64="42E7OKHvnELqEyhMzj/KkRH20mc=">AAACh3icbVFNaxsxEJU3zUc335deehENhh6SsJtLcughYAK9FBKok4Bjwqx2HIvVF9Jsg1lM7rn21/XfVGu7YCcdEDzezOjNzCuckoGy7E8nWfuwvrG59THd3kl39/YPdm6Drb3AvrDK+vsCAippsE+SFN47j6ALhXdF1Wvzd7/QB2nNT5o4HGp4MnIkBVCkrh8PjrLTbBb8PcgX4Igt4vGw8/JQWlFrNCQUhDDIM0fDBjxJoXCaPtQBHYgKnnAQoQGNYdjM5pzybmRKPrI+PkN8xi53NKBDmOgiVmqgcXiba8n/5QY1jS6GjTSuJjRiLjSqFSfL26V5KT0KUpMIQHgZZ+ViDB4ExdOsqNRGClviyVxqJdXOHByKuGRA0iBNyzS9eGwvYc4GMGHBKhnpf7U0Xq7lP9rfU97lzj6jd1bOrqFdNCUal3b5sm7Vth/zCn0lwzQ6lr/15z24PTvNI77J2Bb7zL6wryxn5+ySfWfXrM8EK9kr+518Sr4lvbmzSWdh8SFbieTqL1iay1g=</latexit>
sha1_base64="0A/ahD8VMA0aeWlDrjYFw2BvS2E=">AAAC3XicbZLNattAEMfX6kdSNW2dXntZagwJpEHKpb0UCrm0h4ADdRKwjFmtRvZW+8XuKqlZRF+ht9In6bP00Gv7Gl3JLthJBwR/fjO7szN/5Zoz65LkZy+6d//Bw53dR/HjvSdPn/X39y6sqg2FMVVcmaucWOBMwtgxx+FKGyAi53CZV6dt/vIajGVKfnRLDVNB5pKVjBIX0Kx/nt2wAhbE+UwQtzDCj84+NM3B56PlIX6LM67mWWkI9RJntFAOZ4Mu1/hOdOwwyE60PJ71B8lx0gW+K9K1GKB1jGb7vS9ZoWgtQDrKibWTNNFu6olxjHJo4qy2oAmtyBwmQUoiwE59N3uDh4EUuFQmfNLhjm6e8ERYuxR5qGwHtLdzLfxfblK78s3UM6lrB5KuGpU1x07hdpG4YAao48sgCDUsvBXTBQmrcmHdW11qyagq4NWq1VaqfbPVQMOQFpwgTLbEnwYDDSMraom0a8pZwP9q3WKzFp+1t8d4iLW6AaMV67YhdDA6/AzxEG/2rdrjR7gCUzHbBMvS2wbdFRcnx2nQ5wnaRS/QS3SAUvQavUPv0QiNEUU/0C/0G/2JPkVfo28rc6Pe2uXnaCui738BWDXrXg==</latexit>
sha1_base64="1+VUKp+xN/g/PcPqXlDzf8Wo2ak=">AAAC6HicbVLLattAFB2rr1R9Oemym6HGkEAapG7aTSGQLNJFwIE6CVjGjEZX9lTzYmbU1AjRX8iudNuf6Ld00W37Gx3JKthJLwwczrl37tx7JtWcWRdFP3vBnbv37j/Yehg+evzk6bP+9s65VaWhMKaKK3OZEgucSRg75jhcagNEpBwu0uKo0S8+gbFMyQ9uqWEqyFyynFHiPDXrnyVXLIMFcVUiiFsYUY1O39f17uf95R5+hxOu5kluCK0kTmimHE4GrVZXLWi5PQ9b0PDhrD+IDqI28G0Qd2CAuhjNtntfkkzRUoB0lBNrJ3Gk3bQixjHKoQ6T0oImtCBzmHgoiQA7rdrZazz0TIZzZfyRDrfsekVFhLVLkfrMZkB7U2vI/2mT0uVvpxWTunQg6apRXnLsFG4WiTNmgDq+9IBQw/xbMV0Qvyrn173RpZSMqgxerVptSM2brQbqh7TgBGGyYaojb6BhZMVaIm3Hcubpf7lusZ6LT5vbQzzEWl2B0Yq12xDaG+0/QzjE632LpnwfF2AKZmtvWXzToNvg/PVB7PFZNDg87szbQi/QS7SLYvQGHaITNEJjRNEP9Av9Rn+Cj8F18DX4tkoNel3Nc7QRwfe/g6zssA==</latexit>

𝐏(𝑦|𝑥)𝐏(𝑦)<latexit sha1_base64="iZm2t2viqgME5d2mBcyJL6SmJMc=">AAADD3icjVJBb9MwFHbCYCOw0cGRi0VVqZXGlCAkdkGatAs7bCqIbpOaqnKcl9aKY0e2wxqFiN/Ar+GGuPITuPBbcNoA7caBJ1n69L3v+T2/z1HOmTa+/8Nx72zdvbe9c9978HB371Fn//GFloWiMKKSS3UVEQ2cCRgZZjhc5QpIFnG4jNKTJn/5AZRmUrw3ZQ6TjMwESxglxlLTziK8ZjHMianCjJi5yqrh2Wld9xcH5QC/xiGXszBRhFZ/dbrMogQP6+mfknfn53WN++XHxaD+L+Gg9qadrn/oLwPfBkELuqiN4XTf+RTGkhYZCEM50Xoc+LmZVEQZRjnUXlhoyAlNyQzGFgqSgZ5UyxXVuGeZGCdS2SMMXrLrFRXJdDOvVTaz6pu5hvxXblyY5GhSMZEXBgRdNUoKjo3Ezb5xzBRQw0sLCFXMzorpnNiNGuvKRpdCMCpjeL5qtZFqZtY5UPtIDSYjTDRMdWJ9VoysWE2EblnOLP1ba+brWnzW3O7hHs7lNahcsuU2stz+B/tnvB5e75s25Qc4BZUyXVvLgpsG3QYXLw4Di9++7B6ftubtoKfoGeqjAL1Cx+gNGqIRouins+XsOnvuZ/eL+9X9tpK6TlvzBG2E+/0XCTb9Bg==</latexit>

co-occurrenceby chanceeasy to learn
inappropriate to sparse data

tough to learn
applicable to sparse dataProposed Measure for Computing Co-occurrence Strength: Pointwise HSIC
Dependence of!

and"

.

Mutual Information

Co-occurrence of= E( , )andPMI(𝑥, 𝑦; 𝑋, 𝑌)

contribute

𝐏 (𝑥, 𝑦)= log
𝐏 (𝑥)𝐏 (𝑦)<latexit sha1_base64="(null)">(null)</latexit><latexit sha1_base64="(null)">(null)</latexit>HSIC [Gretton+’05]

Pointwise HSIC

Kernels%: ' × ' → ℝℓ: , × , → ℝ

HSIC(𝑋, 𝑌; 𝑘 , ℓ ) = MMD ,ℓ [𝐏 , 𝐏 𝐏 ]PHSIC(𝑥, 𝑦; 𝑋, 𝑌, 𝑘 , ℓ )= 𝐄= (𝜙(𝑥) − 𝑚 ) 𝐶 (𝜓(𝑦) − 𝑚 )

( , )

= 𝐄

(𝜙(𝑥) − 𝑚 ) 𝐶 (𝜓(𝑦) − 𝑚 )( , ) (<latexit sha1_base64="(null)">(null)</latexit>

𝐄 [𝑘(𝑥, 𝑥 )ℓ(𝑦, 𝑦 )],)$Pointwise Mutual Information

MI(𝑋, 𝑌) = KL[𝐏 ‖𝐏 𝐏 ]𝐏 (𝑥, 𝑦)log
𝐏 (𝑥)𝐏 (𝑦)#=contribute(𝐄 [𝑘(𝑥, 𝑥 )ℓ(𝑦, 𝑦 )],)

<latexit sha1_base64="(null)">(null)</latexit>

Requires very short learning time1000 times faster than RNN-based PMI

Applicable to sparse objects
PHSIC allows various and available similarity metrics to be plugged in as kernels

Pointwise HSIC: A Linear-Time Kernelized Co-occurrence Normfor Sparse Linguistic Expressions (EMNLP2018)
Sho Yokoi (Tohoku U./AIP)*, Sosuke Kobayashi (PFN), Kenji Fukumizu (ISM), Jun Suzuki *, Kentaro. Inui *https://bit.ly/2SfpZmv

1809.00800
input: paired data ! =#$ , &$~ ()*Collocation Extraction

github.com/cl-tohoku/phsic

goal: compute “co-occurrence strength” of #, & ∈ , × .

Dialogue Response Selection

NewYork

I've lost my …

I saw it at …

intheI've lost my …

I’m so sleepy

PMI(𝑥, 𝑦) = log

𝑛 ⋅ #(𝑥, 𝑦)#(𝑥, ⋅)#(⋅, 𝑦)

pip install phsic-cli

PMI(𝑥, 𝑦) = log<latexit sha1_base64="8J8nlmkRzEYQ/hGx73TYH8/olB0=">AAAC6HicbVLLahRBFK1pH4nta6JLN4XDQAIxdItgNkIgLnQRmICTBKaHobr69kyl60VVtXFoGn/Bnbj1J/wWF271N6zuaWEm8ULB4Zx769a9p1LNmXVR9LMX3Lp95+7W9r3w/oOHjx73d56cWVUaCmOquDIXKbHAmYSxY47DhTZARMrhPC2OG/38IxjLlPzglhqmgswlyxklzlOz/mlyxTJYEFclgriFEdXo5H1d737aX+7hNzjhap7khtBK4oRmyuFk0Gp11YKW2/OwBQ0fzvqD6CBqA98EcQcGqIvRbKf3OckULQVIRzmxdhJH2k0rYhyjHOowKS1oQgsyh4mHkgiw06qdvcZDz2Q4V8Yf6XDLrldURFi7FKnPbAa017WG/J82KV1+OK2Y1KUDSVeN8pJjp3CzSJwxA9TxpQeEGubfiumC+FU5v+6NLqVkVGXwYtVqQ2rebDVQP6QFJwiTDVMdewMNIyvWEmk7ljNP/8t1i/VcfNLcHuIh1uoKjFas3YbQ3mj/GcIhXu9bNOX7uABTMFt7y+LrBt0EZy8PYo9PXw2O3nbmbaNn6DnaRTF6jY7QOzRCY0TRD/QL/UZ/gsvgS/A1+LZKDXpdzVO0EcH3v4Ts7LQ=</latexit>
sha1_base64="42E7OKHvnELqEyhMzj/KkRH20mc=">AAACh3icbVFNaxsxEJU3zUc335deehENhh6SsJtLcughYAK9FBKok4Bjwqx2HIvVF9Jsg1lM7rn21/XfVGu7YCcdEDzezOjNzCuckoGy7E8nWfuwvrG59THd3kl39/YPdm6Drb3AvrDK+vsCAippsE+SFN47j6ALhXdF1Wvzd7/QB2nNT5o4HGp4MnIkBVCkrh8PjrLTbBb8PcgX4Igt4vGw8/JQWlFrNCQUhDDIM0fDBjxJoXCaPtQBHYgKnnAQoQGNYdjM5pzybmRKPrI+PkN8xi53NKBDmOgiVmqgcXiba8n/5QY1jS6GjTSuJjRiLjSqFSfL26V5KT0KUpMIQHgZZ+ViDB4ExdOsqNRGClviyVxqJdXOHByKuGRA0iBNyzS9eGwvYc4GMGHBKhnpf7U0Xq7lP9rfU97lzj6jd1bOrqFdNCUal3b5sm7Vth/zCn0lwzQ6lr/15z24PTvNI77J2Bb7zL6wryxn5+ySfWfXrM8EK9kr+518Sr4lvbmzSWdh8SFbieTqL1iay1g=</latexit>
sha1_base64="0A/ahD8VMA0aeWlDrjYFw2BvS2E=">AAAC3XicbZLNattAEMfX6kdSNW2dXntZagwJpEHKpb0UCrm0h4ADdRKwjFmtRvZW+8XuKqlZRF+ht9In6bP00Gv7Gl3JLthJBwR/fjO7szN/5Zoz65LkZy+6d//Bw53dR/HjvSdPn/X39y6sqg2FMVVcmaucWOBMwtgxx+FKGyAi53CZV6dt/vIajGVKfnRLDVNB5pKVjBIX0Kx/nt2wAhbE+UwQtzDCj84+NM3B56PlIX6LM67mWWkI9RJntFAOZ4Mu1/hOdOwwyE60PJ71B8lx0gW+K9K1GKB1jGb7vS9ZoWgtQDrKibWTNNFu6olxjHJo4qy2oAmtyBwmQUoiwE59N3uDh4EUuFQmfNLhjm6e8ERYuxR5qGwHtLdzLfxfblK78s3UM6lrB5KuGpU1x07hdpG4YAao48sgCDUsvBXTBQmrcmHdW11qyagq4NWq1VaqfbPVQMOQFpwgTLbEnwYDDSMraom0a8pZwP9q3WKzFp+1t8d4iLW6AaMV67YhdDA6/AzxEG/2rdrjR7gCUzHbBMvS2wbdFRcnx2nQ5wnaRS/QS3SAUvQavUPv0QiNEUU/0C/0G/2JPkVfo28rc6Pe2uXnaCui738BWDXrXg==</latexit>
sha1_base64="1+VUKp+xN/g/PcPqXlDzf8Wo2ak=">AAAC6HicbVLLattAFB2rr1R9Oemym6HGkEAapG7aTSGQLNJFwIE6CVjGjEZX9lTzYmbU1AjRX8iudNuf6Ld00W37Gx3JKthJLwwczrl37tx7JtWcWRdFP3vBnbv37j/Yehg+evzk6bP+9s65VaWhMKaKK3OZEgucSRg75jhcagNEpBwu0uKo0S8+gbFMyQ9uqWEqyFyynFHiPDXrnyVXLIMFcVUiiFsYUY1O39f17uf95R5+hxOu5kluCK0kTmimHE4GrVZXLWi5PQ9b0PDhrD+IDqI28G0Qd2CAuhjNtntfkkzRUoB0lBNrJ3Gk3bQixjHKoQ6T0oImtCBzmHgoiQA7rdrZazz0TIZzZfyRDrfsekVFhLVLkfrMZkB7U2vI/2mT0uVvpxWTunQg6apRXnLsFG4WiTNmgDq+9IBQw/xbMV0Qvyrn173RpZSMqgxerVptSM2brQbqh7TgBGGyYaojb6BhZMVaIm3Hcubpf7lusZ6LT5vbQzzEWl2B0Yq12xDaG+0/QzjE632LpnwfF2AKZmtvWXzToNvg/PVB7PFZNDg87szbQi/QS7SLYvQGHaITNEJjRNEP9Av9Rn+Cj8F18DX4tkoNel3Nc7QRwfe/g6zssA==</latexit>

Proposed Measure (PHSIC)

𝐏(𝑦|𝑥)𝐏(𝑦)PHSIC(𝑥, 𝑦; 𝑘 , ℓ )1=𝑘(𝑥, 𝑥 )ℓ(𝑦, 𝑦 )𝑛<latexit sha1_base64="(null)">(null)</latexit><latexit sha1_base64="iZm2t2viqgME5d2mBcyJL6SmJMc=">AAADD3icjVJBb9MwFHbCYCOw0cGRi0VVqZXGlCAkdkGatAs7bCqIbpOaqnKcl9aKY0e2wxqFiN/Ar+GGuPITuPBbcNoA7caBJ1n69L3v+T2/z1HOmTa+/8Nx72zdvbe9c9978HB371Fn//GFloWiMKKSS3UVEQ2cCRgZZjhc5QpIFnG4jNKTJn/5AZRmUrw3ZQ6TjMwESxglxlLTziK8ZjHMianCjJi5yqrh2Wld9xcH5QC/xiGXszBRhFZ/dbrMogQP6+mfknfn53WN++XHxaD+L+Gg9qadrn/oLwPfBkELuqiN4XTf+RTGkhYZCEM50Xoc+LmZVEQZRjnUXlhoyAlNyQzGFgqSgZ5UyxXVuGeZGCdS2SMMXrLrFRXJdDOvVTaz6pu5hvxXblyY5GhSMZEXBgRdNUoKjo3Ezb5xzBRQw0sLCFXMzorpnNiNGuvKRpdCMCpjeL5qtZFqZtY5UPtIDSYjTDRMdWJ9VoysWE2EblnOLP1ba+brWnzW3O7hHs7lNahcsuU2stz+B/tnvB5e75s25Qc4BZUyXVvLgpsG3QYXLw4Di9++7B6ftubtoKfoGeqjAL1Cx+gNGqIRouins+XsOnvuZ/eL+9X9tpK6TlvzBG2E+/0XCTb9Bg==</latexit>easy to learn
inappropriate to sparse data

tough to learn
applicable to sparse dataeasy to learn
applicable to sparse data