# Physical Artificial Intelligence: The Concept Expansion of Next-Generation
Artificial Intelligence

Yingbo Li  Hainan University
<EMAIL_ADDRESS>Yucong Duan *Corresponding author<EMAIL_ADDRESS>Hainan University
<EMAIL_ADDRESS>Anamaria-Beatrice Spulber  Visionogy
<EMAIL_ADDRESS>Haoyang Che  Zeekr Group,
<EMAIL_ADDRESS>Zakaria Maamar  Zayed University
<EMAIL_ADDRESS>Zhao Li  Alibaba Group
<EMAIL_ADDRESS>Chen Yang  Ghent University
<EMAIL_ADDRESS>Yu lei  Inner Mongolia University,
<EMAIL_ADDRESS>
###### Abstract

Artificial Intelligence has been a growth catalyst to our society and is
cosidered across all idustries as a fundamental technology. However, its
development has been limited to the signal processing domain that relies on
the generated and collected data from other sensors. In recent research,
concepts of Digital Artificial Intelligence and Physicial Artifical
Intelligence have emerged and this can be considered a big step in the
theoretical development of Artifical Intelligence. In this paper we explore
the concept of Physicial Artifical Intelligence and propose two subdomains:
Integrated Physicial Artifical Intelligence and Distributed Physicial
Artifical Intelligence. The paper will also examine the trend and governance
of Physicial Artifical Intelligence.

###### Index Terms:

Physical Artificial Intelligence, PAI, Artificial Intelligence, DIKW, Deep
learning

##  1 Introduction

Artificial Intelligence (AI) has been one of the most popular topics in the
Information and Communication Technologies (ICT) field. AI powered the
development of many advanced systems such as robotics. AI used to be confined
to digital signal processing such as text processing, image object
recognition, and speech recognition. However, when considering computer
science holistically, signal processing is only a small part of the field. The
AI applications have been extended to include robots, Internet of Things
(IoT), smart cities, etc. In [1], Miriyev and Kovac classified AI into Digital
AI which processes signals, and Physical AI including physical robots. In this
paper we explore the concept of Physical AI and extend it to Integrated
Physical AI such as robots or Distributed Physical AI such as IoT. In [1],
authors considered Integrated Physical AI as Physical AI, whose components are
together and in a restricted space. We propose Distributed Physical AI as a
kind of Physical AI too, whose components could be distributed in a wide
space. The aalysis of the Physical AI concepts brings the opportunity to
discuss about AI and Physical AI from a larger perspective. Additionally, it
enables us to explore further the manifestations of Physical AI.

In this paper, we will begin by reviewing the state of the art of Artificial
Intelligence, and conclude with a discussion about the concept of Physical
Artificial Intelligence and how can we leverage the benefits of it across
diffenrent domains. Throughout the paper we will review the trends in Physical
Artificial Intelligence and the potential governence problem implications.
Addtionally, we propose to use Knowledge Graph and Data-Information-Knowledge-
Wisdom (DIKW) to further develop the research on Physical Artificial
Intelligence. The intenrion of this paper is to advance the theoretical
development of Physical Artificial Intelligence.

##  2 Overview of Artificial Intelligence

AI is well known for its outperforming human capabilities in popular
benchmarks such ImageNet [56]. Its various industrial applications, in both
its own domains such as Natural Language Processing (NLP), speech recognition,
face detection, and image classification, or other disciplines such as
agriculture, biology, and chemistry has widely been recognized.

AI originates from the principle of building a Turing machine from neurons, a
concept proposed by McCulloch and Pitts in 1943 [2]. Since 1988 different NN
milestones such as Backpropagation algorithm continued to develop [3]. Lecun
invented Convolutional Neural Network (CNN) with backpropagation in 1998, and
in 2006 the fast training of Neural Network (NN) was addressed. Considering
the above, both NN and even AI, have begun their fast pace development in 2012
[4]. To succeed, AI needs the support of advanced and affordable computing
hardware such as GPU cards, and machine learning algorithms, especially NN.
The relationships between NN, AI, and other related concepts are illustrated
in Figure 1. NN is essential in powering the AI, however, the development of
the AI domain, involves various disciplines such as knowledge modelling, a
highly researched discipline that involves Knowledge Graph to DIKW. With the
increasing and fundamental importance of NN in mind, we will start by
reviewing the history and successful algorithms of NN.

The success of deep learning originates from deep NN, especially CNN applied
to image classification [5]. Primarily, most NN algorithms were of supervised
type, such as CNN and Recurrent NN (RNN). CNN and its variants are involved
with the classification and recognition purpose such as image classifciation
and face recognition. RNN is different from CNN as it considers the temporal
information in the NN, and as such RNN, including its variant Long Short-Term
Memory (LSTM), has become popular in speech recognition and language
translation uses. The semi-supervised learning such as Generative Adversarial
Networks (GAN) is often used in image generation, image enhancement, and video
game [6].

Figure 1: Disciplines and techniques associated with AI AI architecture

Deep learning algorithms could be classified into supervised, semi-supervised,
unsupervised, and reinforcement learning based on supervision level during the
model training period [7]. At first, the deep learning most supervised
algorithms have been extensively used in face recognition, text sentiment
classification, speech recognition, and other similar cases. When the training
data is not entirely labelled, variants of supervised deep learning algorithms
such as semi-supervised learning algorithms could be used. The unsupervised
learning on the other hand, does not rely on training data labelling but it
learns from the internal relations caused by the initial defined features,
such as Auto-Encoders(AE), GAN, and Restricted Boltzmann Machines (RBM). In
reinforcement learning, the algorithms can only obtain the incremental data
instead of all pre-existing data in each processing step.

Apart from computer science applications, AI has been used in academia and
various industries. For example, it has been used to faciliate the prediction
of the process of catalysis utilization [8]. Other uses involved the financial
market, where AI has been used in the dynamic pricing and fraud detection [9].
In the energy domain, AI is used to reduce the electricity [10] and solar
modelling [11]. In the agriculture AI has been used in the detection of fruit
ripening [12].

Although AI has proved to be useful in various domains of research and
industries, AI has also encountered a few limitations. Most of the current AI
applications are limited to the individual applications. One example is that
CNN is useful in image classifiation and text classification, while RNN is
useful in machine translation and speech recognition. AI still encounters
challenges in mananging trivial details and annoying business rules, and some
of these problems have been the focus of researchers [13]. Almost all AI
algorithms need to understand binary codes or numbers, they lack of high
logical inference and problem solving capabilities that humans have, and this
is mainly because not every real problem can be converted into pure mathematic
problems. For example, AI finds it is hard to understand the sentence
differences between the ”Macbook can be used as the chopping board” and
“Macbook is a computer” in the architecutre concept of DIKW [14]. In addition,
AI mostly worked until now like a black, and while researchers know AI works
well, they are not clear about the reasons behind its success for any specific
problems. Therefore, Explainable Artificial Intelligence (XAI) [15] has been a
research domain that is focused on discovering the reasons behind the success
of some specific NN algorithms.

##  3 The concept expansion of Physical Artificial Intelligence

Currently the concept of Artificial Intelligence, as described in the above
section, is related to processing the data and signals in the computer system.
Even the hardware that is related to the AI only captures the input data and
deliver the output data from the AI system, as illustrated in Figure 2. One
example is the Smart Home [16] supported by Amazon’s Alexa speech assistant
[17]. In [1], Miriyev and Kovac proposed the concept of Digital Artificial
Intelligence (DIAI) that refers to the current popular data-based and date-
processing AI.

Figure 2: The hardware architecture related to AI

Contrary to Digital AI, Miriyev and Kovac [1] have proposed the concept of
Physical Artificial Intelligence (PAI), which refers to the nature-like robots
that are driven by the intelligence. Miriyev and Kovac used the bee robot to
explain the concept of PAI, a multi-discipline that combines autonomous
robots, materials, structures, and perceptions. PAI requires the balance
between software - the intelligent system, and hardware - material, mechanics,
and etc. As illustrated in Figure 3, PAI bears its roots in the materials
science, mechanical engineering, computer science, chemistry and biology.

Figure 3: Multidisciplinary nature of PAI

In the proposed concept of PAI by Miriyev and Mirko [1][54], PAI refers to the
typical robot and robot system. In this paper we propose to extend the concept
of PAI to all the potential applications identifying the advantages of AI for
both the hardware and software. Several examples are used to explain the
extended concept of PAI:

  * •

PAI in IoT. IoT is the typical mixed application of the cloud, sensor,
software and data analytics [18]. The robot concatenates the hardware and
software in one complete intelligent machine, while IoT can be distributed to
either a small space such as a room or to a wide area such as the city. Since
AI can be used to improve the stability of each node of the IoT such as a
sensor or the central data analytics and predication, IoT is a fertile
application domain for PAI. The node of IoT used for sensing and controlling
needs the support of the science and technologies, materials, chemistry,
mechanism, and computer science, even the biology.

  * •

PAI in automobile. The self-driving car can be considered as a variant of the
intelligent robot system. The self-driving car has the same necessary features
as the normal robot: the sensor, the embedded computing module, the mechanical
system, the new material and so on. The self-driving car is often connected to
the Internet for navigation and the latter provides the IoT feature to the
self-driving car.

  * •

PAI in agriculture. The agriculture is one of the most successful applications
of Physical Artificial Intelligence. The sensors including the cameras,
temperature meter and hygrometer are used to monitor the growth progress of
the plants and predict the best harvest time. The defects are often detected
to alarm the potential risk for a intervention.

  * •

PAI in healthcare. The healthcare, especially the healthcare for the
prevention, is a typical usage of Physical Artificial Intelligence. The
biological sensors and the chemical sensors are used to monitor the old man
and the patient to predict the potential risks such as falling or an unstable
situation; the centrual center is notified by the edge device when the risk
happens. The computing happends both at the edge sides and the centrual
servers.

  * •

PAI in Logistics. PAI has been extensively used in multiple aspects of the
logistics. The ”last mile” is the expensive and hard problem of the logistic
industry at involves parcel and food delivery. Some delivery robots and drones
[19] have been used in the delivery market to replace the humans. The
automatic sorting robot has been used in the sorting center of the logistics
[20].

In the above survey, the extended concept of PAI has been extensively used in
multiple industries outside the robot industry. The concept of PAI is based on
the interdiscipline research of five disciplines proposed in Figure 3 [1].

##  4 The Trend of Physical Artificial Intelligence

Until 2012 Digital Artificial Intelligence (DIAI) mimicked the brain
capability of logical thinking and induction in human brain, to process the
data and signals percepted by human eyes and ears. As far as we know, the
capabilities of human beings are not limited to the logical thinking of the
brain. The brain of the human beings is only responsible for processing the
signals and transmitting commands to other parts of the body, that are
responsible for many functions, such as movement, vision perception, sound
perception, digestion and etc. Therefore, DIAI just uncovers a limited part of
the powerful potentials of AI, while PAI like a whole human body with respect
to the whole human body, would heavily extend the application of AI from the
academics to the industries.

PAI has the potential to use deep learning to mimick not only the individual
human but also the human society as a whole. Robots are a typical example of
Integrated PAI (IPAI) that mimick the individual humans, and integrates the
perception of the physical world through multiple sensors that collect signals
and data, the induction from multiple indices, and the physical response in
the physical world as shown in Fig. 4, that illustrates the most important
modules in IPAI. A robot’s perception, computing, and mechanical modules are
confined into a limited space, while similar to the human society Distributed
PAI (DPAI) distributes the perception, the computing and the response modules
across a wide space, such as a factory or a city, as shown in Fig. 5.
Industrial IoT system is a good illustration of DPAI [22].

Figure 4: Integrated PAI Figure 5: Distributed PAI

PAI needs to fuse multiple streams of information including materials,
temperature, vision, sound,etc. from multiple sensors as per Fig. 3.
Therefore, multimodal processing is mandatory to understand the information in
PAI. Through the fuse of the multimodal information, PAI can easier use more
kinds of information to make better decision and better precisions [34, 35].
The data and information sources bring multiple kinds of data, which
outperform a single source of data, to make real-time decisions and
predictions. This is a significant feature of PAI.

We use Fig. 6 to illustrate the components and relations of PAI:IPAI and DPAI.
IPAI will be researched and applied in both home environment and industry
environment. The home environment [23] will receive home service robots like
household robots, while the industry environment will be extensively used in
multiple areas of the Industry 4.0 [24] from the automative to the security.
DPAI will become more and more popular when the edge computing [25] is mature
and every device is connected to the network. IoT and edge computing are
typical DPAI subdomains. Since it is popular for every intelligent system to
be online, IPAI and DPAI will have more overlapped areas as shown in Fig. 6.

Figure 6: IPAI and DPAI

##  5 The DIKW Supported Physical Artificial Intelligence

Artificial Intelligence needs a large volume of data as the ”fuel” to train
the model for the tasks of the classifications and the predictions. Digital
Artificial Intelligence such as image classification and automatic speech
recognition is typically the approach of processing the signal and data from
the sources of the image, the sound, the text and the temporal data. In order
to organize the data used in Digital Artificial Intellgence well, the
researchers and industry use the Knowledge Graph [26] to store the ontology
from different data. Knowledge graph is a complete and correct approach to
associate the semantic data. Kowledge Graph considers all the data inside as
the same hierarchical layer, but it does not work very well in the real world.
For example, the sentence ”the spoiled food can not be eaten” represents one
knowledge or a rule, not only the data indicating ”food”. So DIKW[14]
architecture is proposed to construct the information architecture. The DIKW
architecture is illustrated in Figure 7. In DIKW architecture, the $data$ and
$information$ could be used to infer the $knowledge$, while the $wisdom$ as
partial $knowledge$ needs the support from the $data$ and $information$. One
important feature of DIKW architecture is the presentation the 5 Ws:
$Who,What,When,Where$, and $Why$. $Knowledge$ can well describe $What$
happens. $Wisdom$ in DIKW represents $how$. $Data$ is related to $Who$,
$When$, and $Where$. And $What$ and $How$ can be infered from $Information$
and $Knowledge$ too.

Figure 7: DIKW architecture

Digital Artificial Intelligence originates from data and signal processing,
especially the text, image and acoustic processing. In the DIKW architecture,
most algorithms of above categories belong to the $Data$ layer. For example,
the image object recognition [27] is to use large volume of object image data
to train a model and then recognize an object name in testing images. While,
automatic speech recognition is to convert the speech in the sound to the data
of the text. In the research, the knowledge extraction in Digital Artificial
Intelligence exists but is not as popular as the data extraction. In the
article [28] the authors use the multimodal data processing to extract the
knowledge of the image or video, like ”One bird flies in the sky”. According
to the best of our knowledge, it is rare to find extensive deep learning model
to deal with more advanced knowledge processing. Therefore, Physical
Artificial Intelligence encounters challenging problems as it needs to process
the data, information and knowledge and it is not limited to signals as
Digital Artificial Intelligence is. PAI needs to accept and process the signal
and data from at least five categories: materials, mechanics, chemistry,
bilogy, and computer sensors. In order to deal with more categories of signal
and data, PAI has to use knowledge graph to support the processing and
storage, as illustrated in Figure 8.

Figure 8: Knowledge graph supported PAI

As shown in Figure 8, each node of knowledge graph will contain 5 categories
of data from PAI. All data nodes of the same category are internally and
organically associated to one another. Knowledge graph could handle the
complexity of multiple-indices data. So in Figure 9 we propose to integrate 5
categoris of data with 5 $W$s and 4 layers of DIKW. Thus the semantic
information of PAI could be inferred and stored in DIKW architecture while
keep its original relations to the metadata and other basic data.

##  6 Physical Artificial Intelligence Governance and Sustainable Development

Digitial Artificial Intellgience has been facing the challenges of risk and
governance problems [55]. Among the challenges for DIAI, the most important
challenges will be discussed in this section:

  * •

The security of DIAI [29]. The training and prediction of AI model needs large
volume of data, so the security of the data storage is important. The storage
security will need both hardware and software protection. The data masking
[30] is often used to separate the data with the original source in the
software and algorithm level protection.

  * •

The fake data of DIAI. Deepfake [31] attracted much attention when it appeared
on the Internet. Deepfake could convert the human face in the video to the
desired face, and in many situations the coverted video looks real. The fake
image and video cause the doubt of ”seeing is believing”, which could lead to
the social and legal problem.

  * •

The social privacy of DIAI. The face recognition in the public space has been
banned and identified as illegal in many countries [32]. DIAI has enabled the
tracking of our behavior as easy as possible. In addition, DIAI could easily
track the online data including the social media and infer the profiles of a
person. Therefore, the social privacy has been a big focus in the past years.

  * •

The bias in DIAI. In our society the bias exists even if it is hidden, for
example the data from the Internet. Most of training data of DIAI is from web
source, which means that the training model of DIAI naturally contains the
property of bias. This bias has been found in the hiring screening AI system
[33].

Physical Artificial Intelligence (PAI) has more problems to resolve because of
its characteristics of complexity and ubiquitousness compared to DIAI:

  * •

The existence problem. PAI like IoT needs more extensive installation of
multiple kinds of sensors. If it is in a limited space like a factory, it does
not have much regulation problem. However, if the space is extended to a
larger space which is not under the same regulation, PAI will face more
problems of regulation and social problem.

  * •

The information organization problem. As discussed in the previous section,
the organization of multiple kinds and multiple layers of data and information
will cause the problem of complexity. The proposed Knowledge graph and DIKW
supported PAI could be the potential solution.

  * •

Cannikin Law. The development of PAI depends on at least 5 disciplines of
materials science, mechanical engineering, chemistry, biology and computer
science. Therefore, the slower development of one discipline will cause the
problem of cannikin law and prohibit the development of PAI.

  * •

The social acceptance. Similar to the dilemma of DIAI, the ubiquitous
application of PAI will cause the worry of the society regarding to the
unemployment, the privacy and etc.

We illustrates above problem of PAI in Figure 9.

Figure 9: PAI governence problems

As the future format of Artificial Intelligence, Physical Artificial
Intelligence will be the next popular research topic following the Digital
Artificial Intelligence, because Artificial Intelligence will be more and more
applied in other industries. Physical Artificial Intelligence will support the
development of the mechanics or the agriculture because of their hardware
characteristics. Physical Artificial Intelligence will advance AI application
as a fundamental technology for the world.

##  7 Conclusion

In this paper we have started by reviewing the basic knowledge of artificial
intelligence, including its history, categories and popular algorithms. Then
we reviewed the concept of Physical Artifical Intelligence proposed by Aslan
Miriyev and Mirko Kovac, and discussed the reason of extending the concept of
Physical Aritificial Intelligence by Integrated Physical Artificial
Intelligence and Distributed Physical Artificial Intelligence. After that, we
proposed to use DIKW and knowledge graph to extend the concept of Physical
Artificial Intelligence. Finally we discussed the governance of Physical
Artificial Intelligence and its sustainable development, compared to the
current popular topics of Digital Artificial Intelligence governance. We wish
to use this paper to discuss the potential development of Physical Artificial
Intelligence as the next generation of Artificial Intelligence, and inspire
more research and application of Physcial Artifical Intelligence with the
discussed theoretical support.

## Acknowledgments

Supported by Natural Science Foundation of China Project (No. 61662021 and
No.72062015).

## References

  * [1] Miriyev A, Kovač M. Skills for physical artificial intelligence[J]. Nature Machine Intelligence, 2020, 2(11): 658-660.
  * [2] Zhang L, Zhang B. A geometrical representation of McCulloch-Pitts neural model and its applications[J]. IEEE Transactions on Neural Networks, 1999, 10(4): 925-929.
  * [3] Hecht-Nielsen R. Theory of the backpropagation neural network. Neural networks for perception. Academic Press, 1992: 65-93.
  * [4] Yadav N, Yadav A, Kumar M. History of neural networks[M]//An Introduction to Neural Network Methods for Differential Equations. Springer, Dordrecht, 2015: 13-15.
  * [5] Alom M Z, Taha T M, Yakopcic C, et al. The history began from alexnet: A comprehensive survey on deep learning approaches[J]. arXiv preprint arXiv:1803.01164, 2018.
  * [6] Creswell A, White T, Dumoulin V, et al. Generative adversarial networks: An overview[J]. IEEE Signal Processing Magazine, 2018, 35(1): 53-65.
  * [7] Dey A. Machine learning algorithms: a review[J]. International Journal of Computer Science and Information Technologies, 2016, 7(3): 1174-1179.
  * [8] Li H, Zhang Z, Liu Z. Application of artificial neural networks for catalysis: a review[J]. Catalysts, 2017, 7(10): 306.
  * [9] Ryman-Tubb N F, Krause P, Garn W. How Artificial Intelligence and machine learning research impacts payment card fraud detection: A survey and industry benchmark[J]. Engineering Applications of Artificial Intelligence, 2018, 76: 130-157.
  * [10] Cheng L, Yu T. A new generation of AI: A review and perspective on machine learning technologies applied to smart energy and electric power systems[J]. International Journal of Energy Research, 2019, 43(6): 1928-1973.
  * [11] Belu R. Artificial intelligence techniques for solar energy and photovoltaic applications[M]//Robotics: Concepts, methodologies, tools, and applications. IGI Global, 2014: 1662-1720.
  * [12] May Z, Amaran M H. Automated oil palm fruit grading system using artificial intelligence[J]. Int. J. Eng. Sci, 2011, 11(21): 30-35.
  * [13] Xu Y, Shieh C H, van Esch P, et al. AI customer service: Task complexity, problem-solving ability, and usage intention[J]. Australasian Marketing Journal (AMJ), 2020, 28(4): 189-199.
  * [14] Frické M. The knowledge pyramid: the DIKW hierarchy[J]. KO KNOWLEDGE ORGANIZATION, 2019, 46(1): 33-46.
  * [15] Arrieta A B, Díaz-Rodríguez N, Del Ser J, et al. Explainable Artificial Intelligence (XAI): Concepts, taxonomies, opportunities and challenges toward responsible AI[J]. Information Fusion, 2020, 58: 82-115.
  * [16] Marikyan D, Papagiannidis S, Alamanos E. A systematic review of the smart home literature: A user perspective[J]. Technological Forecasting and Social Change, 2019, 138: 139-154.
  * [17] Karppi T, Granata Y. Non-artificial non-intelligence: Amazon’s Alexa and the frictions of AI[J]. AI & SOCIETY, 2019, 34(4): 867-876.
  * [18] Srinivasan C R, Rajesh B, Saikalyan P, et al. A review on the different types of Internet of Things (IoT)[J]. Journal of Advanced Research in Dynamical and Control Systems, 2019, 11(1): 154-158.
  * [19] Janebäck E, Kristiansson M. Friendly robot delivery: Designing an autonomous delivery droid for collaborative consumption[D]. , 2019.
  * [20] Dekhne A, Hastings G, Murnane J, et al. Automation in logistics: Big opportunity, bigger uncertainty[J]. McKinsey Q, 2019: 1-12.
  * [21] Marechal C, Mikolajewski D, Tyburek K, et al. Survey on AI-Based Multimodal Methods for Emotion Detection[J]. 2019.
  * [22] Cheng J, Chen W, Tao F, et al. Industrial IoT in 5G environment towards smart manufacturing[J]. Journal of Industrial Information Integration, 2018, 10: 10-19.
  * [23] Wilson G, Pereyda C, Raghunath N, et al. Robot-enabled support of daily activities in smart home environments[J]. Cognitive Systems Research, 2019, 54: 258-272.
  * [24] Dalenogare L S, Benitez G B, Ayala N F, et al. The expected contribution of Industry 4.0 technologies for industrial performance[J]. International Journal of Production Economics, 2018, 204: 383-394.
  * [25] Yu W, Liang F, He X, et al. A survey on the edge computing for the Internet of Things[J]. IEEE access, 2017, 6: 6900-6919.
  * [26] Wang Q, Mao Z, Wang B, et al. Knowledge graph embedding: A survey of approaches and applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(12): 2724-2743.
  * [27] Sukanya C M, Gokul R, Paul V. A survey on object recognition methods[J]. International Journal of Science, Engineering and Computer Technology, 2016, 6(1): 48.
  * [28] He X, Deng L. Deep learning for image-to-text generation: A technical overview[J]. IEEE Signal Processing Magazine, 2017, 34(6): 109-116.
  * [29] Gil L, Liska A. Security with AI and Machine Learning[M]. O’Reilly Media, Incorporated, 2019.
  * [30] Asenjo J C. Data masking, encryption, and their effect on classification performance: trade-offs between data security and utility[J]. 2017.
  * [31] Güera D, Delp E J. Deepfake video detection using recurrent neural networks[C]//2018 15th IEEE International Conference on Advanced Video and Signal Based Surveillance (AVSS). IEEE, 2018: 1-6.
  * [32] Deb D, Wiper S, Gong S, et al. Face recognition: Primates in the wild[C]//2018 IEEE 9th International Conference on Biometrics Theory, Applications and Systems (BTAS). IEEE, 2018: 1-10.
  * [33] Dattner B, Chamorro-Premuzic T, Buchband R, et al. The legal and ethical implications of using AI in hiring[J]. Harvard Business Review, 2019, 25.
  * [34] Meyer T, Schmitt M, Dietzek B, et al. Accumulating advantages, reducing limitations: Multimodal nonlinear imaging in biomedical sciences–the synergy of multiple contrast mechanisms[J]. Journal of biophotonics, 2013, 6(11‐12): 887-904.
  * [35] Deng L. Deep learning: from speech recognition to language and multimodal processing[J]. APSIPA Transactions on Signal and Information Processing, 2016, 5.
  * [36] Gadepally V, Goodwin J, Kepner J, et al. Ai enabling technologies: A survey[J]. arXiv preprint arXiv:1905.03592, 2019.
  * [37] Cully, A., Clune, J., Tarapore, D. & Mouret, J.-B. Nature 521, 503–507 (2015).
  * [38] Bilodeau, R. A. & Kramer, R. K. Front. Robot. AI 4, 48 (2017).
  * [39] Petersen, K. H., Napp, N., Stuart-Smith, R., Rus, D. & Kovac, M. Sci. Robot. 4, eaau8479 (2019).
  * [40] Xia, B. et al. Actuators 9, 62 (2020).
  * [41] 5\. Pena-Francesch, A., Jung, H., Demirel, M. C. & Sitti, M. Nat. Mater. 19, 1230–1235 (2020).
  * [42] Sadeghi, A., Mondini, A. & Mazzolai, B. Soft Robot. 4, 211–223 (2017).
  * [43] Man, K. & Damasio, A. Nat. Mach. Intell. 1, 446–452 (2019).
  * [44] Sol, J. A. H. P. et al. Chem. Commun. 55, 1726–1729 (2019).
  * [45] Pfeifer, R., Bongard, J. & Grand, S. How the Body Shapes the Way We Think: A New View of Intelligence (MIT Press, 2007).
  * [46] Mengüç, Y., Correll, N., Kramer, R. & Paik, J. Sci. Robot. 2, eaar4527 (2017).
  * [47] Lipson, H. & Pollack, J. B. Nature 406, 974–978 (2000).
  * [48] Yang, G.-Z. et al. Sci. Robot. 3, eaar7650 (2018).
  * [49] Kovac, M. Science 352, 895–896 (2016).
  * [50] Hauser, H. Nat. Mach. Intell. 1, 338–339 (2019).
  * [51] Howard, D. et al. Nat. Mach. Intell. 1, 12–19 (2019).
  * [52] Chrisley, R. & Ziemke, T. In Encyclopedia of Cognitive Science (Wiley, 2006).
  * [53] Miriyev, A., Stack, K. & Lipson, H. Nat. Commun. 8, 596 (2017).
  * [54] João Paulo Costeira and Pedro Lima (editors), “A simple guide to Physical AI”. Published on the AI4EU platform: http://ai4eu.eu. June 24, 2020.
  * [55] Dafoe, A. (2018). AI governance: a research agenda. Governance of AI Program, Future of Humanity Institute, University of Oxford: Oxford, UK.
  * [56] Deng J, Dong W, Socher R, et al. Imagenet: A large-scale hierarchical image database[C]//2009 IEEE conference on computer vision and pattern recognition. Ieee, 2009: 248-255.


# vi-mistral-x

James Vo
AI Algorithm Research Team
AgileSoDA Inc.
Seoul, South Korea
<EMAIL_ADDRESS>
http://agilesoda.ai

###### Abstract

The advancement of Large Language Models (LLMs) has significantly transformed
the field of natural language processing, although the focus on English-
centric models has created a noticeable research gap for specific languages,
including Vietnamese. To address this issue, this paper presents vi-mistral-x,
an innovative Large Language Model designed expressly for the Vietnamese
language. It utilizes a unique method of continual pre-training, based on the
Mistral architecture, which incorporates grouped-query attention and sliding
window attention techniques. This model, vi-Mistral-X, marks a significant
step forward in improving the understanding and generation of the Vietnamese
language. It introduces an additional phase of continual pre-training,
specifically adapted for Vietnamese, enhancing the model’s capability in
understanding complex language nuances and generating accurate, context-aware
Vietnamese text. Through comprehensive testing on various benchmarks, vi-
mistral-x has shown to outperform existing Vietnamese LLMs in several key
areas, including text classification, question answering, and text generation.
Particularly, in the Vietnamese Multitask Language Understanding (VMLU)
benchmark, vi-mistral-x sets a new standard, outperforming other available
models significantly. This paper highlights the critical role of continual
pre-training in advancing language-specific LLMs and opens new avenues for the
development of multilingual models. We aim for vi-mistral-x to not just be an
important asset for processing the Vietnamese language but also to encourage
more advancements in creating large language models for languages that are
less represented.

_Keywords_ Vietnamese $\cdot$ LLM $\cdot$ Pretraining

##  1 Introduction

The field of natural language processing (NLP) has witnessed a paradigm shift
with the advent of Large Language Models (LLMs), which have shown tremendous
potential in understanding and generating human language. LLMs like ChatGPT
and GPT-4 have paved the way for innovations that edge closer to achieving
Artificial General Intelligence (AGI). However, the progress in this domain
has predominantly centered around English, leading to a substantial disparity
in the development and performance of LLMs for other languages. This disparity
not only limits the global applicability of such models but also underscores a
crucial gap in the research and development of language models that cater to
the diverse linguistic landscape of our world.

In particular, the Vietnamese language, with its unique syntactic and semantic
complexities, has not been adequately represented in the current wave of LLM
advancements. This oversight hinders the ability of Vietnamese NLP
applications to achieve the same level of sophistication and effectiveness as
their English counterparts, thereby creating a significant bottleneck in the
development of Vietnamese language technology.

To bridge this gap, our paper introduces vi-mistral-x, an LLM specifically
designed to address the challenges associated with processing and generating
the Vietnamese language. Building on the foundation laid by the innovative
Mistral architecture, vi-mistral-x incorporates advanced techniques such as
grouped-query attention (GQA) and sliding window attention (SWA) Jiang et al.
(2023). These features are part of a unique approach to continual pre-training
that is tailored to the Vietnamese language, enabling the model to capture its
linguistic nuances more accurately.

The development of vi-mistral-x is inspired by recent efforts in the field to
extend the capabilities of existing models to additional languages. This
includes the adaptation of LLaMA for the Chinese language Cui et al.  and the
Korean language L. Junbum (2023). By employing a similar methodology of
extending vocabulary and incorporating language-specific pre-training and
fine-tuning phases, we aim to achieve a leap in the quality of text
understanding and generation in Vietnamese. This approach is underscored by
the success of the Mistral 7B model, which has demonstrated the effectiveness
of GQA and SWA in improving performance and efficiency across various NLP
tasks.

Our work on vi-mistral-x represents a critical step toward closing the
research gap for the Vietnamese language within the NLP community. By
detailing our approach and sharing our findings, we hope to not only enhance
the capabilities of language models for Vietnamese but also to encourage
further research and development efforts focused on other underrepresented
languages. This endeavor aligns with our broader goal of promoting inclusivity
and diversity in the advancement of natural language processing technologies,
ensuring that the benefits of these innovations are accessible to a wider
audience around the globe.

##  2 Proposed Method

This section details the methodology employed in developing vi-Mistral-X,
focusing on the adaptation of the Mistral architecture for the Vietnamese
language. The process encompasses five main stages: corpus preparation,
tokenizer training, model initialization, model training, and model alignment.

###  2.1 Effective Corpus Preparation

The stage involves refining a Vietnamese text corpus extracted from CulturaX,
a comprehensive multilingual dataset designed to support the development of
Large Language Models (LLMs) across 167 languages, including Vietnamese Nguyen
et al. (2023a). The primary goal was to reduce the original corpus to a more
manageable size while enhancing its quality, which is critical for the
effective training of language models. We employed a multi-step preprocessing
pipeline with the following components:

##### Random Selection

As an initial step, we used a random selection technique to significantly
reduce the corpus’s size. This method allowed us to manage computational
resources better by focusing on a smaller, yet representative, subset of the
original dataset.

##### N-gram-based Filtering for Deduplication

We applied an n-gram-based filtering method to ensure the dataset’s
uniqueness. This technique analyzes the frequency of contiguous sequences of
n-gram in the text to identify and remove duplicate or nearly identical
content. Such deduplication is crucial to reduce the risk of overfitting the
model on repetitive data.

##### BERT-based Binary Classifier for Toxicity Filtering

To further enhance the corpus quality, we used a high-precision BERT-based
binary classifier to filter out toxic content. Deploying this classifier
helped exclude data that could propagate undesirable biases or harmful
expressions within the trained model.

##### Perplexity-based Filtering

The final preprocessing step was perplexity-based filtering. Perplexity, a
measure of a probability model’s predictive accuracy, was used to assess and
filter documents based on their coherence and quality. This criterion is vital
for developing language models, as it ensures that only high-quality and
coherent documents contribute to the training process.

This comprehensive preprocessing pipeline was designed to enhance the quality
of the Vietnamese corpus from CulturaX. Table 1 presents a detailed comparison
between the original CulturaX corpus and the refined corpus used for training
the vi-mistral-x model. Although a formal evaluation employing quantitative
measures to ascertain the processed data’s specific impact on model training
compared to the original data has not yet been conducted, there is reason to
believe that selecting and refining data to improve the consistency and
quality of each data sample can lead to enhanced computational efficiency.
Specifically, reducing the size of the data by removing noisy and non-uniform
samples can decrease computing costs due to lower resource requirements and
may also improve the training quality of the model by concentrating on high-
quality data, thereby optimizing the learning process.

| CulturaX/vi | Selected corpus
---|---|---
No. of documents | 54,988,654 | 7,331,840
Size in GB (parquet) | 150.91 | 20.656
No. of tokens | NA | 8,323,137,536
Table 1: Detailed comparison of the original CulturaX/vi and the refined
corpus for vi-mistral-x model training

###  2.2 Effective Tokenizer Training

The second phase in the adaptation of the pretrained Mistral model for
Vietnamese language processing involves the development of a tokenizer capable
of efficiently handling Vietnamese text. Initially, we utilized Google
SentencePiece111https://github.com/google/sentencepiece to train a new
SentencePiece model (SPM). Subsequently, we performed rule-based token
filtering on the trained SPM, with a focus on Vietnamese character
recognition. The enhanced SPM was then integrated with the original Mistral’s
SPM model. This hybrid tokenizer maintains the ability to process English and
other languages previously supported by Mistral-7B, while also effectively
managing Vietnamese text. This capability is pivotal for facilitating
bilingual or multilingual continual training in the future.

##### SPM Model Training

The new SPM model was developed by employing Google SentencePiece to train a
new model on our refined corpus, which was obtained in the initial stages. The
corpus was significantly reduced to a manageable size (20GB) without
necessitating extra sampling, limiting maximum sentence length, or filtering
character coverage. The vocabulary size was determined by balancing the trade-
off between input complexity and model complexity. A larger vocabulary tends
to decrease the number of tokens passed to the model, thereby reducing input
complexity, but it increases model complexity due to the expansion of the
embedding and language model head dimensions. As illustrated in Figure 1, a
vocabulary size of 8,096 is optimal for our dataset and the Mistral model,
based on our observations.

##### SPM Model Refining

This phase involved the removal of abnormal characters from the trained SPM
model to achieve a high-quality and coherent tokenizer. The refinement rules
were established based on manual definitions and prioritized tokens with the
highest frequency.

##### Model Combination

The refined SPM was integrated with the original Mistral’s SPM model to create
the final tokenizer. This integration process involved several rounds of
tokenizer training and analysis, ensuring the new tokenizer model includes a
comprehensive and relevant vocabulary for our project.

This meticulous approach to tokenizer training and refinement underscores the
importance of adapting language processing tools to efficiently manage
specific linguistic characteristics, thereby enhancing bilingual or
multilingual training capabilities.

Figure 1: Visualization of the Mistral SPM model and customized Vietnamese SPM Vocab Size | Relative Input Complexity | Relative Model Embedding Complexity
---|---|---
1000 | 0.841395049 | 1.01640625
2000 | 0.630757254 | 1.04403125
3000 | 0.584167181 | 1.073125
4000 | 0.557951001 | 1.1025
5000 | 0.539983642 | 1.13171875
6000 | 0.526697283 | 1.16078125
7000 | 0.516199365 | 1.18978125
8000 | 0.50747301 | 1.21909375
9000 | 0.500297369 | 1.2479375
10000 | 0.494061494 | 1.27684375
11000 | 0.488440053 | 1.30575
12000 | 0.483667799 | 1.33428125
13000 | 0.479315439 | 1.36334375
14000 | 0.475368937 | 1.39240625
15000 | 0.471816595 | 1.42109375
16000 | 0.468521178 | 1.4500625
17000 | 0.465535533 | 1.4789375
18000 | 0.462752376 | 1.50753125
19000 | 0.460176296 | 1.5363125
20000 | 0.45770208 | 1.5655625
30000 | 0.439826305 | 1.85509375
40000 | 0.422321581 | 2.14471875
80000 | 0.403156539 | 3.31371875
120000 | 0.395356195 | 4.49840625
Table 2: Input Complexity and Model Embedding Complexity by Vocab Size Figure
2: Relative Input Complexity and Relative Model Embedding Complexity by Vocab
Size.

###  2.3 Effective Model Initialization

For model initialization, we adapted the Mistral architecture to accommodate
the newly-generated Vietnamese token embeddings produced by the novel
tokenizer. This adaptation necessitated the expansion of both the model’s
embedding layer and language model head to include the Vietnamese-specific
tokens, whilst preserving the integrity of the original model’s architecture.
Figure 2 illustrates the architectural comparison between the original Mistral
framework and our modified version tailored to accommodate Vietnamese-specific
tokens.

Figure 3: Model Architecture of the Mistral Model and Our Expanded Model

##### Initilization

Let $V=\\{1,\ldots,n\\}$ be the model’s vocabulary, where $n=32000$. Let
$w_{1:T}$ be a sequence of words. Let $p_{\theta}(w_{i}|w_{1:i-1})$ be the LM
parameterized by $\theta$, defined by:

$P(\boldsymbol{w}_{i}|\boldsymbol{w}_{i-n+1:i-1})=\frac{\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{w_{i}})}{\sum_{j=1}^{m}\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{j})}$

where $\boldsymbol{h}_{i-1}=\phi_{\theta}(w_{1:i-1})\in\mathbb{R}^{d}$ is the
representation of the prefix, and $\boldsymbol{e}_{i}\in\mathbb{R}^{d}$ is the
embedding for word $i\in V$. The $\boldsymbol{e}_{i}$ are contained in
$\theta$.

When a new word, $\text{input\\_ids}\in[32000,38658]$, $n+1\notin V$ is added
to the vocab of the pretrained LM, the new word $n+1\notin V$’s embedding
needs to be initialized as $\boldsymbol{e}_{n+1}$. Let
$p_{\theta^{\prime}}(w_{i}|w_{1:i-1})$ be the new LM, which has parameters
$\theta^{\prime}=\theta\cup\\{\boldsymbol{e}_{n+1}\\}$, defined by:

$p_{\theta^{\prime}}(w_{i}|w_{1:i-1})=\frac{\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{w_{i}})}{\sum_{j=1}^{m}\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{j})+\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{n+1})}$

$p_{\theta}(w_{i}|w_{1:i-1})=p_{\theta}(w_{i}|w_{1:i-1})\times\frac{1}{1+\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{n+1})/\sum_{j=1}^{m}\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{j})}$

The updated probability of a particular word is the original probability of
that word scaled by a multiplicative element that is less than one, denoted as
$\frac{1}{1+\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{n+1})/\sum_{j=1}^{m}\exp(\boldsymbol{h}_{i-1}^{T}\boldsymbol{e}_{j})}$.
This leads the model to incorrectly assign a probability of 1 to newly added
words and 0 to the original words.

Therefore, the new embedding is adjusted as follows:

$\exp(\boldsymbol{h}_{i}^{T}\boldsymbol{e}_{n+1})=\exp\left(\boldsymbol{h}_{i}^{T}\frac{1}{n}\sum_{j=1}^{n}\boldsymbol{e}_{j}\right)$

Finally, the model’s embedding and language model (LM) head are resized to
$V^{\prime}\times H$ and $H\times V^{\prime}$, respectively, where
$V^{\prime}=38659$.

###  2.4 Effective Model training

##### Memory and Computational Efficiency in Training

The core of vi-mistral-x’s development involved continual pre-training on a
Vietnamese corpus. In this stage, our research is driven by the need to
leverage the most effective resources in computational linguistics and machine
learning. We focus on addressing two main challenges in Large Language Models
(LLMs): memory capacity limitations, which lead to Out Of Memory (OOM) errors,
and the requirement for significant computational power, causing long training
times. Our work seeks to overcome these issues by optimizing the model
architecture and training processes.

In our pursuit, we have concentrated on a curated selection of model
architectures, including Llama2, Mistral, and Gemma. These were chosen based
on their potential for high efficiency and compatibility with our objectives.
Additionally, our strategy encompasses the integration of advanced parallelism
techniques, such as Fully Sharded Data Parallelism (FSDP), DeepSpeed ZeRO-3
(DSZERO3), Pipeline Parallelism (PP), and Tensor Parallelism (TP). These
methods are instrumental in distributing the computational load and memory
usage across multiple devices, thereby alleviating the aforementioned
constraints.

Our optimizations have significantly increased training speed, making our
library about twice as fast as similar open-source options. Specifically, it’s
1.6 times faster than both Dao (2023) and the PyTorch version of Scaled Dot
Product Attention (SDPA) (2024).

Our findings highlight the possibility of greatly improving the efficiency of
training transformer-based models, advancing artificial intelligence research.

##### Optimization

Let $W\notin\mathbb{R}^{m\times n}$ be a weight matrix. Let

$G_{t}=-\nabla_{W}\phi_{t}(W_{t})\in\mathbb{R}^{m\times n}$

be the gradient matrix at step $t$. The updated weight matrix is computed by:

$W_{T}=W_{0}+\eta\sum_{t=0}^{T-1}G_{t}$

where $\eta$ is the learning rate and $\phi_{t}$ is a stateful gradient
regularizer, which is memory-intensive. For instance,
[AdamW](https://pytorch.org/docs/stable/generated/torch.optim.AdamW.html)
takes $4\times m\times n$ memory for gradient, variance, momentum, and
parameters.

To enhance memory and computational efficiency during training, LoRA and its
derivatives, which perform a low-rank projection in the weight space as
$W_{T}=W_{0}+B_{T}A_{T}$, were not selected due to their inherent low-rank
limitations. Our goal is to achieve a full-rank update that is both memory-
and computation-efficient. Therefore, ‘Tokenizer‘, ‘Model‘, ‘Trainer‘, and
‘Optimizer‘ are imported from our XLLM library Vo (2023), which has the same
interface as those in the
[Transformers](https://github.com/huggingface/transformers.git) library.
Techniques such as learning rate warm-up and learning rate scheduling, which
adjust the learning rate appropriately across layers, are also applied to
optimize the training process.

##### Training

The model underwent training on a computational framework consisting of eight
Nvidia H100 80GB SXM5 GPUs. Due to the intentional interruption of the
training process for purposes of advanced evaluation and optimization, an
exact duration of training was not documented. However, a rough estimate
suggests that, under conditions of uninterrupted training, the process would
span approximately 104 hours. Financially, this duration translates to an
approximate expenditure of $3902.08,giventheoperationalcostof$37.52 per hour
per node.

###  2.5 Model alignment

Following the pre-training phase, vi-mistral-x underwent a series of fine-
tuning processes aimed at aligning the model with specific NLP tasks. This
alignment involved training the model on task-specific Vietnamese datasets,
such as text classification, question answering, and text generation. Each
task-focused fine-tuning phase allowed vi-mistral-x to adjust its parameters
to optimize performance on that task, thereby ensuring its applicability and
effectiveness across a wide range of NLP applications. This step was crucial
for benchmarking vi-mistral-x against existing Vietnamese LLMs and
demonstrating its superior performance across several key areas.

Through these methodological steps, vi-mistral-x represents a significant
advancement in the development of LLMs for the Vietnamese language, offering
enhanced understanding and generation capabilities that set a new benchmark
for performance in Vietnamese NLP tasks.

##  3 Experimental Results

###  3.1 Pretrained Model

####  3.1.1 Loss and Accuracy

##### References

  * •

anhdungitvn/vi-mistral-x

  * •

mistralai/Mistral-7B-v0.1 Jiang et al. (2023)

  * •

Viet-Mistral/Vistral-7B-Chat Nguyen et al. (2023b)

  * •

vinai/PhoGPT-7B5 Nguyen et al. (2024)

  * •

bkai-foundation-models/vietnamese-llama2-7b-120GB

  * •

meta-llama/Llama-2-7b-hf Touvron et al. (2023)

  * •

meta-llama/Llama-2-13b-hf Touvron et al. (2023)

  * •

google/gemma-7b Team et al. (2024)

##### Setting

  * •

Task: CLM (next token prediction)

  * •

Test data: anhdungitvn/wiki_vi_splitted

  * •

Test data selection: random train_test_split

  * •

Test data size: 10000 documents

  * •

Metrics:

    * –

Tokens: smaller is better

    * –

Loss: smaller is better

    * –

Accuracy: larger is better

##### Experimental Results

Model | Type | Length | Tokens | Loss |  Accuracy*****
---|---|---|---|---|---
anhdungitvn/vi-mistral-x* | Pretrained | 4096 | 2068480 | 2.1566 | 0.5622
mistralai/Mistral-7B-v0.1 | Pretrained | 4096 | 4517888 | 1.3687 | 0.6813
Viet-Mistral/Vistral-7B-Chat |  Finetuned** | 4096 | 2224128 | 1.7354 | 0.6223
vinai/PhoGPT-7B5 | Pretrained | 2048*** | 1982464 | 16.5563**** | 0.0029
bkai…/vietnamese-llama2-7b-120GB | Pretrained | 4096 | 2191360 | 2.4808 | 0.5207
meta-llama/Llama-2-7b | Pretrained | 4096 | 4632576 | 1.1287 | 0.7295
meta-llama/Llama-2-13b | Pretrained | 4096 | 4632576 | 0.9543 | 0.7700
google/gemma-7b | Pretrained | 4096 | 2232320 | … | …
Table 3: Comparison of Pretrained Models

  * *

The model vi-mistral-x* is currently under development. The shown results were
obtained by evaluating a checkpoint at epoch 0.08.

  * **

The Viet-Mistral/Vistral-7B pretrained model is unpublished, so we evaluated
the Viet-Mistral/Vistral-7B finetuned model.

  * ***

The model vinai/PhoGPT-7B5 doesn’t support an input sequence length of 4096. A
RuntimeError occurs in modeling_mpt.py on line 138: "The size of tensor a
(4096) must match the size of tensor b (2048) at non-singleton dimension 3."

  * ****

The same evaluation method was applied to all models. The results indicate
that the loss for this particular model is unusually high, suggesting that the
evaluation method employed may not be appropriate for this model. Further
investigation is required.

  * *****

Improved accuracy in a Causal Language Model (CLM) for next-token prediction
does not guarantee enhanced performance in other tasks or on different
datasets. Loss and accuracy metrics merely indicate the model’s current
training state and can differ substantially among various models. Therefore,
they cannot be directly compared based solely on loss and accuracy.

####  3.1.2 Vietnamese Multitask Language Understanding (VMLU)

##### References

  * •

VMLU

  * •

anhdungitvn/vmlu_v1.5

##### VMLU

VMLU is a benchmark suite aimed at evaluating foundation models’ capabilities,
focusing on the Vietnamese language. It includes 10,880 multiple-choice
questions across 58 subjects within STEM, Humanities, Social Sciences, and
more, covering difficulty levels from basic to advanced.

##### Dataset: anhdungitvn/vmlu_v1.5

The dataset anhdungitvn/vmlu_v1.5 was originally created from vmlu_v1.5 by
formatting it into the Hugging Face datasets format for easier use.

##### Example

Figure 4: Example of VMLU

##### Experimental Results

# | Model | Creator | Access | EvalDate | STEM | SS | Hum | Others | Avg
---|---|---|---|---|---|---|---|---|---
1 | GPT-4 | OpenAI | API | 08/01/2024 | 63.84 | 71.78 | 66.14 | 60.37 | 65.53
2 | gemini | Google | API | 30/01/2024 | 42.8 | 60.31 | 55.35 | 51.30 | 51.03
3 | ChatGPT | OpenAI | API | 08/01/2024 | 43.24 | 51.67 | 46.96 | 46.32 | 46.33
4 | ViGPT-1.6B-v1 | Vin BigData | Private | 08/01/2024 | 35.06 | 48.72 | 47.20 | 42.54 | 42.34
5 | gemma-7b-it | Google | Weight | 22/02/2024 | 39.95 | 44.93 | 43.39 | 40.11 | 41.9
6 | Qwen-7B | Alibaba Cloud | Weight | 08/01/2024 | 30.64 | 35.07 | 34.15 | 32.68 | 32.81
7 | vi-mistral-x* | James | TBD | 15/03/2024 | 24.88 | 34.08 | 35.11 | 29.26 | 30.32
8 | gemma-2b-it | Google | Weight | 22/02/2024 | 24.39 | 29.59 | 31.01 | 26.81 | 27.72
9 | sealion7b | AI Singapore | Weight | 08/01/2024 | 26.28 | 28.57 | 27.66 | 27.34 | 26.73
10 | bloom-1b7 | BigScience | Weight | 08/01/2024 | 25.13 | 25.09 | 26.34 | 25.19 | 25.51
Table 4: Comparision of Pretrained Models on VMLU

The model “vi-mistral-x*” is currently under development. The shown results
were obtained by evaluating a checkpoint at epoch 0.08.

The comparison is shown in Table 4, and the detailed evaluation of “vi-
mistral-x” is presented in Table 5.

Table 5: Detailed Evaluation of VI-Mistral-X* on VMLU Category_Subcategory | Score
---|---
total | 30.32
stem_applied_informatics | 39.44
stem_computer_architecture | 31.11
stem_computer_network | 34.64
stem_discrete_mathematics | 23.64
stem_electrical_engineering | 22.73
stem_elementary_mathematics | 19.44
stem_elementary_science | 55.00
stem_high_school_biology | 15.00
stem_high_school_chemistry | 22.78
stem_high_school_mathematics | 16.22
stem_high_school_physics | 23.33
stem_introduction_to_chemistry | 14.53
stem_introduction_to_physics | 23.12
stem_introduction_to_programming | 29.05
stem_metrology_engineer | 22.70
stem_middle_school_biology | 31.18
stem_middle_school_chemistry | 18.33
stem_middle_school_mathematics | 17.59
stem_middle_school_physics | 21.67
stem_operating_system | 30.56
stem_statistics_and_probability | 10.34
stem_total | 24.88
other_clinical_pharmacology | 26.11
other_driving_license_certificate | 45.61
other_environmental_engineering | 11.70
other_internal_basic_medicine | 34.50
other_preschool_pedagogy | 34.31
other_tax_accountant | 20.69
other_tax_civil_servant | 41.52
other_total | 29.26
other_accountant | 21.43
other_civil_servant | 27.49
humanity_economic_law | 29.81
humanity_education_law | 33.13
humanity_elementary_history | 49.72
humanity_high_school_history | 31.11
humanity_high_school_literature | 25.56
humanity_history_of_world_civilization | 41.11
humanity_idealogical_and_moral_cultivation | 49.44
humanity_introduction_to_laws | 39.68
humanity_introduction_to_vietnam_culture | 28.33
humanity_logic | 18.97
humanity_middle_school_history | 37.78
humanity_middle_school_literature | 37.36
humanity_revolutionary_policy_of_the_vietnamese_commununist_part | 36.67
humanity_vietnamese_language_and_literature | 17.24
humanity_total | 35.11
humanity_administrative_law | 37.78
humanity_business_law | 39.11
humanity_civil_law | 41.11
humanity_criminal_law | 38.04
social_science_middle_school_geography | 27.21
social_science_principles_of_marxism_and_leninism | 36.67
social_science_sociology | 39.89
social_science_business_administration | 20.69
social_science_high_school_civil_education | 43.89
social_science_high_school_geography | 33.33
social_science_ho_chi_minh_ideology | 41.34
social_science_macroeconomics | 21.67
social_science_microeconomics | 23.89
social_science_middle_school_civil_education | 52.25
social_science_total | 34.08

###  3.2 Finetuned Model

The following session is being updated.

## References

  * Jiang et al. [2023] Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed.  Mistral 7b, 2023.
  * [2] Yiming Cui, Ziqing Yang, and Xin Yao.  Efficient and effective text encoding for chinese llama and alpaca.
  * L. Junbum [2023] L. Junbum.  llama-2-ko-7b (revision 4a9993e), 2023.  URL https://huggingface.co/beomi/llama-2-ko-7b.
  * Nguyen et al. [2023a] Thuat Nguyen, Chien Van Nguyen, Viet Dac Lai, Hieu Man, Nghia Trung Ngo, Franck Dernoncourt, Ryan A. Rossi, and Thien Huu Nguyen.  Culturax: A cleaned, enormous, and multilingual dataset for large language models in 167 languages, 2023a.
  * Dao [2023] Tri Dao.  Flashattention-2: Faster attention with better parallelism and work partitioning, 2023.
  * Vo [2023] James Vo.  Enhancing memory and computational efficiency in training transformer-based models, 2023.
  * Nguyen et al. [2023b] Chien Van Nguyen, Thuat Nguyen, Quan Nguyen, Huy Nguyen, Björn Plüster, Nam Pham, Huu Nguyen, Patrick Schramowski, and Thien Nguyen.  Vistral-7b-chat - towards a state-of-the-art large language model for vietnamese.  2023b.
  * Nguyen et al. [2024] Dat Quoc Nguyen, Linh The Nguyen, Chi Tran, Dung Ngoc Nguyen, Dinh Phung, and Hung Bui.  Phogpt: Generative pre-training for vietnamese, 2024.
  * Touvron et al. [2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurelien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom.  Llama 2: Open foundation and fine-tuned chat models, 2023.
  * Team et al. [2024] Gemma Team, Thomas Mesnard, Cassidy Hardin, Robert Dadashi, Surya Bhupatiraju, Shreya Pathak, Laurent Sifre, Morgane Rivière, Mihir Sanjay Kale, Juliette Love, Pouya Tafti, Léonard Hussenot, Aakanksha Chowdhery, Adam Roberts, Aditya Barua, Alex Botev, Alex Castro-Ros, Ambrose Slone, Amélie Héliou, Andrea Tacchetti, Anna Bulanova, Antonia Paterson, Beth Tsai, Bobak Shahriari, Charline Le Lan, Christopher A. Choquette-Choo, Clément Crepy, Daniel Cer, Daphne Ippolito, David Reid, Elena Buchatskaya, Eric Ni, Eric Noland, Geng Yan, George Tucker, George-Christian Muraru, Grigory Rozhdestvenskiy, Henryk Michalewski, Ian Tenney, Ivan Grishchenko, Jacob Austin, James Keeling, Jane Labanowski, Jean-Baptiste Lespiau, Jeff Stanway, Jenny Brennan, Jeremy Chen, Johan Ferret, Justin Chiu, Justin Mao-Jones, Katherine Lee, Kathy Yu, Katie Millican, Lars Lowe Sjoesund, Lisa Lee, Lucas Dixon, Machel Reid, Maciej Mikuła, Mateo Wirth, Michael Sharman, Nikolai Chinaev, Nithum Thain, Olivier Bachem, Oscar Chang, Oscar Wahltinez, Paige Bailey, Paul Michel, Petko Yotov, Pier Giuseppe Sessa, Rahma Chaabouni, Ramona Comanescu, Reena Jana, Rohan Anil, Ross McIlroy, Ruibo Liu, Ryan Mullins, Samuel L Smith, Sebastian Borgeaud, Sertan Girgin, Sholto Douglas, Shree Pandya, Siamak Shakeri, Soham De, Ted Klimenko, Tom Hennigan, Vlad Feinberg, Wojciech Stokowiec, Yu hui Chen, Zafarali Ahmed, Zhitao Gong, Tris Warkentin, Ludovic Peran, Minh Giang, Clément Farabet, Oriol Vinyals, Jeff Dean, Koray Kavukcuoglu, Demis Hassabis, Zoubin Ghahramani, Douglas Eck, Joelle Barral, Fernando Pereira, Eli Collins, Armand Joulin, Noah Fiedel, Evan Senter, Alek Andreev, and Kathleen Kenealy.  Gemma: Open models based on gemini research and technology, 2024.


On the other hand, $\hat{v}^{i}$ satisfies (6.57)-(6.59) with equalities. By
classical comparison theorem, we deduce that

$\displaystyle\overline{v}_{\kappa}^{i}(t,z)\leq\varphi^{i}(t,z)\leq\hat{v}^{i}(t,z),\,\mbox{
in }[0,T)\times D_{0}.$ (6.60)

Step 2: By definition of $\hat{v}^{i}$ and since against the no intervention
strategy of player $i$, the best response of player $j$ is also not to make an
intervention, we have $\hat{v}^{i}(t,z)\leq v_{\kappa}^{i}(t,z)$ for all
$(t,z)$ in a neighborhood of $[0,T)\times D_{0}$. From Proposition 6.3, the
function $\hat{v}^{i}$ is continuous. It yields that:

$\displaystyle\hat{v}^{i}(t^{{}^{\prime}},z^{{}^{\prime}})\leq\underline{v}_{\kappa}^{i}(t^{{}^{\prime}},z^{{}^{\prime}})\mbox{
for all }(t^{{}^{\prime}},z^{{}^{\prime}})\mbox{ in a neighborhood of
}(t,z)\in[0,T)\times D_{0}.$

Using again the continuity property of $\hat{v}^{i}$ (See Proposition 6.3),
and since $\underline{v}_{\kappa}^{i}$ is lsc, we obtain:

$\displaystyle\hat{v}^{i}(t,z)\leq\displaystyle\liminf_{(t^{{}^{\prime}},z^{{}^{\prime}})\longrightarrow(t,z)}\underline{v}_{\kappa}^{i}(t^{{}^{\prime}},z^{{}^{\prime}})=\underline{v}_{\kappa}^{i}(t,z)\mbox{
for all }(t,z)\in[0,T)\times D_{0}.$ (6.61)

From inequalities (6.60), (6.61) and , we deduce inquality (6.53) and the
continuity property of $v_{\kappa}^{i}$ in the boundary (6.54).  $\Box$

Finally, combining the previous results, we obtain the following PDE
characterization of the value function.

###### Corollary 6.1

The value function $v_{\kappa}^{i}$ is continuous on $[0,T)\times{\cal S}$ and
is the unique (in $[0,T)\times{\cal S}$) constrained viscosity solution to the
system of QVIs (6.1)-(6.2) lying in the class of functions with linear growth
in $x$ uniformly in $(t,y^{i},y^{j})$ and satisfying the boundary condition :

$\displaystyle\lim_{(t^{\prime},z^{\prime})\rightarrow(t,z)}v_{\kappa}^{i}(t^{\prime},z^{\prime})=\begin{cases}0&\quad\text{if
}(t,z)\in[0,T)\times\partial^{y^{1}}{\cal S}\cup\partial^{y^{2}}{\cal S},\\\
-\frac{x}{2}(\frac{e^{(\mu-\rho^{i})(T-t)}-1}{\mu-\rho^{i}}+e^{(\mu-\rho^{i})(T-t)})&\quad\text{if
}(t,z)\in[0,T)\times\partial^{x}{\cal S},\end{cases}$

and the terminal condition

$\displaystyle v_{\kappa}^{i}(T,z)$ $\displaystyle=$ $\displaystyle
g^{i}(z),\;\;\;\forall z\in\bar{\cal S}.$

Proof. We have $\bar{v}_{\kappa}^{i}$ is an usc viscosity subsolution to
(6.1)-(6.2) in $[0,T)\times\bar{\cal S}$ and $\underline{v}^{i}_{\kappa}$ is a
lsc viscosity supersolution to (6.1)-(6.2) in $[0,T)\times{\cal S}$. Moreover,
by Proposition 6.4 and Proposition 3.3, we have
$\overline{v}_{\kappa}^{i}(t,z)$$\leq$
$\displaystyle\liminf_{(t^{{}^{\prime}},z^{{}^{\prime}})\longrightarrow(t,z)}\underline{v}_{\kappa}^{i}(t^{{}^{\prime}},z^{{}^{\prime}})$,
for all $(t,z)$ $\in$ $[0,T)\times D_{0}$, and
$\overline{v}^{i}_{\kappa}(T,z)$ $=$ $\underline{v}_{\kappa}^{i}(T,z)$ $=$
$g^{i}(z)$ for all $z$ $\in$ $\bar{\cal S}$. Then by Theorem 6.1, we deduce
$\bar{v}_{\kappa}^{i}$ $\leq$ $\underline{v}_{\kappa}^{i}$ on
$[0,T]\times{\cal S}$, which proves the continuity of $v_{\kappa}^{i}$ on
$[0,T)\times{\cal S}$. On the other hand, suppose that $w_{\kappa}^{i}$ is
another constrained viscosity solution to (6.1)-(6.2) with

$\displaystyle\lim_{(t^{\prime},z^{\prime})\rightarrow(t,z)}w_{\kappa}^{i}(t^{\prime},z^{\prime})=w_{\kappa}^{i}(t,z)=v_{\kappa}^{i}(t,z),\;\;\;\mbox{
for all }(t,z)\in[0,T)\times D_{0},$

and $w_{\kappa}^{i}(T,z)$ $=$ $g^{i}(z)$ for $z$ $\in$ $\bar{\cal S}$. Then,
$\bar{w}_{\kappa}^{i}(t,z)$ $=$ $\underline{v}_{\kappa}^{i}(t,z)$ $=$
$\bar{v}_{\kappa}^{i}(t,z)$ $=$ $\underline{w}_{\kappa}^{i}(t,z)$ for $(t,z)$
$\in$ $[0,T)\times D_{0}$ and $\bar{w}_{\kappa}^{i}(T,z)$ $=$
$\underline{v}_{\kappa}^{i}(T,z)$ $=$ $\bar{v}_{\kappa}^{i}(T,z)$ $=$
$\underline{w}_{\kappa}^{i}(T,z)$ for $z$ in $\bar{\cal S}$. We then deduce by
Theorem 6.1 that $\bar{v}_{\kappa}^{i}$ $\leq$ $\underline{w}_{\kappa}^{i}$
$\leq$ $\bar{w}_{\kappa}^{i}$ $\leq$ $\underline{v}_{\kappa}^{i}$ on
$[0,T]\times{\cal S}$. This proves $v_{\kappa}^{i}$ $=$ $w_{\kappa}^{i}$ on
$[0,T]\times{\cal S}$.
$\Box$

##  7 Numerical illustrations

In this section we provide some numerical results describing the value
functions of the players and their optimal policy. A forward computation of
the value function and the optimal strategy is in our knowledge impossible due
to the high dimension of the state process and the complexity of our model,
therefore we used a numerical scheme based on a quantization technique (see
[18]). The convergence of the numerical solution towards the real solution can
be shown using consistency, monotonicity and stability arguments and will be
further investigated in a future work. A detailed description of the numerical
algorithm can be found in the Appendix.

Numerical tests are performed on the localized and discretized grid
$[0,T]\times[x_{min},..,x_{max}]\times[y_{min}^{1},..,y_{max}^{1}]\times[y_{min}^{2},..,y_{max}^{2}]$.
We used the following values for the parameters of the model: $T=1$, $\mu=0$,
$\sigma=0.5$, $\zeta_{min}=-2.2$, $\zeta_{max}=1.8$, $x_{min}$ $=$
$y_{min}^{1}$ $=$ $y_{min}^{2}=10$, $x_{max}$ $=$ $y_{max}^{1}$ $=$
$y_{max}^{2}$ $=90$, $\lambda=0.1$ and $g^{1}=f^{1}$ and $g^{2}=f^{2}$,
$\rho_{1}=\rho_{2}=0$, $\phi_{1}=5$, $\phi_{2}=2.5$. Besides, the running
costs are $f^{1}(x,y^{1},y_{2})=(y^{1}-x)Q(y^{1}-y^{2})$ and
$f^{2}(x,y^{1},y^{2})=(y^{2}-x)Q(y^{2}-y^{1})$ where

$\displaystyle
Q(x)=\mathds{1}_{]-\infty,-\Delta]}-\frac{x-\Delta}{2\Delta}\mathds{1}_{[-\Delta,\Delta]},$

with $\Delta=40$. Further, the terminal payoffs are chosen such that
$g^{1}(x,y^{1},y^{2})=f^{1}(x,y^{1},y^{2})$ and
$g^{2}(x,y^{1},y^{2})=f^{2}(x,y^{1},y^{2})$.

Figure 1: _The optimal policies for a fixed $(t,x)=(,)$ for the first player
(First Line) and the second player (Second Line). Color code: red: concerned
player intervenes, green: concerned player waits, blue: concerned player
endures the intervention of the other player. _

First, the Figure 1 presents the optimal transaction policy for the two
players, i.e. the different regions of interventions and continuations in the
plane ($y^{1},y^{2})$ for $t=0.5$ and $x=50$ €/MWh. The first line (resp.
second line) of Figure 1 corresponds to the optimal policy regions and the
corresponding interventions of the player 1 (resp. player 2). In the first
column we can distinguish, for both of the players, three different regions,
represented by three different colors, corresponding to the optimal action
given a state $(y^{1},y^{2})$. Indeed, the blue region represents the states
$(y^{1},y^{2})$ where a player is subject to the intervention of the other
player, the green regions represents the states where a player chooses to not
intervene and the red region represents the states where the player makes an
intervention. The second column represents, whenever a player decides to
intervene, the size of the intervention. If the quantity is positive it means
that the price is increased and if it is negative it means that the price is
lowered.

We can see that, as expected, both the players tend to keep the price spread
$|y^{1}-y^{2}|$ as low as possible in order to avoid market share losses. In
fact, for instance, at the state $(y^{1}=85,y^{2}=60)$, player 1 chooses to
push down her price to keep an acceptable market share position. On the other
hand, at the state $(y^{1}=30,y^{2}=70)$, player 1 chooses to push up her
price which allows her to make benefits whilst keeping a reasonable market
share position.

Figure 2:  (Left) One path-scenario of the wholesale market price and the
players’ retail prices. (Right) Retail electricity bill compared to wholesale
price in the UK (source Ofgem).

Second, the Figure 2 (Left) gives an example of a trajectory of the wholesale
electricity price $X$ together with the corresponding retail prices
trajectories $Y^{1}$ and $Y^{2}$ of the two players, where the initial state
is $(X_{0}=30,Y^{1}_{0}=40,Y^{2}_{0}=35)$. As a matter of comparison, Figure 2
(Right) shows the trajectories of the wholesale price of electricity and
retail prices of the six largest energy providers in the UK from January 2004
to March, 2010. We observe several comparable features of the optimal
retailers price resulting from our impulse game and the real-life experience.
Increases in the wholesale price is not immediately followed by an increase in
retail prices. There is a delay given by the optimal time to reach the
boundary of the action region. Further, even if our model only involves two
players, we observe that they do not intervene at the same time, as it is the
case in the UK market example. However, they appear to follow an almost
synchronised behaviour: an increase by a first player is mostly to be followed
by an increase of the second player and not by a decreases. Further, the
optimal trajectories of the retail prices can be increasing while the
wholesale price is decreasing (from $0.2$ to $0.3$ for instance), a phenomenon
which is also observed in the UK case (from April, 2006 to March 2007, for
instance). The optimal trajectories can also decrease, even if these decrease
are limited compared to the same reference case of the UK market. Thus,
contrary to the belief of the UK energy regulator, the Ofgem555The British
energy regulator launched an inquiry on energy retailers in 2014. The headline
findings of the assessment were: (…) Possible tacit co-ordination: The
assessment has not found evidence of explicit collusion between suppliers.
However, there is evidence of possible tacit coordination reflected in the
timing and size of price announcements and new evidence that prices rise
faster when costs rise than they reduce when costs fall. Although tacit
coordination is not a breach of competition law, it reduces competition and
worsens outcomes for consumers. Published on Ofgem website on June 26th, 2014,
at the address: www.ofgem.gov.uk/press-releases/ofgem-refers-energy-market-
full-competition-investigation., the observed behaviour of almost synchronised
increase and decrease of retailers prices might not be the result of a tacit
collusion mechanism, but is simply the result of optimal decision in a Nash
equilibrium.

Figure 3: _The average trajectory of the market price and the players’
prices._

Finally, the Figure 3 shows the average trajectories of the market price and
the players’ optimal retail price processes over ten thousand simulated
trajectories of $X$, $Y^{1}$ and $Y^{2}$ on the horizon $[0,T]$. The initial
state is the same as in the Figure 2. We notice that, although the wholesale
price $X$ is a martingale, the retail prices offered by the two players are
increasing. In addition to this observation, we note that the players have
almost the same tendency as they try to keep a balanced market share
configuration until the maturity. With our choice of parameters, we observe
that player 2 starts with a price lower than the player 1’s price and attains
the maturity with a higher price. This is because the interventions for the
player 2 are less expensive making her more dynamic. We can also observe that,
throughout the time period, the price spread between the two players is quite
small preventing the market share to be imbalanced.

Our model suggests that the players would rather propose increasing prices to
maximize their profit. This result might be surprising as one would expect
that the players would stick to the wholesale price tendency and would propose
a mean constant prices. But, in our model the market shares are split between
the two players only according to the difference in the price they offer:
consumers do not have an outside option to switch to another energy and no
market entry of a competitor may threaten the two players for practicing
increasing prices. The thing we find remarkable in this result is that without
setting any potential communication device between the two players, we observe
on average a behaviour that looks like tacit collusion.

## Appendix

In the following, we give a detailed description of the numerical procedure
used to compute the value function and the optimal policies associated to the
optimal control problem. We recall that we used a numerical scheme based on a
quantization technique (see [18]) mixed with an iterative procedure. The
convergence of the numerical solution towards the real solution can be shown
using consistency, monotonicity and stability arguments and will be further
investigated in a future work.

For a time step $h>0$ on the interval $[0,T],$ we introduce a numerical
backward scheme that approximates the solution of the HJB-QVI system via the
couple of functions $v^{i}_{h},i=1,2$ through:

$\displaystyle\left\\{\begin{array}[]{rlll}\mathcal{M}^{i}v^{i}_{h}(t,z)&-v^{i}_{h}(t,z)\leq
0\\\
v^{i}_{h}(t,z)&=max(\mathcal{M}^{i}\mathcal{H}^{i}v^{i}_{h}(t,z),\mathcal{H}^{i}v^{i}_{h}(t,z))\quad\textrm{in}\quad\overline{\mathcal{I}^{i}}\\\
v^{i}_{h}(t,z)&=\max\left[\mathbb{E}[v^{i}_{h}(t+h,Z^{t,z}_{t+h})]+\Sigma_{i}(t,z),\mathcal{M}^{i}v^{i}_{h}(t,z)\right]\textrm{in}~{}~{}{\mathcal{I}^{i}}\\\
v^{i}_{h}(T,z)&=g^{i}(z),\quad\textrm{in}~{}~{}\mathcal{S}.\end{array}\right.$
(7.5)

Where

$\Sigma_{i}(t,z)=\int^{t+h}_{t}f^{i}(Z_{s}^{t,z})ds.$

This approximation scheme seems a priori implicit due to the nonlocal obstacle
terms $\mathcal{M}^{i}$ and $\mathcal{H}^{i}$. This is typically the case in
impulse control problems, and the usual way to circumvent this problem is to
iterate the scheme by considering a sequence of optimal stopping problems:

$\displaystyle\left\\{\begin{array}[]{rlll}\mathcal{M}^{i}v^{i}_{h,n}(t,z)&-v^{i}_{h,n+1}(t,z)\leq
0\\\
v^{i}_{h,n+1}(t,z)&=max(\mathcal{M}^{i}\mathcal{H}^{i}v^{i}_{h,n}(t,z),\mathcal{H}^{i}v^{i}_{h,n}(t,z))\quad\textrm{in}\quad\overline{\mathcal{I}_{i}}\\\
v^{i}_{h,n+1}(t,z)&=max\left[\mathbb{E}[v^{i}_{h,n+1}(t+h,Z^{t,z}_{t+h})]+\Sigma_{i}(t,z),\mathcal{M}^{i}v^{i}_{h,n}(t,z)\right]~{}~{}\textrm{in}~{}~{}{\mathcal{I}^{i}}\\\
v^{i}_{h,n+1}(T,z)&=g^{i}(z)\quad\textrm{in}~{}~{}\mathcal{S}.\end{array}\right.$
(7.10)

#### Time and Space discretization

$\bullet$ Now let us consider the time grid
$\mathbb{T}:=\\{t_{k}=kh,~{}~{}k=0,..,M,~{}~{}h=\frac{T}{M}\\}$ and
$M\in\mathbb{N}\setminus\\{0\\},$ $z\in\mathcal{S}$ and starting from a pair
$(v^{1}_{0},v^{2}_{0})$ two fixed vectors.

$\displaystyle\left\\{\begin{array}[]{rlll}\mathcal{M}^{i}v^{i}_{h,n}(t_{k},z)&-v^{i}_{h,n+1}(t_{k},z)\leq
0\\\
v^{i}_{h,n+1}(t_{k},z)&=max(\mathcal{M}^{i}\mathcal{H}^{i}v^{i}_{h,n}(t_{k},z),\mathcal{H}^{i}v^{i}_{h,n}(t_{k},z))\quad\textrm{in}\quad\overline{\mathcal{I}^{i}}\\\
v^{i}_{h,n+1}(t_{k},z)&=max\left[\mathbb{E}[v^{i}_{h,n+1}(t_{k+1},Z^{t_{k},z}_{t_{k+1}})]+\Sigma_{i}(t_{k},z),\mathcal{M}^{i}v^{i}_{h,n}(t_{k},z)\right]\quad\textrm{in}\quad{\mathcal{I}^{i}}\\\
v^{i}_{h,n+1}(T,z)&=g^{i}(z_{j})\quad\textrm{in}~{}~{}\mathcal{S}.\\\
\end{array}\right.$ (7.15)

$\bullet$ Let $\mathbb{X}$ the uniform grid on $[x_{min},x_{max}]$ of step
$dx=\frac{x_{max}-x_{min}}{(N_{x}-1)},$ where $x_{min}<x_{max}\in(0,+\infty)$
and $N_{x}>0$. For $j=0,...,N_{x},$ we denote $x_{j}:=x_{min}+jdx$.
$\bullet$ For $i\in\\{1,2\\}$, let $\mathbb{Y}_{i}$ the uniform grid on
$[y_{min}^{i},y_{max}^{i}]$ of step
$dy_{i}=\frac{y_{max}^{i}-y_{min}^{i}}{(N_{y}-1)},$ where
$y_{min}^{i}<y_{max}^{i}\in(0,+\infty).$ For $j=0,...,N_{y},$ we denote
$y_{j}^{i}:=y_{min}^{i}+jdy_{i}$.
Let
$z_{j}=(x_{j},y_{j}^{1},y_{j}^{2})\in\mathbb{G}:=\mathbb{X}\times\mathbb{Y}_{1}\times\mathbb{Y}_{2}$,
we define the following problem:

$\displaystyle\left\\{\begin{array}[]{rlll}\mathcal{M}^{i}v^{i}_{h,n}(t_{k},z_{j})&-v^{i}_{h,n+1}(t_{k},z_{j})\leq
0\\\
v^{i}_{h,n+1}(t_{k},z_{j})&=max(\mathcal{M}^{i}\mathcal{H}^{i}v^{i}_{h,n}(t_{k},z_{j}),\mathcal{H}^{i}v^{i}_{h,n}(t_{k},z_{j}))\quad\textrm{
in }\overline{\mathcal{I}^{i}}\cap\mathbb{G}\\\
v^{i}_{h,n+1}(t_{k},z_{j})&=max\left[\mathbb{E}[v^{i}_{h,n+1}(t_{k+1},Z^{t_{k},z_{j}}_{t_{k+1}})]+\Sigma_{i}(t_{k},z_{j}),\mathcal{M}^{i}v^{i}_{h,n}(t_{k},z_{j})\right]\textrm{
in }\mathcal{I}^{i}\cap\mathbb{G}\\\
v^{i}_{h,n+1}(T,z_{j})&=g^{i}(z_{j})\textrm{ in }\mathcal{S}\cap\mathbb{G}.\\\
\end{array}\right.$ (7.20)

### Quantization of the Brownian Motion

To compute the conditional expectations arising in the numerical backward
scheme, we use the optimal quantization method. The main idea is to use the
quantization theory to construct a suitable approximation of the Brownian
motion.
It is known that there exists a unique strong solution for the SDE,
$\frac{dX_{s}^{t,x}}{X_{s}^{t,x}}=\mu ds+\sigma dW_{s}$. So it suffices to
consider a quantization of the Brownian motion itself.
Recall that the optimal quantization technique consists in approximating the
expectation $\mathbb{E}[f(Z)]$, where $Z$ is a normal distributed variable and
$f$ is a given real function, by

$\displaystyle\mathcal{E}[f(\xi)]$ $\displaystyle=$
$\displaystyle\sum_{k\in\xi(\Omega)}f(k)\mathbb{P}(\xi=k)\;.$

The distribution of the discrete variable $\xi$ is known for a fixed
$N:=card(\xi(\Omega))$ and the approximation is optimal as the $L^{2}$-error
between $\xi$ and $Z$ is of order $1/N$ (see [18]). The optimal grid
$\xi(\Omega)$ and the associated weights $\mathbb{P}(\xi=k)$ can be downloaded
from the website: http://www.quantize.maths-fi.com/downloads.
Let $N$ denote the number of elementary quantizers used to quantize process
$\hat{X}_{s}$. We replace ${X}_{s}$ in by its quantized random vector
$\hat{X}_{s},$ the optimal quantization of $X_{s}$ and we obtain the quantized
dynamic programming backward scheme:

$\displaystyle\left\\{\begin{array}[]{rlll}\mathcal{M}^{i}v^{i}_{h,n}(t_{k},z_{j})&-v^{i}_{h,n+1}(t_{k},z_{j})\leq
0\\\
v^{i}_{h,n+1}(t_{k},z_{j})&=max(\mathcal{M}^{i}\mathcal{H}^{i}v^{i}_{h,n}(t_{k},z_{j}),\mathcal{H}^{i}v^{i}_{h,n}(t_{k},z_{j}))\quad\textrm{
in }\overline{\mathcal{I}^{i}}\cap\mathbb{G}\\\
v^{i}_{h,n+1}(t_{k},z_{j})&=max\left[\mathcal{E}[v^{i}_{h,n+1}(t_{k+1},Z^{t_{k},z_{j}}_{t_{k+1}}))]+\Sigma_{i}(t_{k},z_{j}),\mathcal{M}^{i}v^{i}_{h,n}(t_{k},z_{j})\right],\textrm{
in }\mathcal{I}^{i}\cap\mathbb{G}\\\
v^{i}_{h,n+1}(T,z_{j})&=g^{i}(z_{j})\;\textrm{ in
}\mathcal{S}\cap\mathbb{G}.\\\ \end{array}\right.$ (7.25)

Hence, the expectations arising in the backward scheme are approximated by

$\displaystyle\mathcal{E}[v^{i}_{h,n+1}(t+h,Z^{t,z}_{t+h})]=\sum_{l=1}^{N}v^{i}_{h,n+1}(t+h,xe^{(\mu-\frac{\sigma^{2}}{2})h+\sigma\sqrt{h}\hat{u_{l}}},y^{i},y^{j}){P}_{l},$

where $\hat{u}_{l}$ is the $N$ quantizer of the standard normal distribution.
The weight associated to this quantizer is
${P}_{l}=\mathbb{P}(\hat{U}=\hat{u}_{l})$. The optimal grid $\hat{u}_{l}$ and
the associated weights ${P}_{l}$ are downloaded from the website:
http://www.quantize.maths-fi.com/downloads.
Finally, to approximate the integral $\Sigma_{i}$, we use the rectangle rule
and we obtain:

$\Sigma_{i}(t_{k},z_{j})=\displaystyle{\int_{t_{k}}^{t_{k+1}}f^{i}(Z_{s}^{t_{k},z_{j}}}ds\simeq\displaystyle{hf^{i}(z_{j})}.$

### Final Numerical Algorithm

Thus, considering the iterative scheme defined in (7.25), we obtain the
following final backward scheme for
$(t_{k},z_{j})\in\mathbb{T}\times\mathbb{G}$:

Algorithm 1 Policy iteration for system of QVIs (one-player)

0: Set $\varepsilon>0$ (numerical tolerance) and $n_{max}\in\mathbb{N}$
(maximum iterations).

0: Pick initial guess: $v^{i}_{h,0}\in\mathbb{R}.$

0: Let $n=0$ (iteration counter) and $R^{0}=+\infty$..

0: while ${R}^{n}>\varepsilon$ and $n\leq n_{max}$ do

0: $\begin{array}[]{lcl}v^{i}_{h,n+1}(T,z_{j})=g^{i}(z_{j}),\\\
v^{i}_{h,n+1}(t_{k},z_{j})=max\left[\mathcal{E}[v^{i}_{h,n+1}(t_{k+1},Z^{t_{k},z_{j}}_{t_{k+1}})]+\Sigma_{i},\mathcal{M}^{i}v^{i}_{h,n}(t_{k},z_{j})\right].\\\
\end{array}$

0: Let $R^{n+1}$ be the largest pointwise residual to the QVI,
i.e.$R^{n+1}=||v_{h,n+1}^{i}-v_{h,n}^{i}||.$

0: Let $n=n+1.$

0: end while.

The final Algorithm is as follows

Algorithm 2 Policy iteration for system of QVIs (two players)

0: Set $\varepsilon>0$ (numerical tolerance) $,0<\alpha<1,$ $~{}r^{0}>0$
(relaxation parameters) and $n_{max}\in\mathbb{N}$ (maximum iterations).

0: Pick initial guess:
$(v^{1}_{h,0},v^{2}_{h,0})\in\mathbb{R}\times\mathbb{R}.$

0: Let $n=0$ (iteration counter) and $R^{0}=+\infty$.

0: while ${R}^{n}>\varepsilon$ and $n\leq n_{max}$ do

0: for $i=1,2$ (player $i$) do

0: $l=3-i$ (player $l.$)

0:
$\mathcal{C}^{n}_{l}:=\\{\mathcal{M}^{l}v^{l}_{n}-v^{l}_{n}<-r^{n}\\}\cap\mathbb{G}.$

0: For $t_{k}\in\mathbb{T}$ and $z_{j}\notin\mathcal{C}^{n}_{l},$ let
$v^{n+1}_{i}(t_{k},z_{j})=max(\mathcal{M}^{i}\mathcal{H}^{i}v^{i}_{h,n}(t_{k},z_{j}),\mathcal{H}^{i}v^{i}_{h,n}(t_{k},z_{j})).$

0: For $(t_{k},z_{j})\in\mathbb{T}\times\mathcal{C}^{n}_{l},$ solve for
$v_{n+1}^{i}(t_{k},z_{j})$ by applying Algorithm $1$ to
$\min\\{{-\frac{\partial v_{n+1}^{i}}{\partial
t}-\mathcal{L}^{i}v_{n+1}^{i}-f^{i},v_{n+1}^{i}-\mathcal{M}^{i}v_{n+1}^{i}}\\}=0$

0: end for.

0: Let $R^{n+1}$ be the largest pointwise residual to the system of QVIs,
i.e.$R^{n+1}=max(||v_{h,n+1}^{1}-v_{h,n}^{1}||,||v_{h,n+1}^{2}-v_{h,n}^{2}||).$

0: $r^{n+1}:=max\\{\alpha R^{n+1},\varepsilon\\}$

0: Let $n=n+1.$

0: end while.

## References

  * [1] Akian M., Sulem A. and Taksar M. (2001) : "Dynamic optimization of long term growth rate for a portfolio with transaction costs and logarithm utility", Math. Finance, 11, 153-188.
  * [2] Aïd R., F. Bernal, M. Mnif , D. Zabaljauregui and Zubelli J. P. (2019) : "A policy iteration algorithm for nonzero-sum stochastic impulse games", ESAIM, 65, p. 27-45.
  * [3] Aïd R., M. Basei, G. Callegaro, L. Campi, T. Vargiolu (2019) : "Nonzero-Sum Stochastic Differential Games with Impulse Controls: A Verification Theorem with Applications", Mathematics of Operations Research, 1-28.
  * [4] Barles G. (1994) : Solutions de viscosité des équations d’Hamilton-Jacobi, Math. et Appli., Springer Verlag.
  * [5] Basei M. (2019) : "Optimal price management in retail energy markets: an impulse control problem with asymptotic estimates", Math. Methods in Operations Research, 89(3), 355-383.
  * [6] Bertsekas D. and S. Shreve (1978) : "Stochastic optimal control; the discrete-time case", Math. in Sci. and Eng., Academic Press.
  * [7] Bouchard B. and N. Touzi (2011): "Weak dynamic programming principle for viscosity solutions". SIAM J. Control Optim., 49(3), 948–962
  * [8] Crandall M., H. Ishii and P.L. Lions (1992) : "User’s guide to viscosity solutions of second order partial differential equations", Bul. Amer. Math. Soc., 27, 1-67.
  * [9] Cosso A. (2013) : "Stochastic differential games involving impulse controls and double-obstacle quasi-variational inequalities", SIAM J. Control Optim. 51(3), 2102–2131.
  * [10] Evans L. C., P. E. Souganidis (1984) : "Differential games and representation formulas for solutions of Hamilton-Jacobi-Isaacs equations", Indiana Univ. Math. J., 33(5), 773-797.
  * [11] Gilbarg D. and N. Trudinger (1977) : Elliptic partial differential equations of second order, Springer Verlag, Berlin.
  * [12] Isaacs R. (1965) : Differential games. A mathematical theory with applications to warfare and pursuit, control and optimization, John Wiley and Sons, Inc., New York-London-Sydney.
  * [13] Ishii K. (1993): "Viscosity solutions of nonlinear second order elliptic PDEs associated with impulse control problems", Funkcial. Ekvac., 36, 123-141.
  * [14] Ly Vath V., M. Mnif and H. Pham (2007) : "A model of optimal portfolio selection under liquidity risk and price impact", Finance and Stochastics, 11, 51-90.
  * [15] Øksendal B. (2003) : Stochastic Differential Equations, Springer-Verlag, Berlin.
  * [16] Pagès, G. and H. Luschgy (2006) : "Functional quantization of a class of Brownian diffusions: a constructive approach", Stoch. Process. Appl., 116, 310–336.
  * [17] Pagès, G., Luschgy, H. (2002) : "Functional quantization of Gaussian Process", J. Funct. Anal., 196, 486–531.
  * [18] Pagès G., H. Pham and J. Printems (2004) : "Optimal quantization methods and applications to numerical problems in finance", Handbook on Numerical Methods in Finance (S. Rachev, ed.) 253-298.
  * [19] Soner H. (1986) : "Optimal control with state-space constraint, I and II", SIAM J. Cont. Optim., 24, 552-561, and 1110-1122.
  * [20] Zariphopoulou T. (1988) : Optimal investment-consumption models with constraints, Phd Thesis, Brown University.