Implementation of Trained Factorization Machine Recommendation System on Quantum Annealer Chen-Yu Liu1 2Hsin-Yu Wang3 4Pei-Yen Liao4Ching-Jui Lai5and Min-Hsiu Hsieh1

2025-05-08 0 0 1.81MB 9 页 10玖币

侵权投诉

Implementation of Trained Factorization Machine Recommendation System on

Quantum Annealer

Chen-Yu Liu,1, 2, ∗Hsin-Yu Wang,3, 4, †Pei-Yen Liao,4, ‡Ching-Jui Lai,5, §and Min-Hsiu Hsieh1, ¶

1Hon Hai (Foxconn) Research Institute, Taipei, Taiwan

2Graduate Institute of Applied Physics, National Taiwan University, Taipei, Taiwan

3Department of Finance, National Taiwan University, Taipei, Taiwan

4Department of Mathematics, National Taiwan University, Taipei, Taiwan

5Department of Mathematics, National Cheng Kung University, Tainan, Taiwan

(Dated: November 9, 2023)

Factorization Machine (FM) is the most commonly used model to build a recommendation sys-

tem since it can incorporate side information to improve performance. However, producing item

suggestions for a given user with a trained FM is time-consuming. To address this problem, we

propose a quadratic unconstrained binary optimization (QUBO) scheme to combine with FM and

apply quantum annealing (QA) computation. Compared to classical methods, this hybrid algorithm

provides a fast sub-optimal sampling of good user suggestions. We then demonstrate the aforemen-

tioned computational behavior on current noisy intermediate-scale quantum (NISQ) hardware by

experimenting with a real example on a D-Wave annealer.

I. INTRODUCTION

Recommendation systems are widely used to predict

the rating or preference of items for arbitrary users, such

as suggesting books or movies, and also for many other

business applications [1–4]. A common principle for con-

structing a recommendation system assumes that users

prefer similar things based on past behavior. Amongst

several approaches, the objective of Matrix Factorization

(MF) is to ﬁnd the factor matrices of historical data [5,6].

Together with MF, other improvements such as SVD++

[7], pairwise interaction tensor factorization (PITF) [8],

factorizing personalized Markov chains (FPMC) [9] and

Monte Carlo on bipartite graphs [10] has also been com-

prehensively studied. These methods introduce special-

ized models to treat speciﬁc tasks but with the trade-oﬀ

of losing generality.

To ﬁx this, the Factorization Machine (FM) [11] is pro-

posed as a more general supervised learning method, uni-

fying MF, SVD++, PITF, and FPMC. With the capa-

bility to input arbitrary real-valued feature vectors to the

model, including side information (e.g., gender and age),

FM can be used for regression, classiﬁcation, and ranking

tasks. Moreover, it can be trained with linear complexity

and accurately estimate model parameters from a sparse

dataset, which makes FM highly competent for analyz-

ing large datasets. Thus, it is more natural and adequate

to utilize FM for real-world applications than the other

methods mentioned earlier.

In recent years, quantum computing has become one

of the most popular domains, which aims to beneﬁt from

∗cyliuphys@gapp.nthu.edu.tw

†b07703009@ntu.edu.tw

‡b08705006@ntu.edu.tw

§cjlai72@mail.ncku.edu.tw

¶min-hsiu.hsieh@foxconn.com

the superposition nature of quantum states. Quantum

Machine Learning (QML) employs parameterized quan-

tum circuits as a neural network, which can then be

applied to diﬀerent classes of machine learning, such

as Quantum Neural Network (QNN) [12–14], Quantum

Convolutional Neural Network (QCNN) [15–17], Quan-

tum Reinforcement Learning (QRL) [18–20], and Quan-

tum Generative Adversarial Neural Network (QGAN)

[21–25]. Besides the structural exploration, several works

[26–34] have also investigated the learnability and train-

ability of QNN. Although the data encoding to a Hilbert

space may give potential computational advantages, at

the current stage of the NISQ era, only low-dimensional

or small sample problems can be implemented on real-

world hardware. Thus it is hard to justify the advantage

experimentally, and this needs to be further studied [35].

The concept of a Quantum Recommendation Sys-

tem (QRS) has also been proposed [36], for which

the idea is to sample an approximation of the pref-

erence matrix by quantum singular value estimation

and quantum projection. In that framework, QRS

takes O(poly(k)polylog(mn)) running time with kthe

rank of the approximation and mn the matrix dimen-

sion, while classically reconstructing an approximation

of the preference matrix requires polynomial time mn.

However, a classical analog of QRS, called Quantum-

Inspired Recommendation System (QIRS), provides

O(poly(k)log(mn)) running time [37], which closes the

gap between the classical and quantum methods. Be-

sides gate-based quantum computing, it is possible to

apply quantum annealing for feature selection [38] and

use these features to train a classical ItemKNN content-

based model [39]. This hybrid QPU solver shows good

scalability for larger instances but may not have a signif-

icant advantage in the running time.

The performance of QRS or QIRS depends on a good

low-rank approximation to the preference matrix [36,37].

Moreover, since these algorithms do not incorporate side

information, they may not be competitive with FM. Thus

arXiv:2210.12953v2 [quant-ph] 8 Nov 2023

in the recommendation system domain, an approach to

both utilize the side information and attain potential

speedup is a crucial target for practical quantum com-

puting applications.

In this work, we formulate a hybrid recommendation

system by incorporating a classically trained FM with

a quadratic unconstrained binary optimization (QUBO)

scheme to be solved quantumly. Applying Quantum An-

nealing (QA) computation enables us to sample a large

amount of sub-optimal suggestions in a short period

of time compared to classical methods. Our algorithm

will soon provide a computational advantage from the

prospects of today’s developing NISQ hardware, such as

a D-Wave annealer, for practical problems.

A. Main Results

Our main results in a both theoretical and experimen-

tal speedup of a QA-assisted FM recommendation system

are summarized as follows:

•Suggestion process as energy minimizing task: We

propose a QUBO scheme for the suggestion pro-

cess of the FM recommendation system. The en-

ergy minimization task of the corresponding Ising

problem is equivalent to ﬁnding the highest score

(rating) candidates in the recommendation system.

•NISQ advantage of Quantum Annealing in recom-

mendation system: Ideally, the quantum anneal-

ing process aims to yield the ground state of the

Hamiltonian. However, the presence of noise and

the limitation of annealing time on current NISQ

hardware often leads to a multitude of sub-optimal

solutions for the Hamiltonian. Interestingly, these

sub-optimal solutions align quite well with the ob-

jectives of the recommendation system, which is de-

signed to provide multiple suggestions rather than

just the absolute best one.

•Scalability: The capability of solving fully-

connected size-NpIsing problems of the most ad-

vanced D-Wave Advantage 4.1 system is Np= 145.

At the same time, the corresponding QUBO size of

suggesting Nmcandidates is ⌈log2Nm⌉in our for-

mulation. Hence, theoretically, the solvable prob-

lem size Nmscales up to 2145 ≈1043 in today’s

quantum hardware.

B. Related Work

Several works apply the QUBO scheme to the machine

learning study. Date et al. [40] proposes QUBO for-

mulations of linear regression, support vector machine

(SVM), and balanced k-means clustering, where the re-

quired qubit number usually scales as O(N2

data), with

Ndata the number of the data points of the training data.

However, Ndata could go easily beyond 103in most ma-

chine learning applications, which is higher than the ca-

pability of the most advanced quantum system for solving

an Ising problem: Ndata = 145 from D-Wave [41]. One

can transform an FM into a QUBO problem by binary

encoding with a size equivalent to the length of the in-

put vector. The works [42–45] have applied this idea in

structural design problems to maximize the acquisition

function associated to an FM. In this manner, the size

of the QUBO problem is usually within a range that to-

day’s hardware could reach. These examples open the

possibility of applying such a QUBO-FM scheme to any

FM-related research.

II. PRELIMINARIES

In this preliminary section, we review the key ingredi-

ents of our work: FM, QUBO, and Quantum Annealing

(QA). FM is the most commonly used model in recom-

mendation systems and machine learning. The QUBO

scheme can apply to various combinatorial optimization

problems, and QA is an eﬀective optimization method

for solving QUBO problems.

A. Factorization Machine

A factorization machine (FM) is a supervised learning

algorithm that can be used for classiﬁcation, regression,

and ranking tasks [11]. Here we consider FM with degree

D= 2, which involves only single and pairwise interac-

tions of items. The model equation for an FM of degree

D= 2 with variables

⃗x = (x1, . . . , xd)

is deﬁned as:

yfm(⃗x) := w0+⃗w ·⃗x +

i<j

ivjxixj,(1)

where w0∈Ris the global bias, ⃗w = (w1, . . . , wd)∈Rd

refers to the weights of each variables and

V=

v1v2. . . vd

∈Rk×d(2)

denotes the feature embeddings with kthe dimensionality

of latent factors. The term vT

ivjrepresents the interac-

tion between the i-th and j-th terms.

We can use FM to construct a recommendation system:

Separate the variables ⃗x into xi=uifor 1 ≤i≤nuand

xi+nu=mifor 1 ≤i≤nm, so that the vector ⃗u =

(u1, . . . , unu) denotes the information of a user and ⃗m =

(m1, . . . , mnm) represents the information of an item to

be recommended, with the dimension relation nu+nm=

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ImplementationofTrainedFactorizationMachineRecommendationSystemonQuantumAnnealerChen-YuLiu,1,2,∗Hsin-YuWang,3,4,†Pei-YenLiao,4,‡Ching-JuiLai,5,§andMin-HsiuHsieh1,¶1HonHai(Foxconn)ResearchInstitute,Taipei,Taiwan2GraduateInstituteofAppliedPhysics,NationalTaiwanUniversity,Taipei,Taiwan3DepartmentofFina...

展开>> 收起<<

Implementation of Trained Factorization Machine Recommendation System on Quantum Annealer Chen-Yu Liu1 2Hsin-Yu Wang3 4Pei-Yen Liao4Ching-Jui Lai5and Min-Hsiu Hsieh1.pdf

共9页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Implementation of Trained Factorization Machine Recommendation System on Quantum Annealer Chen-Yu Liu1 2Hsin-Yu Wang3 4Pei-Yen Liao4Ching-Jui Lai5and Min-Hsiu Hsieh1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: