Souheïl Hanoune
email: souheil.hanoune@ensea.fr

Jean Paul Banquet

Mathias Quoy
email: quoy@ensea.fr

Philippe Gaussier
email: gaussier@ensea.fr

Cooperation of S-R habit and cognitive learnings in goal-oriented navigation

The Stimulus-Response (S-R) theory and Tolman's Cognitive Theory of behavior control both issued from behaviorism in the early XXth century still provide a relevant general framework to account for animal rewardbased adaptive behavior. In this paper, we propose a new paradigm for representing and implementing both the cognitive strategy and the S-R habit strategy within a unitary coding frame. Based on a parallel learning of both strategies, the model explains how the fast learning cognitive strategy can supervise and accelerate the slow learning S-R habit strategy. This parallel representation is inspired by the cortico-basal functional loops [Alexander et. al., 1986] and the cooperation between the cognitive associative loop, including the dorsomedial striatum and the mPF; and the sensory-motor loop, associated to the sensory motor cortex in relation with the dorso-lateral striatum.

The implementation of S-R habit strategy is different from a classical Q-learning and is based on the model of [START_REF] Hirel | The Hippocampocortical Loop: Spatio-Temporal Learning and Goal-oriented Planning in Navigation[END_REF], representing the functioning of the sensory-motor loop. This representation is based on a neuronal modelisation of the Q-learning algorithm. The states of the model are represented by the transitions. A transition is an association between two consecutive place-cells during the exploration of the environment, learned in the CA1-CA3 regions of the hippocampus. The cognitive strategy is based on a map representation of the environment namely the cognitive map [O' Keefe & Nadel, 1978]. Based on the association between learned transitions, the cognitive map allows the back-propagation of a reward within a tree, allowing the selection of the shortest path to the goal. While the cognitive map is quickly learned, the Q-values associated with the Q-learning are slower to acquire. On the other hand, the Q-learning tends to be more accurate than the cognitive map when fully learned.

The model exploits this speed difference in its parallel learning. The fast acquisition of the cognitive map allows the robot to quickly choose correct paths to the goal, and thus the time convergence of the Q-learning algorithm is optimized. The cooperation is based on the biasing of the selected transition by the cognitive map and the Q-learning in parallel (see Fig 1). In its early learning stage, the Q-learning biasing is too weak, and the cognitive map is dominant, inducing the supervision of the S-R habit by the cognitive strategy. In the later learning stages, the Q-learning is stronger and more precise. Cooperation of the cognitive strategy and S-R habit enables a faster S-R learning; as shown on Fig 2 . It is also possible to study the lesioning of one or the other path and its effect on the behavior and the learning process.

  Figure 1: Cooperative architecture of the cognitive strategy and the S-R habit.

Figure 2 :

 2 Figure 2: Example of convergence time of the Q-learning with and without the cognitive supervision.


Bernard Kamsu-Foguem
email: bernard.kamsu-foguem@enit.fr

Clovis Foguem
email: cfoguem@yahoo.fr

Adverse drug reactions in some African herbal medicine: literature review and stakeholders' interview

alternative medicines complementary therapies pharmacovigilance practice toxicological risk assessment traditional medicine Background: In view of the large consumption of herbal medicine in Africa countries, it is likely that many adverse drugs reactions go unrecorded with either patients failing to present to health services, or no pharmacovigilance analysis being made, or the analysis not being reported centrally. This problem is of interest especially for those who are working in the general area of adverse drug reactions or stakeholders in the domain of herbal medicine for considering safety issues.

Methods:

We are particularly interested in the way that the use of very well-known and highly valued plants is linked to the observation of adverse drug reactions in African countries. We investigated, through a literature review and using the Internet (with a semantic search strategy), some well-known or popular medicinal plants used in African herbal medicine (AHM). Other information on the properties related to use, and characteristics of medicinal plants was complemented by some interviews with stakeholders.

Results: Although substantial progress has been made in elucidating the mechanisms of action of many drugs, the pharmacological actions of many medicinal plants are generally not well understood. The results of a literature review suggest that the reported adverse drug reactions of herbal remedies are often due to a lack of understanding of their preparation and appropriate use. The results of stakeholders' interviews suggest that there is a growing need to provide patients with correct information about the herbal medicines they consume.

Conclusion:

An important aspect of herbal medicine is the correct, timely, and integrated communication of emerging data on risk as an essential part of pharmacovigilance, which could actually improve the health and safety of patients. This calls for improved collaboration between traditional practitioners and modern healthcare professionals, researchers, and drug regulatory authorities. In addition, there is a need for an adverse drug reaction reporting system to facilitate the collection, monitoring, and evaluation of adverse drug events.

1.

Introduction

Medicinal plants are important materials for the pharmaceutical and cosmetic industries. Neglected since the discovery of synthetic drugs, which can be produced in a wider scale, there has been a resurgence of interest in plant medicines in recent years. It is estimated that approximately half of all synthetic drugs have a natural origin. [START_REF] Gillespie | Biodiversity and International Law. New Horizons in Environmental and Energy Law series[END_REF] Any substance with a healing influence can also generate unwanted or adverse side reactions. As with synthetic drugs, the quality, efficacy, and safety of medicinal plants must also be assured. There is a non-negligible contribution of Africa to the world's medicinal plants' stock. In effect, Africa provides approximately 60,000 of the world's higher plant species and yet contributes < 8% of the 1100 drugs placed on the market worldwide. [START_REF] Dzoyem | 24 -Medicinal Plants Market and Industry in Africa[END_REF] Many plants used in herbal medicine provide valuable promising medical solutions to some diseases [pathologies and infections], since many medicinal plants are a source of new medicines and therefore they have an essential role in medical research. [START_REF] Fokunang | Traditional Medicine: past, present and future research and development prospect and integration in the national health system of Cameroon[END_REF] African traditional medicine is "the most economical and available system of health care for a large number of the African population in rural and semi-urban areas." [START_REF] Kasilo | An overview of the traditional medicine situation in the African Region. The African Health Monitor, magazine of the World Health Organization Regional Office for Africa[END_REF] African herbal medicine (AHM) is a fundamental element of African traditional medicine practices.

However, there are some challenges and opportunities in the improvement of herbal medicine. The various adverse drug reactions of herbal medicine carry with them specific risk factors which can lead to increased vulnerability to human health difficulties. In recognition of the increasing possibilities of purchasing medicinal products on the street or online worldwide, improvement measures are needed to better inform people about the efficiency and vulnerabilities of purchasing medicines. An adverse drug reaction is defined by Edwards and Aronson as "an harmful or troublesome reaction, due to intervention related to the use of a healing substance, which envisages risk from future administration and requires prevention or explicit treatment, or alteration of posology and method of administration, or withdrawal of the medical substance." [START_REF] Edwards | Adverse drug reactions: definitions, diagnosis, and management[END_REF] The latency period between the use of a drug and the occurrence of an adverse reaction can help in its causality assessment in pharmacovigilance management. [START_REF] Shetti | Pharmacovigilance of herbal medicines: Current state and future directions[END_REF] Such information can be invaluable in the interpretation of drug safety signals, and facilitate decisions on further protective actions being taken then and the type of further investigations about alteration in the posology, or removal of the substance.

Methods

We researched some well-known or popular AHM products by using a literature review and through the Internet (using a semantic search strategy). A thorough literature search was made by referring to books, peer-reviewed papers, scientific databases such as Scopus, Science Direct, PubMed, and Google Scholar. Keywords such as adverse drug reactions, African traditional medicine, herbal or natural products, alternative therapy, surveillance, phytotherapy in relation to medicinal plants were the terms employed in the different semantic investigations. Other Development of a trust-based relationship with African traditional health practitio ners for effective co mmunicatio n an d knowled ge elicitation

Conta ct with Afri can t raditional health pr act itione rs

Reported medicinal use s of the pla nts, substa nces is olated, and o bser ved pharmacological effects (medicinal properties and adverse effects)

Literature survey

Type of pla nt (t ree, herb, parasite, shru b, lia na or aqueous pla nt) , preparatio n of remedy (plant part, fresh, dried), dose and regimen, disease or symptoms treated

Collect ion of information abo ut herbal prac tices

Fig. 1 -The adopted information-gathering process for herbal practices.

information on the properties of medicinal plants was complemented by interviews with stakeholders. Medicinal plants were identified based on their traditional use in different aspects of African traditional medicine.

In our approach, the information-gathering process was based both on the details of stakeholders' interviews and the outcomes of the literature review. More specifically, in order to obtain information about herbal practices and their associated effects, we went through the following process with three phases adapted from Kamsu-Foguem et al [START_REF] Kamsu-Foguem | Conceptual graph-based knowledge representation for supporting reasoning in African traditional medicine[END_REF] (Fig. 1):

• Contact with African traditional health practitioners: development of a trust-based relationship with African traditional health practitioners for effective communication and knowledge elicitation. Trust is especially necessary for open and operative communication, since health practitioners keep their knowledge secret and do not wish to share their know-how outside the family environment.

• Collection of information about herbal practices: the information is collected through questionnaires or structured interviews with stakeholders. The form includes the following information for considered herbal medicines: type of plant (tree, herb, parasite, shrub, liana or aqueous plant), preparation of remedy (plant part, fresh, dried), dose and regimen, disease or symptoms treated.

• Literature survey with monographs, chemical abstracts and MEDLINE: we investigated the previously described medicinal uses of the plants, substances isolated and identified pharmacological effects (medicinal properties, alternative options for the use of the plant, and adverse effects).

Results

Our review as such was limited to highlighting the potential for adverse drug reactions in AHM. Thus, we have considered that it is essential to clearly delimit the scope of the study, which has been restricted to certain well-known and highly appreciated plants in AHM. The rich flora of Africa (e.g., the Paleotropical natural environment of Central Africa and the Capensis natural environment of South Africa) contains numerous toxic plants with ethnopharmacological uses (e.g., parasitic, bacterial, fungal or viral treatments, treatment of central nervous system-related conditions, aphrodisiacs, and for maternal health care, miscellaneous conditions such as cancer, arthritis, and heart conditions). Toxic constituents (e.g., neurotoxins, cytotoxins, and metabolic toxins) from these plants can harm the major systems of the human body (cardiovascular system, digestive system, endocrine system, urinary system, immune system, muscular system, nervous system, reproductive system, and respiratory system). [START_REF] Ndhlala | Toxicology of some important medicinal plants in southern Africa[END_REF] Several causality assessment methods have been proposed to assess the relationship between drugs and the appearance of adverse events. Those methods belong to three categories: expert judgment, probabilistic methods, and algorithms or scales. [START_REF] García-Cortés | Causality assessment methods in drug induced liver injury: Strengths and weaknesses[END_REF] In view of their attractive characteristics (successive evaluation of criteria, sum of scores or decision trees), scales and algorithms are usually used for operational assessments of adverse drug reactions and they enable an easy and convenient handling in various situations. For instance, the Council for International Organizations of Medical Sciences (CIOMS) scale, also referred to as the Roussel Uclaf Causality Assessment Method (RUCAM), [START_REF] Danan | Causality assessment of adverse reactions to drugs-I. A novel method based on the conclusions of international consensus meetings: application to drug-induced liver injuries[END_REF] is used by many expert hepatologists, researchers, and regulatory authorities to evaluate the possibility of supposed underlying causes of adverse drug reactions. Particularly, the CIOMS provides advantages [standardized scale (chronology, risk factors, concomitant drug(s) or herbs(s), search for nondrug/herb causes, previous information on hepatotoxicity of the drug/herb, response to unintentional readministration), validation for hepatotoxicity with excellent sensitivity, specificity, and predictive validity] for drug-induced liver injury and herb induced liver injury (HILI) causality assessment. [START_REF] Teschke | Drug and herb induced liver injury: Council for International Organizations of Medical Sciences scale for causality assessment[END_REF] Meanwhile, the CIOMS scale has certain weaknesses (e.g., retrospective use, dechallenge criteria, qualitatively graded risk factors, and limited exclusion of alternative causes). Some challenges (e.g., the quality of adverse reaction reports) influence the accuracy in causality assessment of herbal medicinal products. The exploration of omics technologies (genomics/transcriptomics, proteomics, and metabolomics) applied to toxicology (toxicogenomics, toxicoproteomics, and toxicometabolomics) is a valuable way of providing additional information related to predictive safety assessment of herbal medicinal products. [START_REF] Jordan | Assessment of herbal medicinal products: Challenges, and opportunities to increase the knowledge base for safety assessment[END_REF] The predictive toxicity of herbal constituents generates emerging opportunities that are essential to improve the knowledge base for integrated safety assessment.

The results are presented in two segments, one on the literature review and the other on the stakeholders' interview. We obtained 100 reports from the literature review and > 50 stakeholders' interviews. This research took place over a 2year period from December 2012 to January 2014.

• The literature review conducted in the area of AHM only reported adverse drug reactions often a negligible impact on the global health issues in a country or region. However, people are very often subject to safety risks related to herbal medicine which affect or may affect their vital organs (e.g., kidneys, lungs, liver, gastrointestinal tract) and could cause serious damage to other vulnerable areas of the human body. The survey reveals that adverse drug reactions may be caused by logistical and technical problems or questionable decisions by the traditional health practitioners. The logistical and technical problems include poor harvest, the inadequate identification of complex properties, inappropriate preparation, improper conservation or incorrect packing of natural products. The considered problems are not peculiar to the selected plants alone, but exist also in other herbal medicine products that are not included in this study, because of the nonexhaustive nature of the list of products encountered in AHM. Furthermore, a certain control range can be made to monitor the widespread practice of combining many different compound classes and herbal types or creating heterogeneous product class models for use in therapeutic procedures.

• The stakeholders' interview results in significant information that has highlighted (in addition to managerial and some regulatory problems) insufficient communication in relation to increased consumption of products from AHM.

Traditional health practitioners are capable of identifying simple adverse drug reactions and taking preventive actions by learning ideas with experienced feedback processes. Meanwhile, for complex adverse drug reactions, the lack of apparent symptoms, coupled with the potential to cause severe damage to key organs, means that educational assistance for careful and safe use of herbal medicinal products must be encouraged, with special care for high-risk patients. The problem is typically manifested by the fact that information is often either inaccessible, incomplete, or of low quality about potential adverse drug reactions of used herbal products. The managerial and regulatory barriers are present in many African countries by the lack of clear enforced rules for bearing and sharing various experienced feedback processes, as well as by the absence of systems that can help to promote integrative policies and implementation.

Examples of potential adverse effects of some herbal medicines with their traditional use and their countries of origin are presented in Table 1.

Discussion

Quality of herbal medicines is a matter that affects the whole world today, with a requirement for the safety monitoring of herbal remedies, and there is a growing necessity to provide consumers with the correct information about the medicinal products they consume. In this perspective, quality control of herbal medicine and good practices are indispensable for the advancement of the herbal medicine system. [START_REF] Sen | Challenges and opportunities in the advancement of herbal medicine: India's position and role in a global context[END_REF] Quality problems of herbal medicines can be categorized into two classes: internal factors arising from the drug and external factors in clinical use. [START_REF] Zhang | Quality of herbal medicines: Challenges and solutions[END_REF] The internal safety factors related to drug quality include: raw herbals (species and origin, place of origin and collection, natural environment, processing, storage), inactive ingredients, manufacturing, defects of the prescribing information/package leaflet, limitations of premarketing safety studies, and adulterated and counterfeit drugs. The external safety factors in clinical use comprise: lack of traditional medicine theoretical guidance, failure to adhere to the prescribing information, inappropriate combination with allopathic medicines, inappropriate route and dosing and timing, incorrect preparation, and individual factors. Sore throat, cough, arthritis, and weight loss induction [START_REF] Strader | Hepatotoxicity of herbal preparations[END_REF] Acute kidney injury (hypokalemic nephropathy), amenorrhea, pseudoaldosteronism, hypertension, heart failure, and rhabdomyolysis

Worldwide

African regions are particularly concerned by these issues requiring an adverse drug reaction reporting system to reduce the risks of AHM. However, few African countries (e.g., South Africa, Nigeria, and Cameroon) have subsequently introduced herbal/traditional medicine as part of their pharmacovigilance system. South Africa has a well-built plant biotechnology community, as well as the thorough implementation of a legal and operational framework for the guideline of the manipulation of local botanic resources, and of geneticallymodified organisms to improve human health. [START_REF] Rybicki | Plant-made therapeutics: An emerging platform in South Africa[END_REF] Nigeria is in a position to introduce advanced investigations (assessment of traditional medicine practitioners' disposition and doctors' attitudes) which effectively explore the opportunities for the integration of herbal medicine into the national health system with applicable regulations. [START_REF] Awodele | Towa rd s integrating traditional medicine (TM) into National Health Care Scheme (NHCS): Assessment of TM practitioners' disposition in Lagos, Nigeria[END_REF][START_REF] Awodele | Doctors' attitudes towards the use of herbal medicine in Lagos, Nigeria[END_REF] In Cameroon, the government, in collaboration with the World Health Organization (WHO), has set up a strategic platform for the harmonization of the AHM practices with an organizational framework that has integrated a national commission specializing in pharmacovigilance and traditional pharmacopoeia. [START_REF] Fokunang | Traditional Medicine: past, present and future research and development prospect and integration in the national health system of Cameroon[END_REF] There are also other regions of the world (e.g., China, South Pacific, and India) with some problems related to herbal adverse drug reactions. The characteristics of traditional Chinese medicine drugs and their associated adverse drug reactions require an accurate understanding of local cultural and social realities in order to establish a stringent quality control and a risk management model adapted to the pharmacovigilance system (current practice, risk factors, risk control, and future) in China. [START_REF] Zhang | Pharmacovigilance practice and risk control of Traditional Chinese Medicine drugs in China: Current status and future perspective[END_REF] In this context, a recent toxicity evaluation (risk-benefit analysis, severity of toxic effects, and clinical and preclinical data) of Chinese herbal medicines has led to the proposition of four regulatory classes: prohibited for medicinal usage (e.g., aristolochia); restricted for medicinal usage, (e.g., ephedra); required warning label (e.g., coltsfoot); and over-the-counter herbs (i.e., safe toxicity profiles). [START_REF] Kim | Evidence-based toxicity evaluation and scheduling of Chinese herbal medicines[END_REF] In the South Pacific, we found the kava plant (Piper methysticum) consumed worldwide for its relaxing properties and used to treat general anxiety. Traditional aqueous extracts of this pacific herb used in New Caledonia, Australia, the USA, and Germany are associated with rare hepatotoxicity. The primary cause of the kava problem with this toxicity can be traced to poor quality of the raw material triggered by mold hepatotoxins. [START_REF] Teschke | Kava hepatotoxicity: a clinical survey and critical analysis of 26 suspected cases[END_REF][START_REF] Teschke | Kava and kava hepatotoxicity: requirements for novel experimental, ethnobotanical, and clinical studies based on a review of the evidence[END_REF][START_REF] Teschke | Kava hepatotoxicity in traditional and modern use: the presumed Pacific kava paradox hypothesis revisited[END_REF] In the worldwide cases, the organs most notably affected by herbal medicine consumption are the liver and kidneys, as they functionally detoxify and excrete several toxic substances including metabolic wastes. Many renal syndromes have been reported following the use of medicinal plants, including tubular necrosis, acute interstitial nephritis, Fanconi's syndrome, hypokalemia or hyperkalemia, hypertension, papillary necrosis, chronic interstitial nephritis, nephrolithiasis, urinary retention, and cancer of the urinary tract. [START_REF] Bagnis | Herbs and the kidney[END_REF] A recent United States research study, completed by the Einstein Medical Center, Philadelphia, reported that the use of herbal and dietary supplements (HDS) has a devastating impact on consumers' quality of life, as they begin to damage the liver irreversibly and this requires a relevant clinical perspective to the diagnosis of HDS-induced liver injury (HILI). [START_REF] Rossi | Herbs and liver injury: A clinical perspective[END_REF] In fact, herbal and dietary supplements are generally used throughout the world. There is a large and varied quantity of herbal medicinal products (e.g., Ayurvedic and Chinese herbs, black cohosh, chaparral, germander, greater celandine, green tea, Herbalife, Hydroxycut, kava, pennyroyal, pyrrolizidine alkaloids, skullcap, and usnic acid), which are associated with a range of hepatotoxicity events. [START_REF] Bunchorntavakul | Review article: herbal and dietary supplement hepatotoxicity[END_REF][START_REF] Teschke | Herbal hepatotoxicity: A tabular compilation of reported cases[END_REF][START_REF] Teschke | Herbalife hepatotoxicity: Evaluation of cases with positive reexposure tests[END_REF][START_REF] Teschke | Clinical and causality assessment in herbal hepatotoxicity[END_REF][START_REF] Teschke | Herbal hepatotoxicity: A critical review[END_REF][START_REF] Teschke | Severe hepatotoxicity by Indian Ayurvedic herbal products: A structured causality assessment[END_REF][START_REF] Woodward | The potential impact of the use of homeopathic and herbal remedies on monitoring the safety of prescription products[END_REF] Progress in the understanding of the epidemiology of induced cell and organ injuries, the pathogenesis, clinical observations, and consequences is required to be able to advance herbal medicine safety.

Conclusion

In both developed and developing countries, self-medication and consulting community networks for many herbal medicines tend to decrease monitoring of treatment adherence, as do adverse effects, which patients may not always mention. More specifically, the African reality clearly shows that natural products are perceived as safe and secure with herbal medicines at sustainable low prices. In general, AHM products have some potential side effects (dose-related, timerelated, or failure of therapy) that can damage a basic structural, functional, and biological unit of the organism, such as a cell (cytotoxicity) or an organ such as the kidney (nephrotoxicity) or the heart (cardiotoxicity) or the liver (hepatotoxicity). Particularly, the studied medicinal plants can cause problems in some systems of the human body (e.g., cardiovascular system, digestive system, and nervous system). Thus, with our research sample (Pygeum africanum, wild wisteria, Madagascar rosy periwinkle, round leaf Buchu, South African geranium, Hoodia cactus, red spinach, bird flower, Impila, ox-eye daisy, khat leaf, and licorice), we have noticed some adverse drug reactions with several clinical manifestations of toxic effects of plants that cause gastrointestinal, respiratory, cardiovascular, and neurological disorders. Despite their lack of knowledge of physiopathology and physiomolecular processes, traditional medicine practitioners often possess information and experienced knowledge that is not yet widely or universally known and insufficiently used. However, these practitioners should be equipped with adequate knowledge of the pharmacological properties of medicinal plants to be able to serve as a guide for them to easily identify the information needed for the interpretation of adverse medical effects and counselling patients. Although many important plants of Africa with ethnopharmacological uses could have potential biological activities, there are a number of the active principles (e.g., alkaloids, cardiac glycosides, phorbol esters, lectins, and cyanogenic glycosides) in these medicinal plants that are extremely toxic. Finally, medicinal substances in the African traditional pharmacopoeia must comply with the international Pharmacopoeia and WHO recommendations, to offer good quality products and safe services. These improvements would have a considerable compact on the physical, mental, and social benefits of traditional medicine in development of both preventative and therapeutic health care services to patients in the field of integrative medicine.

Table 1 -

 1 Examples of medicinal plants with their potential adverse drug reactions.

	Medicinal plants	Traditional uses	Potential adverse effects	Origin
	Pygeum africanum	Prostate cancer, prostatitis,	Gastrointestinal upsets 13	Cameroon, South Africa,
	(Prunus africana)	benign prostatic hyperplasia,		and Madagascar
		other urinary tract infections,
		and aphrodisiac
	Wild wisteria, violet tree	Laxative, nervous system	Acute kidney (cortical necrosis,	Tanzania, Malawi,
	(Securidaca	ailments (epilepsy), wounds,	acute interstitial nephritis), injury,	Soudan, Burkina Faso,
	longepedunculata)	sores, coughs, venereal	diarrhea, dehydration, and	Congo, Zambia, and
		diseases, snakebites,	collapse 14	Zimbabwe
		bilharzias, headaches, fever
		related to malaria, erectile
		dysfunction or aphrodisiac,
		dysmenorrhea, and abortion
		induction
	Madagascar rosy	Cancer chemotherapy	Medullary aplasia, leucopoenia,	Madagascar
	periwinkle		incoordination of movements,
	(Catharanthus roseus)		convulsions, fatigue, mucositis,
			constipation, and neutropenia of
			short duration 15
	Round leaf Buchu	Diuretic and urinary tract	Gastrointestinal irritation, and	South Africa
	(Agathosma betulina)	antiseptic, arthritis, treatment	centrilobular hepatic or
		of cellulite, cystitis, diarrhea,	hepatocellular necrosis 16
		flatulence, kidney infections,
		nausea, rheumatism, and
		wounds
	Umckaloabo or South	Coughs, upper respiratory tract	Gastrointestinal complaints	South Africa
	African Geranium	irritations and infections	(nausea, heartburn, diarrhea), skin
	(Pelargonium sidoides)	(bronchitis, sinusitis, and	rashes, and allergic
		pneumonia, tonsillitis, and	(hypersensitivity) reactions 17
		rhinopharyngitis),
		gastrointestinal disorders, and
		pain
	Hoodia cactus	Appetite suppressant and	Potentiation of diabetes mellitus	South Africa and
	(Hoodia gordonii)	anorectic action	(hyperglycemia), sometimes	Namibia
			hypoglycemia and confusions 18
	Red spinach (also	Diuresis [high blood pressure,	Hypotension, skin irritations, to	Africa (e.g., Ethiopia,
	known as Chinese	kidney infections, obesity, and	extensive organ and tissue	South Africa, Kenya,
	spinach, Hon-toi-moi,	the edema associated with	damage with death induction 19	and Uganda), Asia,
	Yin choy, Hsien tsai)	premenstrual syndrome (PMS)		India, Europe, West
	or Spleen amaranth	or traumatic injuries]		Indies, North America,
	(Amaranthus dubius)			and South America
	Bird flower (Crotalaria	Dysmenorrhea and abortion	Acute kidney injury, hepatic	Africa (e.g., Zimbabwe)
	laburnifolia)	induction 20	veno-occlusive disease, pulmonary	and Asia (e.g., Sri Lanka)
			injury, and thrombocytopenia
	Impila, ox-eye daisy	Impotence, evil spirits, and	Chronic renal disease, acute	North and South Africa,
	(Callilepis laureola)	gastrointestinal complaints 21	kidney injury, hyperkalemia,	and Mediterranean
			abdominal pain, vomiting,	Basin
			diarrhea, a disturbed level of
			consciousness, convulsions, and
			liver failure
	Khat leaf (Catha edulis)	Central stimulant action (e.g.,	Chronic kidney disease, acute	East Africa, Yemen
		management of obesity and	kidney injury (acute tubular
		depression) 22	necrosis), hepatotoxicity,
			cardiovascular diseases
			(hypertension, cerebrovascular
			ischemia, dilated cardiomyopathy,
			myocardial infarction, and
			thromboembolism), diabetes,
			sexual dysfunction, duodenal
			ulcer, and hepatitis
	Licorice (Glycyrrhiza
	glabra)

Conflicts of interest

All authors declare no conflicts of interest.


Romain Negrel
email: romain.negrel@ensea.fr

David Picard
email: picard@ensea.fr

Philippe-Henri Gosselin
email: gosselin@ensea.fr

Efficient Metric Learning Based Dimension Reduction Using Sparse Projectors For Image Near Duplicate Retrieval

In this paper, we tackle the storage and computational cost of linear projections used in dimensionality reduction for near duplicate image retrieval. We propose a new method based on metric learning with a lower training cost than existing methods. Moreover, by adding a sparsity constraint, we obtain a projection matrix with a low storage and projection cost. We carry out experiments on a well known near duplicate image dataset and show our algorithm behaves correctly. Retrieval performances are shown to be promising when compared to the memory footprint and the projection cost of the obtained sparse matrix.

I. INTRODUCTION

In this paper, we focus on dimensionality reduction methods for near duplicate image retrieval (NDIR). The goal of NDIR is to retrieve images matching a given query (e.g., images of the same building) from a large set of images. The most successful methods in this area are based on the extraction of local visual descriptors which are then aggregated into an image signature [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF]. As the most efficient signatures are high dimensional, a projection into a small subspace is needed when dealing with large scale datasets [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF]. Even when current dimensionality reduction methods provide low dimensional signatures with good retrieval accuracies, they suffer a high projection cost. Both the memory needed to store the projectors and the computational cost to perform the projection are often prohibitive for such methods, and are what we investigate in this paper.

More specifically, we propose a new method to dramatically reduce the memory footprint and the computational cost of such projections. This method is based on metric learning, and learns a sparse projection matrix. Our two main contributions are:

• A new metric learning based method to obtain the projection matrix with a much lower training cost than existing methods,

• The introduction of a sparsity constraint on the projectors to obtain a low storage and computational projection cost.

The rest of the paper is organized as follows: First, we give an overview of the related work in dimensionality reduction techniques used in image retrieval. Then we present metric learning methods on which our proposal is based. We explain our proposed method in section IV. In section V, we analyze the convergence of our learning method and we show results using state of the art signatures on the well known INRIA Holidays [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF] dataset, before we conclude.

II. RELATED WORK

In this section we present current methods for the reduction of visual features, as well as their main drawbacks. More specifically, we focus on methods that compute linear projectors in Hilbert spaces. The choice of linear projectors can be explained by their simplicity and their ability to deal with large datasets. Each method has its own strategy for computing the projectors, but the projection itself remains the same or very similar. We can classify these approaches into two categories: unsupervised and supervised learning.

Unsupervised approaches learn projectors using a training set of images, usually randomly sampled. The best example in this case is Principal Component Analysis (PCA) which selects components of largest variance. Furthermore, the resulting projectors are orthogonal, and projected data can be whitened [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of pca and whitening[END_REF]. Many methods are then based on these approaches, such as PCA Embedding [START_REF] Gordo | Asymmetric distances for binary embeddings[END_REF], Semi-Supervised Hashing [START_REF] Wang | Semi-supervised hashing for large scale search[END_REF], Spectral Hashing [START_REF] Weiss | Spectral hashing[END_REF] or Tranform Coding [START_REF] Brandt | Transform coding for fast approximate nearest neighbor search in high dimensions[END_REF]. In the context of image retrieval, these methods provide high dimensional reduction with low information lost. For example, visual signatures of hundreds of thousands of dimensions can be reduced to few hundreds, and with similar retrieval performance [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF]. Supervised approaches learn projectors using a labeled training set. The first propositions of such methods compute semantic attributes by training a classifier for each semantic concept [START_REF] Su | Improving object classification using semantic attributes[END_REF]. In this case, projectors are the classification functions, and are as numerous as the number of semantic concepts. Other approaches are based on metric learning that aims to learn a similarity function between two visual features. Other methods are based on the combination of kernel functions, a.k.a. Multiple Kernel Learning [START_REF] Bach | Multiple kernel learning, conic duality, and the smo algorithm[END_REF]. All these methods are proposed in a context of image categorization, and their effectiveness for image retrieval is yet to be shown. However, recent approaches in this scope have been proposed for image retrieval. A first one is based on semantic attributes [START_REF] Douze | Combining attributes and fisher vectors for efficient image retrieval[END_REF] and a second one is based a joint subspace and classification learning [START_REF] Gordoa | Leveraging category-level labels for instance-level image retrieval[END_REF]. In both cases, these methods outperforms unsupervised approaches for near duplicate image retrieval.

Current methods suffer from a major drawback: the size of projectors is as large as the size of visual features. Consequently, even if the size of reduced visual features is small and scalable, the projection itself is not scalable. Actually, since the size of best visual features is at least hundreds of thousands of dimensions, the corresponding projection matrix quickly becomes very large. Such matrix is thus difficult to spread on a computational grid, or simply too large to fit in memory.

Let us note the projection matrix could be compressed using techniques like Product Quantization [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF], like it is often the case for the output signatures. However, the projection would then become non-linear and have a higher computational cost, which is already prohibitive with the linear projection due to its size.

III. METRIC LEARNING

As metric learning approaches offer promising results [START_REF] Gordoa | Leveraging category-level labels for instance-level image retrieval[END_REF], we discuss their key concepts and drawbacks in this section.

The general idea is to learn a parametric similarity function using a training set I = {1, . . . , N } for which a groundtruth is available. The groundtruth is formed by a set of queries Q ⊂ I. For each query q ∈ Q, we have a set P q ⊂ I of positive images (images similar to the query) and a set N q = I \ P q of negatives images (images dissimilar to the query). The learning task is to find the optimal parameters of the similarity function such that the obtained similarity is as close as possible to the groundtruth. The most popular parametric similarity function is

d W (x i , x j ) = x ⊤ i Wx j , (1)
with x i , x j two vectors in R D and W ∈ R D×D . Note that d I (x i , x j ) corresponds to a dot-product in some linear subspace if W is positive definite.

The main problem of this parametric similarity function is the number of parameters that increases quadratically with the dimension of the input space. Thus, for high dimensional vectors the computational cost to learn W is prohibitive. In [START_REF] Bai | Supervised semantic indexing[END_REF] Bai et al. proposed to solve this problem by decomposing W = UU ⊤ with U ∈ R D×R and R < D. Eq.( 1) then becomes:

d U (x i , x j ) = x ⊤ i UU ⊤ x j = U ⊤ x i ⊤ U ⊤ x j . (2)
In this form, and with R fixed, the number of parameters increases linearly with the dimension of the the input space. Eq. ( 2) provides a linear projection in a subspace of dimension R:

y i = U ⊤ x i . ( 3
)
y i is then a low dimensional vector giving the same similarity when used with the standard dot product as d U .

In [START_REF] Bai | Supervised semantic indexing[END_REF] the authors proposed a method for learning U so as to preserve the ranking between positive and negative samples. They state a good similarity measure should satisfy the following sets of constraints:

{d U (x q , x i ) > d U (x q , x j )} q∈Q,i∈Pq,j∈Nq . (4)
Then, they propose an objective function to minimize, with a loss function that measures how much these constraints are violated:

q∈Q i∈Pq j∈Nq [1 -d U (x q , x i ) + d U (x q , x j )] + , (5)
with [x] + = max(0, x). As it is impossible to go through all the triplets (q, i, j) ∈ Q × P q × N q , the authors propose to perform a stochastic gradient descent (SGD) to optimize the objective. In [START_REF] Law | Quadruplet-wise image similarity learning[END_REF], the authors argue that the triplet groundtruth is sometimes difficult to obtain. They propose to generalize the triplets with quadruplets

{x 1 , x 2 , x 3 , x 4 } for which d U (x 1 , x 2 ) > d U (x 3 , x 4
), and find it more convenient to optimize. However, the number of constraints grows to the power 4, which makes such methods impracticable for large datasets.

All the methods presented here share the same drawbacks when dealing with image retrieval. First they take into account a huge number of constraints. In particular, the training set has to be of a sufficient size to cope with the wide variety of images, and consequently the learning procedure has to scale with such large training sets. Secondly, the concerns over the size of the projection matrix stated in the previous section still holds for these methods. Both of these drawbacks make such methods unsuitable for large scale image retrieval.

IV. PROPOSED METHOD

Int this section, we present our main contribution: a new projection matrix for significantly reducing the size of large signatures with a low storage cost and computational cost. Our projection matrix is based on metric learning approaches for ranking problems with a sparsity constraint.

We aim at a projection matrix U that maximizes the mean Average Precision (mAP) used in NDIR. However, the mAP is difficult to optimize directly. On the contrary, it is easy and sufficient to define a set of constraints on the similarity function such that the mAP is maximal: For each query q, the scores of positive images have to be greater than the scores of negative images, i.e., the constraints described in Eq. 4. As already stated in the previous section, the number of such constraints is very large ( q∈Q card(P q ) card(N q )), and the learning cost of such metric becomes prohibitive.

1) Learning with pivot:

To reduce the number of constraints, we introduce for each query q a pivot image p q ∈ N q belonging to the negative images set N q . We thus obtain a new set of constraints:

{d U (x q , x i ) > d U (x q , x pq )} i∈Pq , {d U (x q , x pq ) ≥ d U (x q , x j )} j∈Nq\pq . (6)
The number of constraints is now q∈Q (card(P q ) + card(N q ) -1) which is far less than the original set of constraints [START_REF] Jégou | Negative evidences and co-occurences in image retrieval: The benefit of pca and whitening[END_REF]. It is easy to show that if this set of constraints is respected the mAP is maximal. Any image in N q can be selected as pivot. In order to stay as close a possible to the original signatures, we propose to select the negative image with the largest score using the original signatures.

Then, to learn the metric d U that aims at this set of constraints, we define for each query q an objective function to minimize using the squared loss:

f q (U) = α q i∈Pq [ε + ∆d U (q, i, p q )] 2 + +β q j∈Nq\pq [∆d U (q, p q , j)] 2 + (7)
with

α q = 1 i∈Pq h(ε + ∆d U (q, i, p q )) , (8)
β q = 1 j∈Nq\pq h(∆d U (q, p q , j)) , (9)
∆d U (q, i, j) = d U (x q , x i ) -d U (x q , x j ), ( 10
) = d U (x q , ∆x ij ), (11)
∆x ij = x i -x j , (12)
and h the Heaviside step function and ε a margin (e.g., ε = 10 -6 ). Note that depending on the margin, all constraints can be achieved before the objective function reaches 0. The squared loss gives more importance to very poorly sorted images, i.e., the ones having the biggest influence on the mAP. The global optimization problem can be written as follows:

U * = arg min U q∈Q f q (U) (13)
To solve this problem, we propose to use a Stochastic Gradient Descent (SGD) [START_REF] Bottou | Stochastic learning[END_REF], [START_REF] Shalev-Shwartz | Pegasos: Primal estimated sub-gradient solver for svm[END_REF] improved by using active learning. The gradient for one query q is ∂ fq(U) ∂U = αq i∈Pq h(ε + ∆d U (q, i, pq))(ε + ∆d U (q, i, pq))A qi U + βq j∈Nq h(∆d U (q, pq, j)) ∆d U (q, pq, j)A qj U,

with

A qi = x q ∆x ⊤ pqi + ∆x pqi x ⊤ q .
The training procedure consists in repeating the two following steps:

1) we select a subset Qt of P queries, 2) perform the gradient update on Qt .

To select a subset Qt of P queries, we select the half among the higher value of {f q (U t )} q∈Q (active learning part) and the other half by random sampling (stochastic part). The gradient update is then

U t+1 = U t + µ t q∈ Qt ∂ f q (U t ) ∂U (15)
with µ t the learning rate computed by golden section search [START_REF] Avriel | Optimality proof for the symmetric fibonacci search technique[END_REF].

In [START_REF] Bai | Supervised semantic indexing[END_REF] the authors show that good results are obtained by initializing the values of U randomly. We propose to reduce the convergence time by initializing U with the unsupervised projectors proposed in [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF]. We stop the algorithm when the value of objective function is near the numerical precision (e.g., 10 -16 ) or when the maximum number of iterations is reached (e.g., 2000).

2) Learning with sparsity constraint: Furthermore, we propose to add a sparsity constraint on U to obtain a projection matrix with a low storage cost and a low projection cost. For this, we add a ℓ 0 norm constraint on each column u i of matrix U. We can then rewrite the global optimization problem [START_REF] Gordoa | Leveraging category-level labels for instance-level image retrieval[END_REF] as follows:

U * = arg min As described in Algorithm 1, we use the same algorithm as presented in the previous section to solve the sparse problem, only adding a step of projection onto the ℓ 0 norm constraint. The projection of u i onto the ||u i || 0 = M constraint is performed by thresholding the smaller absolute values:

U q∈Q f q (U) s.t. ||u i || 0 = M, ∀i; (16)
ûki = u ki h(|u ik | -∇ i ), ∀k (17)
with ∇ i ∈ R + the threshold selected to comply with the sparsity constraint.

Although such operation is non-smooth and might hinder the convergence of the algorithm, we empirically show that our algorithm behaves correctly in the experiments.

It is sometimes more useful to define the sparsity constraint independently of the dimension of the input vectors. To this end, we note by τ the rate of zero values in a sparse matrix:

τ (U) = Number of zero values in U Number of values in U . ( 18
)
In the case of our matrix U constrained by ℓ 0 norm, we have the following relation between M and τ :

τ (U) = D -M D . ( 19
)
In the experiments, we use τ instead of M to measure the impact of the sparsity constraint on our algorithm. [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] ON THE TESTING SET.

V. EXPERIMENTS

In this section, we present our experimental protocol and the evaluation of our proposed method.

A. Dataset and Experimental Protocol

To evaluate our method, we use the well known benchmark INRIA Holidays [START_REF] Jegou | Hamming embedding and weak geometric consistency for large scale image search[END_REF]. Holidays dataset is a set of images (typically personal holiday photographs) ; it contains 1,491 images gathered in 500 groups. Each group is composed of one query image and up to 4 images of correct retrieval results. Evaluation on this dataset is obtained by computing the mean average precision (mAP) over all queries.

Since we need a training set to learn our projectors, we split the image groups of Holidays dataset in two separate sets: a training set and a testing set. The two sets are composed of 250 groups randomly and independently sampled. We use the same evaluation protocol as for the whole Holidays dataset to evaluate both the training and testing subsets.

B. Signatures

For all our experiments, we perform a two-step preprocessing on all images: (a) image resizing (to a maximum width of 512 pixels); (b) histogram equalization. We use the HOG local descriptors (128-dimensional) [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF], extracted on a regular dense grid of 3 pixels at 4 scales. We use this descriptors to compute "Vector Aggregating Local Descriptors" (VLAD) [START_REF] Jégou | Aggregating local descriptors into a compact image representation[END_REF] and "Fisher Vector" (FV) [START_REF] Perronnin | Large-scale image retrieval with compressed fisher vectors[END_REF] signatures with a codebook of 64, 128, 256 and 512 codewords trained only using the training set. We compute the VLAD signature with a Principal Component Analysis (PCA) cluster-wise [START_REF] Negrel | Using spatial pyramids with compacted vlat for image categorization[END_REF] which preserves 80 dimensions by cluster. For the FV signature, we perform a PCA on local descriptors that preserves 80 dimensions. Finally, we perform a power-normalization (for all experiments set to 0.1) and ℓ 2 -normalization on both signatures.

As a baseline, Table I shows the mAP on the testing set obtained by the original signatures and by the reduced signatures using the unsupervised method proposed in [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF]. Rows are the differents signatures (e.g., VLAD-64 is VLAD signature with a codebook of 64 clusters). The second column is the size of original signatures, the third column is the mAP for the original signatures, and from the fourth to the seventh column are the mAP of reduced signatures for different values of the output dimension R. We can see that for original signatures, Fisher Vectors provide better results than VLAD, the best result being obtain with FV-256 (88.1% of mAP). For the reduced signatures, the best results are always obtained with the maximum output dimension R = 256.

C. Convergence Analysis

In this section we analyze the convergence of the proposed algorithm with and without the sparsity constraint. For all experiments in this section we use Fisher Vectors with a codebook of 512 clusters, i.e., an original size 82k dimensions.

Figure 2(a) shows the evolution of the objective function without the sparsity constraint for different values of R. We see that the proposed algorithm minimizes the objective function. Furthermore, the convergence rate seems to be exponential. We note that the proposed algorithm needs more iterations to converge with small values of R. However, even for very small value of R, our algorithm converges, meaning all constraints are respected. (sparsity rate of matrix U). We see that the proposed algorithm always decreases the objective function, albeit with a slower the convergence rate. We note that the higher the sparsity, the slower the convergence. 100%, provided the sparsity constraint does not hinder the convergence speed enough to achieve the optimal objective value in reasonable time.

D. Retrieval performances

Now, we focus on the generalization capability of our method by training the projectors on the training set and evaluating the mAP on the testing set.

Figure 4 shows the evolution of mAP on the training set and the testing set with the sparsity constraint fixed at τ =99% for different values of R. We see our algorithm increases the mAP on the testing set. This increase is even bigger when the number of projectors is small (e.g., 22% mAP increase with R = 32). Note that the mAP quickly stabilizes on the testing set, even if the algorithm has not fully converged.

Table II shows the mAP on the testing set obtained by the reduced signatures using our sparse projectors. Rows are the different signatures. The second to the fifth columns are reported the mAP with τ = 90% for different values of R, and from the sixth to the ninth columns are reported the mAP with τ = 99% for different values of R. We can see the mAP also increases with R.

If we compare the performance of the obtained signatures and the performance of signatures obtained with the method presented in [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] (Table I), we can see that at equivalent final dimension, the signatures of [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF] provide better results (e.g., for R = 256 the FV-256 provides 86.38% of mAP with [START_REF] Negrel | Web-scale image retrieval using compact tensor aggregation of visual descriptors[END_REF], 84.31% of mAP with our sparse projectors at τ = 90%, and 83.21% of mAP with our sparse projectors at τ = 99%). However, note that 256 projectors with τ = 99% have the same storage cost that 2,6 full projectors. For the FV-256 signatures the mAP with 256 sparse projectors at τ = 99% is 83.21%, whereas it is 78.39% when using 32 full projectors that are still 12,5 times more costly to store and use.

VI. CONCLUSION

In this paper, we tackle the storage and computational cost of dimensionality reduction techniques for near duplicate image retrieval. We proposed a new method based on metric learning to train a sparse projection matrix. To learn the matrix, we propose an efficient algorithm based on stochastic gradient descent coupled with an active learning strategy. Using state of the art input signatures, we carried out a study of the convergence of our method on the INRIA Holidays dataset. By evaluating the performance of our projectors, we show promising results with a much lower storage and computational projection cost than existing methods.

Fig. 1 .

 1 Fig. 1. Images from Holidays dataset [3].

Figure 2 (

 2 Figure 2(b) shows the evolution of mAP on the training set without the sparsity constraint for different values of R. We see the mAP increases up to 100% (perfect sorting of images for all the queries), which is consistent with the objective function converging to 0.

Figure 3 (

 3 Figure 3(a) shows the evolution of the objective function with the sparsity constraint for different values of τ (U) (sparsity rate of matrix U). We see that the proposed algorithm always decreases the objective function, albeit with a slower the convergence rate. We note that the higher the sparsity, the slower the convergence.

Figure 3 (Fig. 2 .

 32 Figure 3(b) shows the evolution of mAP on Train set with the sparsity constraint for different values of τ (U). Again, we see our algorithm is able to increase the mAP up to

Fig. 3 .

 3 Fig. 3. Objective function and mAP evolution on the training set for various sparsity rates.

Fig. 4 .

 4 Fig. 4. mAP on training set and testing set vs algorithm iteration

  with || • || 0 the ℓ 0 norm and M the number of non-zero entries by columns of matrix U.

	Algorithm 1 Rank optimized projectors with ℓ 0 constraint
	t ← 1.
	Initialize the matrix U 1 with the projection provided with
	unsupervised algothims of paper [9].

Project U 1 onto the ||u i || 0 = M constraint. repeat Select a subset Qt of P query in Q. Compute the gradient on the subset Qt . Compute the optimal learning rate µ t . Perform the gradient update to compute U t+1 Project U t+1 onto the ||u i || 0 = M constraint. t ← t + 1. until objective function < 10 -12 or t > maxIter

TABLE I .

 I

MAP (IN %) OF VLAD AND FV SIGNATURES AND REDUCED SIGNATURES USING

TABLE II .

 II PERFORMANCES OF REDUCE SIGNATURE WITH SPARSITY ON THE TESTING SET (MAP IN %).