text:
Once consumers can access this content, they want to engage with something that fits their needs and is sensory and interactive — from the early popularity of web portals to the spread of online video, to the next generation virtual realities. Their digital desires are marked by a thirst for content. The old media adage that “content is king" is correct. There is no question that the desire to engage with content is a key driver of customer behavior.
Think about the words that a user might search for to find a piece of your content. Users who know a lot about the topic might use different keywords in their search queries than someone who is new to the topic. For example, a long-time football fan might search for [fifa], an acronym for the Fédération Internationale de Football Association, while a new fan might use a more general query like [football playoffs]. Anticipating these differences in search behavior and accounting for them while writing your content (using a good mix of keyword phrases) could produce positive results. Google Ads provides a handy Keyword Planner34 that helps you discover new keyword variations and see the approximate search volume for each keyword. Also, Google Search Console provides you with the top search queries your site appears for and the ones that led the most users to your site in the Performance Report35.
To avoid undesirable content in the search indexes, webmasters can instruct spiders not to crawl certain files or directories through the standard robots.txt file in the root directory of the domain. Additionally, a page can be explicitly excluded from a search engine's database by using a meta tag specific to robots (usually ). When a search engine visits a site, the robots.txt located in the root directory is the first file crawled. The robots.txt file is then parsed and will instruct the robot as to which pages are not to be crawled. As a search engine crawler may keep a cached copy of this file, it may on occasion crawl pages a webmaster does not wish crawled. Pages typically prevented from being crawled include login specific pages such as shopping carts and user-specific content such as search results from internal searches. In March 2007, Google warned webmasters that they should prevent indexing of internal search results because those pages are considered search spam.[46]
And if you really want to know what are the most important, relevant pages to get links from, forget PageRank. Think search rank. Search for the words you’d like to rank for. See what pages come up tops in Google. Those are the most important and relevant pages you want to seek links from. That’s because Google is explicitly telling you that on the topic you searched for, these are the best.
Although GoTo.com started PPC in 1998, Yahoo! did not start syndicating GoTo.com (later Overture) advertisers until November 2001.[14] Prior to this, Yahoo's primary source of SERPS advertising included contextual IAB advertising units (mainly 468x60 display ads). When the syndication contract with Yahoo! was up for renewal in July 2003, Yahoo! announced intent to acquire Overture for $1.63 billion.[15] Today, companies such as adMarketplace, ValueClick and adknowledge offer PPC services, as an alternative to AdWords and AdCenter.  8. Technical SEO. Technical SEO is one of the most intimidating portions of the SEO knowledge base, but it’s an essential one. Don’t let the name scare you; the most technical elements of SEO can be learned even if you don’t have any programming or website development experience. For example, you can easily learn how to update and replace your site’s robots.txt file, and with the help of an online template, you should be able to put together your sitemap efficiently.  Lost IS (rank), aka “Quality Score too low” – Are your Keyword Quality Scores (QS) below 5/10? Per Google, since “Ad Rank” is a calculation of your Bid and QS, it would behoove you to improve Quality Scores by focusing on increasing CTRs in your Ads and Keywords. Improve CTRs by tightening up Ad Groups that only consist of closely related keywords and Ads that are the most relevant to these keywords.  Pagerank has recently been used to quantify the scientific impact of researchers. The underlying citation and collaboration networks are used in conjunction with pagerank algorithm in order to come up with a ranking system for individual publications which propagates to individual authors. The new index known as pagerank-index (Pi) is demonstrated to be fairer compared to h-index in the context of many drawbacks exhibited by h-index.[61]  Unlike most offline marketing efforts, digital marketing allows marketers to see accurate results in real time. If you've ever put an advert in a newspaper, you'll know how difficult it is to estimate how many people actually flipped to that page and paid attention to your ad. There's no surefire way to know if that ad was responsible for any sales at all. Optimization techniques are highly tuned to the dominant search engines in the target market. The search engines' market shares vary from market to market, as does competition. In 2003, Danny Sullivan stated that Google represented about 75% of all searches.[63] In markets outside the United States, Google's share is often larger, and Google remains the dominant search engine worldwide as of 2007.[64] As of 2006, Google had an 85–90% market share in Germany.[65] While there were hundreds of SEO firms in the US at that time, there were only about five in Germany.[65] As of June 2008, the marketshare of Google in the UK was close to 90% according to Hitwise.[66] That market share is achieved in a number of countries.  For any webmaster, it is important to know the rank of its web pages using a quality PR checker in order to maintain the health of its websites. One of the simplest ways to achieve that is to make use of some PR Checker tool. PR Checker is a tool that you can use to determine the significance of any webpage. It is one of the key factors that are used to determine which web pages appear in the search results and how do they rank. Keep in mind that the results of PR Checker can have significant influence on your overall Google ranking. This PR checker tool will help you to check page rank of any web page. This shows the number of pages indexed by Google that match your keyword search. If your search is very general (such as “tulips”) you will get more pages of results than if you type something very specific. Of course, probably no one in the history of the Internet has ever paged through these to see the last page of results when there are thousands of pages of results. Most users stick to the first page of results, which is why your goal as a search engine optimizer should be to get on the first page of results. If users aren’t finding what they are looking for, instead of continuing to page through dozens of SERPs, they are more likely to refine their search phrase to make it more specific or better match their intention. ### By using Internet platforms, businesses can create competitive advantage through various means. To reach the maximum potential of digital marketing, firms use social media as its main tool to create a channel of information. Through this a business can create a system in which they are able to pinpoint behavioral patterns of clients and feedback on their needs.[30] This means of content has shown to have a larger impingement on those who have a long-standing relationship with the firm and with consumers who are relatively active social media users. Relative to this, creating a social media page will further increase relation quality between new consumers and existing consumers as well as consistent brand reinforcement therefore improving brand awareness resulting in a possible rise for consumers up the Brand Awareness Pyramid.[31] Although there may be inconstancy with product images;[32] maintaining a successful social media presence requires a business to be consistent in interactions through creating a two way feed of information; firms consider their content based on the feedback received through this channel, this is a result of the environment being dynamic due to the global nature of the internet.[29] Effective use of digital marketing can result in relatively lowered costs in relation to traditional means of marketing; Lowered external service costs, advertising costs, promotion costs, processing costs, interface design costs and control costs.[32] Google has a very large team of search quality raters that evaluate the quality of search results, that gets fed into a machine learning algorithm. Google’s search quality rater guidelines provide plenty of detail and examples of what Google class as high or low quality content and websites, and their emphasis on wanting to reward sites that clearly show their expertise, authority and trust (EAT). In both cases the total PageRank in the site is 3 (the maximum) so none is being wasted. Also in both cases you can see that page A has a much larger proportion of the PageRank than the other 2 pages. This is because pages B and C are passing PageRank to A and not to any other pages. We have channeled a large proportion of the site’s PageRank to where we wanted it. Columns are another cross advertising platform feature that shows pre-determined metrics. Columns can be edited on all tabs within the engine interfaces. You can add data such as assisted conversations, competitive impression share metrics, conversion data calculations, and more. Columns act as a great way to customize the interface and view for your goals and analysis needs. Another classic example of a custom combination is targeting people who have visited the cart of an eCommerce site, while excluding those who have already purchased an item. This strategy allows you to target people who came close to buying, but didn’t. They are often persuaded into purchasing with an ad that gives them a bit of a discount or free shipping. A clearly defined online customer value proposition tailored to your different target customer personas will help you differentiate your online service encouraging existing and new customers to engage initially and stay loyal. Developing a competitive content marketing strategy is key to this for many organizations since the content is what engages your audiences through different channels like search, social, email marketing and on your blog. Customer acquisition costs money. Whether you write a check for a billboard, pay for a radio spot or invest in online marketing, advertising costs money. The good news is, PPC marketing is one of THE most accountable and measurable forms of marketing. So start spending. Create a budget you’re comfortable with, spend money to buy test traffic and take copious notes on what works and what doesn’t for your business. While ordinary users were not that interested in pages' scores, SEOs of a different caliber felt that this was a great opportunity to make a difference for their customers. This obsession of SEOs with PageRank made everyone feel that this ranking signal is more or less the only important one. In spite of the fact that pages with a lower PR score can beat those with a higher score! What did we receive then, as a result? All major crawler-based search engines leverage links from across of the web, but none of them report a static “importance” score in the way Google does via its Google Toolbar. That score, while a great resource for surfers, has also provided one of the few windows into how Google ranks web pages. Some webmasters, desperate to get inside Google, keep flying into that window like confused birds, smacking their heads and losing their orientation…. “I have been very pleased with the responsiveness, diligent work efforts and creative ideas Brick Marketing has shown me since we started our organic SEO optimization campaign. My account executive has provided great support and has written relevant and timely articles for our website blog. Her willingness to go above and beyond to achieve the best possible results is very evident. I would recommend Brick Marketing to anyone looking to enhance their online business profile.” In February 1998 Jeffrey Brewer of Goto.com, a 25-employee startup company (later Overture, now part of Yahoo!), presented a pay per click search engine proof-of-concept to the TED conference in California.[11] This presentation and the events that followed created the PPC advertising system. Credit for the concept of the PPC model is generally given to Idealab and Goto.com founder Bill Gross.[12] ###### The overall rule of thumb? Focus, focus, focus. Organic search engine optimization is a PR-based, long-term attempt to grow your brand and image. Pay per click advertising, however, should be handled like any other form of paid advertising: proactively, and with a clear, quantifiable short- or medium-term goal in mind. In other words: concentrate on conversions, not just clicks. The PageRank formula also contains a damping factor (d) . According to the PageRank theory, there is an imaginary surfer who is randomly clicking on links, and at some point he gets bored and eventually stops clicking. The probability that the person will continue clicking at any step is a damping factor. Thus, this factor is introduced to stop some pages having too much influence. As a result, their total vote is damped down by multiplying it by 0.85 (a generally assumed value). Among PPC providers, Google AdWords, Microsoft adCenter and Yahoo! Search Marketing had been the three largest network operators, all three operating under a bid-based model.[1] For example, in the year 2014, PPC(Adwords) or online advertising attributed approximately$45 billion USD of the total \$66 billion USD of Google's annual revenue[16] In 2010, Yahoo and Microsoft launched their combined effort against Google, and Microsoft's Bing began to be the search engine that Yahoo used to provide its search results.[17] Since they joined forces, their PPC platform was renamed AdCenter. Their combined network of third party sites that allow AdCenter ads to populate banner and text ads on their site is called BingAds.[18]

We're a growth company looking for a highly experienced Pay Per Click manager to launch and optimize campaigns in Google Adwords, Bing Ads, and more with a focus on B2B. Looking for 5+ experience: - managing enterprise campaigns in Adwords and Bing - tracking and optimizing to goals - executing a/b tests in adwords and bing - reporting and optimizing campaigns We are a fast moving, well funded, profitable startup in search of someone who is highly experienced, and able to respond quickly to the campaign needs of our business.

Write a description that would both inform and interest users if they saw your description meta tag as a snippet in a search result. While there's no minimal or maximal length for the text in a description meta tag, we recommend making sure that it's long enough to be fully shown in Search (note that users may see different sized snippets depending on how and where they search), and contains all the relevant information users would need to determine whether the page will be useful and relevant to them.
So, although adding new pages does increase the total PageRank within the site, some of the site’s pages will lose PageRank as a result. The answer is to link new pages is such a way within the site that the important pages don’t suffer, or add sufficient new pages to make up for the effect (that can sometimes mean adding a large number of new pages), or better still, get some more inbound links.
When calculating PageRank, pages with no outbound links are assumed to link out to all other pages in the collection. Their PageRank scores are therefore divided evenly among all other pages. In other words, to be fair with pages that are not sinks, these random transitions are added to all nodes in the Web, with a residual probability usually set to d = 0.85, estimated from the frequency that an average surfer uses his or her browser's bookmark feature.
Digital marketing methods such as search engine optimization (SEO), search engine marketing (SEM), content marketing, influencer marketing, content automation, campaign marketing, data-driven marketing,[6] e-commerce marketing, social media marketing, social media optimization, e-mail direct marketing, display advertising, e–books, and optical disks and games are becoming more common in our advancing technology. In fact, digital marketing now extends to non-Internet channels that provide digital media, such as mobile phones (SMS and MMS), callback, and on-hold mobile ring tones.[7] In essence, this extension to non-Internet channels helps to differentiate digital marketing from online marketing, another catch-all term for the marketing methods mentioned above, which strictly occur online.
(1 - d) - The (1 – d) bit at the beginning is a bit of probability math magic so the “sum of all web pages' PageRanks will be one”: it adds in the bit lost by the d(.... It also means that if a page has no links to it (no backlinks) even then it will still get a small PR of 0.15 (i.e. 1 – 0.85). (Aside: the Google paper says “the sum of all pages” but they mean the “the normalised sum” – otherwise known as “the average” to you and me.
Search engine advertising is one of the most popular forms of PPC. It allows advertisers to bid for ad placement in a search engine's sponsored links when someone searches on a keyword that is related to their business offering. For example, if we bid on the keyword “PPC software,” our ad might show up in the very top spot on the Google results page.
I think Google will always be working to discern and deliver “quality, trustworthy” content and I think analyzing inbound links as endorsements is a solid tool the SE won’t be sunsetting anytime soon. Why would they? If the president of the United States links to your page that is undoubtedly an endorsement that tells Google you’re a legitimate trusted source. I know that is an extreme example, but I think it illustrates the principals of a linking-as-endorsement model well.

### Over the years, the composition of search engine results pages have changed dramatically. Most recently, the world’s number one search engine, Google, removed ads from it’s “right rail” on desktop search, and moved these ads where organic search engine results used to live. This new SERP layout now pushes organic search results well below the visible page fold on desktop, leaving only the Ad blocks and local pack visible to the searcher.

We are going to look at some example calculations to see how a site’s PageRank can be manipulated, but before doing that, I need to point out that a page will be included in the Google index only if one or more pages on the web link to it. That’s according to Google. If a page is not in the Google index, any links from it can’t be included in the calculations.

Using an omni-channel strategy is becoming increasingly important for enterprises who must adapt to the changing expectations of consumers who want ever-more sophisticated offerings throughout the purchasing journey. Retailers are increasingly focusing on their online presence, including online shops that operate alongside existing store-based outlets. The "endless aisle" within the retail space can lead consumers to purchase products online that fit their needs while retailers do not have to carry the inventory within the physical location of the store. Solely Internet-based retailers are also entering the market; some are establishing corresponding store-based outlets to provide personal services, professional help, and tangible experiences with their products.[24]

WordStream Advisor, our intuitive, centralized digital marketing management platform, makes online advertising easy. With full integration with Facebook Advertising, a suite of specialized keyword research and diagnostic tools, and intuitive, customized reporting, WordStream Advisor gives you everything you need to own the SERP and grow your business through digital marketing.
There are simple and fast random walk-based distributed algorithms for computing PageRank of nodes in a network.[31] They present a simple algorithm that takes {\displaystyle O(\log n/\epsilon )} rounds with high probability on any graph (directed or undirected), where n is the network size and {\displaystyle \epsilon } is the reset probability ( {\displaystyle 1-\epsilon } is also called as damping factor) used in the PageRank computation. They also present a faster algorithm that takes {\displaystyle O({\sqrt {\log n}}/\epsilon )} rounds in undirected graphs. Both of the above algorithms are scalable, as each node processes and sends only small (polylogarithmic in n, the network size) number of bits per round.
Many websites need to contain some outbound links that are nothing to do with PageRank. Unfortunately, all ‘normal’ outbound links leak PageRank. But there are ‘abnormal’ ways of linking to other sites that don’t result in leaks. PageRank is leaked when Google recognizes a link to another site. The answer is to use links that Google doesn’t recognize or count. These include form actions and links contained in javascript code.
Content marketing specialists are the digital content creators. They frequently keep track of the company's blogging calendar, and come up with a content strategy that includes video as well. These professionals often work with people in other departments to ensure the products and campaigns the business launches are supported with promotional content on each digital channel.

NOTE: You may be curious what your site’s or your competitor’s PR score is. But Google no longer reveals the PageRank score for websites. It used to display at the top of web browsers right in the Google Toolbar, but no more. And PR data is no longer available to developers through APIs, either. Even though it’s now hidden from public view, however, PageRank remains an important ingredient in Google’s secret ranking algorithms.
Search engines may penalize sites they discover using black hat methods, either by reducing their rankings or eliminating their listings from their databases altogether. Such penalties can be applied either automatically by the search engines' algorithms, or by a manual site review. One example was the February 2006 Google removal of both BMW Germany and Ricoh Germany for use of deceptive practices.[53] Both companies, however, quickly apologized, fixed the offending pages, and were restored to Google's list.[54]


text:
# Yao's Minimax Principle with error

In Yao's paper proving Yao's principle, he equates the lower bound of a randomized Las Vegas algorithm with the expected run time of the best deterministic algorithm on the worst input. He goes on to generalize this to Monte Carlo algorithms with error, in particular in Theorem 3:

However I do not understand how this result follows from the original principle. Could someone please explain/shed some color?

Cheers

format: plain


text:
# Is S2 still the fastest known star in the galaxy?

Wikipedia's entry for the star S2 says that it has

the fastest known ballistic orbit, reaching speeds exceeding 5,000 km/s (11,000,000 mph, or 1⁄60 the speed of light) and acceleration of about 1.5 m/s2 (almost one-sixth of Earth's surface gravity).

But the referenced link to the press release Surfing a Black Hole is dated 2002. Have any stars with faster orbital speeds at perimelasma (periapsis for a black hole orbit) in the 19 years since this press release? Is it possible that there is a star on an even faster orbital trajectory than S2 or has any such possibility been ruled out?

• I've just asked Was GRAVITY built to look at one star? and hopefully you will ask when S62 will next pass periapsis and if it was measured by GRAVITY on it's previous and if not why not; I need to disconnect from SE for a few hours and get something done!
– uhoh
Apr 3 at 5:23
• You’re talking about speed relative to what? Apr 5 at 7:44
• I am asking about the speed relative to the black hole center of mass. We could use the orbital system center of mass instead, but that would be similar since the black hole is much more massive than the star. Apr 5 at 15:45

S0-2 (I assume you mean the star orbiting the Milky Way central black hole) actually reaches speeds of 7650 km/s at periapsis.

However, if you read further down the wikipedia article you will see that there are stars S0-102 and S62 which have shorter orbital periods than S0-2 (11.5 and 9.2 years vs 16.05 years).

Star S62 is also in a highly elliptical orbit ($$e=0.976$$, Peißker et al. 2020) and has a periapsis distance that is even closer to the black hole than S0-2, where it has a speed clocking in at about 30,000 km/s$$^{1}$$. No actual value or error bar is given in the paper.

The plot shows its orbit (in red) compared with other stars in the region.

STOP PRESS

A telegram issued by Peißker et al. 2020 claims detection of a new winner - S4714. They appear to have revised downwards their estimate of the peri-centre speed of S62 to 20,000 km/s and say that this new, very faint object, has a peri-centre speed of 24,000 km/s.

$$^1$$ Of course that is the speed as seen by a distant observer. If you were to go there and put a speed gun on it as it went past, then it would be a touch larger.

• From that plot alone, the fit for the $\color{red}{\text{red orbit}}$ looks pretty weird; it's certainly not the ellipse-of-best-fit, as it'd seem more sensible if the left-hand-side were slanted upward a bit. Guessing that the plot's informed by other factors that'd make the plotted orbit seem more sensible than it appears?
– Nat
Apr 3 at 11:03
• @Nat the position of Sgr A* is known and fixed in their fitting. Apr 3 at 11:28
• These ellipses do not look confocal to me. Especially if the red, green and orange ones may be nearly confocal, their common focus is not anywhere near the focus of the blue one, no? Apr 3 at 23:03
• Perhaps you are forgetting these are the projections of ellipses onto the plane of the sky? @მამუკაჯიბლაძე Apr 3 at 23:07
• Thanks! I did not realize that (even if they are all in the same plane) confocality is not preserved under projections Apr 4 at 4:43

There are a couple of stars with smaller orbits (and hence faster average speeds) S55 and S62. Of these, S62 has a faster speed at periapsis, approximately 10% of the speed of light:

the orbital time scale is measured to be 9.9 years, the next peri-center passage will be around March 2023. During that passage, the star will have a velocity of about 10% the speed of light. (S62 on a 9.9-year orbit around SgrA*. Florian Peiβker, Andreas Eckart and Marzieh Parsa, paper in preprint in Feb 2020)


text:
### International Journal of Nonlinear Analysis and Applications

##### Stability and superstability of n-Jordan ∗-homomorphisms in Frechet locally C*-algebras

Articles in Press, Corrected Proof, Available Online from 01 June 2022

##### Stability of maximum preserving in multi-Banach lattice by fixed point method with some of homogeneity properties

Articles in Press, Corrected Proof, Available Online from 13 September 2022

Nafiseh Salehi

##### An example for the nonstability of multicubic mappings

Articles in Press, Corrected Proof, Available Online from 30 September 2022

Abasalt Bodaghi

##### Asymptotic behavior of a radical quadratic functional equation in quasi-β-Banach spaces

Articles in Press, Corrected Proof, Available Online from 09 March 2023

##### Generalized Euler-Lagrange (m,n)-cubic functional equation and its stability

Volume 14, Issue 1, January 2023, Pages 193-204

Matina J. Rassias; P. Narasimman; Choonkil Park; Jung Rye Lee

##### Existence theory and stability analysis to the system of infinite point fractional order BVPs by multivariate best proximity point theorem

Volume 13, Issue 2, July 2022, Pages 1713-1733

##### An additive $(u, \beta)$-functional equation and linear mappings in Banach modules

Volume 13, Issue 2, July 2022, Pages 1747-1755

Siriluk Paokanta; Choonkil Park; Jung Rye Lee

##### Characterization and stability of multi-cubic mappings

Volume 13, Issue 2, July 2022, Pages 2493-2502

##### On asymptotic and Hyers-Ulam stability of Hilfer fractional initial value problem involving a $(p_{1} ,p_{2},\dots, p _{n})$-Laplacian operator

Volume 13, Issue 2, July 2022, Pages 2723-2742

##### Hyers-Ulam-Rassias stability of orthogonality equation on restricted domains

Volume 13, Issue 2, July 2022, Pages 3213-3222

Ginkyu Choi; Soon-Mo Jung

##### n-Jordan *-Derivations in Frechet locally C*-algebras

Volume 13, Issue 1, January 2022, Pages 555-562

##### On an equation characterizing multi-quartic mappings and its stability

Volume 13, Issue 1, January 2022, Pages 991-1002

Zohreh Abbasbeygi; Abasalt Bodaghi; Ayoub Gharibkhajeh

##### A fixed point approach to the stability of additive-quadratic-quartic functional equations

Volume 11, Issue 2, May 2020, Pages 17-28

Abasalt Bodaghi; Th.M. Rassias; Abbas Zivari-Kazempour

##### On the stability of linear differential equations of second order

Volume 8, Issue 2, December 2017, Pages 65-70

Abbas Najati; Mohammad Abdollahpour; Choonkil Park

##### Quadratic $\alpha$-functional equations

Volume 8, Issue 1, April 2017, Pages 1-9

Choonkil Park; Sang Og Kim

##### Quadratic $\rho$-functional inequalities in $\beta$-homogeneous normed spaces

Volume 6, Issue 2, January 2015, Pages 21-26

Choonkil Park; Sang Og Kim; Jung Rye Lee; Dong Yun Shin

##### Approximately $n$-order linear differential equations

Volume 6, Issue 1, January 2015, Pages 135-139

##### On approximate dectic mappings in non-Archimedean spaces: A fixed point approach

Volume 5, Issue 2, July 2014, Pages 111-122

A. Ebadian; R. Aghalary; M.A. Abolfathi

##### A fixed point approach to the Hyers-Ulam stability of an $AQ$ functional equation in probabilistic modular spaces

Volume 4, Issue 2, June 2013, Pages 89-101

S. Zolfaghari; A. Ebadian; S. Ostadbashi; M. De La Sen; M. Eshaghi Gordji

##### Approximate additive and quadratic mappings in 2-Banach spaces and related topics

Volume 3, Issue 2, June 2012, Pages 75-81

Y. J. Cho; C. Park; M. Eshaghi Gordji

##### On the approximate solution of Hosszus functional equation

Volume 3, Issue 1, January 2012, Pages 40-44

B. Bouikhalene; J. M. Rassias; A. Charifi; S. Kabbaj


text:
## Wednesday, February 25, 2015

### 2/24 Combinatorics

This session I decided to try out some more of the fivetriangle problems. I gave out a double sided sheet with 2 problems on it and let the kids decided whether to start with the easier one or go straight to the more complex problem.

1. Magic Square (easier)
http://fivetriangles.blogspot.com/2015/02/215-integer-table.htm
This one was a general success. Almost everyone finished on their own. Although this is fairly amenable to a guess and check attack so its not surprising to see this happen. I ran a small experiment with a bit of competition that was interesting here.  Five minutes in or so, I announced to the group that 2 of the girls had finished this problem.  It immediately engaged the boys to know the girls were going faster but led to more final answer sharing rather than method sharing. So I need a middle path - engagement without corner cutting.

2. Geometry problem.
http://fivetriangles.blogspot.com/2015/02/216-three-kissing-circles.html
This problem's tougher and took more time and individual prompting.  You essentially have to figure out the correct order of steps and then:

• Recognize an isosceles triangle based on it having two sides that are the radii of the same circle.
• Determine the rest of the angles in this triangle given one and the fact its isosceles.
• Find the third side of the larger right triangle that was found in the previous step using the Pythagorean theorem.
• Find a linear system to solve. The first part based on the radii of the largest circle. The second part based on the unknown radii also adding up to the third side of the triangle found above.

On the bright side I had a few aha moments with several of the kids as they worked their way through it. It also was decent practice for some mechanical skills like using the Pythagorean theorem. On the other hand, I exposed some general weaknesses.

1. Several kids did not know how to find the area of circle. This should have been covered given their curriculum especially for the fifth graders. However, I didn't pre-query if they knew it which is my primary take away.  Since I'm brainstorming activities for Pi day, I'm going to bear this in mind. Maybe we should warm up practicing some basic skills like area and circumference calculations and go forward from there.
2. Isosceles triangles. Also shaky and theoretically covered. This falls under the same thought about basic skill warmups.
3. Applying the Pythagorean theorem. For example: one student didn't fully realize that c^2 had to be the hypotenuse of the triangle. Lesson: when we worked on proving it, a good warm up would have been some sample applications.  I assumed since everyone said they had seen it but just didn't know how it works that this was already true.

After finishing up the above activities I moved kids individually along to a packet I cribbed from AoPS on beginning combinatorics. I've not really touched this topic this year and its been on my pending list. Structurally this meant there was no great place for a central lecture. It didn't appear necessary here and for the most part the kids had few questions about this material. I'm going to return back to it in more depth and I'll discover if this is really the case. On the bright side, I had a few kids actually lingering past pickup time to work out the last few problems and I also had a few asking for my third backup package of AMC8 problems. Score one for engagement.

For the future I'm going to think a lot about whether the followup activity needs to be mostly self driven or require small assists versus the complexity of the warmup. If I expect to do some group work together then the warmup needs to be more uniformly finishable in 10-15 minutes so I can refocus the kids.  One possibility is to move the challenging problems towards the end. I'm a bit reluctant to do so though because I feel like I get the best efforts at the start of the session.

## Wednesday, February 18, 2015

### Triangle Number Exercise

Admin note: This is my first experiment getting latex formatting working for formulas so there's going to be more sigma notation than I would use in class. We're also on a break until next week. MathJax TeX Test Page
A triangle number is a sum 1 + 2 + ... + n which is also written $\sum\limits_{i=1}^n i$.

Two cool theorems that can be fairly easily proved are:

• $\sum\limits_{i=1}^n i$ = $\frac{n(n+1)}{2}$

• $(\sum\limits_{i=1}^n i)^2 = \sum\limits_{i=1}^n i^3$
The first one is not to hard to see and I expect many of the kids have already at least informally discovered it.  The second however is a bit more complicated and I'm considering whether we can walk our way through it during a  session.

There's a geometric interpretation that makes this fairly obvious:

New: cool triple triangle proof http://t.co/2QwN1sKdeY

However, I don't see the kids discovering this on their own but I suppose I could provide cut outs and have them do the transforms manually.

The inductive proof on the other hand might be more easily discovered but I foresee two problems.

1. Most of the kids don't have a good grasp on multiplying expressions like $(a + b)^2 = a^2 + 2ab + b^2$.  We could review this fact again (which we did once during the pythagorean theorem session.

2. Secondly I don't think most kids have done any inductive proofs. So it would probably also require a session just on that to work out the principles using simpler problems. TODO: what would a good set look like?

With those techniques in hand the following would be workable:

Let $s_1 = (\sum\limits_{i=1}^n i)$

Then

$(\sum\limits_{i=1}^{n+1} i)^2 = (s_1 + (n+1))^2$

Which expands to:

$s_1^2 + 2*s_1*(n+1) + (n+1)^2$

Then since we also know $s_1 = \frac{n(n+1)}{2}$ we can substitute that into the second term.

$s_1^2 + 2*\frac{n(n+1)}{2}*(n+1) + (n+1)^2$

which simplifies to

$s_1^2 + n(n+1)^2 + (n+1)^2$

And then using the distribute law to factor out n+1 you get:

$s_1^2 + (n + 1) (n+1)^2 = s_1^2 + (n+1)^3$

That's enough to use the inductive principle i.e. each successive term means adding the next cube and I think I could move the kids through steps via a worksheet type approach.

## Tuesday, February 10, 2015

Olympiad days usually go well and this one was no different. (Perhaps this means I should introduce more competitive tasks on regular days despite my instincts)  To start I gave out my first worksheet. After a math session with my son, I decided  that the curriculum is neglecting how to convert repeating decimals back into fractions and that would make a fun warm-up exercise. I started by asking how many already knew how to do this. The most amusing answer: "I've memorized all the conversions".   So I made up a sheet that walked the kids through some examples and then made the transition to transforming some geometric series into a simple fraction i.e.

1/K + 1/K^2 + 1/K^3 ...   = 1 / K - 1  for K > 1

This worked out really well. After  short bit of lecturing at the start where I demoed converting .11111...,  Many of the kids had a bunch of aha moments.

We then did the Olympiad. I haven't graded the results yet but from glancing at the sheets as they were working it looks like they did fairly well overall.

Once again, on review as a group I was struck by the spectrum of algebraic thinking.

Given a problem:  A group of dimes and nickels add up to X and there are Y more dimes than nickels. The most common technique was to create a chart and effectively brute force test the first few possible combinations.  This works fine in a MOEMS test because they create problems that  are very amenable to this and other guess and check strategies.

Addendum: I tried this out on my son and it was very interesting. He spent about 30 seconds and guessed the correct answer. I then asked him if he could do it algebraically and he proceeded to setup the equation and solve it. So maybe I'm underestimating the kids. The problems are structured so that the guess and check alternative is so easy that it might not pay to setup an equation. I'd have to give them some problems that require fractional answers to know for sure. Moral: structure your problems carefully. Provide an easy guessable answer only if you want to encourage that.

One other note, I had an extra parent volunteer at the club today and that was tremendously helpful. I'm hoping to have more volunteers in future weeks. In general I'm finding my bandwidth starts to max out at 10:1 and extra adults are extremely useful.

### Brainstorming:

Pi day is coming up soon and I definitely want to do something themed for it near that day. Maybe we'll explore alternating series to derive pi/4 a bit.

Also I've been fiddling with the idea of doing an algebra readiness assessment at the end of the year. The district doesn't do anything officially that I find interesting and I wonder if the parents would appreciate it.

## Friday, February 6, 2015

### Field Testing

 Whiteboard in the hallway at My Office I like to try out potential problems on my coworkers. Actually sometimes I put ones up that I've found that I think are fun and probably too advanced for the club.

## Tuesday, February 3, 2015

### 2/3 Finish what we started

My main goal for this week was to get to all the problems we didn't do last week after our KenKen digression.  So I started reviewing the AMC8 6-10 problems. These again didn't feel very deep and the kids had a pretty easy time outlining solutions to each other.

One note: Given a problem like

There are four more girls than boys in Ms. Raub's class of  students. What is the ratio of number of girls to the number of boys in her class?

Most of the kids tend to decompose the problem by saying if equally divided there would 14 of each and since there are four more then we should add and subtract 2 from 14 to get the two subtotals: 16 and 12.   I'm surprised that no one tends think in terms of equations i.e. x + x -4 = 28 solve for x.  This is a general trend through most of the problem solving. I'm not sure if its developmental and post algebra this all changes and if its worth emphasizing looking at the more algebraic approach.

After the AMC problems I had everyone choose between some practice Maths Olympiads or some problems from the five triangle site. This worked out pretty well. Almost everyone stayed on track and finished at least one sheet. The only drawback is that it doesn't allow for group solution sharing. I'll have to think if there is any way to do both without an extra person.


text:
# Prove that matrix $A$ is symmetric

If $$A$$, $$B$$ are square matrices, $$B$$ is symmetric and $$(A+B)^2$$ is symmetric, prove that $$A$$ is also symmetric.

• Show your effort. Where did you get stuck? – mwt Jan 12 at 14:11
• i used the equality (A+B)^2=((A+B)^2)^T , and B= (B)^T – Kostas Giatzo Jan 12 at 14:40
• You were on the right track, see computation details below. – ex.nihil Jan 12 at 14:43
• Where did you find this exercise? As you can see, the statement is false. – egreg Jan 12 at 15:36
• Guys thank you for the help and your time:) I guess my teacher did a typo in or smth in this one – Kostas Giatzo Jan 13 at 6:19

The statement you want to prove is wrong. Take $$A=\begin{pmatrix} 0 & 1 \\ 0 & 0\end{pmatrix}$$ and $$B$$ the zero matrix. Then $$B$$ is symmetric, $$(A+B)^2 = A^2$$ is the zero matrix (and therefore symmetric), but $$A$$ is not symmetric.


text:
# Gas Station Refueling¶

Covers:

This examples models a gas station and cars that arrive at the station for refueling.

The gas station has a limited number of fuel pumps and a fuel tank that is shared between the fuel pumps. The gas station is thus modeled as a Resource. The shared fuel tank is modeled with a Container.

Vehicles arriving at the gas station first request a fuel pump from the station. Once they acquire one, they try to take the desired amount of fuel from the fuel pump. They leave when they are done.

The gas stations fuel level is reqularly monitored by gas station control. When the level drops below a certain threshold, a tank truck is called to refuel the gas station itself.

using SimJulia
using Distributions

const RANDOM_SEED = 14021986
const GAS_STATION_SIZE = 200                    # liters
const THRESHOLD = 10                            # Threshold for calling the tank truck (in %)
const FUEL_TANK_SIZE = 50                       # liters
const FUEL_TANK_LEVEL = DiscreteUniform(5, 25)  # Min/max levels of fuel tanks (in liters)
const REFUELING_SPEED = 2.0                     # liters / second
const TANK_TRUCK_TIME = 300.0                   # Seconds it takes the tank truck to arrive
const T_INTER = Uniform(30.0, 300.0)            # Create a car every (min, max) seconds
const SIM_TIME = 2000.0                         # Simulation time in seconds

function car(env::Environment, name::ASCIIString, gas_station::Resource, fuel_pump::Container{Int})
fuel_tank_level = rand(FUEL_TANK_LEVEL)
println("$name arriving at gas station at$(round(now(env), 2)) with $fuel_tank_level liters left in tank.") start = now(env) yield(Request(gas_station)) liters_required = FUEL_TANK_SIZE - fuel_tank_level yield(Get(fuel_pump, liters_required)) yield(Timeout(env, liters_required / REFUELING_SPEED)) println("$name finished refueling in $(round((now(env)-start), 2)) seconds.") yield(Release(gas_station)) end function gas_station_control(env::Environment, fuel_pump::Container{Int}) while true if level(fuel_pump) / capacity(fuel_pump) * 100 < THRESHOLD println("Calling tank truck at$(round(now(env), 2)).")
yield(Process(env, tank_truck, fuel_pump))
end
yield(Timeout(env, 10.0))  # Check every 10 seconds
end
end

function tank_truck(env::Environment, fuel_pump::Container)
yield(Timeout(env, TANK_TRUCK_TIME))
println("Tank truck arriving at time $(round(now(env), 2)).") amount = capacity(fuel_pump) - level(fuel_pump) println("Tank truck refuelling$amount liters.")
yield(Put(fuel_pump, amount))
end

function car_generator(env::Environment, gas_station::Resource, fuel_pump::Container{Int})
i = 0
while true
yield(Timeout(env, rand(T_INTER)))
Process(env, car, "Car \$(i+=1)", gas_station, fuel_pump)
end
end

# Setup and start the simulation
println("Gas Station refuelling")
srand(RANDOM_SEED)

# Create environment and start processes
env = Environment()
gas_station = Resource(env, 2)
fuel_pump = Container{Int}(env, GAS_STATION_SIZE, GAS_STATION_SIZE)
Process(env, gas_station_control, fuel_pump)
Process(env, car_generator, gas_station, fuel_pump)

# Execute!
run(env, SIM_TIME)

The simulation’s output:

Gas Station refuelling
Car 1 arriving at gas station at 212.43 with 8 liters left in tank.
Car 1 finished refueling in 21.0 seconds.
Car 2 arriving at gas station at 482.13 with 22 liters left in tank.
Car 2 finished refueling in 14.0 seconds.
Car 3 arriving at gas station at 779.36 with 25 liters left in tank.
Car 3 finished refueling in 12.5 seconds.
Car 4 arriving at gas station at 964.75 with 17 liters left in tank.
Car 4 finished refueling in 16.5 seconds.
Car 5 arriving at gas station at 1011.92 with 9 liters left in tank.
Car 5 finished refueling in 20.5 seconds.
Car 6 arriving at gas station at 1121.88 with 20 liters left in tank.
Calling tank truck at 1130.0.
Car 6 finished refueling in 15.0 seconds.
Car 7 arriving at gas station at 1361.4 with 25 liters left in tank.
Tank truck arriving at time 1430.0.
Tank truck refuelling 199 liters.
Car 7 finished refueling in 81.1 seconds.
Car 8 arriving at gas station at 1605.04 with 19 liters left in tank.
Car 8 finished refueling in 15.5 seconds.
Car 9 arriving at gas station at 1890.62 with 14 liters left in tank.
Car 9 finished refueling in 18.0 seconds.


text:
# Help understanding a semi-controlled full rectifier

Tags:
1. Nov 12, 2016

### jendrix

Hi, I'm analysing the the circuit here

http://imgur.com/a/23GUZ

And I'm having some trouble understand the Vout waveform and why it goes to 0 when when pi<wt<pi+a

If there is always an output current wouldn't there always be a voltage out? The only thing I could think would be the voltage across the inductor cancelling out the voltage across the resistor?

2. Nov 12, 2016

### FOIWATER

I swear this looks exactly like an old professor of mine hand writing (uddin?)

To answer your question - the Vout waveform goes to zero because both controlled rectifiers (T1 and T2) are not conducting (reverse biased). Are you aware that inductors oppose changes in current by creating their own current flow by using their own stored energy? that is what is happening here.

The path that io is flowing is through the resistor and inductor and through diodes D1 and D2. And you are correct, the inductor is creating the voltage that is dropped across the resistor. think of the path through D1 and D2 as a wire in a conventional circuit and Vo is basically putting your meter across it.

FYI - diodes D1 and D2 are acting like "flyback" or "freewheeling" diodes during this part of the cycle.

#### Attached Files:

• ###### cct.png
File size:
4.7 KB
Views:
32
Last edited: Nov 12, 2016
3. Nov 12, 2016

### jendrix

It could be :)I'm working through a similar problem and found the notes here

http://www.slideshare.net/maneesh001/phase-controlled-rectifiers

Thanks for clearing up the question, it's clearer now I'm a bit rusty with inductors.

I'm still a bit confused with the voltage across the thyristors, we analysed a similar circuit in the lab and I got a different waveform. I added it to the link, it is the pink line on the oscilliscope? Any idea why there is a discrepancy?

4. Nov 12, 2016

### FOIWATER

Not sure where the waveforms are

5. Nov 12, 2016

### jendrix

http://imgur.com/a/i67f8

They bottom (pink) signal in each one is supposed supposed to be Voltage of T1, voltage of D2 and voltage of the inductor with a firing angle of 90 degrees - I think they may have been mislabeled

Yellow -Vin
Green -Vout
Blue -Iout

But I'm having trouble what was being measure on the pink signal in each

6. Nov 12, 2016

### FOIWATER

It would make sense to me if the pink was the voltage across T1 and the voltage across D2, since they conduct during the positive half cycle of Vs, and do not conduct during the negative half cycle of Vs.

7. Nov 13, 2016

### jendrix

Thanks, that sounds right to me

Do you know what the waveform would look like for the ac source current? I thought it would be the same as Iout but 0 from

0-pi

pi+a - 2pi

Or would it be negative during the period pi+a to 2pi?

Thanks

8. Nov 13, 2016

### FOIWATER

Only time the source current isn't flowing (is 0) is from $$0 - \alpha$$ $$\pi - (\pi+\alpha)$$ $$2\pi - (2\pi + \alpha)$$ $$\vdots$$ Unlike the output current, the source current flows in two directions depending on which rectifiers are on

9. Nov 14, 2016

### jendrix

Thanks for the help, all much clearer now

10. Nov 14, 2016

### FOIWATER

Not a problem


text:
Licensed under the MIT License. You may not use this file except in compliance with the License. Use and/or modification of this code outside of 6.S191 must reference:

© MIT 6.S191: Introduction to Deep Learning http://introtodeeplearning.com

## Debiasing Facial Detection Systems

In this lab, we'll investigate one recently published approach to addressing algorithmic bias. We'll build a facial detection model that learns the latent variables underlying face image datasets and uses this to adaptively re-sample the training data, thus mitigating any biases that may be present in order to train a debiased model.

import tensorflow as tf
import numpy as np
import matplotlib.pyplot as plt
import functools
from IPython import display as ipythondisplay
from tqdm import tqdm
import time
import os
import sys
import h5py
import glob
import cv2

# Check that we are using a GPU, if not switch runtimes
#   using Runtime > Change Runtime Type > GPU
assert len(tf.config.list_physical_devices('GPU')) > 0

## Dataset

We'll be using three datasets in this lab. In order to train our facial detection models, we'll need a dataset of positive examples (i.e., of faces) and a dataset of negative examples (i.e., of things that are not faces). We'll use these data to train our models to classify images as either faces or not faces. Finally, we'll need a test dataset of face images. Since we're concerned about the potential bias of our learned models against certain demographics, it's important that the test dataset we use has equal representation across the demographics or features of interest. In this lab, we'll consider skin tone and gender.

1. Positive training data: CelebA Dataset. A large-scale (over 200K images) of celebrity faces.
2. Negative training data: ImageNet. Many images across many different categories. We'll take negative examples from a variety of non-human categories. Fitzpatrick Scale skin type classification system, with each image labeled as "Lighter'' or "Darker''.

Let's begin by importing these datasets. We've written a class that does a bit of data pre-processing to import the training data in a usable format.

class TrainingDatasetLoader(object):
def __init__(self, data_path):

print ("Opening {}".format(data_path))
sys.stdout.flush()

self.cache = h5py.File(data_path, 'r')

sys.stdout.flush()
self.images = self.cache['images'][:]
self.labels = self.cache['labels'][:].astype(np.float32)
self.image_dims = self.images.shape
n_train_samples = self.image_dims[0]

self.train_inds = np.random.permutation(np.arange(n_train_samples))

self.pos_train_inds = self.train_inds[ self.labels[self.train_inds, 0] == 1.0 ]
self.neg_train_inds = self.train_inds[ self.labels[self.train_inds, 0] != 1.0 ]

def get_train_size(self):
return self.train_inds.shape[0]

def get_train_steps_per_epoch(self, batch_size, factor=10):
return self.get_train_size()//factor//batch_size

def get_batch(self, n, only_faces=False, p_pos=None, p_neg=None, return_inds=False):
if only_faces:
selected_inds = np.random.choice(self.pos_train_inds, size=n, replace=False, p=p_pos)
else:
selected_pos_inds = np.random.choice(self.pos_train_inds, size=n//2, replace=False, p=p_pos)
selected_neg_inds = np.random.choice(self.neg_train_inds, size=n//2, replace=False, p=p_neg)
selected_inds = np.concatenate((selected_pos_inds, selected_neg_inds))

sorted_inds = np.sort(selected_inds)
train_img = (self.images[sorted_inds,:,:,::-1]/255.).astype(np.float32)
train_label = self.labels[sorted_inds,...]
return (train_img, train_label, sorted_inds) if return_inds else (train_img, train_label)

def get_n_most_prob_faces(self, prob, n):
idx = np.argsort(prob)[::-1]
most_prob_inds = self.pos_train_inds[idx[:10*n:10]]
return (self.images[most_prob_inds,...]/255.).astype(np.float32)

def get_all_train_faces(self):
return self.images[ self.pos_train_inds ]

path_to_training_data = tf.keras.utils.get_file('train_face.h5', 'https://www.dropbox.com/s/hlz8atheyozp1yx/train_face.h5?dl=1')

Opening C:\Users\kcsgo\.keras\datasets\train_face.h5

We can look at the size of the training dataset and grab a batch of size 100:

number_of_training_examples = loader.get_train_size()

Play around with displaying images to get a sense of what the training data actually looks like!

images.shape

(100, 64, 64, 3)
face_images = images[np.where(labels==1)[0]]
not_face_images = images[np.where(labels==0)[0]]

idx_face = np.random.choice(face_images.shape[0])
idx_not_face = np.random.choice(not_face_images.shape[0])

plt.figure(figsize=(8, 8))
plt.subplot(1, 2, 1)
plt.imshow(face_images[idx_face])
plt.title("Face")
plt.grid(False)

plt.subplot(1, 2, 2)
plt.imshow(not_face_images[idx_not_face])
plt.title("Not Face")
plt.grid(False)

Remember we'll be training our facial detection classifiers on the large, well-curated CelebA dataset (and ImageNet), and then evaluating their accuracy by testing them on an independent test dataset. Our goal is to build a model that trains on CelebA and achieves high classification accuracy on the the test dataset across all demographics, and to thus show that this model does not suffer from any hidden bias.

What exactly do we mean when we say a classifier is biased? In order to formalize this, we'll need to think about latent variables, variables that define a dataset but are not strictly observed. As defined in the generative modeling lecture, we'll use the term latent space to refer to the probability distributions of the aforementioned latent variables. Putting these ideas together, we consider a classifier biased if its classification decision changes after it sees some additional latent features. This notion of bias may be helpful to keep in mind throughout the rest of the lab.

## CNN for facial detection

First, we'll define and train a CNN on the facial classification task, and evaluate its accuracy. Later, we'll evaluate the performance of our debiased models against this baseline CNN. The CNN model has a relatively standard architecture consisting of a series of convolutional layers with batch normalization followed by two fully connected layers to flatten the convolution output and generate a class prediction.

### Define and train the CNN model

Like we did in the first part of the lab, we'll define our CNN model, and then train on the CelebA and ImageNet datasets using the tf.GradientTape class and the tf.GradientTape.gradient method.

n_filters = 12 # base number of convolutional filters

'''Function to define a standard CNN model'''
def make_standard_classifier(n_outputs=1):
BatchNormalization = tf.keras.layers.BatchNormalization
Flatten = tf.keras.layers.Flatten
Dense = functools.partial(tf.keras.layers.Dense, activation='relu')

model = tf.keras.Sequential([
Conv2D(filters=1*n_filters, kernel_size=5,  strides=2),
BatchNormalization(),

Conv2D(filters=2*n_filters, kernel_size=5,  strides=2),
BatchNormalization(),

Conv2D(filters=4*n_filters, kernel_size=3,  strides=2),
BatchNormalization(),

Conv2D(filters=6*n_filters, kernel_size=3,  strides=2),
BatchNormalization(),

Flatten(),
Dense(512),
Dense(n_outputs, activation=None),
])
return model

standard_classifier = make_standard_classifier()

Now let's train the standard CNN!

class LossHistory:
def __init__(self, smoothing_factor=0.0):
self.alpha = smoothing_factor
self.loss = []
def append(self, value):
self.loss.append( self.alpha*self.loss[-1] + (1-self.alpha)*value if len(self.loss)>0 else value )
def get(self):
return self.loss

class PeriodicPlotter:
def __init__(self, sec, xlabel='', ylabel='', scale=None):

self.xlabel = xlabel
self.ylabel = ylabel
self.sec = sec
self.scale = scale

self.tic = time.time()

def plot(self, data):
if time.time() - self.tic > self.sec:
plt.cla()

if self.scale is None:
plt.plot(data)
elif self.scale == 'semilogx':
plt.semilogx(data)
elif self.scale == 'semilogy':
plt.semilogy(data)
elif self.scale == 'loglog':
plt.loglog(data)
else:
raise ValueError("unrecognized parameter scale {}".format(self.scale))

plt.xlabel(self.xlabel); plt.ylabel(self.ylabel)
ipythondisplay.clear_output(wait=True)
ipythondisplay.display(plt.gcf())

self.tic = time.time()

# Training hyperparameters
batch_size = 32
num_epochs = 2  # keep small to run faster
learning_rate = 5e-4

optimizer = tf.keras.optimizers.Adam(learning_rate) # define our optimizer
loss_history = LossHistory(smoothing_factor=0.99) # to record loss evolution
plotter = PeriodicPlotter(sec=2, scale='semilogy')
if hasattr(tqdm, '_instances'): tqdm._instances.clear() # clear if it exists

@tf.function
def standard_train_step(x, y):
# feed the images into the model
logits = standard_classifier(x)
# Compute the loss
loss = tf.nn.sigmoid_cross_entropy_with_logits(labels=y, logits=logits)

# Backpropagation
return loss

# The training loop!
for epoch in range(num_epochs):
# Grab a batch of training data and propagate through the network
loss = standard_train_step(x, y)

# Record the loss and plot the evolution of the loss as a function of training
loss_history.append(loss.numpy().mean())
plotter.plot(loss_history.get())

100%|██████████████████████████████████████████████████████████████████████████████| 3434/3434 [00:48<00:00, 70.69it/s]

### Evaluate performance of the standard CNN

Next, let's evaluate the classification performance of our CelebA-trained standard CNN on the training dataset.

# TRAINING DATA
# Evaluate on a subset of CelebA+Imagenet
y_pred_standard = tf.round(tf.nn.sigmoid(standard_classifier.predict(batch_x)))
acc_standard = tf.reduce_mean(tf.cast(tf.equal(batch_y, y_pred_standard), tf.float32))

print("Standard CNN accuracy on (potentially biased) training set: {:.4f}".format(acc_standard.numpy()))

Standard CNN accuracy on (potentially biased) training set: 0.9968

We will also evaluate our networks on an independent test dataset containing faces that were not seen during training. For the test data, we'll look at the classification accuracy across four different demographics, based on the Fitzpatrick skin scale and sex-based labels: dark-skinned male, dark-skinned female, light-skinned male, and light-skinned female.

Let's take a look at some sample faces in the test set.

def get_test_faces():
cwd = os.path.dirname('./')
images = {
"LF": [],
"LM": [],
"DF": [],
"DM": []
}
for key in images.keys():
files = glob.glob(os.path.join(cwd, "dataset", "faces", key, "*.png"))
for file in sorted(files):
images[key].append(image)

return images["LF"], images["LM"], images["DF"], images["DM"]

test_faces = get_test_faces()

keys = ["Light Female", "Light Male", "Dark Female", "Dark Male"]
for group, key in zip(test_faces,keys):
plt.figure(figsize=(8, 8))
plt.imshow(np.hstack(group))
plt.title(key, fontsize=15)

Now, let's evaluated the probability of each of these face demographics being classified as a face using the standard CNN classifier we've just trained.

standard_classifier_logits = [standard_classifier(np.array(x, dtype=np.float32)) for x in test_faces]
standard_classifier_probs = tf.squeeze(tf.sigmoid(standard_classifier_logits))

# Plot the prediction accuracies per demographic
xx = range(len(keys))
yy = standard_classifier_probs.numpy().mean(1)
plt.bar(xx, yy)
plt.xticks(xx, keys)
plt.ylim(max(0,yy.min()-yy.ptp()/2.), yy.max()+yy.ptp()/2.)
plt.title("Standard classifier predictions")
plt.show()

Take a look at the accuracies for this first model across these four groups. What do you observe? Would you consider this model biased or unbiased? What are some reasons why a trained model may have biased accuracies?

## Mitigating algorithmic bias

Imbalances in the training data can result in unwanted algorithmic bias. For example, the majority of faces in CelebA (our training set) are those of light-skinned females. As a result, a classifier trained on CelebA will be better suited at recognizing and classifying faces with features similar to these, and will thus be biased.

How could we overcome this? A naive solution -- and one that is being adopted by many companies and organizations -- would be to annotate different subclasses (i.e., light-skinned females, males with hats, etc.) within the training data, and then manually even out the data with respect to these groups.

But this approach has two major disadvantages. First, it requires annotating massive amounts of data, which is not scalable. Second, it requires that we know what potential biases (e.g., race, gender, pose, occlusion, hats, glasses, etc.) to look for in the data. As a result, manual annotation may not capture all the different features that are imbalanced within the training data.

Instead, let's actually learn these features in an unbiased, unsupervised manner, without the need for any annotation, and then train a classifier fairly with respect to these features. In the rest of this lab, we'll do exactly that.

## Variational autoencoder (VAE) for learning latent structure

As you saw, the accuracy of the CNN varies across the four demographics we looked at. To think about why this may be, consider the dataset the model was trained on, CelebA. If certain features, such as dark skin or hats, are rare in CelebA, the model may end up biased against these as a result of training with a biased dataset. That is to say, its classification accuracy will be worse on faces that have under-represented features, such as dark-skinned faces or faces with hats, relevative to faces with features well-represented in the training data! This is a problem.

Our goal is to train a debiased version of this classifier -- one that accounts for potential disparities in feature representation within the training data. Specifically, to build a debiased facial classifier, we'll train a model that learns a representation of the underlying latent space to the face training data. The model then uses this information to mitigate unwanted biases by sampling faces with rare features, like dark skin or hats, more frequently during training. The key design requirement for our model is that it can learn an encoding of the latent features in the face data in an entirely unsupervised way. To achieve this, we'll turn to variational autoencoders (VAEs).

As shown in the schematic above and in Lecture 4, VAEs rely on an encoder-decoder structure to learn a latent representation of the input data. In the context of computer vision, the encoder network takes in input images, encodes them into a series of variables defined by a mean and standard deviation, and then draws from the distributions defined by these parameters to generate a set of sampled latent variables. The decoder network then "decodes" these variables to generate a reconstruction of the original image, which is used during training to help the model identify which latent variables are important to learn.

Let's formalize two key aspects of the VAE model and define relevant functions for each.

### Understanding VAEs: loss function

In practice, how can we train a VAE? In learning the latent space, we constrain the means and standard deviations to approximately follow a unit Gaussian. Recall that these are learned parameters, and therefore must factor into the loss computation, and that the decoder portion of the VAE is using these parameters to output a reconstruction that should closely match the input image, which also must factor into the loss. What this means is that we'll have two terms in our VAE loss function:

1. Latent loss ($L_{KL}$): measures how closely the learned latent variables match a unit Gaussian and is defined by the Kullback-Leibler (KL) divergence.
2. Reconstruction loss ($L_{x}{(x,\hat{x})}$): measures how accurately the reconstructed outputs match the input and is given by the $L^1$ norm of the input image and its reconstructed output.

The equation for the latent loss is provided by:

$$L_{KL}(\mu, \sigma) = \frac{1}{2}\sum_{j=0}^{k-1} (\sigma_j + \mu_j^2 - 1 - \log{\sigma_j})$$

The equation for the reconstruction loss is provided by:

$$L_{x}{(x,\hat{x})} = ||x-\hat{x}||_1$$

Thus for the VAE loss we have:

$$L_{VAE} = c\cdot L_{KL} + L_{x}{(x,\hat{x})}$$

where $c$ is a weighting coefficient used for regularization. Now we're ready to define our VAE loss function:

''' Function to calculate VAE loss given:
an input x,
reconstructed output x_recon,
encoded means mu,
encoded log of standard deviation logsigma,
weight parameter for the latent loss kl_weight
'''
def vae_loss_function(x, x_recon, mu, logsigma, kl_weight=0.0005):
# Define the latent loss.
latent_loss = 0.5 * tf.reduce_sum(tf.exp(logsigma) + tf.square(mu) - 1.0 - logsigma, axis=1)

# Define the reconstruction loss as the mean absolute pixel-wise
# difference between the input and reconstruction. Hint: you'll need to
# use tf.reduce_mean, and supply an axis argument which specifies which
# dimensions to reduce over. For example, reconstruction loss needs to average
# over the height, width, and channel image dimensions.
# https://www.tensorflow.org/api_docs/python/tf/math/reduce_mean
reconstruction_loss = tf.reduce_mean(tf.abs(x - x_recon), axis=(1, 2, 3))

# Define the VAE loss.
vae_loss = reconstruction_loss + kl_weight * latent_loss

return vae_loss

Great! Now that we have a more concrete sense of how VAEs work, let's explore how we can leverage this network structure to train a debiased facial classifier.

### Understanding VAEs: reparameterization

As you may recall from lecture, VAEs use a "reparameterization trick" for sampling learned latent variables. Instead of the VAE encoder generating a single vector of real numbers for each latent variable, it generates a vector of means and a vector of standard deviations that are constrained to roughly follow Gaussian distributions. We then sample from the standard deviations and add back the mean to output this as our sampled latent vector. Formalizing this for a latent variable $z$ where we sample $\epsilon \sim \mathcal{N}(0,(I))$ we have:

$$z = \mu + e^{\left(\frac{1}{2} \cdot \log{\Sigma}\right)}\circ \epsilon$$

where $\mu$ is the mean and $\Sigma$ is the covariance matrix. This is useful because it will let us neatly define the loss function for the VAE, generate randomly sampled latent variables, achieve improved network generalization, and make our complete VAE network differentiable so that it can be trained via backpropagation. Quite powerful!

Let's define a function to implement the VAE sampling operation:

"""Reparameterization trick by sampling from an isotropic unit Gaussian.
# Arguments
z_mean, z_logsigma (tensor): mean and log of standard deviation of latent distribution (Q(z|X))
# Returns
z (tensor): sampled latent vector
"""
def sampling(z_mean, z_logsigma):
# By default, random.normal is "standard" (ie. mean=0 and std=1.0)
batch, latent_dim = z_mean.shape
epsilon = tf.random.normal(shape=(batch, latent_dim))

# Define the reparameterization computation!
z = z_mean + tf.math.exp(0.5 * z_logsigma) * epsilon
return z

## Debiasing variational autoencoder (DB-VAE)

Now, we'll use the general idea behind the VAE architecture to build a model, termed a debiasing variational autoencoder or DB-VAE, to mitigate (potentially) unknown biases present within the training idea. We'll train our DB-VAE model on the facial detection task, run the debiasing operation during training, evaluate on the PPB dataset, and compare its accuracy to our original, biased CNN model.

### The DB-VAE model

The key idea behind this debiasing approach is to use the latent variables learned via a VAE to adaptively re-sample the CelebA data during training. Specifically, we will alter the probability that a given image is used during training based on how often its latent features appear in the dataset. So, faces with rarer features (like dark skin, sunglasses, or hats) should become more likely to be sampled during training, while the sampling probability for faces with features that are over-represented in the training dataset should decrease (relative to uniform random sampling across the training data).

A general schematic of the DB-VAE approach is shown here:

Recall that we want to apply our DB-VAE to a supervised classification problem -- the facial detection task. Importantly, note how the encoder portion in the DB-VAE architecture also outputs a single supervised variable, $z_o$, corresponding to the class prediction -- face or not face. Usually, VAEs are not trained to output any supervised variables (such as a class prediction)! This is another key distinction between the DB-VAE and a traditional VAE.

Keep in mind that we only want to learn the latent representation of faces, as that's what we're ultimately debiasing against, even though we are training a model on a binary classification problem. We'll need to ensure that, for faces, our DB-VAE model both learns a representation of the unsupervised latent variables, captured by the distribution $q_\phi(z|x)$, and outputs a supervised class prediction $z_o$, but that, for negative examples, it only outputs a class prediction $z_o$.

### Defining the DB-VAE loss function

This means we'll need to be a bit clever about the loss function for the DB-VAE. The form of the loss will depend on whether it's a face image or a non-face image that's being considered.

For face images, our loss function will have two components:

1. VAE loss ($L_{VAE}$): consists of the latent loss and the reconstruction loss.
2. Classification loss ($L_y(y,\hat{y})$): standard cross-entropy loss for a binary classification problem.

In contrast, for images of non-faces, our loss function is solely the classification loss.

We can write a single expression for the loss by defining an indicator variable $\mathcal{I}_f$which reflects which training data are images of faces ($\mathcal{I}_f(y) = 1$ ) and which are images of non-faces ($\mathcal{I}_f(y) = 0$). Using this, we obtain:

$$L_{total} = L_y(y,\hat{y}) + \mathcal{I}_f(y)\Big[L_{VAE}\Big]$$

Let's write a function to define the DB-VAE loss function:

"""Loss function for DB-VAE.
# Arguments
x: true input x
x_pred: reconstructed x
y: true label (face or not face)
y_logit: predicted labels
mu: mean of latent distribution (Q(z|X))
logsigma: log of standard deviation of latent distribution (Q(z|X))
# Returns
total_loss: DB-VAE total loss
classification_loss = DB-VAE classification loss
"""
def debiasing_loss_function(x, x_pred, y, y_logit, mu, logsigma):

# call the relevant function to obtain VAE loss
vae_loss = vae_loss_function(x, x_pred, mu, logsigma)

# define the classification loss using sigmoid_cross_entropy
# https://www.tensorflow.org/api_docs/python/tf/nn/sigmoid_cross_entropy_with_logits
classification_loss = tf.nn.sigmoid_cross_entropy_with_logits(y, y_logit)

# Use the training data labels to create variable face_indicator:
#   indicator that reflects which training data are images of faces
face_indicator = tf.cast(tf.equal(y, 1), tf.float32)

# define the DB-VAE total loss
total_loss = tf.reduce_mean(classification_loss + face_indicator * vae_loss)

### DB-VAE architecture

Now we're ready to define the DB-VAE architecture. To build the DB-VAE, we will use the standard CNN classifier from above as our encoder, and then define a decoder network. We will create and initialize the two models, and then construct the end-to-end VAE. We will use a latent space with 100 latent variables.

The decoder network will take as input the sampled latent variables, run them through a series of deconvolutional layers, and output a reconstruction of the original input image.

n_filters = 12 # base number of convolutional filters, same as standard CNN
latent_dim = 100 # number of latent variables

def make_face_decoder_network():
# Functionally define the different layer types we will use
Flatten = tf.keras.layers.Flatten
Dense = functools.partial(tf.keras.layers.Dense, activation='relu')
Reshape = tf.keras.layers.Reshape

# Build the decoder network using the Sequential API
decoder = tf.keras.Sequential([
# Transform to pre-convolutional generation
Dense(units=4*4*6*n_filters),  # 4x4 feature maps (with 6N occurances)
Reshape(target_shape=(4, 4, 6*n_filters)),

# Upscaling convolutions (inverse of encoder)
Conv2DTranspose(filters=4*n_filters, kernel_size=3,  strides=2),
Conv2DTranspose(filters=2*n_filters, kernel_size=3,  strides=2),
Conv2DTranspose(filters=1*n_filters, kernel_size=5,  strides=2),
Conv2DTranspose(filters=3, kernel_size=5,  strides=2),
])

return decoder

Now, we will put this decoder together with the standard CNN classifier as our encoder to define the DB-VAE. Note that at this point, there is nothing special about how we put the model together that makes it a "debiasing" model -- that will come when we define the training operation. Here, we will define the core VAE architecture by sublassing the Model class; defining encoding, reparameterization, and decoding operations; and calling the network end-to-end.

class DB_VAE(tf.keras.Model):
def __init__(self, latent_dim):
super(DB_VAE, self).__init__()
self.latent_dim = latent_dim

# Define the number of outputs for the encoder. Recall that we have
# latent_dim latent variables, as well as a supervised output for the
# classification.
num_encoder_dims = 2*self.latent_dim + 1

self.encoder = make_standard_classifier(num_encoder_dims)
self.decoder = make_face_decoder_network()

# function to feed images into encoder, encode the latent space, and output
#   classification probability
def encode(self, x):
# encoder output
encoder_output = self.encoder(x)

# classification prediction
y_logit = tf.expand_dims(encoder_output[:, 0], -1)
# latent variable distribution parameters
z_mean = encoder_output[:, 1:self.latent_dim+1]
z_logsigma = encoder_output[:, self.latent_dim+1:]

return y_logit, z_mean, z_logsigma

# VAE reparameterization: given a mean and logsigma, sample latent variables
def reparameterize(self, z_mean, z_logsigma):
# call the sampling function defined above
z = sampling(z_mean, z_logsigma)
return z

# Decode the latent space and output reconstruction
def decode(self, z):
# use the decoder to output the reconstruction
reconstruction = self.decoder(z)
return reconstruction

# The call function will be used to pass inputs x through the core VAE
def call(self, x):
# Encode input to a prediction and latent space
y_logit, z_mean, z_logsigma = self.encode(x)

# reparameterization
z = self.reparameterize(z_mean, z_logsigma)

# reconstruction
recon = self.decode(z)
return y_logit, z_mean, z_logsigma, recon

# Predict face or not face logit for given input x
def predict(self, x):
y_logit, z_mean, z_logsigma = self.encode(x)
return y_logit

dbvae = DB_VAE(latent_dim)

As stated, the encoder architecture is identical to the CNN from earlier in this lab. Note the outputs of our constructed DB_VAE model in the call function: y_logit, z_mean, z_logsigma, z. Think carefully about why each of these are outputted and their significance to the problem at hand.

### Adaptive resampling for automated debiasing with DB-VAE

So, how can we actually use DB-VAE to train a debiased facial detection classifier?

Recall the DB-VAE architecture: as input images are fed through the network, the encoder learns an estimate $\mathcal{Q}(z|X)$ of the latent space. We want to increase the relative frequency of rare data by increased sampling of under-represented regions of the latent space. We can approximate $\mathcal{Q}(z|X)$ using the frequency distributions of each of the learned latent variables, and then define the probability distribution of selecting a given datapoint $x$ based on this approximation. These probability distributions will be used during training to re-sample the data.

You'll write a function to execute this update of the sampling probabilities, and then call this function within the DB-VAE training loop to actually debias the model.

First, we've defined a short helper function get_latent_mu that returns the latent variable means returned by the encoder after a batch of images is inputted to the network:

def get_latent_mu(images, dbvae, batch_size=1024):
N = images.shape[0]
mu = np.zeros((N, latent_dim))
for start_ind in range(0, N, batch_size):
end_ind = min(start_ind+batch_size, N+1)
batch = (images[start_ind:end_ind]).astype(np.float32)/255.
_, batch_mu, _ = dbvae.encode(batch)
mu[start_ind:end_ind] = batch_mu
return mu

Now, let's define the actual resampling algorithm get_training_sample_probabilities. Importantly note the argument smoothing_fac. This parameter tunes the degree of debiasing: for smoothing_fac=0, the re-sampled training set will tend towards falling uniformly over the latent space, i.e., the most extreme debiasing.

'''Function that recomputes the sampling probabilities for images within a batch
based on how they distribute across the training data'''
def get_training_sample_probabilities(images, dbvae, bins=10, smoothing_fac=0.001):
print("Recomputing the sampling probabilities")

# run the input batch and get the latent variable means
mu = get_latent_mu(images, dbvae)

# sampling probabilities for the images
training_sample_p = np.zeros(mu.shape[0])

# consider the distribution for each latent variable
for i in range(latent_dim):

latent_distribution = mu[:,i]
# generate a histogram of the latent distribution
hist_density, bin_edges =  np.histogram(latent_distribution, density=True, bins=bins)

# find which latent bin every data sample falls in
bin_edges[0] = -float('inf')
bin_edges[-1] = float('inf')

# call the digitize function to find which bins in the latent distribution
#    every data sample falls in to
# https://docs.scipy.org/doc/numpy-1.13.0/reference/generated/numpy.digitize.html
bin_idx = np.digitize(latent_distribution, bin_edges)

# smooth the density function
hist_smoothed_density = hist_density + smoothing_fac
hist_smoothed_density = hist_smoothed_density / np.sum(hist_smoothed_density)

# invert the density function
p = 1.0/(hist_smoothed_density[bin_idx-1])

# normalize all probabilities
p = p / np.sum(p)

# update sampling probabilities by considering whether the newly
# computed p is greater than the existing sampling probabilities.
training_sample_p = np.maximum(p, training_sample_p)

# final normalization
training_sample_p /= np.sum(training_sample_p)

return training_sample_p

Now that we've defined the resampling update, we can train our DB-VAE model on the CelebA/ImageNet training data, and run the above operation to re-weight the importance of particular data points as we train the model. Remember again that we only want to debias for features relevant to faces, not the set of negative examples. Complete the code block below to execute the training loop!

def plot_sample(x,y,vae):
plt.figure(figsize=(2,1))
plt.subplot(1, 2, 1)

idx = np.where(y==1)[0][0]
plt.imshow(x[idx])
plt.grid(False)

plt.subplot(1, 2, 2)
_, _, _, recon = vae(x)
recon = np.clip(recon, 0, 1)
plt.imshow(recon[idx])
plt.grid(False)

plt.show()

batch_size = 32
learning_rate = 5e-4
latent_dim = 100

# DB-VAE needs slightly more epochs to train since its more complex than
# the standard classifier so we use 6 instead of 2
num_epochs = 6

# instantiate a new DB-VAE model and optimizer
dbvae = DB_VAE(100)

# To define the training operation, we will use tf.function which is a powerful tool
#   that lets us turn a Python function into a TensorFlow computation graph.
@tf.function
def debiasing_train_step(x, y):

# Feed input x into dbvae. Note that this is using the DB_VAE call function!
y_logit, z_mean, z_logsigma, x_recon = dbvae(x)

# call the DB_VAE loss function to compute the loss
loss, class_loss = debiasing_loss_function(x, x_recon, y, y_logit, z_mean, z_logsigma)

# Hint: this is with respect to the trainable_variables of the dbvae.

return loss

# get training faces from data loader

if hasattr(tqdm, '_instances'): tqdm._instances.clear() # clear if it exists

# The training loop -- outer loop iterates over the number of epochs
for i in range(num_epochs):

ipythondisplay.clear_output(wait=True)
print("Starting epoch {}/{}".format(i+1, num_epochs))

# recompute the sampling probabilities for debiasing
p_faces = get_training_sample_probabilities(all_faces, dbvae)

# get a batch of training data and compute the training step
for j in tqdm(range(loader.get_train_size() // batch_size)):
# load a batch of data
# loss optimization
loss = debiasing_train_step(x, y)

# plot the progress every 200 steps
if j % 500 == 0:
plot_sample(x, y, dbvae)

Starting epoch 6/6
Recomputing the sampling probabilities

  0%|                                                                                | 0/3434 [00:00<?, ?it/s]
 14%|███████████▎                                                                   | 492/3434 [00:06<00:36, 80.27it/s]
 29%|██████████████████████▉                                                        | 999/3434 [00:13<00:33, 72.79it/s]
 44%|█████████████████████████████████▉                                            | 1495/3434 [00:19<00:26, 74.19it/s]
 58%|█████████████████████████████████████████████▎                                | 1997/3434 [00:26<00:18, 75.81it/s]
 73%|████████████████████████████████████████████████████████▋                     | 2493/3434 [00:33<00:13, 71.73it/s]
 87%|████████████████████████████████████████████████████████████████████          | 2998/3434 [00:40<00:05, 75.18it/s]
100%|██████████████████████████████████████████████████████████████████████████████| 3434/3434 [00:46<00:00, 73.58it/s]

## Evaluation of DB-VAE on test dataset

Finally let's test our DB-VAE model on the test dataset, looking specifically at its accuracy on each the "Dark Male", "Dark Female", "Light Male", and "Light Female" demographics. We will compare the performance of this debiased model against the (potentially biased) standard CNN from earlier in the lab.

dbvae_logits = [dbvae.predict(np.array(x, dtype=np.float32)) for x in test_faces]
dbvae_probs = tf.squeeze(tf.sigmoid(dbvae_logits))

xx = np.arange(len(keys))
plt.bar(xx, standard_classifier_probs.numpy().mean(1), width=0.2, label="Standard CNN")
plt.bar(xx+0.2, dbvae_probs.numpy().mean(1), width=0.2, label="DB-VAE")
plt.xticks(xx, keys);
plt.title("Network predictions on test dataset")
plt.ylabel("Probability")
plt.legend(bbox_to_anchor=(1.04,1), loc="upper left")
plt.show()

## Conclusion and submission information

We encourage you to think about and maybe even address some questions raised by the approach and results outlined here:

• How does the accuracy of the DB-VAE across the four demographics compare to that of the standard CNN? Do you find this result surprising in any way?
• How can the performance of the DB-VAE classifier be improved even further? We purposely did not optimize hyperparameters to leave this up to you!
• In which applications (either related to facial detection or not!) would debiasing in this way be desired? Are there applications where you may not want to debias your model?
• Do you think it should be necessary for companies to demonstrate that their models, particularly in the context of tasks like facial detection, are not biased? If so, do you have thoughts on how this could be standardized and implemented?
• Do you have ideas for other ways to address issues of bias, particularly in terms of the training data?

Try to optimize your model to achieve improved performance.

Hopefully this lab has shed some light on a few concepts, from vision based tasks, to VAEs, to algorithmic bias. We like to think it has, but we're biased ;).


text:
# sheaf isomorphisms does not necessarily glue to be isomorphism

For an isomorphism of sheaf on X $$f : \mathscr{F} \to \mathscr{G}$$, suppose it is "locally isomorphic," that is, there is an open cover $$U_i$$ such that $$f|U_i: \mathscr{F}_{U_i} \to \mathscr{G}_{U_i}$$ is an isomorphism for all $$U_i$$.

I cannot specify where is wrong about the argument below :

$$f$$ is isomorphic

iff $$f_x$$ is isomorphic for all $$x\in X$$

iff $$f_x$$ is isomorphic for all $$U_i$$ and $$x\in U_i$$

iff $$f|U_i$$ is isomorphic for all $$U_i$$.

• Why do you think there is something wrong with this argument? – Alex Kruckman Apr 30 at 3:07
• I cosidered problem "locally open embedding morphisms are not necessarily open embeddings", and I tried to generalize the situation. But it seems that I went wrong – Angol Mois Apr 30 at 3:46

Your equivalences you're listing are correct. The isomorphisms already glue since they given by $$f$$. For example, the correct statement for the second point is "There exist a morphism $$f : \mathscr F \to \mathscr G$$ such that for all $$x \in X$$, $$f_x$$ is an isomorphism."
The wrong statement would be to assume that if $$f_x : \mathscr F_x \to \mathscr G_x$$ is an arbitrary family family of isomorphisms, then $$\mathscr F \cong \mathscr G$$ are isomorphic (e.g a counter-example is given by any non-trivial locally free sheaf).


text:
# Math Help - A prime returning function?

1. ## A prime returning function?

Is there such a fuction of the form $P(n)$ which returns the $nth$ prime number? The function would be such that:

$P(1) = 2$
$P(2) = 3$
$P(3) = 5$
$P(4) = 7$
$P(5) = 11$
.
.
.
.

I think the idea is clear. Is there such a function? Or reasearch on such a function?

2. Originally Posted by mfetch22
Is there such a fuction of the form $P(n)$ which returns the $nth$ prime number? The function would be such that:

$P(1) = 2$
$P(2) = 3$
$P(3) = 5$
$P(4) = 7$
$P(5) = 11$
.
.
.
.

I think the idea is clear. Is there such a function? Or reasearch on such a function?
If you don't need to go very high, you could write a sieve. Here's a website that allows you to find the nth prime for n up to $10^{12}$.

3. Originally Posted by mfetch22
Is there such a fuction of the form $P(n)$ which returns the $nth$ prime number? The function would be such that:

$P(1) = 2$
$P(2) = 3$
$P(3) = 5$
$P(4) = 7$
$P(5) = 11$
.
.
.
.

I think the idea is clear. Is there such a function? Or reasearch on such a function?
Formula for primes - Wikipedia, the free encyclopedia

This is as close as you can get to a true prime number formula.

4. Originally Posted by chiph588@
Formula for primes - Wikipedia, the free encyclopedia

This is as close as you can get to a true prime number formula.
That polynomial inequality in 26 variables is trippy! Thanks for the link.

5. Of much interest is also Riemann's "explicit formula"!


text:
3531

Patch-Tensor Low-n-Rank Reconstruction for Oscillating Steady State fMRI Acceleration
Shouchang Guo1 and Douglas C. Noll2

1Electrical and Computer Engineering, University of Michigan, Ann Arbor, MI, United States, 2Biomedical Engineering, University of Michigan, Ann Arbor, MI, United States

Synopsis

Oscillating steady-state imaging is a new acquisition method for T2*-weighted functional MRI that offers very high SNR, but longer acquisition times. The oscillations are highly reproducible, which make low-rank models suitable. In this work, a sparse sampling scheme combined with a patch-based low-rank tensor reconstruction is introduced to speed the image acquisitions. The low-n-rank algorithm was applied to oscillating steady state data to demonstrate the utility of this approach for functional MRI, demonstrating a 17-fold speed up with error levels less than 3%.

Introduction

The goals of functional MRI (fMRI) acquisition include high spatial and temporal resolution while maintaining a high signal to noise ratio (SNR). Oscillating steady state (OSS) acquisition is a new approach for fMRI acquisition that offers higher SNR but does so at the expense of imaging time. In this work, we propose to reduce imaging time through the use of undersampling in k-space and a novel reconstruction approach based on a well-generalizable patch-tensor low-n-rank model almost fully recovers OSS images from very few k-space samples. Combined with parallel imaging and non-uniform Fourier transform (NUFFT), the model uses a practical spiral random sampling pattern and can achieve as much as a 17-fold acceleration.

Methods

OSS imaging is a fundamentally new fMRI method similar to balanced steady-state free precession in the sense that multiple images are collected with RF cycling, except that it uses quadratic phase increments. Depending on parameters, the resultant signals are T2*-weighted and suitable for fMRI, but oscillate with a periodicity dictated by the phase progression.

There is past work on the use of low-rank (LR) models or LR and sparse (e.g. LR+S) models for fMRI 1. It uses space and time as the two dimension in the LR model. In the current work, there are two time dimensions, the oscillating or fast time dimension, and the time series or slow time dimension, which is a good match for patch-based low-rank tensors. We proposed to process OSS fMRI data as low-n-rank tensors, which imposes low-rank on all the tensor unfoldings 2. Since local information is more likely to be low-rank, the original tensor is partitioned into patch-tensors, which are further reshaped to satisfy the low-n-rank assumption. Using this non-direct low-n-rank structure of the original data greatly improves model adaptivity and potentially benefits random sampling pattern selection.

The convex optimization problem based on patch-tensor low-n-rank is expressed as

$$\text{minimize }\sum_{\mathcal{P^*}} \sum_{i = 1}^{N}\lVert\mathcal{P}(\mathbf{X})_{(i)}\rVert_* + \frac{\lambda}{2}\lVert\mathcal{A}(\mathbf{X})-b\rVert_2^2 ,$$

where $\mathbf{X}\in\mathbb{R}^{I_x\times I_y\times I_t}$ represents the OSS fMRI images to be recovered, $\mathcal{P}(\mathbf{\cdot})$ divides the original tensor into patches and reshapes them to low-n-rank tensors. $\mathcal{P}(\mathbf{X})\in\mathbb{R}^{I_{xy}\times I_{ft} \times I_{st}}$, where $I_{xy}$ is a vectorized spatial dimension, $I_{ft}$ is the oscillating acquisition dimension and equals the number of TR's for the oscillation, $I_{st}$ denotes a temporal block of the functional signal. $\mathcal{P}(\mathbf{X})_{(i)}$ is the mode-$n$ unfolding of $\mathcal{P}(\mathbf{X})$. $\mathcal{A}(\mathbf{\cdot})$ can be composed of coil sensitivities and NUFFT. $b$ contains undersampled k-space measurements. We used two kinds of retrospective sampling patterns. The main pattern is given in Fig. 1 (a). It takes an undersampled variable-density spiral for each temporal frame and rotates with the golden-angle between frames. The other is Poisson-disk sampling without multi-coil to test the model capacity. The patch-tensors are treated as independent modules, and the updating algorithm derived from Alternating Direction Methods of Multipliers (ADMM) 3 is given in Fig. 2.

All the data were collected by the OSS acquisition, the parameters includes TR = 15 ms, $I_{ft} = 10$, FOV = 22 cm, and slice thickness of 4 mm. The human experiments were performed with a finger tapping task repeated 4 cycles, and the activation maps were generated by correlation with the reference waveform.

Results

The model achieved at least 7-fold acceleration with a single-coil acquisition and Poisson disk sampling (Fig. 3). It also helped on sparse noise reduction of the functional time course. Thought the use of multi-coil and the proposed spiral sampling pattern, the original phantom images were recovered with less than 2% error given 5.83% of the k-space samples (Fig. 4). In the case of multi-coil functional human data, the error was less than 3% and the activation map was also recovered (Fig. 5).

Conclusion

A novel fMRI reconstruction model based on patch-tensor low-n-rank is proposed. It uses a spiral random sampling pattern that is easy to implement and can recover OSS images with less than 6% of the original k-space samples. By fully exploring local spatial-temporal relationships as demonstrated, the algorithm shows a strong capacity for data completion. It can be generalized to other image reconstruction problems as long as the non-direct patch-tensor low-n-rank assumption is satisfied, which is easier to satisfy and more flexible than assumptions enforced on the whole dataset.

Acknowledgements

This work was supported by NIH Grant R01EB023618.

References

1. Chiew, M., Graedel, N. N., McNab, J. A., Smith, S. M. and Miller, K. L. (2016), Accelerating functional MRI using fixed-rank approximations and radial-cartesian sampling. Magn. Reson. Med., 76: 1825–1836.

2. T. G. Kolda and B. W. Bader, "Tensor decompositions and applications", SIAM Review, 2009, pp. 455-500.

3. S. Boyd, N. Parikh, E. Chu, et al, “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers,” Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1-122, 2010.

Figures

Figure 1. The model uses very limited k-space samples compared to the fully sampled condition (a) and recovers the oscillating steady-state images (b) by enforcing low-rank on all three unfoldings of the reshaped tensor (c), which has two time dimensions and one spatial dimension. Fig. 1. (a) also shows how the variable-density, undersampled spiral rotates with the golden angle between frames.

Figure 2. The main steps of the algorithm are given. The parameters $k$, $\lambda$, $\beta$ were tuned empirically. $N = 3$ is the number of unfoldings or the dimension of the patch-tensor. The updates treat patch-tensors independently, so the computation can be easily parallelized.

Figure 3. The Poisson disk sampling was performed with a densely sampled core (upper right). The chosen patch-tensor size is 64 x 10 x 66 (space x fast time x slow time). The activation map obtained from the recovered images looks very similar to the original fully sampled result (left column). The time course recovered has a lower spike (green arrow) compared to the fully sampled, which indicates that the patch-tensor low-n-rank model can remove sparse noise without sacrificing accuracy.

Figure 4. The phantom data was acquired with a 32-channel coil and the proposed spiral undersampling. Patch-tensor size 64 x 10 x 40 (space x fast time x slow time) was chosen. The reconstruction result using the proposed algorithm is compared to SENSE reconstruction with a roughness penalty. The model can almost fully recover the original images.

Figure 5. This set of human data was collected with multi-coil and processed with the spiral sampling. Patch-tensor size 16 x 10 x 44 (space x fast time x slow time) was selected. The decreased spatial dimension often leads to better reconstruction performance. The activation maps (lower panel) used a contiguity threshold of 2, and proposed algorithm presents a much better activation map than the SENSE reconstruction.

Proc. Intl. Soc. Mag. Reson. Med. 26 (2018)
3531


text:
# Spectroscopie $\gamma$ des noyaux riches en neutrons autour de N=20

Abstract : There is an island of inversion around $^{32}$Mg (12 protons, 20 neutrons) in contradiction with a shell closure N=20. It means a coexitence of spherical and deformed shapes.

Record views


text:
# How to estimate parameters of a normal distribution?

Suppose one knew that 105 workers were evaluated by their boss. Such evaluation is distributed according to a normal distribution with mean $\mu$ and std. deviation $\sigma$. We also know that 20 workers received score less than 2, 25 were evaluated between 2 and 5, and 60 with evaluations bigger than 5. How can I form reasonable estimates for $\mu$ and $\sigma$?

-

You know two proportions, i.e. two probabilities. So you know two areas under the normal curve for $N(\mu,\sigma)$.
There is a correspondence between $x$-values on the curve for $N(\mu,\sigma)$ and $z$-values on the curve for the standardized $N(0,1)$, for the same areas under the curves.


text:
# Tag Info

6

As the magnet approaches the solenoid, a current is induced. The current generates a magnetic field. The field repels the magnet, slowing it's approach. The amplitude of the oscillations diminish. If there was no resistance, this would work in reverse as the magnet receded from the solenoid. The magnetic field would accelerate the magnet. The magnet would ...

1

This should go on forever, and current should keep appearing across the load resistance. This is a contradiction. Since there is current through (not across) the load resistance, there is work being done on the load: $p = i^2R$. Let's be clear on this: the coil-load system does no work on the pendulum, the pendulum does work on the coil-load ...

1

The force on the pendulum only applies when the pendulum is in the vicinity of the coil. At that moment the harmonic motion of the pendulum is distorted. It 's amplitude is lessened and with it the upward motion. So the kinetic energy of the pendulum is converted into gravitational energy and electric energy. But the gravitational energy is less than without ...

1

The short answer is that there is a induced force on the magnet. This induced force will make the pendulum loose energy in the same proportions as there is electrical energy being generated. A good experiment to show this effect is by having a small bar magnet and a copper pipe Or solenoid. When you let a small bar magnet drop from a certain height it will ...

1

Finally the bottom line of question is, can we experimentally prove that energy, total energy is actually conserved ? (a Yes answer requires a detailed experiment with complete conservation and no loopholes) Elementary particle physicists have been doing this for more than sixty years. Conservation of energy is one of the main constraints that built ...

1

As of last week, scientists have created a thermoelectric material that increases its efficiency to 15-20%. This is still not good enough to heat or cool your house, but it gives me hope that someday in the future, we have materials so good and cheap that we can build our houses and cars with it. So we may not be able to use the heat inside the house to cool ...

Only top voted, non community-wiki answers of a minimum length are eligible